Implement gcd in sdk.

sdk/lib/_internal/compiler/js_lib/js_number.dart

Index: sdk/lib/_internal/compiler/js_lib/js_number.dart
diff --git a/sdk/lib/_internal/compiler/js_lib/js_number.dart b/sdk/lib/_internal/compiler/js_lib/js_number.dart
index 157b433e3b8daf9e47eb2de11678bfe6489b678b..b340247a59fa3f338ba2c5bc115c51b4574db8df 100644
--- a/sdk/lib/_internal/compiler/js_lib/js_number.dart
+++ b/sdk/lib/_internal/compiler/js_lib/js_number.dart
@@ -410,18 +410,26 @@ class JSInt extends JSNumber implements int, double {
     return r;
   }
 
-  // Returns 1/this % m, with m > 0.
-  int modInverse(int m) {
-    if (m is! int) throw argumentErrorValue(m);
-    if (m <= 0) throw new RangeError(m);
-    if (m == 1) return 0;
-    int t = this;
-    if ((t < 0) || (t >= m)) t %= m;
-    if (t == 1) return 1;
-    final bool ac = m.isEven;
-    if ((t == 0) || (ac && t.isEven)) throw new RangeError("Not coprime");
-    int u = m;
-    int v = t;
+  // If inv is false, returns gcd(x, y).
+  // If inv is true and gcd(x, y) = 1, returns d, so that c*x + d*y = 1.
+  // If inv is true and gcd(x, y) != 1, throws RangeError("Not coprime").
+  static int _binaryGcd(int x, int y, bool inv) {
+    int s = 1;
+    if (!inv) {
+      while (x.isEven && y.isEven) {
+        x ~/= 2;
+        y ~/= 2;
+        s *= 2;
+      }
+      if (y.isOdd) {
+        var t = x;
+        x = y;
+        y = t;
+      }
+    }
+    final bool ac = x.isEven;
+    int u = x;
+    int v = y;
     int a = 1,
         b = 0,
         c = 0,
@@ -431,12 +439,12 @@ class JSInt extends JSNumber implements int, double {
         u ~/= 2;
         if (ac) {
           if (!a.isEven || !b.isEven) {
-            a += t;
-            b -= m;
+            a += y;
+            b -= x;
           }
           a ~/= 2;
         } else if (!b.isEven) {
-          b -= m;
+          b -= x;
         }
         b ~/= 2;
       }
@@ -444,12 +452,12 @@ class JSInt extends JSNumber implements int, double {
         v ~/= 2;
         if (ac) {
           if (!c.isEven || !d.isEven) {
-            c += t;
-            d -= m;
+            c += y;
+            d -= x;
           }
           c ~/= 2;
         } else if (!d.isEven) {
-          d -= m;
+          d -= x;
         }
         d ~/= 2;
       }
@@ -463,17 +471,40 @@ class JSInt extends JSNumber implements int, double {
         d -= b;
       }
     } while (u != 0);
+    if (!inv) return s*v;
     if (v != 1) throw new RangeError("Not coprime");
     if (d < 0) {
-      d += m;
-      if (d < 0) d += m;
-    } else if (d > m) {
-      d -= m;
-      if (d > m) d -= m;
+      d += x;
+      if (d < 0) d += x;
+    } else if (d > x) {
+      d -= x;
+      if (d > x) d -= x;
     }
     return d;
   }
 
+  // Returns 1/this % m, with m > 0.
+  int modInverse(int m) {
+    if (m is! int) throw new ArgumentError(m);
+    if (m <= 0) throw new RangeError(m);
+    if (m == 1) return 0;
+    int t = this;
+    if ((t < 0) || (t >= m)) t %= m;
+    if (t == 1) return 1;
+    if ((t == 0) || (t.isEven && m.isEven)) throw new RangeError("Not coprime");
+    return _binaryGcd(m, t, true);
+  }
+
+  // Returns gcd of abs(this) and abs(other), with this != 0 and other !=0.
+  int gcd(int other) {
+    if (other is! int) throw new ArgumentError(other);
+    if ((this == 0) || (other == 0)) throw new RangeError(0);
+    int x = this.abs();
+    int y = other.abs();
+    if ((x == 1) || (y == 1)) return 1;
+    return _binaryGcd(x, y, false);
+  }
+
   // Assumes i is <= 32-bit and unsigned.
   static int _bitCount(int i) {
     // See "Hacker's Delight", section 5-1, "Counting 1-Bits".