acm 0.1.4

Arithmetic congruence monoid implementation in Rust
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

pub trait GCD {
    // Extended Euclidean algorithm
    fn gcd(self, other: Self) -> Self;
}

impl<T: Into<i32> + From<i32>> GCD for T {
    fn gcd(self, other: Self) -> Self {
        let a: i32 = self.into();
        let b: i32 = other.into();
        let mut prev = [a, 1, 0];
        let mut curr = [b, 0, 1];
        while curr[0] != 0 {
            let q = prev[0] / curr[0];
            for i in 0..2 {
                let temp = curr[i];
                curr[i] = prev[i] - q * temp;
                prev[i] = temp;
            }
        }
        prev[0].into()
    }
}