large_primes/operations/
gcd.rs

1use num_bigint::BigUint;
2use num_traits::Zero;
3
4/// Computes the greatest common divisor (GCD) of two `BigUint` numbers using the Euclidean algorithm.
5///
6/// The function applies the Euclidean algorithm to find the largest number that divides both `a` and `b`
7/// without leaving a remainder. This algorithm involves a series of division steps until the remainder is zero.
8///
9/// # Arguments
10///
11/// * `a` - A reference to a `BigUint` representing the first number.
12/// * `b` - A reference to a `BigUint` representing the second number.
13///
14/// # Returns
15///
16/// The greatest common divisor of `a` and `b`.
17///
18/// # Examples
19///
20/// ```
21/// use num_bigint::BigUint;
22/// use large_primes::gcd;
23/// 
24/// let a = BigUint::from(60u32);
25/// let b = BigUint::from(48u32);
26/// let gcd_value = gcd(&a, &b);
27/// assert_eq!(gcd_value, BigUint::from(12u32));
28/// ```
29pub fn gcd(a: &BigUint, b: &BigUint) -> BigUint {
30    // Euclidean algorithm
31    let mut a = a.clone();
32    let mut b = b.clone();
33
34    let zero = BigUint::zero();
35
36    while b > zero {
37        let temp = b.clone();
38        b = a % b;
39        a = temp;
40    }
41
42    return a;
43}
44
45#[cfg(test)]
46mod tests {
47    use num_bigint::BigUint;
48    use num_traits::{ One, Zero };
49
50    use super::*;
51
52    #[test]
53    fn edge_cases() {
54        // Test case 0: 0
55        assert_eq!(gcd(&BigUint::zero(), &BigUint::zero()), BigUint::zero());
56
57        // Test case 1: 1
58        assert_eq!(gcd(&BigUint::one(), &BigUint::zero()), BigUint::one());
59
60        // Test case 2: 1
61        assert_eq!(gcd(&BigUint::zero(), &BigUint::one()), BigUint::one());
62
63        // Test case 3: 2
64        assert_eq!(gcd(&BigUint::from(2u32), &BigUint::from(2u32)), BigUint::from(2u32));
65
66        // Test case 4: 1
67        assert_eq!(gcd(&BigUint::from(2u32), &BigUint::from(3u32)), BigUint::one());
68
69        // Test case 5: 2
70        assert_eq!(gcd(&BigUint::from(2u32), &BigUint::from(4u32)), BigUint::from(2u32));
71
72        // Test case 6: 1
73        assert_eq!(gcd(&BigUint::from(3u32), &BigUint::from(5u32)), BigUint::one());
74
75        // Test case 7: 3
76        assert_eq!(gcd(&BigUint::from(3u32), &BigUint::from(6u32)), BigUint::from(3u32));
77
78        // Test case 8: 1
79        assert_eq!(gcd(&BigUint::from(4u32), &BigUint::from(7u32)), BigUint::one());
80
81        // Test case 9: 4
82        assert_eq!(gcd(&BigUint::from(4u32), &BigUint::from(8u32)), BigUint::from(4u32));
83
84        // Test case 10: 1
85        assert_eq!(gcd(&BigUint::from(5u32), &BigUint::from(9u32)), BigUint::one());
86
87        // Test case 11: 5
88        assert_eq!(gcd(&BigUint::from(5u32), &BigUint::from(10u32)), BigUint::from(5u32));
89    }
90
91    #[test]
92    fn general_cases() {
93        // Big Numbers 6-8 digits
94
95        assert_eq!(
96            gcd(&BigUint::from(123456u32), &BigUint::from(123456u32)),
97            BigUint::from(123456u32)
98        );
99        assert_eq!(gcd(&BigUint::from(123456u32), &BigUint::from(123457u32)), BigUint::one());
100        assert_eq!(gcd(&BigUint::from(123456u32), &BigUint::from(123458u32)), BigUint::from(2u32));
101        assert_eq!(gcd(&BigUint::from(123456u32), &BigUint::from(123459u32)), BigUint::from(3u32));
102        assert_eq!(gcd(&BigUint::from(123456u32), &BigUint::from(123460u32)), BigUint::from(4u32));
103        assert_eq!(gcd(&BigUint::from(123456u32), &BigUint::from(123461u32)), BigUint::one());
104        assert_eq!(gcd(&BigUint::from(123456u32), &BigUint::from(123462u32)), BigUint::from(6u32));
105        assert_eq!(gcd(&BigUint::from(123456u32), &BigUint::from(123463u32)), BigUint::one());
106        assert_eq!(gcd(&BigUint::from(123456u32), &BigUint::from(123464u32)), BigUint::from(8u32));
107        assert_eq!(gcd(&BigUint::from(123456u32), &BigUint::from(123465u32)), BigUint::from(3u32));
108    }
109}
large_primes/operations/gcd.rs

large_primes/operations/
gcd.rs
