ruint/
log.rs

Help
1#![cfg(feature = "std")]
2
3use crate::Uint;
4
5impl<const BITS: usize, const LIMBS: usize> Uint<BITS, LIMBS> {
6    /// Returns the logarithm of the number, rounded down.
7    ///
8    /// Returns None if the base is less than two, or this number is zero.
9    #[inline]
10    #[must_use]
11    pub fn checked_log(self, base: Self) -> Option<usize> {
12        if base < Self::from(2) || self.is_zero() {
13            return None;
14        }
15        Some(self.log(base))
16    }
17
18    /// Returns the base 10 logarithm of the number, rounded down.
19    ///
20    /// Returns None if the number is zero.
21    #[inline]
22    #[must_use]
23    pub fn checked_log10(self) -> Option<usize> {
24        self.checked_log(Self::from(10))
25    }
26
27    /// Returns the base 2 logarithm of the number, rounded down.
28    ///
29    /// This is equivalent to the index of the highest set bit.
30    ///
31    /// Returns None if the number is zero.
32    #[inline]
33    #[must_use]
34    pub fn checked_log2(self) -> Option<usize> {
35        self.checked_log(Self::from(2))
36    }
37
38    /// Returns the logarithm of the number, rounded down.
39    ///
40    /// # Panics
41    ///
42    /// Panics if the `base` is less than 2 or if the number is zero.
43    #[inline]
44    #[must_use]
45    pub fn log(self, base: Self) -> usize {
46        assert!(self != Self::ZERO);
47        assert!(base >= Self::from(2));
48        if base == Self::from(2) {
49            return self.bit_len() - 1;
50        }
51        if self < base {
52            return 0;
53        }
54
55        // Find approximate result
56        #[allow(clippy::cast_precision_loss)] // Casting base to `f64` is fine.
57        let result = self.approx_log2() / base.approx_log2();
58        // We handled edge cases above, so the result should be normal and fit `Self`.
59        assert!(result.is_normal());
60        let mut result = result.try_into().unwrap();
61
62        // Adjust result to get the exact value. At most one of these should happen, but
63        // we loop regardless.
64        loop {
65            if let Some(value) = base.checked_pow(result) {
66                if value > self {
67                    assert!(result != Self::ZERO);
68                    result -= Self::from(1);
69                    continue;
70                }
71            } else {
72                // Overflow, so definitely larger than `value`
73                result -= Self::from(1);
74            }
75            break;
76        }
77        while let Some(trial) = result.checked_add(Self::from(1)) {
78            if let Some(value) = base.checked_pow(trial) {
79                if value <= self {
80                    result = trial;
81                    continue;
82                }
83            }
84            break;
85        }
86
87        // Should always be possible.
88        result.to()
89    }
90
91    /// Returns the base 10 logarithm of the number, rounded down.
92    ///
93    /// # Panics
94    ///
95    /// Panics if the `base` if the number is zero.
96    #[inline]
97    #[must_use]
98    pub fn log10(self) -> usize {
99        self.log(Self::from(10))
100    }
101
102    /// Returns the base 2 logarithm of the number, rounded down.
103    ///
104    /// # Panics
105    ///
106    /// Panics if the `base` if the number is zero.
107    #[inline]
108    #[must_use]
109    pub fn log2(self) -> usize {
110        self.log(Self::from(2))
111    }
112
113    /// Double precision logarithm.
114    #[inline]
115    #[must_use]
116    pub fn approx_log(self, base: f64) -> f64 {
117        self.approx_log2() / base.log2()
118    }
119
120    /// Double precision binary logarithm.
121    ///
122    /// # Examples
123    ///
124    /// ```
125    /// # use ruint::{Uint, uint, aliases::*};
126    /// # uint!{
127    /// assert_eq!(0_U64.approx_log2(), f64::NEG_INFINITY);
128    /// assert_eq!(1_U64.approx_log2(), 0.0);
129    /// assert_eq!(2_U64.approx_log2(), 1.0);
130    /// assert_eq!(U64::MAX.approx_log2(), 64.0);
131    /// # }
132    /// ```
133    #[inline]
134    #[must_use]
135    #[allow(clippy::cast_precision_loss)]
136    pub fn approx_log2(self) -> f64 {
137        // The naive solution would be `f64::from(self).log2()`, but
138        // `f64::from(self)` quickly overflows (`f64::MAX` is 2^1024).
139        // So instead we first approximate as `bits * 2^exp` and then
140        // compute using`log2(bits * 2^exp) = log2(bits) + exp`
141        let (bits, exp) = self.most_significant_bits();
142        // Convert to floats
143        let bits = bits as f64;
144        let exp = exp as f64;
145        bits.log2() + exp
146    }
147
148    /// Double precision decimal logarithm.
149    #[inline]
150    #[must_use]
151    pub fn approx_log10(self) -> f64 {
152        self.approx_log2() / core::f64::consts::LOG2_10
153    }
154}
155
156#[cfg(test)]
157mod tests {
158    use super::*;
159    use crate::{aliases::U128, const_for, nlimbs};
160    use proptest::{prop_assume, proptest};
161
162    #[test]
163    fn test_checked_log2() {
164        assert_eq!(U128::from(0).checked_log2(), None);
165        assert_eq!(U128::from(1).checked_log2(), Some(0));
166        assert_eq!(U128::from(2).checked_log2(), Some(1));
167        assert_eq!(U128::from(3).checked_log2(), Some(1));
168        assert_eq!(U128::from(127).checked_log2(), Some(6));
169        assert_eq!(U128::from(128).checked_log2(), Some(7));
170    }
171
172    #[test]
173    fn test_approx_log2_pow2() {
174        const_for!(BITS in SIZES {
175            const LIMBS: usize = nlimbs(BITS);
176            type U = Uint<BITS, LIMBS>;
177            proptest!(|(value: U)| {
178                let log = value.approx_log2();
179                let pow = U::approx_pow2(log).unwrap();
180                let error = value.abs_diff(pow);
181                let correct_bits = value.bit_len() - error.bit_len();
182                // The maximum precision we could expect here is 53 bits.
183                // OPT: Find out exactly where the precision is lost and what
184                // the bounds are.
185                assert!(correct_bits == value.bit_len() || correct_bits >= 42);
186            });
187        });
188    }
189
190    #[test]
191    fn test_pow_log() {
192        const_for!(BITS in NON_ZERO if (BITS >= 64) {
193            const LIMBS: usize = nlimbs(BITS);
194            type U = Uint<BITS, LIMBS>;
195            proptest!(|(b in 2_u64..100, e in 0..BITS)| {
196                if let Some(value) = U::from(b).checked_pow(U::from(e)) {
197                    assert!(value > U::ZERO);
198                    assert_eq!(value.log(U::from(b)), e);
199                    // assert_eq!(value.log(b + U::from(1)), e as u64);
200                }
201            });
202        });
203    }
204
205    #[test]
206    fn test_log_pow() {
207        const_for!(BITS in NON_ZERO if (BITS >= 64) {
208            const LIMBS: usize = nlimbs(BITS);
209            type U = Uint<BITS, LIMBS>;
210            proptest!(|(b in 2_u64..100, n: U)| {
211                prop_assume!(n > U::ZERO);
212                let e = n.log(U::from(b));
213                assert!(U::from(b).pow(U::from(e)) <= n);
214                if let Some(value) = U::from(b).checked_pow(U::from(e + 1)) {
215                    assert!(value > n);
216                }
217            });
218        });
219    }
220}
ruint/log.rs

ruint/
log.rs
