ruint/
special.rs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
use crate::Uint;

// FEATURE: Special functions
// * Factorial
// * Extended GCD and LCM
// * https://en.wikipedia.org/wiki/Euler%27s_totient_function
// * https://en.wikipedia.org/wiki/Carmichael_function
// * https://en.wikipedia.org/wiki/Jordan%27s_totient_function
// * Feature parity with GMP:
//   * https://gmplib.org/manual/Integer-Functions.html#Integer-Functions

// https://en.wikipedia.org/wiki/Kronecker_symbol
// Subsumes Jacobi and Legendre symbols.

// Primality testing
// https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test#Testing_against_small_sets_of_bases

impl<const BITS: usize, const LIMBS: usize> Uint<BITS, LIMBS> {
    /// Returns `true` if and only if `self == 2^k` for some `k`.
    #[inline]
    #[must_use]
    pub fn is_power_of_two(self) -> bool {
        self.count_ones() == 1
    }

    /// Returns the smallest power of two greater than or equal to self.
    ///
    /// # Panics
    ///
    /// Panics if the value overlfows.
    #[inline]
    #[must_use]
    pub fn next_power_of_two(self) -> Self {
        self.checked_next_power_of_two().unwrap()
    }

    /// Returns the smallest power of two greater than or equal to `self`. If
    /// the next power of two is greater than the type’s maximum value,
    /// [`None`] is returned, otherwise the power of two is wrapped in
    /// [`Some`].
    ///
    /// # Examples
    ///
    /// ```
    /// # use ruint::{Uint, uint, aliases::U64};
    /// # uint!{
    /// assert_eq!(0_U64.checked_next_power_of_two(), Some(1_U64));
    /// assert_eq!(1_U64.checked_next_power_of_two(), Some(1_U64));
    /// assert_eq!(2_U64.checked_next_power_of_two(), Some(2_U64));
    /// assert_eq!(3_U64.checked_next_power_of_two(), Some(4_U64));
    /// assert_eq!(U64::MAX.checked_next_power_of_two(), None);
    /// # }
    /// ```
    #[inline]
    #[must_use]
    pub fn checked_next_power_of_two(self) -> Option<Self> {
        if self.is_power_of_two() {
            return Some(self);
        }
        let exp = self.bit_len();
        if exp >= BITS {
            return None;
        }
        Some(Self::from(1) << exp)
    }
}

impl<const BITS: usize, const LIMBS: usize> Uint<BITS, LIMBS> {
    /// Calculates the smallest value greater than or equal to self that is a
    /// multiple of rhs.
    ///
    /// # Panics
    ///
    /// This function will panic if `rhs` is 0 or the operation results in
    /// overflow.
    #[inline]
    #[must_use]
    pub fn next_multiple_of(self, rhs: Self) -> Self {
        self.checked_next_multiple_of(rhs).unwrap();
        todo!()
    }

    /// Calculates the smallest value greater than or equal to `self` that is a
    /// multiple of `rhs`. Returns [`None`] is `rhs` is zero or the
    /// operation would result in overflow.
    ///
    /// # Examples
    ///
    /// ```
    /// # use ruint::{Uint, uint, aliases::U64};
    /// # uint!{
    /// assert_eq!(16_U64.checked_next_multiple_of(8_U64), Some(16_U64));
    /// assert_eq!(23_U64.checked_next_multiple_of(8_U64), Some(24_U64));
    /// assert_eq!(1_U64.checked_next_multiple_of(0_U64), None);
    /// assert_eq!(U64::MAX.checked_next_multiple_of(2_U64), None);
    /// }
    /// ```
    ///
    /// ```
    /// # use ruint::{Uint, uint};
    /// # uint!{
    /// assert_eq!(0_U0.checked_next_multiple_of(0_U0), None);
    /// assert_eq!(0_U1.checked_next_multiple_of(0_U1), None);
    /// assert_eq!(0_U1.checked_next_multiple_of(1_U1), Some(0_U1));
    /// assert_eq!(1_U1.checked_next_multiple_of(0_U1), None);
    /// assert_eq!(1_U1.checked_next_multiple_of(1_U1), Some(1_U1));
    /// }
    /// ```
    #[inline]
    #[must_use]
    pub fn checked_next_multiple_of(self, rhs: Self) -> Option<Self> {
        if rhs == Self::ZERO {
            return None;
        }
        let (q, r) = self.div_rem(rhs);
        if r == Self::ZERO {
            return Some(self);
        }
        let q = q.checked_add(Self::from(1))?;
        q.checked_mul(rhs)
    }
}