94 lines
3.0 KiB
Rust
94 lines
3.0 KiB
Rust
use std::cmp::{max, min};
|
|
|
|
pub trait UnsignedGCD {
|
|
/// Find the greatest common denominator of two numbers
|
|
fn gcd(a: Self, b: Self) -> Self;
|
|
|
|
/// Euclid gcd algorithm
|
|
fn e_gcd(a: Self, b: Self) -> Self;
|
|
|
|
/// Stein gcd algorithm
|
|
fn stein_gcd(a: Self, b: Self) -> Self;
|
|
|
|
/// Find the least common multiple of two numbers
|
|
fn lcm(a: Self, b: Self) -> Self;
|
|
}
|
|
|
|
macro_rules! impl_unsigned {
|
|
($($Type: ty),* ) => {
|
|
$(
|
|
impl UnsignedGCD for $Type {
|
|
/// Implementation based on
|
|
/// [Binary GCD algorithm](https://en.wikipedia.org/wiki/Binary_GCD_algorithm)
|
|
fn gcd(a: $Type, b: $Type) -> $Type {
|
|
if a == b {
|
|
return a;
|
|
} else if a == 0 {
|
|
return b;
|
|
} else if b == 0 {
|
|
return a;
|
|
}
|
|
|
|
let a_even = a % 2 == 0;
|
|
let b_even = b % 2 == 0;
|
|
|
|
if a_even {
|
|
if b_even {
|
|
// Both a & b are even
|
|
return Self::gcd(a >> 1, b >> 1) << 1;
|
|
} else if !b_even {
|
|
// b is odd
|
|
return Self::gcd(a >> 1, b);
|
|
}
|
|
}
|
|
|
|
// a is odd, b is even
|
|
if (!a_even) && b_even {
|
|
return Self::gcd(a, b >> 1);
|
|
}
|
|
|
|
if a > b {
|
|
return Self::gcd((a - b) >> 1, b);
|
|
}
|
|
|
|
Self::gcd((b - a) >> 1, a)
|
|
}
|
|
|
|
fn e_gcd(x: $Type, y: $Type) -> $Type {
|
|
let mut x = x;
|
|
let mut y = y;
|
|
while y != 0 {
|
|
let t = y;
|
|
y = x % y;
|
|
x = t;
|
|
}
|
|
x
|
|
}
|
|
|
|
fn stein_gcd(a: Self, b: Self) -> Self {
|
|
match ((a, b), (a & 1, b & 1)) {
|
|
((x, y), _) if x == y => y,
|
|
((0, x), _) | ((x, 0), _) => x,
|
|
((x, y), (0, 1)) | ((y, x), (1, 0)) => Self::stein_gcd(x >> 1, y),
|
|
((x, y), (0, 0)) => Self::stein_gcd(x >> 1, y >> 1) << 1,
|
|
((x, y), (1, 1)) => {
|
|
let (x, y) = (min(x, y), max(x, y));
|
|
Self::stein_gcd((y - x) >> 1, x)
|
|
}
|
|
_ => unreachable!(),
|
|
}
|
|
}
|
|
|
|
fn lcm(a: $Type, b: $Type) -> $Type {
|
|
if (a == 0 && b == 0) {
|
|
return 0;
|
|
}
|
|
|
|
a * b / Self::gcd(a, b)
|
|
}
|
|
}
|
|
)*
|
|
};
|
|
}
|
|
|
|
impl_unsigned!(u8, u16, u32, u64, u128, usize); |