Skip to content

Instantly share code, notes, and snippets.

@Rudxain
Last active March 10, 2023 05:54
Show Gist options
  • Save Rudxain/f25ae51470da7e934196d1184fb913d2 to your computer and use it in GitHub Desktop.
Save Rudxain/f25ae51470da7e934196d1184fb913d2 to your computer and use it in GitHub Desktop.
calculates the greatest-common-divisor of many argv `i128`s using Euclidean algorithm
/// # Greatest Common Divisor / Highest Common Factor
/// between `a` & `b`,
/// using https://en.wikipedia.org/wiki/Euclidean_algorithm.
///
/// It only supports unsigneds,
/// because it's easier to avoid bugs,
/// and allows wider input ranges.
const fn gcd(mut a: u128, mut b: u128) -> u128 {
// rustc doesn't have TCO, so recursion is not an option
while b != 0 {
// we could use tuple literals, instead of array literals,
// but arrays are "more type safe", because of homogeneity
[a, b] = [b, a % b];
// this destructuring asignment allows us to get the beauty of recursion
// with imperative programming!
}
a
}
fn main() {
println!(
"{}",
std::env::args()
.skip(1)
.map(|s| s.parse::<i128>().unwrap().unsigned_abs())
.reduce(gcd)
.unwrap_or(0) // GCD identity: gcd(x, 0) = x
);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment