Anonymous user
Greatest common divisor: Difference between revisions
→{{header|Rust}}: Added Stein's Algorithm
(→{{header|Rust}}: Added Stein's Algorithm) |
|||
Line 3,302:
gcd(n % m, m)
}
}</lang>
===Stein's Algorithm====
Stein's algorithm is very much like Euclid's except that it uses bitwise operators (and consequently slightly more performant) and the integers must be unsigned. The following is a recursive implementation that leverages Rust's pattern matching.
<lang rust>use std::cmp::{min, max};
fn gcd(a: usize, b: usize) -> usize {
match ((a, b), (a & 1, b & 1)) {
// a and b are equal
((x, y), _) if x == y => y,
// Either a or b is zero
((0, x), _) | ((x, 0), _) => x,
// One of a or b is odd and one is even
((x, y), (0, 1)) | ((y, x), (1, 0)) => gcd(x >> 1, y),
// Both a and b are even
((x, y), (0, 0)) => gcd(x >> 1, y >> 1) << 1,
// Both a and b are odd
((x, y), (1, 1)) => { let (x, y) = (min(x, y), max(x, y));
gcd((y - x) >> 1, x)
}
_ => unreachable!(),
}
}</lang>
| |||