malachite_base/num/arithmetic/
log_base.rs

1// Copyright © 2025 Mikhail Hogrefe
2//
3// This file is part of Malachite.
4//
5// Malachite is free software: you can redistribute it and/or modify it under the terms of the GNU
6// Lesser General Public License (LGPL) as published by the Free Software Foundation; either version
7// 3 of the License, or (at your option) any later version. See <https://www.gnu.org/licenses/>.
8
9use crate::num::arithmetic::traits::{CeilingLogBase, CheckedLogBase, FloorLogBase};
10use crate::num::basic::unsigneds::PrimitiveUnsigned;
11
12fn floor_log_base_naive<T: PrimitiveUnsigned>(x: T, base: T) -> u64 {
13    assert_ne!(x, T::ZERO);
14    assert!(base > T::ONE);
15    let mut result = 0;
16    let mut p = T::ONE;
17    // loop always executes at least once
18    while p <= x {
19        result += 1;
20        if let Some(next_p) = p.checked_mul(base) {
21            p = next_p;
22        } else {
23            break;
24        }
25    }
26    result - 1
27}
28
29pub_test! {ceiling_log_base_naive<T: PrimitiveUnsigned>(x: T, base: T) -> u64 {
30    assert_ne!(x, T::ZERO);
31    assert!(base > T::ONE);
32    let mut result = 0;
33    let mut p = T::ONE;
34    while p < x {
35        result += 1;
36        if let Some(next_p) = p.checked_mul(base) {
37            p = next_p;
38        } else {
39            break;
40        }
41    }
42    result
43}}
44
45pub_test! {checked_log_base_naive<T: PrimitiveUnsigned>(x: T, base: T) -> Option<u64> {
46    assert_ne!(x, T::ZERO);
47    assert!(base > T::ONE);
48    let mut result = 0;
49    let mut p = T::ONE;
50    while p < x {
51        result += 1;
52        if let Some(next_p) = p.checked_mul(base) {
53            p = next_p;
54        } else {
55            return None;
56        }
57    }
58    if p == x {
59        Some(result)
60    } else {
61        None
62    }
63}}
64
65fn floor_log_base<T: PrimitiveUnsigned>(x: T, base: T) -> u64 {
66    if let Some(log_base) = base.checked_log_base_2() {
67        x.floor_log_base_power_of_2(log_base)
68    } else {
69        floor_log_base_naive(x, base)
70    }
71}
72
73fn ceiling_log_base<T: PrimitiveUnsigned>(x: T, base: T) -> u64 {
74    if let Some(log_base) = base.checked_log_base_2() {
75        x.ceiling_log_base_power_of_2(log_base)
76    } else {
77        ceiling_log_base_naive(x, base)
78    }
79}
80
81fn checked_log_base<T: PrimitiveUnsigned>(x: T, base: T) -> Option<u64> {
82    if let Some(log_base) = base.checked_log_base_2() {
83        x.checked_log_base_power_of_2(log_base)
84    } else {
85        checked_log_base_naive(x, base)
86    }
87}
88
89macro_rules! impl_log_base_unsigned {
90    ($t:ident) => {
91        impl FloorLogBase for $t {
92            type Output = u64;
93
94            /// Returns the floor of the base-$b$ logarithm of a positive integer.
95            ///
96            /// $f(x, b) = \lfloor\log_b x\rfloor$.
97            ///
98            /// # Worst-case complexity
99            /// $T(n) = O(n)$
100            ///
101            /// $M(n) = O(1)$
102            ///
103            /// where $T$ is time, $M$ is additional memory, and $n$ is `self.significant_bits() /
104            /// base.significant_bits()`.
105            ///
106            /// # Panics
107            /// Panics if `self` is 0 or `base` is less than 2.
108            ///
109            /// # Examples
110            /// See [here](super::log_base#floor_log_base).
111            #[inline]
112            fn floor_log_base(self, base: $t) -> u64 {
113                // TODO use ilog once stabilized
114                floor_log_base(self, base)
115            }
116        }
117
118        impl CeilingLogBase for $t {
119            type Output = u64;
120
121            /// Returns the ceiling of the base-$b$ logarithm of a positive integer.
122            ///
123            /// $f(x, b) = \lceil\log_b x\rceil$.
124            ///
125            /// # Worst-case complexity
126            /// $T(n) = O(n)$
127            ///
128            /// $M(n) = O(1)$
129            ///
130            /// where $T$ is time, $M$ is additional memory, and $n$ is `self.significant_bits() /
131            /// base.significant_bits()`.
132            ///
133            /// # Panics
134            /// Panics if `self` is 0 or `base` is less than 2.
135            ///
136            /// # Examples
137            /// See [here](super::log_base#ceiling_log_base).
138            #[inline]
139            fn ceiling_log_base(self, base: $t) -> u64 {
140                ceiling_log_base(self, base)
141            }
142        }
143
144        impl CheckedLogBase for $t {
145            type Output = u64;
146
147            /// Returns the base-$b$ logarithm of a positive integer. If the integer is not a power
148            /// of $b$, `None` is returned.
149            ///
150            /// $$
151            /// f(x, b) = \\begin{cases}
152            ///     \operatorname{Some}(\log_b x) & \text{if} \\quad \log_b x \in \Z, \\\\
153            ///     \operatorname{None} & \textrm{otherwise}.
154            /// \\end{cases}
155            /// $$
156            ///
157            /// # Worst-case complexity
158            /// $T(n) = O(n)$
159            ///
160            /// $M(n) = O(1)$
161            ///
162            /// where $T$ is time, $M$ is additional memory, and $n$ is `self.significant_bits() /
163            /// base.significant_bits()`.
164            ///
165            /// # Panics
166            /// Panics if `self` is 0 or `base` is less than 2.
167            ///
168            /// # Examples
169            /// See [here](super::log_base#checked_log_base).
170            #[inline]
171            fn checked_log_base(self, base: $t) -> Option<u64> {
172                checked_log_base(self, base)
173            }
174        }
175    };
176}
177apply_to_unsigneds!(impl_log_base_unsigned);
malachite_base/num/arithmetic/log_base.rs

malachite_base/num/arithmetic/
log_base.rs
