User:Inthar/Code: Difference between revisions

← Older edit Newer edit →

VisualWikitext

@@ Line 694: / Line 694: @@
 }
-fn gcd(m: i64, n: i64) -> i64 {
+/// Gives the greatest common denominator of the two inputs, unless that's 2^63.
-	let mut x = m;
+/// 2^63 doesn't fit in an `i64`, so it returns -2^63, which does.
-	let mut y = n;
+pub fn gcd(u: i64, v: i64) -> i64 {
-	while x != 0 && y != 0 {
+    // `wrapping_abs` gives a number's absolute value, unless that's 2^63. 2^63
-		if x > y {
+    // won't fit in `i64`, so it gives -2^63 instead.
-			x = x % y;
+    let mut v = v.wrapping_abs() as u64;
-		} else {
+    if u == 0 {
-			y = y % x;
+        return v as i64;
-		}
+    }
-	}
+    let mut u = u.wrapping_abs() as u64;
-	if y == 0 {x} else {y}
+    if v == 0 {
+        return u as i64;
+    }
+    // `|` is bitwise OR. `trailing_zeros` quickly counts a binary number's
+    // trailing zeros, giving its prime factorization's exponent on two.
+    let gcd_exponent_on_two = (u | v).trailing_zeros();
+    // `>>=` divides the left by two to the power of the right, storing that in
+    // the left variable. `u` divided by its prime factorization's power of two
+    // turns it odd.
+    u >>= u.trailing_zeros();
+    v >>= v.trailing_zeros();
+    while u != v {
+        if u < v {
+            // Swap the variables' values with each other.
+            core::mem::swap(&mut u, &mut v);
+        }
+        u -= v;
+        u >>= u.trailing_zeros();
+    }
+    // `<<` multiplies the left by two to the power of the right.
+    (u << gcd_exponent_on_two) as i64
 }
@@ Line 924: / Line 948: @@
 }
 </syntaxhighlight>
 === main.rs ===
 <syntaxhighlight lang="rust>