Index: pkg/math/lib/math.dart |
diff --git a/pkg/math/lib/math.dart b/pkg/math/lib/math.dart |
deleted file mode 100644 |
index 323bcf7b4d66da6bab47b94ed916e0269343adf1..0000000000000000000000000000000000000000 |
--- a/pkg/math/lib/math.dart |
+++ /dev/null |
@@ -1,154 +0,0 @@ |
-// Copyright (c) 2013, the Dart project authors. Please see the AUTHORS file |
-// for details. All rights reserved. Use of this source code is governed by a |
-// BSD-style license that can be found in the LICENSE file. |
- |
-library dart.pkg.math; |
- |
-/** |
- * Computes the greatest common divisor between [a] and [b]. |
- * |
- * The result is always positive even if either `a` or `b` is negative. |
- */ |
-int gcd(int a, int b) { |
- if (a == null) throw new ArgumentError(a); |
- if (b == null) throw new ArgumentError(b); |
- a = a.abs(); |
- b = b.abs(); |
- |
- // Iterative Binary GCD algorithm. |
- if (a == 0) return b; |
- if (b == 0) return a; |
- int powerOfTwo = 1; |
- 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) { |
- int temp = b; |
- b = a; |
- a = temp; |
- } |
- b -= a; |
- } while (b != 0); |
- |
- return a * powerOfTwo; |
-} |
- |
-/** |
- * Computes the greatest common divisor between [a] and [b], as well as [x] and |
- * [y] such that `ax+by == gcd(a,b)`. |
- * |
- * The return value is a List of three ints: the greatest common divisor, `x`, |
- * and `y`, in that order. |
- */ |
-List<int> gcdext(int a, int b) { |
- if (a == null) throw new ArgumentError(a); |
- if (b == null) throw new ArgumentError(b); |
- |
- if (a < 0) { |
- List<int> result = gcdext(-a, b); |
- result[1] = -result[1]; |
- return result; |
- } |
- if (b < 0) { |
- List<int> result = gcdext(a, -b); |
- result[2] = -result[2]; |
- return result; |
- } |
- |
- int r0 = a; |
- int r1 = b; |
- int x0, x1, y0, y1; |
- x0 = y1 = 1; |
- x1 = y0 = 0; |
- |
- while (r1 != 0) { |
- int q = r0 ~/ r1; |
- int tmp = r0; |
- r0 = r1; |
- r1 = tmp - q*r1; |
- |
- tmp = x0; |
- x0 = x1; |
- x1 = tmp - q*x1; |
- |
- tmp = y0; |
- y0 = y1; |
- y1 = tmp - q*y1; |
- } |
- |
- return new List<int>(3) |
- ..[0] = r0 |
- ..[1] = x0 |
- ..[2] = y0; |
-} |
- |
-/** |
- * Computes the inverse of [a] modulo [m]. |
- * |
- * Throws an [IntegerDivisionByZeroException] if `a` has no inverse modulo `m`: |
- * |
- * invert(4, 7); // 2 |
- * invert(4, 10); // throws IntegerDivisionByZeroException |
- */ |
-int invert(int a, int m) { |
- List<int> results = gcdext(a, m); |
- int g = results[0]; |
- int x = results[1]; |
- if (g != 1) { |
- throw new IntegerDivisionByZeroException(); |
- } |
- return x % m; |
-} |
- |
-/** |
- * Computes the least common multiple between [a] and [b]. |
- */ |
-int lcm(int a, int b) { |
- if (a == null) throw new ArgumentError(a); |
- if (b == null) throw new ArgumentError(b); |
- if (a == 0 && b == 0) return 0; |
- |
- return a.abs() ~/ gcd(a, b) * b.abs(); |
-} |
- |
-/** |
- * Computes [base] raised to [exp] modulo [mod]. |
- * |
- * The result is always positive, in keeping with the behavior of modulus |
- * operator (`%`). |
- * |
- * Throws an [IntegerDivisionByZeroException] if `exp` is negative and `base` |
- * has no inverse modulo `mod`. |
- */ |
-int powmod(int base, int exp, int mod) { |
- if (base == null) throw new ArgumentError(base); |
- if (exp == null) throw new ArgumentError(exp); |
- if (mod == null) throw new ArgumentError(mod); |
- |
- // Right-to-left binary method of modular exponentiation. |
- if (exp < 0) { |
- base = invert(base, mod); |
- exp = -exp; |
- } |
- if (exp == 0) { return 1; } |
- |
- int result = 1; |
- base = base % mod; |
- while (true) { |
- if (exp.isOdd) { |
- result = (result * base) % mod; |
- } |
- exp ~/= 2; |
- if (exp == 0) { |
- return result; |
- } |
- base = (base * base) % mod; |
- } |
-} |