Implement math.gcd in dart.

sdk/lib/math/math.dart

Index: sdk/lib/math/math.dart
diff --git a/sdk/lib/math/math.dart b/sdk/lib/math/math.dart
index 95ed261e2753eade411dd52f6e86202ca3a5e881..feacc79cb3aa9fed222c679bb3ca4656a9aa7125 100644
--- a/sdk/lib/math/math.dart
+++ b/sdk/lib/math/math.dart
@@ -251,3 +251,41 @@ external double exp(num x);
  * Returns NaN if [x] is NaN or less than zero.
  */
 external double log(num x);
+
+/**
+ * Computes the greatest common divisor between [a] and [b].
+ *
+ * [a] and [b] must be non-negative integers.
+ */
+int gcd(int a, int b) {

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

Adding an uncapitalized top-level name to a dart: library is considered a
breaking change.
If someone has a class
  class C {
     int gcd;
     bool isGcd(int x) => x == gcd;
  }
it will break after importing the new math library.

For this reason, I would prefer to put gcd in package:math instead of dart:math.

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

Done and done. Thanks for this recommendation. I've also split the test out.

+  if (a is! int) throw new ArgumentError(a);
+  if (b is! int) throw new ArgumentError(b);
+  if (a.isNegative || b.isNegative) {
+    throw new RangeError("a and b must not be negative; received $a and $b.");
+  }
+
+  // Iterative Binary GCD algorithm.
+  if (a == 0) return b;
+  if (b == 0) return a;
+  int powersOfTwo = 0;
+  int temp;
+  while (((a | b) & 1) == 0) {
+    powersOfTwo++;
+    a >>= 1;
+    b >>= 1;

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

This may be surprising when it doesn't work for values >2^32 in dart2js.
Use "a ~/= 2" instead of "a >>= 1".
Dittos below.

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

Done.

+  }
+
+  while ((a & 1) == 0) a >>= 1;

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

a.isEven, ditto b below.

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

Done.

+
+  do {
+    while ((b & 1) == 0) b >>= 1;
+    if (a > b) {
+      temp = b;
+      b = a;
+      a = temp;
+    }
+    b -= a;
+  } while (b != 0);
+
+  return a << powersOfTwo;

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

Same problem. You could keep powersOf2 as a factor instead:

int powerOfTwo = 1;
powerOfTwo*=2;  // instead of powersOfTwo++

return a * powerOfTwo;

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

Done.

+}