Implement math.gcd in dart.

tests/lib/math/math_test.dart

Index: tests/lib/math/math_test.dart
diff --git a/tests/lib/math/math_test.dart b/tests/lib/math/math_test.dart
index b911e0a5157d1f305cab9c099c878d8068538703..05170033c8f0e1e45ee80a287566852d732a80b7 100644
--- a/tests/lib/math/math_test.dart
+++ b/tests/lib/math/math_test.dart
@@ -146,6 +146,63 @@ class MathTest {
     checkVeryClose(LN2, log(2.0));
   }
 
+  static void testGcd() {
+    Expect.equals(7, gcd(0, 7));
+    Expect.equals(5, gcd(5, 0));
+    Expect.equals(0, gcd(0, 0));
+    Expect.equals(1, gcd(5, 7));
+    Expect.equals(6, gcd(12, 18));
+    Expect.equals(6, gcd(18, 12));
+    Expect.equals(15, gcd(45, 105));
+
+    Expect.throws(() => gcd(0, -1), (e) => e is RangeError);
+    Expect.throws(() => gcd(-1, 0), (e) => e is RangeError);
+    Expect.throws(() => gcd(0, null), (e) => e is ArgumentError);
+    Expect.throws(() => gcd(null, 0), (e) => e is ArgumentError);
+
+    // Cover all branches in Binary GCD implementation.
+    // 0 shared powers-of-two factors.
+    Expect.equals(1, gcd(2*2, 7));
+    // 1 shared power-of-two factor.
+    Expect.equals(2, gcd(2*2, 2*7));
+    // >1 shared powers-of-two factors.
+    Expect.equals(8, gcd(2*2*2*3, 2*2*2*5));
+
+    // 0 remaining powers-of-two in a.
+    Expect.equals(6, gcd(2*3, 2*3*3));
+    // 1 remaining power-of-two in a.
+    Expect.equals(6, gcd(2*2*3, 2*3*3));
+    // >1 remaining powers-of-two in a.
+    Expect.equals(6, gcd(2*2*2*2*3, 2*3*3));
+
+    // 0 remaining powers-of-two in b.
+    Expect.equals(6, gcd(2*3, 2*3*3));
+    // 1 remaining power-of-two in b.
+    Expect.equals(6, gcd(2*3, 2*2*3));
+    // >1 remaining powers-of-two in b.
+    Expect.equals(6, gcd(2*3, 2*2*2*3*3));
+
+    // Innermost 'if'
+    // a > b.
+    Expect.equals(6, gcd(2*2*3*5, 2*3));
+    // a == b.
+    Expect.equals(6, gcd(2*3, 2*2*2*3));
+    // a < b.
+    Expect.equals(6, gcd(2*3, 2*2*3*7));
+
+    // do while loop executions.
+    // Executed 1 time.
+    Expect.equals(6, gcd(2*3, 2*2*2*3));
+    // Executed >1 times.
+    Expect.equals(6, gcd(2*3*3, 2*2*3*5));
+
+    // Medium int (mint) arguments.
+    Expect.equals(pow(2, 61), gcd(pow(2, 61)*3, pow(2,62)));
+
+    // Big integer (bigint) arguments.
+    Expect.equals(pow(2, 63)*3, gcd(pow(2, 64)*3*5, pow(2,63)*3*7));

[Lasse Reichstein Nielsen, 2014/08/19 08:31:31]

This is very quickly reduced by dividing by 2 63 times. 
How about keeping the number big without factors of two:
  gcd(3 * 982451653, 7 * 982451653);

[srawlins, 2014/08/20 01:06:27]

Good idea. Done and split into bigint tests since, eg: 31*595056260442243647 ==
18446744073709552000 in javascript's double :(

+  }

[Lasse Reichstein Nielsen, 2014/08/19 08:31:31]

Do these tests succeed on dart2js?

If so, you need more tests :)

[srawlins, 2014/08/20 01:06:27]

Sorry, that test file is expected to raise a RuntimeError, so my tests were
_NOT_ running in dart2js. I've fixed this with the separation into a new file.

+
   static bool parseIntThrowsFormatException(str) {
     try {
       int.parse(str);
@@ -245,6 +302,7 @@ class MathTest {
     testSqrt();
     testLog();
     testExp();
+    testGcd();
     testParseInt();
   }
 }