Function gcd

pub fn gcd(lhs: u64, rhs: u64) -> u64

Finds an GCD (Greatest Common Divisor) for a pair of numbers.

Examples

use ads_rs::prelude::v1::math::gcd;

let res0 = gcd(42, 144);
let res1 = gcd(377, 610);
let res2 = gcd(105, 25);

assert_eq!(6, res0);
assert_eq!(1, res1);
assert_eq!(5, res2);

Corner case

GCD of both zero numbers equals 0.

use ads_rs::prelude::v1::math::gcd;

let res = gcd(0, 0);

assert_eq!(0, res);

Implementation details

• Stein’s algorithm used (from gcd_many).
• Time complexity: O(N²) where N - number of bits in the biggest number.