ruint/
gcd.rs

Help
1use crate::{algorithms, Uint};
2
3impl<const BITS: usize, const LIMBS: usize> Uint<BITS, LIMBS> {
4    /// Compute the greatest common divisor of two [`Uint`]s.
5    ///
6    /// # Examples
7    ///
8    /// ```
9    /// # use ruint::{Uint, uint, aliases::*};
10    /// # uint! {
11    /// assert_eq!(0_U128.gcd(0_U128), 0_U128);
12    /// # }
13    /// ```
14    #[inline]
15    #[must_use]
16    pub fn gcd(self, other: Self) -> Self {
17        algorithms::gcd(self, other)
18    }
19
20    /// Compute the least common multiple of two [`Uint`]s or [`None`] if the
21    /// result would be too large.
22    #[inline]
23    #[must_use]
24    pub fn lcm(self, other: Self) -> Option<Self> {
25        let other = other.checked_div(self.gcd(other)).unwrap_or_default();
26        self.checked_mul(other)
27    }
28
29    /// ⚠️ Compute the greatest common divisor and the Bézout coefficients.
30    ///
31    /// **Warning.** This is API is unstable and may change in a minor release.
32    ///
33    /// Returns $(\mathtt{gcd}, \mathtt{x}, \mathtt{y}, \mathtt{sign})$ such
34    /// that
35    ///
36    /// $$
37    /// \gcd(\mathtt{self}, \mathtt{other}) = \mathtt{gcd} = \begin{cases}
38    ///     \mathtt{self} · \mathtt{x} - \mathtt{other} . \mathtt{y} &
39    /// \mathtt{sign} \\\\     \mathtt{other} · \mathtt{y} - \mathtt{self} ·
40    /// \mathtt{x} & ¬\mathtt{sign} \end{cases}
41    /// $$
42    ///
43    /// Note that the intermediate products may overflow, even though the result
44    /// after subtraction will fit in the bit size of the [`Uint`].
45    #[inline]
46    #[must_use]
47    pub fn gcd_extended(self, other: Self) -> (Self, Self, Self, bool) {
48        algorithms::gcd_extended(self, other)
49    }
50}
51
52#[cfg(test)]
53mod tests {
54    use super::*;
55    use crate::{const_for, nlimbs};
56    use proptest::{proptest, test_runner::Config};
57
58    #[test]
59    #[allow(clippy::absurd_extreme_comparisons)] // Generated code
60    fn test_gcd_identities() {
61        const_for!(BITS in SIZES {
62            const LIMBS: usize = nlimbs(BITS);
63            type U = Uint<BITS, LIMBS>;
64            let config = Config { cases: 5, ..Default::default() };
65            proptest!(config, |(a: U, b: U)| {
66                let g = a.gcd(b);
67                assert_eq!(b.gcd(a), g);
68                if a == U::ZERO && b == U::ZERO {
69                    assert_eq!(g, U::ZERO);
70                } else {
71                    assert_eq!(a % g, U::ZERO);
72                    assert_eq!(b % g, U::ZERO);
73                }
74
75                let l = a.lcm(b);
76                assert_eq!(b.lcm(a), l);
77                if let Some(l) = l {
78                    if a == U::ZERO || b == U::ZERO {
79                        assert_eq!(l, U::ZERO);
80                    } else {
81                        assert_eq!(l % a, U::ZERO);
82                        assert_eq!(l % b, U::ZERO);
83                    }
84                }
85
86                let (ge, x, y, sign) = a.gcd_extended(b);
87                assert_eq!(ge, g);
88                if sign {
89                    assert_eq!(a * x - b * y, g);
90                } else {
91                    assert_eq!(b * y - a * x, g);
92                }
93            });
94        });
95    }
96}
ruint/gcd.rs

ruint/
gcd.rs
