Implement gcd in sdk.

tests/corelib/big_integer_arith_vm_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.
 
 // Testing Bigints with and without intrinsics.
 // VMOptions=
 // VMOptions=--no_intrinsify
 
 library big_integer_test;
 import "package:expect/expect.dart";
@@ skipping 275 matching lines @@
   m = 123456789012345678901234567890;
   Expect.throws(() => x.modInverse(m), (e) => e is RangeError);  // Not coprime.
   x = 123456789012345678901234567891;
   m = 123456789012345678901234567890;
   Expect.equals(1, x.modInverse(m));
   x = 123456789012345678901234567891;
   m = 123456789012345678901234567899;
   Expect.equals(46296295879629629587962962962, x.modInverse(m));
 }
 
+testBigintGcd() {
+  var x, m;
+  x = 1;
+  m = 1;
+  Expect.equals(1, x.gcd(m));
+  x = 693;
+  m = 609;
+  Expect.equals(21, x.gcd(m));
+  x = 693 << 40;
+  m = 609 << 40;
+  Expect.equals(21 << 40, x.gcd(m));
+  x = 609 << 40;;
+  m = 693 << 40;;
+  Expect.equals(21 <<40, x.gcd(m));
+  x = 0;
+  m = 1000000001;
+  Expect.throws(() => x.gcd(m), (e) => e is RangeError);
+  x = 1000000001;
+  m = 0;
+  Expect.throws(() => x.gcd(m), (e) => e is RangeError);
+  x = 1234567890;
+  m = 19;
+  Expect.equals(1, x.gcd(m));
+  x = 1234567890;
+  m = 1000000001;
+  Expect.equals(1, x.gcd(m));
+  x = 19;
+  m = 1000000001;
+  Expect.equals(19, x.gcd(m));
+  x = 19;
+  m = 1234567890;
+  Expect.equals(1, x.gcd(m));
+  x = 1000000001;
+  m = 1234567890;
+  Expect.equals(1, x.gcd(m));
+  x = 1000000001;
+  m = 19;
+  Expect.equals(19, x.gcd(m));
+  x = 12345678901234567890;
+  m = 19;
+  Expect.equals(1, x.gcd(m));
+  x = 12345678901234567890;
+  m = 10000000000000000001;
+  Expect.equals(1, x.gcd(m));
+  x = 19;
+  m = 10000000000000000001;
+  Expect.equals(1, x.gcd(m));
+  x = 19;
+  m = 12345678901234567890;
+  Expect.equals(1, x.gcd(m));
+  x = 10000000000000000001;
+  m = 12345678901234567890;
+  Expect.equals(1, x.gcd(m));
+  x = 10000000000000000001;
+  m = 19;
+  Expect.equals(1, x.gcd(m));
+  x = 12345678901234567890;
+  m = 10000000000000000001;
+  Expect.equals(1, x.gcd(m));
+  x = 12345678901234567890;
+  m = 19;
+  Expect.equals(1, x.gcd(m));
+  x = 123456789012345678901234567890;
+  m = 123456789012345678901234567899;
+  Expect.equals(9, x.gcd(m));
+  x = 123456789012345678901234567890;
+  m = 123456789012345678901234567891;
+  Expect.equals(1, x.gcd(m));
+  x = 123456789012345678901234567899;
+  m = 123456789012345678901234567891;
+  Expect.equals(1, x.gcd(m));
+  x = 123456789012345678901234567899;
+  m = 123456789012345678901234567890;
+  Expect.equals(9, x.gcd(m));
+  x = 123456789012345678901234567891;
+  m = 123456789012345678901234567890;
+  Expect.equals(1, x.gcd(m));
+  x = 123456789012345678901234567891;
+  m = 123456789012345678901234567899;
+  Expect.equals(1, x.gcd(m));
+}
+
 testBigintNegate() {
   var a = 0xF000000000000000F;
   var b = ~a;  // negate.
   Expect.equals(-0xF0000000000000010, b);
   Expect.equals(0, a & b);
   Expect.equals(-1, a | b);
 }
 
 testShiftAmount() {
   Expect.equals(0, 12 >> 111111111111111111111111111111);
@@ skipping 12 matching lines @@
   Expect.equals(12345678901234567890, bar());
   testSmiOverflow();
   testBigintAdd();
   testBigintSub();
   testBigintMul();
   testBigintTruncDiv();
   testBigintDiv();
   testBigintModulo();
   testBigintModPow();
   testBigintModInverse();
+  testBigintGcd();
   testBigintNegate();
   testShiftAmount();
   Expect.equals(12345678901234567890, (12345678901234567890).abs());
   Expect.equals(12345678901234567890, (-12345678901234567890).abs());
   var a = 10000000000000000000;
   var b = 10000000000000000001;
   Expect.equals(false, a.hashCode == b.hashCode);
   Expect.equals(true, a.hashCode == (b - 1).hashCode);
 }