ruint/
special.rs

Help
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 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 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 fn checked_next_power_of_two(self) -> Option<Self> {
57        if self.is_power_of_two() {
58            return Some(self);
59        }
60        let exp = self.bit_len();
61        if exp >= BITS {
62            return None;
63        }
64        Some(Self::from(1) << exp)
65    }
66}
67
68impl<const BITS: usize, const LIMBS: usize> Uint<BITS, LIMBS> {
69    /// Calculates the smallest value greater than or equal to self that is a
70    /// multiple of rhs.
71    ///
72    /// # Panics
73    ///
74    /// This function will panic if `rhs` is 0 or the operation results in
75    /// overflow.
76    #[inline]
77    #[must_use]
78    pub fn next_multiple_of(self, rhs: Self) -> Self {
79        self.checked_next_multiple_of(rhs).unwrap();
80        todo!()
81    }
82
83    /// Calculates the smallest value greater than or equal to `self` that is a
84    /// multiple of `rhs`. Returns [`None`] is `rhs` is zero or the
85    /// operation would result in overflow.
86    ///
87    /// # Examples
88    ///
89    /// ```
90    /// # use ruint::{Uint, uint, aliases::U64};
91    /// # uint!{
92    /// assert_eq!(16_U64.checked_next_multiple_of(8_U64), Some(16_U64));
93    /// assert_eq!(23_U64.checked_next_multiple_of(8_U64), Some(24_U64));
94    /// assert_eq!(1_U64.checked_next_multiple_of(0_U64), None);
95    /// assert_eq!(U64::MAX.checked_next_multiple_of(2_U64), None);
96    /// }
97    /// ```
98    ///
99    /// ```
100    /// # use ruint::{Uint, uint};
101    /// # uint!{
102    /// assert_eq!(0_U0.checked_next_multiple_of(0_U0), None);
103    /// assert_eq!(0_U1.checked_next_multiple_of(0_U1), None);
104    /// assert_eq!(0_U1.checked_next_multiple_of(1_U1), Some(0_U1));
105    /// assert_eq!(1_U1.checked_next_multiple_of(0_U1), None);
106    /// assert_eq!(1_U1.checked_next_multiple_of(1_U1), Some(1_U1));
107    /// }
108    /// ```
109    #[inline]
110    #[must_use]
111    pub fn checked_next_multiple_of(self, rhs: Self) -> Option<Self> {
112        if rhs.is_zero() {
113            return None;
114        }
115        let (q, r) = self.div_rem(rhs);
116        if r.is_zero() {
117            return Some(self);
118        }
119        let q = q.checked_add(Self::from(1))?;
120        q.checked_mul(rhs)
121    }
122}
ruint/special.rs

ruint/
special.rs
