Implement math.gcd in dart.

pkg/math/lib/math.dart

Index: pkg/math/lib/math.dart
diff --git a/pkg/math/lib/math.dart b/pkg/math/lib/math.dart
index 9958bec52ba1800eb71959658cd887967d62e4f5..47f8026c758477952321c24b933f9dfbd3aee8f5 100644
--- a/pkg/math/lib/math.dart
+++ b/pkg/math/lib/math.dart
@@ -4,4 +4,40 @@
 
 library dart.pkg.math;
 
-// Placeholder library, reserved for future extension.
+/**
+ * Computes the greatest common divisor between [a] and [b].
+ *
+ * [a] and [b] must be non-negative integers.

[Lasse Reichstein Nielsen, 2014/08/20 12:17:02]

-> Both `a` and `b` must be non-negative integers.


This avoid starting the sentence with a lower-case letter, and there is no need
to make [a]/[b] a link more than once in the same documentation.

[srawlins, 2014/08/25 05:43:54]

Done.

+ */
+int gcd(int a, int b) {
+  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.");

[Lasse Reichstein Nielsen, 2014/08/20 12:17:02]

"Both a and b ... 

[srawlins, 2014/08/25 05:43:53]

Done.

+  }
+
+  // Iterative Binary GCD algorithm.
+  if (a == 0) return b;
+  if (b == 0) return a;
+  int powerOfTwo = 1;
+  int temp;
+  while (((a | b) & 1) == 0) {
+    powerOfTwo *= 2;
+    a ~/= 2;
+    b ~/= 2;
+  }
+
+  while (a.isEven) a ~/= 2;
+
+  do {
+    while (b.isEven) b ~/= 2;
+    if (a > b) {
+      temp = b;
+      b = a;
+      a = temp;
+    }
+    b -= a;
+  } while (b != 0);
+
+  return a * powerOfTwo;
+}