Implement math.gcd in dart.

tests/lib/math/math_test.dart

 // Copyright (c) 2011, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 library math_test;
 import "package:expect/expect.dart";
 import 'dart:math';
 
 class MathTest {
   static void testConstants() {
@@ skipping 128 matching lines @@
   }
 
   static void testLog() {
     // Even though E is imprecise, it is good enough to get really close to 1.
     // We still provide an epsilon.
     checkClose(1.0, log(E), 1e-16);
     checkVeryClose(LN10, log(10.0));
     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);
       return false;
     } on FormatException catch (e) {
       return true;
     }
   }
 
   static void testParseInt() {
@@ skipping 79 matching lines @@
     testSin();
     testCos();
     testTan();
     testAsin();
     testAcos();
     testAtan();
     testAtan2();
     testSqrt();
     testLog();
     testExp();
+    testGcd();
     testParseInt();
   }
 }
 
 main() {
   MathTest.testMain();
 }