ruint/
gcd.rs

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 core::cmp::min;
57    use proptest::{proptest, test_runner::Config};
58
59    #[test]
60    #[allow(clippy::absurd_extreme_comparisons)] // Generated code
61    fn test_gcd_identities() {
62        const_for!(BITS in SIZES {
63            const LIMBS: usize = nlimbs(BITS);
64            type U = Uint<BITS, LIMBS>;
65            // TODO: Increase cases when perf is better.
66            let mut config = Config::default();
67            config.cases = min(config.cases, if BITS > 500 { 3 } else { 10 });
68            proptest!(config, |(a: U, b: U)| {
69                let g = a.gcd(b);
70                assert_eq!(b.gcd(a), g);
71                if a == U::ZERO && b == U::ZERO {
72                    assert_eq!(g, U::ZERO);
73                } else {
74                    assert_eq!(a % g, U::ZERO);
75                    assert_eq!(b % g, U::ZERO);
76                }
77
78                let l = a.lcm(b);
79                assert_eq!(b.lcm(a), l);
80                if let Some(l) = l {
81                    if a == U::ZERO || b == U::ZERO {
82                        assert_eq!(l, U::ZERO);
83                    } else {
84                        assert_eq!(l % a, U::ZERO);
85                        assert_eq!(l % b, U::ZERO);
86                    }
87                }
88
89                let (ge, x, y, sign) = a.gcd_extended(b);
90                assert_eq!(ge, g);
91                if sign {
92                    assert_eq!(a * x - b * y, g);
93                } else {
94                    assert_eq!(b * y - a * x, g);
95                }
96            });
97        });
98    }
99}
ruint/gcd.rs

ruint/
gcd.rs
