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

#![no_std]

use core::mem;

pub trait Gcd {
    /// Determine [greatest common divisor](https://en.wikipedia.org/wiki/Greatest_common_divisor)
    /// using [`gcd_binary`].
    ///
    /// [`gcd_binary`]: #method.gcd_binary
    ///
    /// # Examples
    ///
    /// ```
    /// use gcd::Gcd;
    ///
    /// assert_eq!(0, 0u8.gcd(0));
    /// assert_eq!(10, 10u8.gcd(0));
    /// assert_eq!(10, 0u8.gcd(10));
    /// assert_eq!(10, 10u8.gcd(20));
    /// assert_eq!(44, 2024u32.gcd(748));
    /// ```
    fn gcd(self, other: Self) -> Self;

    /// Determine [greatest common divisor](https://en.wikipedia.org/wiki/Greatest_common_divisor)
    /// using the [Binary GCD algorithm](https://en.wikipedia.org/wiki/Binary_GCD_algorithm).
    fn gcd_binary(self, other: Self) -> Self;

    /// Determine [greatest common divisor](https://en.wikipedia.org/wiki/Greatest_common_divisor)
    /// using the [Euclidean algorithm](https://en.wikipedia.org/wiki/Euclidean_algorithm).
    fn gcd_euclid(self, other: Self) -> Self;
}

macro_rules! gcd_impl {
    ($($T:ty),*) => {$(
        impl Gcd for $T {
            fn gcd(self, other: $T) -> $T {
                self.gcd_binary(other)
            }

            fn gcd_binary(self, mut v: $T) -> $T {
                let mut u = self;

                if u == 0 { return v; }
                if v == 0 { return u; }

                let shift = (u | v).trailing_zeros();
                u >>= shift;
                v >>= shift;
                u >>= u.trailing_zeros();

                loop {
                    v >>= v.trailing_zeros();

                    if u > v {
                        mem::swap(&mut u, &mut v);
                    }

                    v -= u; // here v >= u

                    if v == 0 { break; }
                }

                u << shift
            }

            fn gcd_euclid(self, other: $T) -> $T {
                // variable names based off euclidean divison equation: a = b · q + r
                let (mut a, mut b) = if self > other {
                    (self, other)
                } else {
                    (other, self)
                };

                while b != 0 {
                    mem::swap(&mut a, &mut b);
                    b %= a;
                }

                a
            }
        }
    )*};
}

gcd_impl! { u8, u16, u32, u64, u128, usize }

#[cfg(test)]
mod test {
    use super::Gcd;

    #[test]
    fn test_gcd() {
        assert_eq!(0, 0u8.gcd_euclid(0));
        assert_eq!(10, 10u8.gcd_euclid(0));
        assert_eq!(10, 0u8.gcd_euclid(10));
        assert_eq!(10, 10u8.gcd_euclid(20));
        assert_eq!(44, 2024u32.gcd_euclid(748));

        assert_eq!(0, 0u8.gcd_binary(0));
        assert_eq!(10, 10u8.gcd_binary(0));
        assert_eq!(10, 0u8.gcd_binary(10));
        assert_eq!(10, 10u8.gcd_binary(20));
        assert_eq!(44, 2024u32.gcd_binary(748));
    }
}