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

Unified Diff: runtime/lib/integers.dart

Issue 1174513004: Implement modInverse (bigint version does not support even modulus yet). (Closed) Base URL: git@github.com:dart-lang/sdk.git@master
Patch Set: Address review comments 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 | « runtime/lib/bigint.dart ('k') | sdk/lib/_internal/compiler/js_lib/js_number.dart » ('j') | no next file with comments »
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
Index: runtime/lib/integers.dart
diff --git a/runtime/lib/integers.dart b/runtime/lib/integers.dart
index 857a41568507c93b27a500a2c34e55eea1838af6..5bee4047dbd11db280680ebdff7e562ee85e1368 100644
--- a/runtime/lib/integers.dart
+++ b/runtime/lib/integers.dart
@@ -275,7 +275,6 @@ class _IntegerImplementation extends _Num {
if (e is _Bigint || m is _Bigint) {
return _toBigint().modPow(e, m);
}
- if (e < 1) return 1;
int b = this;
if (b < 0 || b > m) {
b %= m;
@@ -290,6 +289,64 @@ class _IntegerImplementation extends _Num {
}
return r;
}
+
+ // 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 is _Bigint) {
+ return _toBigint().modInverse(m);
+ }
+ bool ac = m.isEven;
+ int u = m;
+ int v = this;
+ int a = 1,
+ b = 0,
+ c = 0,
+ d = 1;
+ while (u != 0) {
+ while (u.isEven) {
+ u >>= 1;
+ if (ac) {
+ if (!a.isEven || !b.isEven) {
+ a += this;
+ b -= m;
+ }
+ a >>= 1;
+ } else if (!b.isEven) {
+ b -= m;
+ }
+ b >>= 1;
+ }
+ while (v.isEven) {
+ v >>= 1;
+ if (ac) {
+ if (!c.isEven || !d.isEven) {
+ c += this;
+ d -= m;
+ }
+ c >>= 1;
+ } else if (!d.isEven) {
+ d -= m;
+ }
+ d >>= 1;
+ }
+ if (u >= v) {
+ u -= v;
+ if (ac) a -= c;
+ b -= d;
+ } else {
+ v -= u;
+ if (ac) c -= a;
+ d -= b;
+ }
+ }
+ if (v != 1) return 0;
+ if (d > m) return d - m;
+ if (d < 0) d += m;
+ if (d < 0) d += m;
+ return d;
+ }
}
class _Smi extends _IntegerImplementation implements int {
« no previous file with comments | « runtime/lib/bigint.dart ('k') | sdk/lib/_internal/compiler/js_lib/js_number.dart » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698