OLD | NEW |
1 // Copyright (c) 2014, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2014, the Dart project authors. Please see the AUTHORS file |
2 // for details. All rights reserved. Use of this source code is governed by a | 2 // for details. All rights reserved. Use of this source code is governed by a |
3 // BSD-style license that can be found in the LICENSE file. | 3 // BSD-style license that can be found in the LICENSE file. |
4 | 4 |
5 // Copyright 2009 The Go Authors. All rights reserved. | 5 // Copyright 2009 The Go Authors. All rights reserved. |
6 // Use of this source code is governed by a BSD-style | 6 // Use of this source code is governed by a BSD-style |
7 // license that can be found in the LICENSE file. | 7 // license that can be found in the LICENSE file. |
8 | 8 |
9 /* | 9 /* |
10 * Copyright (c) 2003-2005 Tom Wu | 10 * Copyright (c) 2003-2005 Tom Wu |
(...skipping 1204 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1215 | 1215 |
1216 int get bitLength { | 1216 int get bitLength { |
1217 if (_used == 0) return 0; | 1217 if (_used == 0) return 0; |
1218 if (_neg) return (~this).bitLength; | 1218 if (_neg) return (~this).bitLength; |
1219 return _DIGIT_BITS*(_used - 1) + _nbits(_digits[_used - 1]); | 1219 return _DIGIT_BITS*(_used - 1) + _nbits(_digits[_used - 1]); |
1220 } | 1220 } |
1221 | 1221 |
1222 // This method must support smi._toBigint()._shrFromInt(int). | 1222 // This method must support smi._toBigint()._shrFromInt(int). |
1223 int _shrFromInt(int other) { | 1223 int _shrFromInt(int other) { |
1224 if (_used == 0) return other; // Shift amount is zero. | 1224 if (_used == 0) return other; // Shift amount is zero. |
1225 if (_neg) throw new RangeError(this); | 1225 if (_neg) throw new RangeError.range(this, 0, null); |
1226 assert(_DIGIT_BITS == 32); // Otherwise this code needs to be revised. | 1226 assert(_DIGIT_BITS == 32); // Otherwise this code needs to be revised. |
1227 var shift; | 1227 var shift; |
1228 if ((_used > 2) || ((_used == 2) && (_digits[1] > 0x10000000))) { | 1228 if ((_used > 2) || ((_used == 2) && (_digits[1] > 0x10000000))) { |
1229 if (other < 0) { | 1229 if (other < 0) { |
1230 return -1; | 1230 return -1; |
1231 } else { | 1231 } else { |
1232 return 0; | 1232 return 0; |
1233 } | 1233 } |
1234 } else { | 1234 } else { |
1235 shift = ((_used == 2) ? (_digits[1] << _DIGIT_BITS) : 0) + _digits[0]; | 1235 shift = ((_used == 2) ? (_digits[1] << _DIGIT_BITS) : 0) + _digits[0]; |
1236 } | 1236 } |
1237 return other._toBigint()._rShift(shift)._toValidInt(); | 1237 return other._toBigint()._rShift(shift)._toValidInt(); |
1238 } | 1238 } |
1239 | 1239 |
1240 // This method must support smi._toBigint()._shlFromInt(int). | 1240 // This method must support smi._toBigint()._shlFromInt(int). |
1241 // An out of memory exception is thrown if the result cannot be allocated. | 1241 // An out of memory exception is thrown if the result cannot be allocated. |
1242 int _shlFromInt(int other) { | 1242 int _shlFromInt(int other) { |
1243 if (_used == 0) return other; // Shift amount is zero. | 1243 if (_used == 0) return other; // Shift amount is zero. |
1244 if (_neg) throw new RangeError(this); | 1244 if (_neg) throw new RangeError.range(this, 0, null); |
1245 assert(_DIGIT_BITS == 32); // Otherwise this code needs to be revised. | 1245 assert(_DIGIT_BITS == 32); // Otherwise this code needs to be revised. |
1246 var shift; | 1246 var shift; |
1247 if (_used > 2 || (_used == 2 && _digits[1] > 0x10000000)) { | 1247 if (_used > 2 || (_used == 2 && _digits[1] > 0x10000000)) { |
1248 if (other == 0) return 0; // Shifted value is zero. | 1248 if (other == 0) return 0; // Shifted value is zero. |
1249 throw new OutOfMemoryError(); | 1249 throw new OutOfMemoryError(); |
1250 } else { | 1250 } else { |
1251 shift = ((_used == 2) ? (_digits[1] << _DIGIT_BITS) : 0) + _digits[0]; | 1251 shift = ((_used == 2) ? (_digits[1] << _DIGIT_BITS) : 0) + _digits[0]; |
1252 } | 1252 } |
1253 return other._toBigint()._lShift(shift)._toValidInt(); | 1253 return other._toBigint()._lShift(shift)._toValidInt(); |
1254 } | 1254 } |
(...skipping 137 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1392 } | 1392 } |
1393 bool _greaterThanFromInteger(int other) { | 1393 bool _greaterThanFromInteger(int other) { |
1394 return other._toBigint()._compare(this) > 0; | 1394 return other._toBigint()._compare(this) > 0; |
1395 } | 1395 } |
1396 bool _equalToInteger(int other) { | 1396 bool _equalToInteger(int other) { |
1397 return other._toBigint()._compare(this) == 0; | 1397 return other._toBigint()._compare(this) == 0; |
1398 } | 1398 } |
1399 | 1399 |
1400 // Returns pow(this, e) % m, with e >= 0, m > 0. | 1400 // Returns pow(this, e) % m, with e >= 0, m > 0. |
1401 int modPow(int e, int m) { | 1401 int modPow(int e, int m) { |
1402 if (e is! int) throw new ArgumentError(e); | 1402 if (e is! int) { |
1403 if (m is! int) throw new ArgumentError(m); | 1403 throw new ArgumentError.value(e, "exponent", "not an integer"); |
1404 if (e < 0) throw new RangeError(e); | 1404 } |
1405 if (m <= 0) throw new RangeError(m); | 1405 if (m is! int) { |
| 1406 throw new ArgumentError.value(m, "modulus", "not an integer"); |
| 1407 } |
| 1408 if (e < 0) throw new RangeError.range(e, 0, null, "exponent"); |
| 1409 if (m <= 0) throw new RangeError.range(m, 1, null, "modulus"); |
1406 if (e == 0) return 1; | 1410 if (e == 0) return 1; |
1407 m = m._toBigint(); | 1411 m = m._toBigint(); |
1408 final m_used = m._used; | 1412 final m_used = m._used; |
1409 final m_used2p4 = 2 * m_used + 4; | 1413 final m_used2p4 = 2 * m_used + 4; |
1410 final e_bitlen = e.bitLength; | 1414 final e_bitlen = e.bitLength; |
1411 if (e_bitlen <= 0) return 1; | 1415 if (e_bitlen <= 0) return 1; |
1412 final bool cannotUseMontgomery = m.isEven || _abs() >= m; | 1416 final bool cannotUseMontgomery = m.isEven || _abs() >= m; |
1413 if (cannotUseMontgomery || e_bitlen < 64) { | 1417 if (cannotUseMontgomery || e_bitlen < 64) { |
1414 _Reduction z = (cannotUseMontgomery || e_bitlen < 8) ? | 1418 _Reduction z = (cannotUseMontgomery || e_bitlen < 8) ? |
1415 new _Classic(m) : new _Montgomery(m); | 1419 new _Classic(m) : new _Montgomery(m); |
(...skipping 120 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1536 --j; | 1540 --j; |
1537 } | 1541 } |
1538 } | 1542 } |
1539 } | 1543 } |
1540 assert(!is1); | 1544 assert(!is1); |
1541 return z._revert(r_digits, r_used)._toValidInt(); | 1545 return z._revert(r_digits, r_used)._toValidInt(); |
1542 } | 1546 } |
1543 | 1547 |
1544 // If inv is false, returns gcd(x, y). | 1548 // If inv is false, returns gcd(x, y). |
1545 // If inv is true and gcd(x, y) = 1, returns d, so that c*x + d*y = 1. | 1549 // If inv is true and gcd(x, y) = 1, returns d, so that c*x + d*y = 1. |
1546 // If inv is true and gcd(x, y) != 1, throws RangeError("Not coprime"). | 1550 // If inv is true and gcd(x, y) != 1, throws Exception("Not coprime"). |
1547 static int _binaryGcd(_Bigint x, _Bigint y, bool inv) { | 1551 static int _binaryGcd(_Bigint x, _Bigint y, bool inv) { |
1548 var x_digits = x._digits; | 1552 var x_digits = x._digits; |
1549 var y_digits = y._digits; | 1553 var y_digits = y._digits; |
1550 var x_used = x._used; | 1554 var x_used = x._used; |
1551 var y_used = y._used; | 1555 var y_used = y._used; |
1552 var m_used = x_used > y_used ? x_used : y_used; | 1556 var m_used = x_used > y_used ? x_used : y_used; |
1553 final m_len = m_used + (m_used & 1); | 1557 final m_len = m_used + (m_used & 1); |
1554 x_digits = _cloneDigits(x_digits, 0, x_used, m_len); | 1558 x_digits = _cloneDigits(x_digits, 0, x_used, m_len); |
1555 y_digits = _cloneDigits(y_digits, 0, y_used, m_len); | 1559 y_digits = _cloneDigits(y_digits, 0, y_used, m_len); |
1556 int s = 0; | 1560 int s = 0; |
1557 if (inv) { | 1561 if (inv) { |
1558 if ((y_used == 1) && (y_digits[0] == 1)) return 1; | 1562 if ((y_used == 1) && (y_digits[0] == 1)) return 1; |
1559 if ((y_used == 0) || (y_digits[0].isEven && x_digits[0].isEven)) { | 1563 if ((y_used == 0) || (y_digits[0].isEven && x_digits[0].isEven)) { |
1560 throw new RangeError("Not coprime"); | 1564 throw new Exception("Not coprime"); |
1561 } | 1565 } |
1562 } else { | 1566 } else { |
1563 if ((x_used == 0) || (y_used == 0)) throw new RangeError(0); | 1567 if (x_used == 0) { |
| 1568 throw new ArgumentError.value(0, "this", "must not be zero"); |
| 1569 } |
| 1570 if (y_used == 0) { |
| 1571 throw new ArgumentError.value(0, "other", "must not be zero"); |
| 1572 } |
1564 if (((x_used == 1) && (x_digits[0] == 1)) || | 1573 if (((x_used == 1) && (x_digits[0] == 1)) || |
1565 ((y_used == 1) && (y_digits[0] == 1))) return 1; | 1574 ((y_used == 1) && (y_digits[0] == 1))) return 1; |
1566 bool xy_cloned = false; | 1575 bool xy_cloned = false; |
1567 while (((x_digits[0] & 1) == 0) && ((y_digits[0] & 1) == 0)) { | 1576 while (((x_digits[0] & 1) == 0) && ((y_digits[0] & 1) == 0)) { |
1568 _rsh(x_digits, x_used, 1, x_digits); | 1577 _rsh(x_digits, x_used, 1, x_digits); |
1569 _rsh(y_digits, y_used, 1, y_digits); | 1578 _rsh(y_digits, y_used, 1, y_digits); |
1570 s++; | 1579 s++; |
1571 } | 1580 } |
1572 if (s >= _DIGIT_BITS) { | 1581 if (s >= _DIGIT_BITS) { |
1573 var sd = s >> _LOG2_DIGIT_BITS; | 1582 var sd = s >> _LOG2_DIGIT_BITS; |
(...skipping 175 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1749 } | 1758 } |
1750 if (!inv) { | 1759 if (!inv) { |
1751 if (s > 0) { | 1760 if (s > 0) { |
1752 m_used = _lShiftDigits(v_digits, m_used, s, v_digits); | 1761 m_used = _lShiftDigits(v_digits, m_used, s, v_digits); |
1753 } | 1762 } |
1754 return new _Bigint(false, m_used, v_digits)._toValidInt(); | 1763 return new _Bigint(false, m_used, v_digits)._toValidInt(); |
1755 } | 1764 } |
1756 // No inverse if v != 1. | 1765 // No inverse if v != 1. |
1757 var i = m_used - 1; | 1766 var i = m_used - 1; |
1758 while ((i > 0) && (v_digits[i] == 0)) --i; | 1767 while ((i > 0) && (v_digits[i] == 0)) --i; |
1759 if ((i != 0) || (v_digits[0] != 1)) throw new RangeError("Not coprime"); | 1768 if ((i != 0) || (v_digits[0] != 1)) { |
| 1769 throw new Exception("Not coprime"); |
| 1770 } |
1760 | 1771 |
1761 if (d_neg) { | 1772 if (d_neg) { |
1762 if ((d_digits[m_used] != 0) || | 1773 if ((d_digits[m_used] != 0) || |
1763 (_compareDigits(d_digits, m_used, x_digits, m_used) > 0)) { | 1774 (_compareDigits(d_digits, m_used, x_digits, m_used) > 0)) { |
1764 _absSub(d_digits, abcd_used, x_digits, m_used, d_digits); | 1775 _absSub(d_digits, abcd_used, x_digits, m_used, d_digits); |
1765 if ((d_digits[m_used] != 0) || | 1776 if ((d_digits[m_used] != 0) || |
1766 (_compareDigits(d_digits, m_used, x_digits, m_used) > 0)) { | 1777 (_compareDigits(d_digits, m_used, x_digits, m_used) > 0)) { |
1767 _absSub(d_digits, abcd_used, x_digits, m_used, d_digits); | 1778 _absSub(d_digits, abcd_used, x_digits, m_used, d_digits); |
1768 } else { | 1779 } else { |
1769 _absSub(x_digits, m_used, d_digits, m_used, d_digits); | 1780 _absSub(x_digits, m_used, d_digits, m_used, d_digits); |
1770 d_neg = false; | 1781 d_neg = false; |
1771 } | 1782 } |
1772 } else { | 1783 } else { |
1773 _absSub(x_digits, m_used, d_digits, m_used, d_digits); | 1784 _absSub(x_digits, m_used, d_digits, m_used, d_digits); |
1774 d_neg = false; | 1785 d_neg = false; |
1775 } | 1786 } |
1776 } else if ((d_digits[m_used] != 0) || | 1787 } else if ((d_digits[m_used] != 0) || |
1777 (_compareDigits(d_digits, m_used, x_digits, m_used) > 0)) { | 1788 (_compareDigits(d_digits, m_used, x_digits, m_used) > 0)) { |
1778 _absSub(d_digits, abcd_used, x_digits, m_used, d_digits); | 1789 _absSub(d_digits, abcd_used, x_digits, m_used, d_digits); |
1779 if ((d_digits[m_used] != 0) || | 1790 if ((d_digits[m_used] != 0) || |
1780 (_compareDigits(d_digits, m_used, x_digits, m_used) > 0)) { | 1791 (_compareDigits(d_digits, m_used, x_digits, m_used) > 0)) { |
1781 _absSub(d_digits, abcd_used, x_digits, m_used, d_digits); | 1792 _absSub(d_digits, abcd_used, x_digits, m_used, d_digits); |
1782 } | 1793 } |
1783 } | 1794 } |
1784 return new _Bigint(false, m_used, d_digits)._toValidInt(); | 1795 return new _Bigint(false, m_used, d_digits)._toValidInt(); |
1785 } | 1796 } |
1786 | 1797 |
1787 // Returns 1/this % m, with m > 0. | 1798 // Returns 1/this % m, with m > 0. |
1788 int modInverse(int m) { | 1799 int modInverse(int m) { |
1789 if (m is! int) throw new ArgumentError(m); | 1800 if (m is! int) { |
1790 if (m <= 0) throw new RangeError(m); | 1801 throw new ArgumentError.value(m, "modulus", "not an integer"); |
| 1802 } |
| 1803 if (m <= 0) throw new RangeError.range(m, 1, null, "modulus"); |
1791 if (m == 1) return 0; | 1804 if (m == 1) return 0; |
1792 m = m._toBigint(); | 1805 m = m._toBigint(); |
1793 var t = this; | 1806 var t = this; |
1794 if (t._neg || (t._absCompare(m) >= 0)) { | 1807 if (t._neg || (t._absCompare(m) >= 0)) { |
1795 t %= m; | 1808 t %= m; |
1796 t = t._toBigint(); | 1809 t = t._toBigint(); |
1797 } | 1810 } |
1798 return _binaryGcd(m, t, true); | 1811 return _binaryGcd(m, t, true); |
1799 } | 1812 } |
1800 | 1813 |
1801 // Returns gcd of abs(this) and abs(other), with this != 0 and other !=0. | 1814 // Returns gcd of abs(this) and abs(other), with this != 0 and other !=0. |
1802 int gcd(int other) { | 1815 int gcd(int other) { |
1803 if (other is! int) throw new ArgumentError(other); | 1816 if (other is! int) { |
| 1817 throw new ArgumentError.value(other, "other", "not an integer"); |
| 1818 } |
1804 return _binaryGcd(this, other._toBigint(), false); | 1819 return _binaryGcd(this, other._toBigint(), false); |
1805 } | 1820 } |
1806 } | 1821 } |
1807 | 1822 |
1808 // Interface for modular reduction. | 1823 // Interface for modular reduction. |
1809 class _Reduction { | 1824 class _Reduction { |
1810 // Return the number of digits used by r_digits. | 1825 // Return the number of digits used by r_digits. |
1811 int _convert(_Bigint x, Uint32List r_digits); | 1826 int _convert(_Bigint x, Uint32List r_digits); |
1812 int _mul(Uint32List x_digits, int x_used, | 1827 int _mul(Uint32List x_digits, int x_used, |
1813 Uint32List y_digits, int y_used, Uint32List r_digits); | 1828 Uint32List y_digits, int y_used, Uint32List r_digits); |
(...skipping 258 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
2072 | 2087 |
2073 int _mul(Uint32List x_digits, int x_used, | 2088 int _mul(Uint32List x_digits, int x_used, |
2074 Uint32List y_digits, int y_used, | 2089 Uint32List y_digits, int y_used, |
2075 Uint32List r_digits) { | 2090 Uint32List r_digits) { |
2076 var r_used = _Bigint._mulDigits(x_digits, x_used, | 2091 var r_used = _Bigint._mulDigits(x_digits, x_used, |
2077 y_digits, y_used, | 2092 y_digits, y_used, |
2078 r_digits); | 2093 r_digits); |
2079 return _reduce(r_digits, r_used); | 2094 return _reduce(r_digits, r_used); |
2080 } | 2095 } |
2081 } | 2096 } |
OLD | NEW |