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.
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; |
+} |