osom_lib_numbers/
gcd.rs

1//! Hold helpers for computing the greatest common divisor.
2
3macro_rules! gcd_impl {
4    ( $a: expr, $b: expr ) => {{
5        let mut a = { $a };
6        let mut b = { $b };
7        if a == 0 {
8            return b;
9        }
10        if b == 0 {
11            return a;
12        }
13
14        let shift = (a | b).trailing_zeros();
15
16        a >>= a.trailing_zeros();
17        b >>= b.trailing_zeros();
18
19        while b != 0 {
20            b >>= b.trailing_zeros();
21            if a < b {
22                b -= a;
23            } else {
24                let temp = a - b;
25                a = b;
26                b = temp;
27            }
28        }
29        a << shift
30    }};
31}
32
33/// Computes the greatest common divisor of two 32-bit unsigned integers
34/// in an efficient way.
35#[must_use]
36pub const fn gcd_32(a: u32, b: u32) -> u32 {
37    gcd_impl!(a, b)
38}
39
40/// Computes the greatest common divisor of two 64-bit unsigned integers
41/// in an efficient way.
42#[must_use]
43pub const fn gcd_64(a: u64, b: u64) -> u64 {
44    gcd_impl!(a, b)
45}
osom_lib_numbers/gcd.rs

osom_lib_numbers/
gcd.rs
