Greatest common divisor: Difference between revisions
Content deleted Content added
→{{header|Rust}}: Added Stein's Algorithm |
→Stein's Algorithm: Removed extra = |
||
| Line 3,304: | Line 3,304: | ||
}</lang> |
}</lang> |
||
===Stein's Algorithm |
===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. |
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. |
||
| Line 3,310: | Line 3,310: | ||
fn gcd(a: usize, b: usize) -> usize { |
fn gcd(a: usize, b: usize) -> usize { |
||
match ((a, b), (a & 1, b & 1)) { |
match ((a, b), (a & 1, b & 1)) { |
||
// a and b are equal |
|||
((x, y), _) if x == y => y, |
((x, y), _) if x == y => y, |
||
// Either a or b is zero |
|||
((0, x), _) | ((x, 0), _) => x, |
((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), |
((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, |
((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)); |
((x, y), (1, 1)) => { let (x, y) = (min(x, y), max(x, y)); |
||
gcd((y - x) >> 1, x) |
gcd((y - x) >> 1, x) |
||