Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(57)

Unified Diff: pkg/math/lib/math.dart

Issue 475463005: Implement math.gcd in dart. (Closed) Base URL: https://dart.googlecode.com/svn/branches/bleeding_edge/dart
Patch Set: Move gcd to pkg/math; move tests; fix implementation; split bigint tests Created 6 years, 4 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View side-by-side diff with in-line comments
Download patch
« no previous file with comments | « no previous file | tests/lib/lib.status » ('j') | tests/lib/math/math_package_bigint_test.dart » ('J')
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
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;
+}
« no previous file with comments | « no previous file | tests/lib/lib.status » ('j') | tests/lib/math/math_package_bigint_test.dart » ('J')

Powered by Google App Engine
This is Rietveld 408576698