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

Issues Search
    My Issues | Starred     Open | Closed | All

Unified Diff: runtime/lib/bigint.dart

Issue 1199513003: Implement gcd in sdk. (Closed) Base URL: git@github.com:dart-lang/sdk.git@master
Patch Set: Created 5 years, 6 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 | runtime/lib/integers.dart » ('j') | no next file with comments »
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
Index: runtime/lib/bigint.dart
diff --git a/runtime/lib/bigint.dart b/runtime/lib/bigint.dart
index 04b85b7d4d5610fe8edbf480bbe1f2f83d85fa31..adfb0db4cca73f924008dec248d1c07a09a464d5 100644
--- a/runtime/lib/bigint.dart
+++ b/runtime/lib/bigint.dart
@@ -47,6 +47,7 @@
class _Bigint extends _IntegerImplementation implements int {
// Bits per digit.
static const int _DIGIT_BITS = 32;
+ static const int _LOG2_DIGIT_BITS = 5;
static const int _DIGIT_BASE = 1 << _DIGIT_BITS;
static const int _DIGIT_MASK = (1 << _DIGIT_BITS) - 1;
@@ -1538,27 +1539,52 @@ class _Bigint extends _IntegerImplementation implements int {
return z._revert(r_digits, r_used)._toValidInt();
}
- // 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;
- m = m._toBigint();
- var t = this;
- if (t._neg || (t._absCompare(m) >= 0)) {
- t %= m;
- t = t._toBigint();
+ // 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(_Bigint x, _Bigint y, bool inv) {
+ var x_digits = x._digits;
+ var y_digits = y._digits;
+ var x_used = x._used;
+ var y_used = y._used;
+ var m_used = x_used > y_used ? x_used : y_used;
+ final m_len = m_used + (m_used & 1);
+ x_digits = _cloneDigits(x_digits, 0, x_used, m_len);
+ y_digits = _cloneDigits(y_digits, 0, y_used, m_len);
+ int s = 0;
+ if (inv) {
+ if ((y_used == 1) && (y_digits[0] == 1)) return 1;
+ if ((y_used == 0) || (y_digits[0].isEven && x_digits[0].isEven)) {
+ throw new RangeError("Not coprime");
+ }
+ } else {
+ if ((x_used == 0) || (y_used == 0)) throw new RangeError(0);
+ if (((x_used == 1) && (x_digits[0] == 1)) ||
+ ((y_used == 1) && (y_digits[0] == 1))) return 1;
+ bool xy_cloned = false;
+ while (x.isEven && y.isEven) {
+ _rsh(x_digits, x_used, 1, x_digits);
+ _rsh(y_digits, y_used, 1, y_digits);
+ s++;
+ }
+ if (s >= _DIGIT_BITS) {
+ var sd = s >> _LOG2_DIGIT_BITS;
+ x_used -= sd;
+ y_used -= sd;
+ m_used -= sd;
+ }
+ if ((y_digits[0] & 1) == 1) {
+ var t_digits = x_digits;
+ var t_used = x_used;
+ x_digits = y_digits;
+ x_used = y_used;
+ y_digits = t_digits;
+ y_used = t_used;
+ }
}
- final bool ac = m.isEven;
- final t_used = t._used;
- if ((t_used == 1) && (t._digits[0] == 1)) return 1;
- if ((t_used == 0) || (ac && t.isEven)) throw new RangeError("Not coprime");
- final m_digits = m._digits;
- final m_used = m._used;
- final tuv_len = m_used + (m_used & 1);
- final t_digits = _cloneDigits(t._digits, 0, t_used, tuv_len);
- var u_digits = _cloneDigits(m_digits, 0, m_used, tuv_len);
- var v_digits = _cloneDigits(t_digits, 0, t_used, tuv_len);
+ var u_digits = _cloneDigits(x_digits, 0, x_used, m_len);
+ var v_digits = _cloneDigits(y_digits, 0, y_used, m_len);
+ final bool ac = (x_digits[0] & 1) == 0;
// Variables a, b, c, and d require one more digit.
final abcd_used = m_used + 1;
@@ -1585,34 +1611,34 @@ class _Bigint extends _IntegerImplementation implements int {
if (((a_digits[0] & 1) == 1) || ((b_digits[0] & 1) == 1)) {
if (a_neg) {
if ((a_digits[m_used] != 0) ||
- (_compareDigits(a_digits, m_used, t_digits, m_used)) > 0) {
- _absSub(a_digits, abcd_used, t_digits, m_used, a_digits);
+ (_compareDigits(a_digits, m_used, y_digits, m_used)) > 0) {
+ _absSub(a_digits, abcd_used, y_digits, m_used, a_digits);
} else {
- _absSub(t_digits, m_used, a_digits, m_used, a_digits);
+ _absSub(y_digits, m_used, a_digits, m_used, a_digits);
a_neg = false;
}
} else {
- _absAdd(a_digits, abcd_used, t_digits, m_used, a_digits);
+ _absAdd(a_digits, abcd_used, y_digits, m_used, a_digits);
}
if (b_neg) {
- _absAdd(b_digits, abcd_used, m_digits, m_used, b_digits);
+ _absAdd(b_digits, abcd_used, x_digits, m_used, b_digits);
} else if ((b_digits[m_used] != 0) ||
- (_compareDigits(b_digits, m_used, m_digits, m_used) > 0)) {
- _absSub(b_digits, abcd_used, m_digits, m_used, b_digits);
+ (_compareDigits(b_digits, m_used, x_digits, m_used) > 0)) {
+ _absSub(b_digits, abcd_used, x_digits, m_used, b_digits);
} else {
- _absSub(m_digits, m_used, b_digits, m_used, b_digits);
+ _absSub(x_digits, m_used, b_digits, m_used, b_digits);
b_neg = true;
}
}
_rsh(a_digits, abcd_used, 1, a_digits);
} else if ((b_digits[0] & 1) == 1) {
if (b_neg) {
- _absAdd(b_digits, abcd_used, m_digits, m_used, b_digits);
+ _absAdd(b_digits, abcd_used, x_digits, m_used, b_digits);
} else if ((b_digits[m_used] != 0) ||
- (_compareDigits(b_digits, m_used, m_digits, m_used) > 0)) {
- _absSub(b_digits, abcd_used, m_digits, m_used, b_digits);
+ (_compareDigits(b_digits, m_used, x_digits, m_used) > 0)) {
+ _absSub(b_digits, abcd_used, x_digits, m_used, b_digits);
} else {
- _absSub(m_digits, m_used, b_digits, m_used, b_digits);
+ _absSub(x_digits, m_used, b_digits, m_used, b_digits);
b_neg = true;
}
}
@@ -1624,34 +1650,34 @@ class _Bigint extends _IntegerImplementation implements int {
if (((c_digits[0] & 1) == 1) || ((d_digits[0] & 1) == 1)) {
if (c_neg) {
if ((c_digits[m_used] != 0) ||
- (_compareDigits(c_digits, m_used, t_digits, m_used) > 0)) {
- _absSub(c_digits, abcd_used, t_digits, m_used, c_digits);
+ (_compareDigits(c_digits, m_used, y_digits, m_used) > 0)) {
+ _absSub(c_digits, abcd_used, y_digits, m_used, c_digits);
} else {
- _absSub(t_digits, m_used, c_digits, m_used, c_digits);
+ _absSub(y_digits, m_used, c_digits, m_used, c_digits);
c_neg = false;
}
} else {
- _absAdd(c_digits, abcd_used, t_digits, m_used, c_digits);
+ _absAdd(c_digits, abcd_used, y_digits, m_used, c_digits);
}
if (d_neg) {
- _absAdd(d_digits, abcd_used, m_digits, m_used, d_digits);
+ _absAdd(d_digits, abcd_used, x_digits, m_used, d_digits);
} else if ((d_digits[m_used] != 0) ||
- (_compareDigits(d_digits, m_used, m_digits, m_used) > 0)) {
- _absSub(d_digits, abcd_used, m_digits, m_used, d_digits);
+ (_compareDigits(d_digits, m_used, x_digits, m_used) > 0)) {
+ _absSub(d_digits, abcd_used, x_digits, m_used, d_digits);
} else {
- _absSub(m_digits, m_used, d_digits, m_used, d_digits);
+ _absSub(x_digits, m_used, d_digits, m_used, d_digits);
d_neg = true;
}
}
_rsh(c_digits, abcd_used, 1, c_digits);
} else if ((d_digits[0] & 1) == 1) {
if (d_neg) {
- _absAdd(d_digits, abcd_used, m_digits, m_used, d_digits);
+ _absAdd(d_digits, abcd_used, x_digits, m_used, d_digits);
} else if ((d_digits[m_used] != 0) ||
- (_compareDigits(d_digits, m_used, m_digits, m_used) > 0)) {
- _absSub(d_digits, abcd_used, m_digits, m_used, d_digits);
+ (_compareDigits(d_digits, m_used, x_digits, m_used) > 0)) {
+ _absSub(d_digits, abcd_used, x_digits, m_used, d_digits);
} else {
- _absSub(m_digits, m_used, d_digits, m_used, d_digits);
+ _absSub(x_digits, m_used, d_digits, m_used, d_digits);
d_neg = true;
}
}
@@ -1719,6 +1745,12 @@ class _Bigint extends _IntegerImplementation implements int {
while ((i > 0) && (u_digits[i - 1] == 0)) --i;
if (i == 0) break;
}
+ if (!inv) {
+ if (s > 0) {
+ _lsh(v_digits, m_used, s, v_digits);
+ }
+ return new _Bigint(false, m_used, v_digits)._toValidInt();
+ }
// No inverse if v != 1.
var i = m_used - 1;
while ((i > 0) && (v_digits[i] == 0)) --i;
@@ -1726,29 +1758,49 @@ class _Bigint extends _IntegerImplementation implements int {
if (d_neg) {
if ((d_digits[m_used] != 0) ||
- (_compareDigits(d_digits, m_used, m_digits, m_used) > 0)) {
- _absSub(d_digits, abcd_used, m_digits, m_used, d_digits);
+ (_compareDigits(d_digits, m_used, x_digits, m_used) > 0)) {
+ _absSub(d_digits, abcd_used, x_digits, m_used, d_digits);
if ((d_digits[m_used] != 0) ||
- (_compareDigits(d_digits, m_used, m_digits, m_used) > 0)) {
- _absSub(d_digits, abcd_used, m_digits, m_used, d_digits);
+ (_compareDigits(d_digits, m_used, x_digits, m_used) > 0)) {
+ _absSub(d_digits, abcd_used, x_digits, m_used, d_digits);
} else {
- _absSub(m_digits, m_used, d_digits, m_used, d_digits);
+ _absSub(x_digits, m_used, d_digits, m_used, d_digits);
d_neg = false;
}
} else {
- _absSub(m_digits, m_used, d_digits, m_used, d_digits);
+ _absSub(x_digits, m_used, d_digits, m_used, d_digits);
d_neg = false;
}
} else if ((d_digits[m_used] != 0) ||
- (_compareDigits(d_digits, m_used, m_digits, m_used) > 0)) {
- _absSub(d_digits, abcd_used, m_digits, m_used, d_digits);
+ (_compareDigits(d_digits, m_used, x_digits, m_used) > 0)) {
+ _absSub(d_digits, abcd_used, x_digits, m_used, d_digits);
if ((d_digits[m_used] != 0) ||
- (_compareDigits(d_digits, m_used, m_digits, m_used) > 0)) {
- _absSub(d_digits, abcd_used, m_digits, m_used, d_digits);
+ (_compareDigits(d_digits, m_used, x_digits, m_used) > 0)) {
+ _absSub(d_digits, abcd_used, x_digits, m_used, d_digits);
}
}
return new _Bigint(false, m_used, d_digits)._toValidInt();
}
+
+ // 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;
+ m = m._toBigint();
+ var t = this;
+ if (t._neg || (t._absCompare(m) >= 0)) {
+ t %= m;
+ t = t._toBigint();
+ }
+ 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);
+ return _binaryGcd(this, other._toBigint(), false);
+ }
}
// Interface for modular reduction.
« no previous file with comments | « no previous file | runtime/lib/integers.dart » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698