Implement math.gcd in dart.

sdk/lib/math/math.dart

 // Copyright (c) 2012, 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.
 
 /**
  * Mathematical constants and functions, plus a random number generator.
  */
 library dart.math;
 
 part "jenkins_smi_hash.dart";
@@ skipping 233 matching lines @@
  * Returns NaN if [x] is NaN.
  */
 external double exp(num x);
 
 /**
  * Converts [x] to a double and returns the natural logarithm of the value.
  * Returns negative infinity if [x] is equal to zero.
  * 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.

+}