Function extended_gcd

pub fn extended_gcd(lhs: u64, rhs: u64) -> (u64, i64, i64)

Finds an extended GCD (Greatest Common Divisor) for a pair of numbers.
“Extended” means that algorithm will return not only GCD, but two coefficients x and y such that the equality

x * lhs + y * rhs = gcd(lhs, rhs)

holds.

Examples

use ads_rs::prelude::v1::math::extended_gcd;

let res0 = extended_gcd(30, 20);
let res1 = extended_gcd(15, 35);
let res2 = extended_gcd(161, 28);

assert_eq!((10, 1, -1), res0);
assert_eq!((5, -2, 1), res1);
assert_eq!((7, -1, 6), res2);

Corner case

• Result of extended_gcd(0, 0) equals tuple (0, 1, 0).
• Negative numbers is not supported, but implementation allows it.

use ads_rs::prelude::v1::math::extended_gcd;

let res = extended_gcd(0, 0);

assert_eq!((0, 1, 0), res);

Implementation details

• Euclid’s algorithm used, because its extended version is faster than Stein’s algorithm
• Time complexity is O(log₂(min(lhs, rhs)))