Index: sdk/lib/_internal/compiler/js_lib/js_number.dart |
diff --git a/sdk/lib/_internal/compiler/js_lib/js_number.dart b/sdk/lib/_internal/compiler/js_lib/js_number.dart |
index 157b433e3b8daf9e47eb2de11678bfe6489b678b..b340247a59fa3f338ba2c5bc115c51b4574db8df 100644 |
--- a/sdk/lib/_internal/compiler/js_lib/js_number.dart |
+++ b/sdk/lib/_internal/compiler/js_lib/js_number.dart |
@@ -410,18 +410,26 @@ class JSInt extends JSNumber implements int, double { |
return r; |
} |
- // Returns 1/this % m, with m > 0. |
- int modInverse(int m) { |
- if (m is! int) throw argumentErrorValue(m); |
- if (m <= 0) throw new RangeError(m); |
- if (m == 1) return 0; |
- int t = this; |
- if ((t < 0) || (t >= m)) t %= m; |
- if (t == 1) return 1; |
- final bool ac = m.isEven; |
- if ((t == 0) || (ac && t.isEven)) throw new RangeError("Not coprime"); |
- int u = m; |
- int v = t; |
+ // If inv is false, returns gcd(x, y). |
+ // If inv is true and gcd(x, y) = 1, returns d, so that c*x + d*y = 1. |
+ // If inv is true and gcd(x, y) != 1, throws RangeError("Not coprime"). |
+ static int _binaryGcd(int x, int y, bool inv) { |
+ int s = 1; |
+ if (!inv) { |
+ while (x.isEven && y.isEven) { |
+ x ~/= 2; |
+ y ~/= 2; |
+ s *= 2; |
+ } |
+ if (y.isOdd) { |
+ var t = x; |
+ x = y; |
+ y = t; |
+ } |
+ } |
+ final bool ac = x.isEven; |
+ int u = x; |
+ int v = y; |
int a = 1, |
b = 0, |
c = 0, |
@@ -431,12 +439,12 @@ class JSInt extends JSNumber implements int, double { |
u ~/= 2; |
if (ac) { |
if (!a.isEven || !b.isEven) { |
- a += t; |
- b -= m; |
+ a += y; |
+ b -= x; |
} |
a ~/= 2; |
} else if (!b.isEven) { |
- b -= m; |
+ b -= x; |
} |
b ~/= 2; |
} |
@@ -444,12 +452,12 @@ class JSInt extends JSNumber implements int, double { |
v ~/= 2; |
if (ac) { |
if (!c.isEven || !d.isEven) { |
- c += t; |
- d -= m; |
+ c += y; |
+ d -= x; |
} |
c ~/= 2; |
} else if (!d.isEven) { |
- d -= m; |
+ d -= x; |
} |
d ~/= 2; |
} |
@@ -463,17 +471,40 @@ class JSInt extends JSNumber implements int, double { |
d -= b; |
} |
} while (u != 0); |
+ if (!inv) return s*v; |
if (v != 1) throw new RangeError("Not coprime"); |
if (d < 0) { |
- d += m; |
- if (d < 0) d += m; |
- } else if (d > m) { |
- d -= m; |
- if (d > m) d -= m; |
+ d += x; |
+ if (d < 0) d += x; |
+ } else if (d > x) { |
+ d -= x; |
+ if (d > x) d -= x; |
} |
return d; |
} |
+ // Returns 1/this % m, with m > 0. |
+ int modInverse(int m) { |
+ if (m is! int) throw new ArgumentError(m); |
+ if (m <= 0) throw new RangeError(m); |
+ if (m == 1) return 0; |
+ int t = this; |
+ if ((t < 0) || (t >= m)) t %= m; |
+ if (t == 1) return 1; |
+ if ((t == 0) || (t.isEven && m.isEven)) throw new RangeError("Not coprime"); |
+ return _binaryGcd(m, t, true); |
+ } |
+ |
+ // Returns gcd of abs(this) and abs(other), with this != 0 and other !=0. |
+ int gcd(int other) { |
+ if (other is! int) throw new ArgumentError(other); |
+ if ((this == 0) || (other == 0)) throw new RangeError(0); |
+ int x = this.abs(); |
+ int y = other.abs(); |
+ if ((x == 1) || (y == 1)) return 1; |
+ return _binaryGcd(x, y, false); |
+ } |
+ |
// Assumes i is <= 32-bit and unsigned. |
static int _bitCount(int i) { |
// See "Hacker's Delight", section 5-1, "Counting 1-Bits". |