Calculating the Greatest Common Divisor in Rust

I recently learned that Rust does not have a greatest common divisor function. See Anonymous (2020) to read some discussion about it.

So if the GCD function is not implemented natively in Rust, how can we go about calculating it?

One option is to use the implementation available in Blandy and Orendorff (2021).

fn gcd(mut n: u64, mut m: u64) -> u64 {
    assert!(n != 0 && m != 0);
    while m != 0 {
        if m < n {
            let t = m;
            m = n;
            n = t;
        }
        m = m % n;
    }
    n
}

let x: u64 = 2024;
let y: u64 = 748;
println!("gcd({}, {}) = {}", x, y, gcd(x, y));

gcd(2024, 748) = 44

Another option is that we could use the gcd crate.

:dep gcd
use gcd::Gcd;

println!("gcd({}, {}) = {}", x, y, x.gcd(y));

gcd(2024, 748) = 44

Often I think going with the existing crate for work projects. There’s no need to reinvent such a simple wheel, and it supports a wider variety of types than the example from Blandy and Orendorff (2021). But it is also a great code example since calculating the GCD is a well-known, and relatively simple, task.

References

Anonymous. 2020. “Why No GCD in Standard Lib?” 2020. https://users.rust-lang.org/t/why-no-gcd-in-standard-lib/36490/7.

Blandy, Jim, and Jason Orendorff. 2021. Programming Rust: Fast, Safe Systems Development. O’Reilly Media. https://www.amazon.ca/Programming-Rust-Fast-Systems-Development/dp/1491927283.