malachite_base/num/arithmetic/
log_base.rs

1// Copyright © 2026 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        p = p.checked_mul(base)?;
53    }
54    if p == x {
55        Some(result)
56    } else {
57        None
58    }
59}}
60
61fn floor_log_base<T: PrimitiveUnsigned>(x: T, base: T) -> u64 {
62    if let Some(log_base) = base.checked_log_base_2() {
63        x.floor_log_base_power_of_2(log_base)
64    } else {
65        floor_log_base_naive(x, base)
66    }
67}
68
69fn ceiling_log_base<T: PrimitiveUnsigned>(x: T, base: T) -> u64 {
70    if let Some(log_base) = base.checked_log_base_2() {
71        x.ceiling_log_base_power_of_2(log_base)
72    } else {
73        ceiling_log_base_naive(x, base)
74    }
75}
76
77fn checked_log_base<T: PrimitiveUnsigned>(x: T, base: T) -> Option<u64> {
78    if let Some(log_base) = base.checked_log_base_2() {
79        x.checked_log_base_power_of_2(log_base)
80    } else {
81        checked_log_base_naive(x, base)
82    }
83}
84
85macro_rules! impl_log_base_unsigned {
86    ($t:ident) => {
87        impl FloorLogBase for $t {
88            type Output = u64;
89
90            /// Returns the floor of the base-$b$ logarithm of a positive integer.
91            ///
92            /// $f(x, b) = \lfloor\log_b x\rfloor$.
93            ///
94            /// # Worst-case complexity
95            /// $T(n) = O(n)$
96            ///
97            /// $M(n) = O(1)$
98            ///
99            /// where $T$ is time, $M$ is additional memory, and $n$ is `self.significant_bits() /
100            /// base.significant_bits()`.
101            ///
102            /// # Panics
103            /// Panics if `self` is 0 or `base` is less than 2.
104            ///
105            /// # Examples
106            /// See [here](super::log_base#floor_log_base).
107            #[inline]
108            fn floor_log_base(self, base: $t) -> u64 {
109                // TODO use ilog once stabilized
110                floor_log_base(self, base)
111            }
112        }
113
114        impl CeilingLogBase for $t {
115            type Output = u64;
116
117            /// Returns the ceiling of the base-$b$ logarithm of a positive integer.
118            ///
119            /// $f(x, b) = \lceil\log_b x\rceil$.
120            ///
121            /// # Worst-case complexity
122            /// $T(n) = O(n)$
123            ///
124            /// $M(n) = O(1)$
125            ///
126            /// where $T$ is time, $M$ is additional memory, and $n$ is `self.significant_bits() /
127            /// base.significant_bits()`.
128            ///
129            /// # Panics
130            /// Panics if `self` is 0 or `base` is less than 2.
131            ///
132            /// # Examples
133            /// See [here](super::log_base#ceiling_log_base).
134            #[inline]
135            fn ceiling_log_base(self, base: $t) -> u64 {
136                ceiling_log_base(self, base)
137            }
138        }
139
140        impl CheckedLogBase for $t {
141            type Output = u64;
142
143            /// Returns the base-$b$ logarithm of a positive integer. If the integer is not a power
144            /// of $b$, `None` is returned.
145            ///
146            /// $$
147            /// f(x, b) = \\begin{cases}
148            ///     \operatorname{Some}(\log_b x) & \text{if} \\quad \log_b x \in \Z, \\\\
149            ///     \operatorname{None} & \textrm{otherwise}.
150            /// \\end{cases}
151            /// $$
152            ///
153            /// # Worst-case complexity
154            /// $T(n) = O(n)$
155            ///
156            /// $M(n) = O(1)$
157            ///
158            /// where $T$ is time, $M$ is additional memory, and $n$ is `self.significant_bits() /
159            /// base.significant_bits()`.
160            ///
161            /// # Panics
162            /// Panics if `self` is 0 or `base` is less than 2.
163            ///
164            /// # Examples
165            /// See [here](super::log_base#checked_log_base).
166            #[inline]
167            fn checked_log_base(self, base: $t) -> Option<u64> {
168                checked_log_base(self, base)
169            }
170        }
171    };
172}
173apply_to_unsigneds!(impl_log_base_unsigned);
malachite_base/num/arithmetic/log_base.rs

malachite_base/num/arithmetic/
log_base.rs
