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:
srawlins
2014/08/20 01:06:27
Done and done. Thanks for this recommendation. I'v
|
+ 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 va
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
srawlins
2014/08/20 01:06:26
Done.
|
+} |