ruint/
special.rs

1use crate::Uint;
2
3// FEATURE: Special functions
4// * Factorial
5// * Extended GCD and LCM
6// * https://en.wikipedia.org/wiki/Euler%27s_totient_function
7// * https://en.wikipedia.org/wiki/Carmichael_function
8// * https://en.wikipedia.org/wiki/Jordan%27s_totient_function
9// * Feature parity with GMP:
10//   * https://gmplib.org/manual/Integer-Functions.html#Integer-Functions
11
12// https://en.wikipedia.org/wiki/Kronecker_symbol
13// Subsumes Jacobi and Legendre symbols.
14
15// Primality testing
16// https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test#Testing_against_small_sets_of_bases
17
18impl<const BITS: usize, const LIMBS: usize> Uint<BITS, LIMBS> {
19    /// Returns `true` if and only if `self == 2^k` for some `k`.
20    #[inline]
21    #[must_use]
22    pub const fn is_power_of_two(self) -> bool {
23        self.count_ones() == 1
24    }
25
26    /// Returns the smallest power of two greater than or equal to self.
27    ///
28    /// # Panics
29    ///
30    /// Panics if the value overlfows.
31    #[inline]
32    #[must_use]
33    pub const fn next_power_of_two(self) -> Self {
34        self.checked_next_power_of_two().unwrap()
35    }
36
37    /// Returns the smallest power of two greater than or equal to `self`. If
38    /// the next power of two is greater than the type’s maximum value,
39    /// [`None`] is returned, otherwise the power of two is wrapped in
40    /// [`Some`].
41    ///
42    /// # Examples
43    ///
44    /// ```
45    /// # use ruint::{Uint, uint, aliases::U64};
46    /// # uint!{
47    /// assert_eq!(0_U64.checked_next_power_of_two(), Some(1_U64));
48    /// assert_eq!(1_U64.checked_next_power_of_two(), Some(1_U64));
49    /// assert_eq!(2_U64.checked_next_power_of_two(), Some(2_U64));
50    /// assert_eq!(3_U64.checked_next_power_of_two(), Some(4_U64));
51    /// assert_eq!(U64::MAX.checked_next_power_of_two(), None);
52    /// # }
53    /// ```
54    #[inline]
55    #[must_use]
56    pub const fn checked_next_power_of_two(self) -> Option<Self> {
57        self.one_less_than_next_power_of_two()
58            .checked_add(Self::ONE)
59    }
60
61    const fn one_less_than_next_power_of_two(self) -> Self {
62        if self.const_is_zero() || self.const_eq(&Self::ONE) {
63            return Self::ZERO;
64        }
65
66        let p = self.wrapping_sub(Self::ONE);
67        let z = p.leading_zeros();
68        Self::MAX.wrapping_shr(z)
69    }
70
71    /// Calculates the smallest value greater than or equal to self that is a
72    /// multiple of rhs.
73    ///
74    /// # Panics
75    ///
76    /// This function will panic if `rhs` is 0 or the operation results in
77    /// overflow.
78    #[inline]
79    #[must_use]
80    #[track_caller]
81    pub fn next_multiple_of(self, rhs: Self) -> Self {
82        let r = self % rhs;
83        if r.is_zero() {
84            self
85        } else {
86            // rhs - r cannot overflow because r is smaller than rhs
87            self.checked_add(rhs - r).unwrap()
88        }
89    }
90
91    /// Calculates the smallest value greater than or equal to `self` that is a
92    /// multiple of `rhs`. Returns [`None`] is `rhs` is zero or the
93    /// operation would result in overflow.
94    ///
95    /// # Examples
96    ///
97    /// ```
98    /// # use ruint::{Uint, uint, aliases::U64};
99    /// # uint!{
100    /// assert_eq!(16_U64.checked_next_multiple_of(8_U64), Some(16_U64));
101    /// assert_eq!(23_U64.checked_next_multiple_of(8_U64), Some(24_U64));
102    /// assert_eq!(1_U64.checked_next_multiple_of(0_U64), None);
103    /// assert_eq!(U64::MAX.checked_next_multiple_of(2_U64), None);
104    /// # }
105    /// ```
106    ///
107    /// ```
108    /// # use ruint::{Uint, uint};
109    /// # uint!{
110    /// assert_eq!(0_U0.checked_next_multiple_of(0_U0), None);
111    /// assert_eq!(0_U1.checked_next_multiple_of(0_U1), None);
112    /// assert_eq!(0_U1.checked_next_multiple_of(1_U1), Some(0_U1));
113    /// assert_eq!(1_U1.checked_next_multiple_of(0_U1), None);
114    /// assert_eq!(1_U1.checked_next_multiple_of(1_U1), Some(1_U1));
115    /// # }
116    /// ```
117    #[inline]
118    #[must_use]
119    pub fn checked_next_multiple_of(self, rhs: Self) -> Option<Self> {
120        let r = self.checked_rem(rhs)?;
121        if r.is_zero() {
122            Some(self)
123        } else {
124            // rhs - r cannot overflow because r is smaller than rhs
125            self.checked_add(rhs - r)
126        }
127    }
128}
ruint/special.rs

ruint/
special.rs
