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

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

Issue 475463005: Implement math.gcd in dart. (Closed) Base URL: https://dart.googlecode.com/svn/branches/bleeding_edge/dart
Patch Set: mint and 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/math/math_test.dart » ('j') | tests/lib/math/math_test.dart » ('J')
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
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.
+}
« no previous file with comments | « no previous file | tests/lib/math/math_test.dart » ('j') | tests/lib/math/math_test.dart » ('J')

Powered by Google App Engine
This is Rietveld 408576698