Implement math.gcd in dart.

pkg/math/lib/math.dart

 // Copyright (c) 2013, 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 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;
+}