From b6dbc2a1aea8eeab2d41a4d44f9d7522ecc59a50 Mon Sep 17 00:00:00 2001 From: Ian Coleman Date: Wed, 16 Nov 2016 10:54:34 +1100 Subject: BigInteger library moved to own file --- src/index.html | 1 + src/js/biginteger.js | 1620 +++++++++++++++++++++++++++++++++++++++++++++++++ src/js/entropy.js | 1627 -------------------------------------------------- 3 files changed, 1621 insertions(+), 1627 deletions(-) create mode 100644 src/js/biginteger.js diff --git a/src/index.html b/src/index.html index e772546..b938226 100644 --- a/src/index.html +++ b/src/index.html @@ -571,6 +571,7 @@ + diff --git a/src/js/biginteger.js b/src/js/biginteger.js new file mode 100644 index 0000000..3f56d18 --- /dev/null +++ b/src/js/biginteger.js @@ -0,0 +1,1620 @@ +/* + JavaScript BigInteger library version 0.9.1 + http://silentmatt.com/biginteger/ + + Copyright (c) 2009 Matthew Crumley + Copyright (c) 2010,2011 by John Tobey + Licensed under the MIT license. + + Support for arbitrary internal representation base was added by + Vitaly Magerya. +*/ + +/* + File: biginteger.js + + Exports: + + +*/ +(function(exports) { +"use strict"; +/* + Class: BigInteger + An arbitrarily-large integer. + + objects should be considered immutable. None of the "built-in" + methods modify *this* or their arguments. All properties should be + considered private. + + All the methods of instances can be called "statically". The + static versions are convenient if you don't already have a + object. + + As an example, these calls are equivalent. + + > BigInteger(4).multiply(5); // returns BigInteger(20); + > BigInteger.multiply(4, 5); // returns BigInteger(20); + + > var a = 42; + > var a = BigInteger.toJSValue("0b101010"); // Not completely useless... +*/ + +var CONSTRUCT = {}; // Unique token to call "private" version of constructor + +/* + Constructor: BigInteger() + Convert a value to a . + + Although is the constructor for objects, it is + best not to call it as a constructor. If *n* is a object, it is + simply returned as-is. Otherwise, is equivalent to + without a radix argument. + + > var n0 = BigInteger(); // Same as + > var n1 = BigInteger("123"); // Create a new with value 123 + > var n2 = BigInteger(123); // Create a new with value 123 + > var n3 = BigInteger(n2); // Return n2, unchanged + + The constructor form only takes an array and a sign. *n* must be an + array of numbers in little-endian order, where each digit is between 0 + and BigInteger.base. The second parameter sets the sign: -1 for + negative, +1 for positive, or 0 for zero. The array is *not copied and + may be modified*. If the array contains only zeros, the sign parameter + is ignored and is forced to zero. + + > new BigInteger([5], -1): create a new BigInteger with value -5 + + Parameters: + + n - Value to convert to a . + + Returns: + + A value. + + See Also: + + , +*/ +function BigInteger(n, s, token) { + if (token !== CONSTRUCT) { + if (n instanceof BigInteger) { + return n; + } + else if (typeof n === "undefined") { + return ZERO; + } + return BigInteger.parse(n); + } + + n = n || []; // Provide the nullary constructor for subclasses. + while (n.length && !n[n.length - 1]) { + --n.length; + } + this._d = n; + this._s = n.length ? (s || 1) : 0; +} + +BigInteger._construct = function(n, s) { + return new BigInteger(n, s, CONSTRUCT); +}; + +// Base-10 speedup hacks in parse, toString, exp10 and log functions +// require base to be a power of 10. 10^7 is the largest such power +// that won't cause a precision loss when digits are multiplied. +var BigInteger_base = 10000000; +var BigInteger_base_log10 = 7; + +BigInteger.base = BigInteger_base; +BigInteger.base_log10 = BigInteger_base_log10; + +var ZERO = new BigInteger([], 0, CONSTRUCT); +// Constant: ZERO +// 0. +BigInteger.ZERO = ZERO; + +var ONE = new BigInteger([1], 1, CONSTRUCT); +// Constant: ONE +// 1. +BigInteger.ONE = ONE; + +var M_ONE = new BigInteger(ONE._d, -1, CONSTRUCT); +// Constant: M_ONE +// -1. +BigInteger.M_ONE = M_ONE; + +// Constant: _0 +// Shortcut for . +BigInteger._0 = ZERO; + +// Constant: _1 +// Shortcut for . +BigInteger._1 = ONE; + +/* + Constant: small + Array of from 0 to 36. + + These are used internally for parsing, but useful when you need a "small" + . + + See Also: + + , , <_0>, <_1> +*/ +BigInteger.small = [ + ZERO, + ONE, + /* Assuming BigInteger_base > 36 */ + new BigInteger( [2], 1, CONSTRUCT), + new BigInteger( [3], 1, CONSTRUCT), + new BigInteger( [4], 1, CONSTRUCT), + new BigInteger( [5], 1, CONSTRUCT), + new BigInteger( [6], 1, CONSTRUCT), + new BigInteger( [7], 1, CONSTRUCT), + new BigInteger( [8], 1, CONSTRUCT), + new BigInteger( [9], 1, CONSTRUCT), + new BigInteger([10], 1, CONSTRUCT), + new BigInteger([11], 1, CONSTRUCT), + new BigInteger([12], 1, CONSTRUCT), + new BigInteger([13], 1, CONSTRUCT), + new BigInteger([14], 1, CONSTRUCT), + new BigInteger([15], 1, CONSTRUCT), + new BigInteger([16], 1, CONSTRUCT), + new BigInteger([17], 1, CONSTRUCT), + new BigInteger([18], 1, CONSTRUCT), + new BigInteger([19], 1, CONSTRUCT), + new BigInteger([20], 1, CONSTRUCT), + new BigInteger([21], 1, CONSTRUCT), + new BigInteger([22], 1, CONSTRUCT), + new BigInteger([23], 1, CONSTRUCT), + new BigInteger([24], 1, CONSTRUCT), + new BigInteger([25], 1, CONSTRUCT), + new BigInteger([26], 1, CONSTRUCT), + new BigInteger([27], 1, CONSTRUCT), + new BigInteger([28], 1, CONSTRUCT), + new BigInteger([29], 1, CONSTRUCT), + new BigInteger([30], 1, CONSTRUCT), + new BigInteger([31], 1, CONSTRUCT), + new BigInteger([32], 1, CONSTRUCT), + new BigInteger([33], 1, CONSTRUCT), + new BigInteger([34], 1, CONSTRUCT), + new BigInteger([35], 1, CONSTRUCT), + new BigInteger([36], 1, CONSTRUCT) +]; + +// Used for parsing/radix conversion +BigInteger.digits = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ".split(""); + +/* + Method: toString + Convert a to a string. + + When *base* is greater than 10, letters are upper case. + + Parameters: + + base - Optional base to represent the number in (default is base 10). + Must be between 2 and 36 inclusive, or an Error will be thrown. + + Returns: + + The string representation of the . +*/ +BigInteger.prototype.toString = function(base) { + base = +base || 10; + if (base < 2 || base > 36) { + throw new Error("illegal radix " + base + "."); + } + if (this._s === 0) { + return "0"; + } + if (base === 10) { + var str = this._s < 0 ? "-" : ""; + str += this._d[this._d.length - 1].toString(); + for (var i = this._d.length - 2; i >= 0; i--) { + var group = this._d[i].toString(); + while (group.length < BigInteger_base_log10) group = '0' + group; + str += group; + } + return str; + } + else { + var numerals = BigInteger.digits; + base = BigInteger.small[base]; + var sign = this._s; + + var n = this.abs(); + var digits = []; + var digit; + + while (n._s !== 0) { + var divmod = n.divRem(base); + n = divmod[0]; + digit = divmod[1]; + // TODO: This could be changed to unshift instead of reversing at the end. + // Benchmark both to compare speeds. + digits.push(numerals[digit.valueOf()]); + } + return (sign < 0 ? "-" : "") + digits.reverse().join(""); + } +}; + +// Verify strings for parsing +BigInteger.radixRegex = [ + /^$/, + /^$/, + /^[01]*$/, + /^[012]*$/, + /^[0-3]*$/, + /^[0-4]*$/, + /^[0-5]*$/, + /^[0-6]*$/, + /^[0-7]*$/, + /^[0-8]*$/, + /^[0-9]*$/, + /^[0-9aA]*$/, + /^[0-9abAB]*$/, + /^[0-9abcABC]*$/, + /^[0-9a-dA-D]*$/, + /^[0-9a-eA-E]*$/, + /^[0-9a-fA-F]*$/, + /^[0-9a-gA-G]*$/, + /^[0-9a-hA-H]*$/, + /^[0-9a-iA-I]*$/, + /^[0-9a-jA-J]*$/, + /^[0-9a-kA-K]*$/, + /^[0-9a-lA-L]*$/, + /^[0-9a-mA-M]*$/, + /^[0-9a-nA-N]*$/, + /^[0-9a-oA-O]*$/, + /^[0-9a-pA-P]*$/, + /^[0-9a-qA-Q]*$/, + /^[0-9a-rA-R]*$/, + /^[0-9a-sA-S]*$/, + /^[0-9a-tA-T]*$/, + /^[0-9a-uA-U]*$/, + /^[0-9a-vA-V]*$/, + /^[0-9a-wA-W]*$/, + /^[0-9a-xA-X]*$/, + /^[0-9a-yA-Y]*$/, + /^[0-9a-zA-Z]*$/ +]; + +/* + Function: parse + Parse a string into a . + + *base* is optional but, if provided, must be from 2 to 36 inclusive. If + *base* is not provided, it will be guessed based on the leading characters + of *s* as follows: + + - "0x" or "0X": *base* = 16 + - "0c" or "0C": *base* = 8 + - "0b" or "0B": *base* = 2 + - else: *base* = 10 + + If no base is provided, or *base* is 10, the number can be in exponential + form. For example, these are all valid: + + > BigInteger.parse("1e9"); // Same as "1000000000" + > BigInteger.parse("1.234*10^3"); // Same as 1234 + > BigInteger.parse("56789 * 10 ** -2"); // Same as 567 + + If any characters fall outside the range defined by the radix, an exception + will be thrown. + + Parameters: + + s - The string to parse. + base - Optional radix (default is to guess based on *s*). + + Returns: + + a instance. +*/ +BigInteger.parse = function(s, base) { + // Expands a number in exponential form to decimal form. + // expandExponential("-13.441*10^5") === "1344100"; + // expandExponential("1.12300e-1") === "0.112300"; + // expandExponential(1000000000000000000000000000000) === "1000000000000000000000000000000"; + function expandExponential(str) { + str = str.replace(/\s*[*xX]\s*10\s*(\^|\*\*)\s*/, "e"); + + return str.replace(/^([+\-])?(\d+)\.?(\d*)[eE]([+\-]?\d+)$/, function(x, s, n, f, c) { + c = +c; + var l = c < 0; + var i = n.length + c; + x = (l ? n : f).length; + c = ((c = Math.abs(c)) >= x ? c - x + l : 0); + var z = (new Array(c + 1)).join("0"); + var r = n + f; + return (s || "") + (l ? r = z + r : r += z).substr(0, i += l ? z.length : 0) + (i < r.length ? "." + r.substr(i) : ""); + }); + } + + s = s.toString(); + if (typeof base === "undefined" || +base === 10) { + s = expandExponential(s); + } + + var prefixRE; + if (typeof base === "undefined") { + prefixRE = '0[xcb]'; + } + else if (base == 16) { + prefixRE = '0x'; + } + else if (base == 8) { + prefixRE = '0c'; + } + else if (base == 2) { + prefixRE = '0b'; + } + else { + prefixRE = ''; + } + var parts = new RegExp('^([+\\-]?)(' + prefixRE + ')?([0-9a-z]*)(?:\\.\\d*)?$', 'i').exec(s); + if (parts) { + var sign = parts[1] || "+"; + var baseSection = parts[2] || ""; + var digits = parts[3] || ""; + + if (typeof base === "undefined") { + // Guess base + if (baseSection === "0x" || baseSection === "0X") { // Hex + base = 16; + } + else if (baseSection === "0c" || baseSection === "0C") { // Octal + base = 8; + } + else if (baseSection === "0b" || baseSection === "0B") { // Binary + base = 2; + } + else { + base = 10; + } + } + else if (base < 2 || base > 36) { + throw new Error("Illegal radix " + base + "."); + } + + base = +base; + + // Check for digits outside the range + if (!(BigInteger.radixRegex[base].test(digits))) { + throw new Error("Bad digit for radix " + base); + } + + // Strip leading zeros, and convert to array + digits = digits.replace(/^0+/, "").split(""); + if (digits.length === 0) { + return ZERO; + } + + // Get the sign (we know it's not zero) + sign = (sign === "-") ? -1 : 1; + + // Optimize 10 + if (base == 10) { + var d = []; + while (digits.length >= BigInteger_base_log10) { + d.push(parseInt(digits.splice(digits.length-BigInteger.base_log10, BigInteger.base_log10).join(''), 10)); + } + d.push(parseInt(digits.join(''), 10)); + return new BigInteger(d, sign, CONSTRUCT); + } + + // Do the conversion + var d = ZERO; + base = BigInteger.small[base]; + var small = BigInteger.small; + for (var i = 0; i < digits.length; i++) { + d = d.multiply(base).add(small[parseInt(digits[i], 36)]); + } + return new BigInteger(d._d, sign, CONSTRUCT); + } + else { + throw new Error("Invalid BigInteger format: " + s); + } +}; + +/* + Function: add + Add two . + + Parameters: + + n - The number to add to *this*. Will be converted to a . + + Returns: + + The numbers added together. + + See Also: + + , , , +*/ +BigInteger.prototype.add = function(n) { + if (this._s === 0) { + return BigInteger(n); + } + + n = BigInteger(n); + if (n._s === 0) { + return this; + } + if (this._s !== n._s) { + n = n.negate(); + return this.subtract(n); + } + + var a = this._d; + var b = n._d; + var al = a.length; + var bl = b.length; + var sum = new Array(Math.max(al, bl) + 1); + var size = Math.min(al, bl); + var carry = 0; + var digit; + + for (var i = 0; i < size; i++) { + digit = a[i] + b[i] + carry; + sum[i] = digit % BigInteger_base; + carry = (digit / BigInteger_base) | 0; + } + if (bl > al) { + a = b; + al = bl; + } + for (i = size; carry && i < al; i++) { + digit = a[i] + carry; + sum[i] = digit % BigInteger_base; + carry = (digit / BigInteger_base) | 0; + } + if (carry) { + sum[i] = carry; + } + + for ( ; i < al; i++) { + sum[i] = a[i]; + } + + return new BigInteger(sum, this._s, CONSTRUCT); +}; + +/* + Function: negate + Get the additive inverse of a . + + Returns: + + A with the same magnatude, but with the opposite sign. + + See Also: + + +*/ +BigInteger.prototype.negate = function() { + return new BigInteger(this._d, (-this._s) | 0, CONSTRUCT); +}; + +/* + Function: abs + Get the absolute value of a . + + Returns: + + A with the same magnatude, but always positive (or zero). + + See Also: + + +*/ +BigInteger.prototype.abs = function() { + return (this._s < 0) ? this.negate() : this; +}; + +/* + Function: subtract + Subtract two . + + Parameters: + + n - The number to subtract from *this*. Will be converted to a . + + Returns: + + The *n* subtracted from *this*. + + See Also: + + , , , +*/ +BigInteger.prototype.subtract = function(n) { + if (this._s === 0) { + return BigInteger(n).negate(); + } + + n = BigInteger(n); + if (n._s === 0) { + return this; + } + if (this._s !== n._s) { + n = n.negate(); + return this.add(n); + } + + var m = this; + // negative - negative => -|a| - -|b| => -|a| + |b| => |b| - |a| + if (this._s < 0) { + m = new BigInteger(n._d, 1, CONSTRUCT); + n = new BigInteger(this._d, 1, CONSTRUCT); + } + + // Both are positive => a - b + var sign = m.compareAbs(n); + if (sign === 0) { + return ZERO; + } + else if (sign < 0) { + // swap m and n + var t = n; + n = m; + m = t; + } + + // a > b + var a = m._d; + var b = n._d; + var al = a.length; + var bl = b.length; + var diff = new Array(al); // al >= bl since a > b + var borrow = 0; + var i; + var digit; + + for (i = 0; i < bl; i++) { + digit = a[i] - borrow - b[i]; + if (digit < 0) { + digit += BigInteger_base; + borrow = 1; + } + else { + borrow = 0; + } + diff[i] = digit; + } + for (i = bl; i < al; i++) { + digit = a[i] - borrow; + if (digit < 0) { + digit += BigInteger_base; + } + else { + diff[i++] = digit; + break; + } + diff[i] = digit; + } + for ( ; i < al; i++) { + diff[i] = a[i]; + } + + return new BigInteger(diff, sign, CONSTRUCT); +}; + +(function() { + function addOne(n, sign) { + var a = n._d; + var sum = a.slice(); + var carry = true; + var i = 0; + + while (true) { + var digit = (a[i] || 0) + 1; + sum[i] = digit % BigInteger_base; + if (digit <= BigInteger_base - 1) { + break; + } + ++i; + } + + return new BigInteger(sum, sign, CONSTRUCT); + } + + function subtractOne(n, sign) { + var a = n._d; + var sum = a.slice(); + var borrow = true; + var i = 0; + + while (true) { + var digit = (a[i] || 0) - 1; + if (digit < 0) { + sum[i] = digit + BigInteger_base; + } + else { + sum[i] = digit; + break; + } + ++i; + } + + return new BigInteger(sum, sign, CONSTRUCT); + } + + /* + Function: next + Get the next (add one). + + Returns: + + *this* + 1. + + See Also: + + , + */ + BigInteger.prototype.next = function() { + switch (this._s) { + case 0: + return ONE; + case -1: + return subtractOne(this, -1); + // case 1: + default: + return addOne(this, 1); + } + }; + + /* + Function: prev + Get the previous (subtract one). + + Returns: + + *this* - 1. + + See Also: + + , + */ + BigInteger.prototype.prev = function() { + switch (this._s) { + case 0: + return M_ONE; + case -1: + return addOne(this, -1); + // case 1: + default: + return subtractOne(this, 1); + } + }; +})(); + +/* + Function: compareAbs + Compare the absolute value of two . + + Calling is faster than calling twice, then . + + Parameters: + + n - The number to compare to *this*. Will be converted to a . + + Returns: + + -1, 0, or +1 if *|this|* is less than, equal to, or greater than *|n|*. + + See Also: + + , +*/ +BigInteger.prototype.compareAbs = function(n) { + if (this === n) { + return 0; + } + + if (!(n instanceof BigInteger)) { + if (!isFinite(n)) { + return(isNaN(n) ? n : -1); + } + n = BigInteger(n); + } + + if (this._s === 0) { + return (n._s !== 0) ? -1 : 0; + } + if (n._s === 0) { + return 1; + } + + var l = this._d.length; + var nl = n._d.length; + if (l < nl) { + return -1; + } + else if (l > nl) { + return 1; + } + + var a = this._d; + var b = n._d; + for (var i = l-1; i >= 0; i--) { + if (a[i] !== b[i]) { + return a[i] < b[i] ? -1 : 1; + } + } + + return 0; +}; + +/* + Function: compare + Compare two . + + Parameters: + + n - The number to compare to *this*. Will be converted to a . + + Returns: + + -1, 0, or +1 if *this* is less than, equal to, or greater than *n*. + + See Also: + + , , , +*/ +BigInteger.prototype.compare = function(n) { + if (this === n) { + return 0; + } + + n = BigInteger(n); + + if (this._s === 0) { + return -n._s; + } + + if (this._s === n._s) { // both positive or both negative + var cmp = this.compareAbs(n); + return cmp * this._s; + } + else { + return this._s; + } +}; + +/* + Function: isUnit + Return true iff *this* is either 1 or -1. + + Returns: + + true if *this* compares equal to or . + + See Also: + + , , , , , + , +*/ +BigInteger.prototype.isUnit = function() { + return this === ONE || + this === M_ONE || + (this._d.length === 1 && this._d[0] === 1); +}; + +/* + Function: multiply + Multiply two . + + Parameters: + + n - The number to multiply *this* by. Will be converted to a + . + + Returns: + + The numbers multiplied together. + + See Also: + + , , , +*/ +BigInteger.prototype.multiply = function(n) { + // TODO: Consider adding Karatsuba multiplication for large numbers + if (this._s === 0) { + return ZERO; + } + + n = BigInteger(n); + if (n._s === 0) { + return ZERO; + } + if (this.isUnit()) { + if (this._s < 0) { + return n.negate(); + } + return n; + } + if (n.isUnit()) { + if (n._s < 0) { + return this.negate(); + } + return this; + } + if (this === n) { + return this.square(); + } + + var r = (this._d.length >= n._d.length); + var a = (r ? this : n)._d; // a will be longer than b + var b = (r ? n : this)._d; + var al = a.length; + var bl = b.length; + + var pl = al + bl; + var partial = new Array(pl); + var i; + for (i = 0; i < pl; i++) { + partial[i] = 0; + } + + for (i = 0; i < bl; i++) { + var carry = 0; + var bi = b[i]; + var jlimit = al + i; + var digit; + for (var j = i; j < jlimit; j++) { + digit = partial[j] + bi * a[j - i] + carry; + carry = (digit / BigInteger_base) | 0; + partial[j] = (digit % BigInteger_base) | 0; + } + if (carry) { + digit = partial[j] + carry; + carry = (digit / BigInteger_base) | 0; + partial[j] = digit % BigInteger_base; + } + } + return new BigInteger(partial, this._s * n._s, CONSTRUCT); +}; + +// Multiply a BigInteger by a single-digit native number +// Assumes that this and n are >= 0 +// This is not really intended to be used outside the library itself +BigInteger.prototype.multiplySingleDigit = function(n) { + if (n === 0 || this._s === 0) { + return ZERO; + } + if (n === 1) { + return this; + } + + var digit; + if (this._d.length === 1) { + digit = this._d[0] * n; + if (digit >= BigInteger_base) { + return new BigInteger([(digit % BigInteger_base)|0, + (digit / BigInteger_base)|0], 1, CONSTRUCT); + } + return new BigInteger([digit], 1, CONSTRUCT); + } + + if (n === 2) { + return this.add(this); + } + if (this.isUnit()) { + return new BigInteger([n], 1, CONSTRUCT); + } + + var a = this._d; + var al = a.length; + + var pl = al + 1; + var partial = new Array(pl); + for (var i = 0; i < pl; i++) { + partial[i] = 0; + } + + var carry = 0; + for (var j = 0; j < al; j++) { + digit = n * a[j] + carry; + carry = (digit / BigInteger_base) | 0; + partial[j] = (digit % BigInteger_base) | 0; + } + if (carry) { + partial[j] = carry; + } + + return new BigInteger(partial, 1, CONSTRUCT); +}; + +/* + Function: square + Multiply a by itself. + + This is slightly faster than regular multiplication, since it removes the + duplicated multiplcations. + + Returns: + + > this.multiply(this) + + See Also: + +*/ +BigInteger.prototype.square = function() { + // Normally, squaring a 10-digit number would take 100 multiplications. + // Of these 10 are unique diagonals, of the remaining 90 (100-10), 45 are repeated. + // This procedure saves (N*(N-1))/2 multiplications, (e.g., 45 of 100 multiplies). + // Based on code by Gary Darby, Intellitech Systems Inc., www.DelphiForFun.org + + if (this._s === 0) { + return ZERO; + } + if (this.isUnit()) { + return ONE; + } + + var digits = this._d; + var length = digits.length; + var imult1 = new Array(length + length + 1); + var product, carry, k; + var i; + + // Calculate diagonal + for (i = 0; i < length; i++) { + k = i * 2; + product = digits[i] * digits[i]; + carry = (product / BigInteger_base) | 0; + imult1[k] = product % BigInteger_base; + imult1[k + 1] = carry; + } + + // Calculate repeating part + for (i = 0; i < length; i++) { + carry = 0; + k = i * 2 + 1; + for (var j = i + 1; j < length; j++, k++) { + product = digits[j] * digits[i] * 2 + imult1[k] + carry; + carry = (product / BigInteger_base) | 0; + imult1[k] = product % BigInteger_base; + } + k = length + i; + var digit = carry + imult1[k]; + carry = (digit / BigInteger_base) | 0; + imult1[k] = digit % BigInteger_base; + imult1[k + 1] += carry; + } + + return new BigInteger(imult1, 1, CONSTRUCT); +}; + +/* + Function: quotient + Divide two and truncate towards zero. + + throws an exception if *n* is zero. + + Parameters: + + n - The number to divide *this* by. Will be converted to a . + + Returns: + + The *this* / *n*, truncated to an integer. + + See Also: + + , , , , +*/ +BigInteger.prototype.quotient = function(n) { + return this.divRem(n)[0]; +}; + +/* + Function: divide + Deprecated synonym for . +*/ +BigInteger.prototype.divide = BigInteger.prototype.quotient; + +/* + Function: remainder + Calculate the remainder of two . + + throws an exception if *n* is zero. + + Parameters: + + n - The remainder after *this* is divided *this* by *n*. Will be + converted to a . + + Returns: + + *this* % *n*. + + See Also: + + , +*/ +BigInteger.prototype.remainder = function(n) { + return this.divRem(n)[1]; +}; + +/* + Function: divRem + Calculate the integer quotient and remainder of two . + + throws an exception if *n* is zero. + + Parameters: + + n - The number to divide *this* by. Will be converted to a . + + Returns: + + A two-element array containing the quotient and the remainder. + + > a.divRem(b) + + is exactly equivalent to + + > [a.quotient(b), a.remainder(b)] + + except it is faster, because they are calculated at the same time. + + See Also: + + , +*/ +BigInteger.prototype.divRem = function(n) { + n = BigInteger(n); + if (n._s === 0) { + throw new Error("Divide by zero"); + } + if (this._s === 0) { + return [ZERO, ZERO]; + } + if (n._d.length === 1) { + return this.divRemSmall(n._s * n._d[0]); + } + + // Test for easy cases -- |n1| <= |n2| + switch (this.compareAbs(n)) { + case 0: // n1 == n2 + return [this._s === n._s ? ONE : M_ONE, ZERO]; + case -1: // |n1| < |n2| + return [ZERO, this]; + } + + var sign = this._s * n._s; + var a = n.abs(); + var b_digits = this._d; + var b_index = b_digits.length; + var digits = n._d.length; + var quot = []; + var guess; + + var part = new BigInteger([], 0, CONSTRUCT); + + while (b_index) { + part._d.unshift(b_digits[--b_index]); + part = new BigInteger(part._d, 1, CONSTRUCT); + + if (part.compareAbs(n) < 0) { + quot.push(0); + continue; + } + if (part._s === 0) { + guess = 0; + } + else { + var xlen = part._d.length, ylen = a._d.length; + var highx = part._d[xlen-1]*BigInteger_base + part._d[xlen-2]; + var highy = a._d[ylen-1]*BigInteger_base + a._d[ylen-2]; + if (part._d.length > a._d.length) { + // The length of part._d can either match a._d length, + // or exceed it by one. + highx = (highx+1)*BigInteger_base; + } + guess = Math.ceil(highx/highy); + } + do { + var check = a.multiplySingleDigit(guess); + if (check.compareAbs(part) <= 0) { + break; + } + guess--; + } while (guess); + + quot.push(guess); + if (!guess) { + continue; + } + var diff = part.subtract(check); + part._d = diff._d.slice(); + } + + return [new BigInteger(quot.reverse(), sign, CONSTRUCT), + new BigInteger(part._d, this._s, CONSTRUCT)]; +}; + +// Throws an exception if n is outside of (-BigInteger.base, -1] or +// [1, BigInteger.base). It's not necessary to call this, since the +// other division functions will call it if they are able to. +BigInteger.prototype.divRemSmall = function(n) { + var r; + n = +n; + if (n === 0) { + throw new Error("Divide by zero"); + } + + var n_s = n < 0 ? -1 : 1; + var sign = this._s * n_s; + n = Math.abs(n); + + if (n < 1 || n >= BigInteger_base) { + throw new Error("Argument out of range"); + } + + if (this._s === 0) { + return [ZERO, ZERO]; + } + + if (n === 1 || n === -1) { + return [(sign === 1) ? this.abs() : new BigInteger(this._d, sign, CONSTRUCT), ZERO]; + } + + // 2 <= n < BigInteger_base + + // divide a single digit by a single digit + if (this._d.length === 1) { + var q = new BigInteger([(this._d[0] / n) | 0], 1, CONSTRUCT); + r = new BigInteger([(this._d[0] % n) | 0], 1, CONSTRUCT); + if (sign < 0) { + q = q.negate(); + } + if (this._s < 0) { + r = r.negate(); + } + return [q, r]; + } + + var digits = this._d.slice(); + var quot = new Array(digits.length); + var part = 0; + var diff = 0; + var i = 0; + var guess; + + while (digits.length) { + part = part * BigInteger_base + digits[digits.length - 1]; + if (part < n) { + quot[i++] = 0; + digits.pop(); + diff = BigInteger_base * diff + part; + continue; + } + if (part === 0) { + guess = 0; + } + else { + guess = (part / n) | 0; + } + + var check = n * guess; + diff = part - check; + quot[i++] = guess; + if (!guess) { + digits.pop(); + continue; + } + + digits.pop(); + part = diff; + } + + r = new BigInteger([diff], 1, CONSTRUCT); + if (this._s < 0) { + r = r.negate(); + } + return [new BigInteger(quot.reverse(), sign, CONSTRUCT), r]; +}; + +/* + Function: isEven + Return true iff *this* is divisible by two. + + Note that is even. + + Returns: + + true if *this* is even, false otherwise. + + See Also: + + +*/ +BigInteger.prototype.isEven = function() { + var digits = this._d; + return this._s === 0 || digits.length === 0 || (digits[0] % 2) === 0; +}; + +/* + Function: isOdd + Return true iff *this* is not divisible by two. + + Returns: + + true if *this* is odd, false otherwise. + + See Also: + + +*/ +BigInteger.prototype.isOdd = function() { + return !this.isEven(); +}; + +/* + Function: sign + Get the sign of a . + + Returns: + + * -1 if *this* < 0 + * 0 if *this* == 0 + * +1 if *this* > 0 + + See Also: + + , , , , +*/ +BigInteger.prototype.sign = function() { + return this._s; +}; + +/* + Function: isPositive + Return true iff *this* > 0. + + Returns: + + true if *this*.compare() == 1. + + See Also: + + , , , , , +*/ +BigInteger.prototype.isPositive = function() { + return this._s > 0; +}; + +/* + Function: isNegative + Return true iff *this* < 0. + + Returns: + + true if *this*.compare() == -1. + + See Also: + + , , , , , +*/ +BigInteger.prototype.isNegative = function() { + return this._s < 0; +}; + +/* + Function: isZero + Return true iff *this* == 0. + + Returns: + + true if *this*.compare() == 0. + + See Also: + + , , , , +*/ +BigInteger.prototype.isZero = function() { + return this._s === 0; +}; + +/* + Function: exp10 + Multiply a by a power of 10. + + This is equivalent to, but faster than + + > if (n >= 0) { + > return this.multiply(BigInteger("1e" + n)); + > } + > else { // n <= 0 + > return this.quotient(BigInteger("1e" + -n)); + > } + + Parameters: + + n - The power of 10 to multiply *this* by. *n* is converted to a + javascipt number and must be no greater than + (0x7FFFFFFF), or an exception will be thrown. + + Returns: + + *this* * (10 ** *n*), truncated to an integer if necessary. + + See Also: + + , +*/ +BigInteger.prototype.exp10 = function(n) { + n = +n; + if (n === 0) { + return this; + } + if (Math.abs(n) > Number(MAX_EXP)) { + throw new Error("exponent too large in BigInteger.exp10"); + } + // Optimization for this == 0. This also keeps us from having to trim zeros in the positive n case + if (this._s === 0) { + return ZERO; + } + if (n > 0) { + var k = new BigInteger(this._d.slice(), this._s, CONSTRUCT); + + for (; n >= BigInteger_base_log10; n -= BigInteger_base_log10) { + k._d.unshift(0); + } + if (n == 0) + return k; + k._s = 1; + k = k.multiplySingleDigit(Math.pow(10, n)); + return (this._s < 0 ? k.negate() : k); + } else if (-n >= this._d.length*BigInteger_base_log10) { + return ZERO; + } else { + var k = new BigInteger(this._d.slice(), this._s, CONSTRUCT); + + for (n = -n; n >= BigInteger_base_log10; n -= BigInteger_base_log10) { + k._d.shift(); + } + return (n == 0) ? k : k.divRemSmall(Math.pow(10, n))[0]; + } +}; + +/* + Function: pow + Raise a to a power. + + In this implementation, 0**0 is 1. + + Parameters: + + n - The exponent to raise *this* by. *n* must be no greater than + (0x7FFFFFFF), or an exception will be thrown. + + Returns: + + *this* raised to the *nth* power. + + See Also: + + +*/ +BigInteger.prototype.pow = function(n) { + if (this.isUnit()) { + if (this._s > 0) { + return this; + } + else { + return BigInteger(n).isOdd() ? this : this.negate(); + } + } + + n = BigInteger(n); + if (n._s === 0) { + return ONE; + } + else if (n._s < 0) { + if (this._s === 0) { + throw new Error("Divide by zero"); + } + else { + return ZERO; + } + } + if (this._s === 0) { + return ZERO; + } + if (n.isUnit()) { + return this; + } + + if (n.compareAbs(MAX_EXP) > 0) { + throw new Error("exponent too large in BigInteger.pow"); + } + var x = this; + var aux = ONE; + var two = BigInteger.small[2]; + + while (n.isPositive()) { + if (n.isOdd()) { + aux = aux.multiply(x); + if (n.isUnit()) { + return aux; + } + } + x = x.square(); + n = n.quotient(two); + } + + return aux; +}; + +/* + Function: modPow + Raise a to a power (mod m). + + Because it is reduced by a modulus, is not limited by + like . + + Parameters: + + exponent - The exponent to raise *this* by. Must be positive. + modulus - The modulus. + + Returns: + + *this* ^ *exponent* (mod *modulus*). + + See Also: + + , +*/ +BigInteger.prototype.modPow = function(exponent, modulus) { + var result = ONE; + var base = this; + + while (exponent.isPositive()) { + if (exponent.isOdd()) { + result = result.multiply(base).remainder(modulus); + } + + exponent = exponent.quotient(BigInteger.small[2]); + if (exponent.isPositive()) { + base = base.square().remainder(modulus); + } + } + + return result; +}; + +/* + Function: log + Get the natural logarithm of a as a native JavaScript number. + + This is equivalent to + + > Math.log(this.toJSValue()) + + but handles values outside of the native number range. + + Returns: + + log( *this* ) + + See Also: + + +*/ +BigInteger.prototype.log = function() { + switch (this._s) { + case 0: return -Infinity; + case -1: return NaN; + default: // Fall through. + } + + var l = this._d.length; + + if (l*BigInteger_base_log10 < 30) { + return Math.log(this.valueOf()); + } + + var N = Math.ceil(30/BigInteger_base_log10); + var firstNdigits = this._d.slice(l - N); + return Math.log((new BigInteger(firstNdigits, 1, CONSTRUCT)).valueOf()) + (l - N) * Math.log(BigInteger_base); +}; + +/* + Function: valueOf + Convert a to a native JavaScript integer. + + This is called automatically by JavaScipt to convert a to a + native value. + + Returns: + + > parseInt(this.toString(), 10) + + See Also: + + , +*/ +BigInteger.prototype.valueOf = function() { + return parseInt(this.toString(), 10); +}; + +/* + Function: toJSValue + Convert a to a native JavaScript integer. + + This is the same as valueOf, but more explicitly named. + + Returns: + + > parseInt(this.toString(), 10) + + See Also: + + , +*/ +BigInteger.prototype.toJSValue = function() { + return parseInt(this.toString(), 10); +}; + +var MAX_EXP = BigInteger(0x7FFFFFFF); +// Constant: MAX_EXP +// The largest exponent allowed in and (0x7FFFFFFF or 2147483647). +BigInteger.MAX_EXP = MAX_EXP; + +(function() { + function makeUnary(fn) { + return function(a) { + return fn.call(BigInteger(a)); + }; + } + + function makeBinary(fn) { + return function(a, b) { + return fn.call(BigInteger(a), BigInteger(b)); + }; + } + + function makeTrinary(fn) { + return function(a, b, c) { + return fn.call(BigInteger(a), BigInteger(b), BigInteger(c)); + }; + } + + (function() { + var i, fn; + var unary = "toJSValue,isEven,isOdd,sign,isZero,isNegative,abs,isUnit,square,negate,isPositive,toString,next,prev,log".split(","); + var binary = "compare,remainder,divRem,subtract,add,quotient,divide,multiply,pow,compareAbs".split(","); + var trinary = ["modPow"]; + + for (i = 0; i < unary.length; i++) { + fn = unary[i]; + BigInteger[fn] = makeUnary(BigInteger.prototype[fn]); + } + + for (i = 0; i < binary.length; i++) { + fn = binary[i]; + BigInteger[fn] = makeBinary(BigInteger.prototype[fn]); + } + + for (i = 0; i < trinary.length; i++) { + fn = trinary[i]; + BigInteger[fn] = makeTrinary(BigInteger.prototype[fn]); + } + + BigInteger.exp10 = function(x, n) { + return BigInteger(x).exp10(n); + }; + })(); +})(); + +exports.BigInteger = BigInteger; +})(typeof exports !== 'undefined' ? exports : this); diff --git a/src/js/entropy.js b/src/js/entropy.js index 0b76dcf..c28620a 100644 --- a/src/js/entropy.js +++ b/src/js/entropy.js @@ -222,1630 +222,3 @@ window.Entropy = new (function() { }; })(); - - -// BigInteger library included here because -// only the entropy library depends on it -// so if entropy detection is removed so is the dependency - - -/* - JavaScript BigInteger library version 0.9.1 - http://silentmatt.com/biginteger/ - - Copyright (c) 2009 Matthew Crumley - Copyright (c) 2010,2011 by John Tobey - Licensed under the MIT license. - - Support for arbitrary internal representation base was added by - Vitaly Magerya. -*/ - -/* - File: biginteger.js - - Exports: - - -*/ -(function(exports) { -"use strict"; -/* - Class: BigInteger - An arbitrarily-large integer. - - objects should be considered immutable. None of the "built-in" - methods modify *this* or their arguments. All properties should be - considered private. - - All the methods of instances can be called "statically". The - static versions are convenient if you don't already have a - object. - - As an example, these calls are equivalent. - - > BigInteger(4).multiply(5); // returns BigInteger(20); - > BigInteger.multiply(4, 5); // returns BigInteger(20); - - > var a = 42; - > var a = BigInteger.toJSValue("0b101010"); // Not completely useless... -*/ - -var CONSTRUCT = {}; // Unique token to call "private" version of constructor - -/* - Constructor: BigInteger() - Convert a value to a . - - Although is the constructor for objects, it is - best not to call it as a constructor. If *n* is a object, it is - simply returned as-is. Otherwise, is equivalent to - without a radix argument. - - > var n0 = BigInteger(); // Same as - > var n1 = BigInteger("123"); // Create a new with value 123 - > var n2 = BigInteger(123); // Create a new with value 123 - > var n3 = BigInteger(n2); // Return n2, unchanged - - The constructor form only takes an array and a sign. *n* must be an - array of numbers in little-endian order, where each digit is between 0 - and BigInteger.base. The second parameter sets the sign: -1 for - negative, +1 for positive, or 0 for zero. The array is *not copied and - may be modified*. If the array contains only zeros, the sign parameter - is ignored and is forced to zero. - - > new BigInteger([5], -1): create a new BigInteger with value -5 - - Parameters: - - n - Value to convert to a . - - Returns: - - A value. - - See Also: - - , -*/ -function BigInteger(n, s, token) { - if (token !== CONSTRUCT) { - if (n instanceof BigInteger) { - return n; - } - else if (typeof n === "undefined") { - return ZERO; - } - return BigInteger.parse(n); - } - - n = n || []; // Provide the nullary constructor for subclasses. - while (n.length && !n[n.length - 1]) { - --n.length; - } - this._d = n; - this._s = n.length ? (s || 1) : 0; -} - -BigInteger._construct = function(n, s) { - return new BigInteger(n, s, CONSTRUCT); -}; - -// Base-10 speedup hacks in parse, toString, exp10 and log functions -// require base to be a power of 10. 10^7 is the largest such power -// that won't cause a precision loss when digits are multiplied. -var BigInteger_base = 10000000; -var BigInteger_base_log10 = 7; - -BigInteger.base = BigInteger_base; -BigInteger.base_log10 = BigInteger_base_log10; - -var ZERO = new BigInteger([], 0, CONSTRUCT); -// Constant: ZERO -// 0. -BigInteger.ZERO = ZERO; - -var ONE = new BigInteger([1], 1, CONSTRUCT); -// Constant: ONE -// 1. -BigInteger.ONE = ONE; - -var M_ONE = new BigInteger(ONE._d, -1, CONSTRUCT); -// Constant: M_ONE -// -1. -BigInteger.M_ONE = M_ONE; - -// Constant: _0 -// Shortcut for . -BigInteger._0 = ZERO; - -// Constant: _1 -// Shortcut for . -BigInteger._1 = ONE; - -/* - Constant: small - Array of from 0 to 36. - - These are used internally for parsing, but useful when you need a "small" - . - - See Also: - - , , <_0>, <_1> -*/ -BigInteger.small = [ - ZERO, - ONE, - /* Assuming BigInteger_base > 36 */ - new BigInteger( [2], 1, CONSTRUCT), - new BigInteger( [3], 1, CONSTRUCT), - new BigInteger( [4], 1, CONSTRUCT), - new BigInteger( [5], 1, CONSTRUCT), - new BigInteger( [6], 1, CONSTRUCT), - new BigInteger( [7], 1, CONSTRUCT), - new BigInteger( [8], 1, CONSTRUCT), - new BigInteger( [9], 1, CONSTRUCT), - new BigInteger([10], 1, CONSTRUCT), - new BigInteger([11], 1, CONSTRUCT), - new BigInteger([12], 1, CONSTRUCT), - new BigInteger([13], 1, CONSTRUCT), - new BigInteger([14], 1, CONSTRUCT), - new BigInteger([15], 1, CONSTRUCT), - new BigInteger([16], 1, CONSTRUCT), - new BigInteger([17], 1, CONSTRUCT), - new BigInteger([18], 1, CONSTRUCT), - new BigInteger([19], 1, CONSTRUCT), - new BigInteger([20], 1, CONSTRUCT), - new BigInteger([21], 1, CONSTRUCT), - new BigInteger([22], 1, CONSTRUCT), - new BigInteger([23], 1, CONSTRUCT), - new BigInteger([24], 1, CONSTRUCT), - new BigInteger([25], 1, CONSTRUCT), - new BigInteger([26], 1, CONSTRUCT), - new BigInteger([27], 1, CONSTRUCT), - new BigInteger([28], 1, CONSTRUCT), - new BigInteger([29], 1, CONSTRUCT), - new BigInteger([30], 1, CONSTRUCT), - new BigInteger([31], 1, CONSTRUCT), - new BigInteger([32], 1, CONSTRUCT), - new BigInteger([33], 1, CONSTRUCT), - new BigInteger([34], 1, CONSTRUCT), - new BigInteger([35], 1, CONSTRUCT), - new BigInteger([36], 1, CONSTRUCT) -]; - -// Used for parsing/radix conversion -BigInteger.digits = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ".split(""); - -/* - Method: toString - Convert a to a string. - - When *base* is greater than 10, letters are upper case. - - Parameters: - - base - Optional base to represent the number in (default is base 10). - Must be between 2 and 36 inclusive, or an Error will be thrown. - - Returns: - - The string representation of the . -*/ -BigInteger.prototype.toString = function(base) { - base = +base || 10; - if (base < 2 || base > 36) { - throw new Error("illegal radix " + base + "."); - } - if (this._s === 0) { - return "0"; - } - if (base === 10) { - var str = this._s < 0 ? "-" : ""; - str += this._d[this._d.length - 1].toString(); - for (var i = this._d.length - 2; i >= 0; i--) { - var group = this._d[i].toString(); - while (group.length < BigInteger_base_log10) group = '0' + group; - str += group; - } - return str; - } - else { - var numerals = BigInteger.digits; - base = BigInteger.small[base]; - var sign = this._s; - - var n = this.abs(); - var digits = []; - var digit; - - while (n._s !== 0) { - var divmod = n.divRem(base); - n = divmod[0]; - digit = divmod[1]; - // TODO: This could be changed to unshift instead of reversing at the end. - // Benchmark both to compare speeds. - digits.push(numerals[digit.valueOf()]); - } - return (sign < 0 ? "-" : "") + digits.reverse().join(""); - } -}; - -// Verify strings for parsing -BigInteger.radixRegex = [ - /^$/, - /^$/, - /^[01]*$/, - /^[012]*$/, - /^[0-3]*$/, - /^[0-4]*$/, - /^[0-5]*$/, - /^[0-6]*$/, - /^[0-7]*$/, - /^[0-8]*$/, - /^[0-9]*$/, - /^[0-9aA]*$/, - /^[0-9abAB]*$/, - /^[0-9abcABC]*$/, - /^[0-9a-dA-D]*$/, - /^[0-9a-eA-E]*$/, - /^[0-9a-fA-F]*$/, - /^[0-9a-gA-G]*$/, - /^[0-9a-hA-H]*$/, - /^[0-9a-iA-I]*$/, - /^[0-9a-jA-J]*$/, - /^[0-9a-kA-K]*$/, - /^[0-9a-lA-L]*$/, - /^[0-9a-mA-M]*$/, - /^[0-9a-nA-N]*$/, - /^[0-9a-oA-O]*$/, - /^[0-9a-pA-P]*$/, - /^[0-9a-qA-Q]*$/, - /^[0-9a-rA-R]*$/, - /^[0-9a-sA-S]*$/, - /^[0-9a-tA-T]*$/, - /^[0-9a-uA-U]*$/, - /^[0-9a-vA-V]*$/, - /^[0-9a-wA-W]*$/, - /^[0-9a-xA-X]*$/, - /^[0-9a-yA-Y]*$/, - /^[0-9a-zA-Z]*$/ -]; - -/* - Function: parse - Parse a string into a . - - *base* is optional but, if provided, must be from 2 to 36 inclusive. If - *base* is not provided, it will be guessed based on the leading characters - of *s* as follows: - - - "0x" or "0X": *base* = 16 - - "0c" or "0C": *base* = 8 - - "0b" or "0B": *base* = 2 - - else: *base* = 10 - - If no base is provided, or *base* is 10, the number can be in exponential - form. For example, these are all valid: - - > BigInteger.parse("1e9"); // Same as "1000000000" - > BigInteger.parse("1.234*10^3"); // Same as 1234 - > BigInteger.parse("56789 * 10 ** -2"); // Same as 567 - - If any characters fall outside the range defined by the radix, an exception - will be thrown. - - Parameters: - - s - The string to parse. - base - Optional radix (default is to guess based on *s*). - - Returns: - - a instance. -*/ -BigInteger.parse = function(s, base) { - // Expands a number in exponential form to decimal form. - // expandExponential("-13.441*10^5") === "1344100"; - // expandExponential("1.12300e-1") === "0.112300"; - // expandExponential(1000000000000000000000000000000) === "1000000000000000000000000000000"; - function expandExponential(str) { - str = str.replace(/\s*[*xX]\s*10\s*(\^|\*\*)\s*/, "e"); - - return str.replace(/^([+\-])?(\d+)\.?(\d*)[eE]([+\-]?\d+)$/, function(x, s, n, f, c) { - c = +c; - var l = c < 0; - var i = n.length + c; - x = (l ? n : f).length; - c = ((c = Math.abs(c)) >= x ? c - x + l : 0); - var z = (new Array(c + 1)).join("0"); - var r = n + f; - return (s || "") + (l ? r = z + r : r += z).substr(0, i += l ? z.length : 0) + (i < r.length ? "." + r.substr(i) : ""); - }); - } - - s = s.toString(); - if (typeof base === "undefined" || +base === 10) { - s = expandExponential(s); - } - - var prefixRE; - if (typeof base === "undefined") { - prefixRE = '0[xcb]'; - } - else if (base == 16) { - prefixRE = '0x'; - } - else if (base == 8) { - prefixRE = '0c'; - } - else if (base == 2) { - prefixRE = '0b'; - } - else { - prefixRE = ''; - } - var parts = new RegExp('^([+\\-]?)(' + prefixRE + ')?([0-9a-z]*)(?:\\.\\d*)?$', 'i').exec(s); - if (parts) { - var sign = parts[1] || "+"; - var baseSection = parts[2] || ""; - var digits = parts[3] || ""; - - if (typeof base === "undefined") { - // Guess base - if (baseSection === "0x" || baseSection === "0X") { // Hex - base = 16; - } - else if (baseSection === "0c" || baseSection === "0C") { // Octal - base = 8; - } - else if (baseSection === "0b" || baseSection === "0B") { // Binary - base = 2; - } - else { - base = 10; - } - } - else if (base < 2 || base > 36) { - throw new Error("Illegal radix " + base + "."); - } - - base = +base; - - // Check for digits outside the range - if (!(BigInteger.radixRegex[base].test(digits))) { - throw new Error("Bad digit for radix " + base); - } - - // Strip leading zeros, and convert to array - digits = digits.replace(/^0+/, "").split(""); - if (digits.length === 0) { - return ZERO; - } - - // Get the sign (we know it's not zero) - sign = (sign === "-") ? -1 : 1; - - // Optimize 10 - if (base == 10) { - var d = []; - while (digits.length >= BigInteger_base_log10) { - d.push(parseInt(digits.splice(digits.length-BigInteger.base_log10, BigInteger.base_log10).join(''), 10)); - } - d.push(parseInt(digits.join(''), 10)); - return new BigInteger(d, sign, CONSTRUCT); - } - - // Do the conversion - var d = ZERO; - base = BigInteger.small[base]; - var small = BigInteger.small; - for (var i = 0; i < digits.length; i++) { - d = d.multiply(base).add(small[parseInt(digits[i], 36)]); - } - return new BigInteger(d._d, sign, CONSTRUCT); - } - else { - throw new Error("Invalid BigInteger format: " + s); - } -}; - -/* - Function: add - Add two . - - Parameters: - - n - The number to add to *this*. Will be converted to a . - - Returns: - - The numbers added together. - - See Also: - - , , , -*/ -BigInteger.prototype.add = function(n) { - if (this._s === 0) { - return BigInteger(n); - } - - n = BigInteger(n); - if (n._s === 0) { - return this; - } - if (this._s !== n._s) { - n = n.negate(); - return this.subtract(n); - } - - var a = this._d; - var b = n._d; - var al = a.length; - var bl = b.length; - var sum = new Array(Math.max(al, bl) + 1); - var size = Math.min(al, bl); - var carry = 0; - var digit; - - for (var i = 0; i < size; i++) { - digit = a[i] + b[i] + carry; - sum[i] = digit % BigInteger_base; - carry = (digit / BigInteger_base) | 0; - } - if (bl > al) { - a = b; - al = bl; - } - for (i = size; carry && i < al; i++) { - digit = a[i] + carry; - sum[i] = digit % BigInteger_base; - carry = (digit / BigInteger_base) | 0; - } - if (carry) { - sum[i] = carry; - } - - for ( ; i < al; i++) { - sum[i] = a[i]; - } - - return new BigInteger(sum, this._s, CONSTRUCT); -}; - -/* - Function: negate - Get the additive inverse of a . - - Returns: - - A with the same magnatude, but with the opposite sign. - - See Also: - - -*/ -BigInteger.prototype.negate = function() { - return new BigInteger(this._d, (-this._s) | 0, CONSTRUCT); -}; - -/* - Function: abs - Get the absolute value of a . - - Returns: - - A with the same magnatude, but always positive (or zero). - - See Also: - - -*/ -BigInteger.prototype.abs = function() { - return (this._s < 0) ? this.negate() : this; -}; - -/* - Function: subtract - Subtract two . - - Parameters: - - n - The number to subtract from *this*. Will be converted to a . - - Returns: - - The *n* subtracted from *this*. - - See Also: - - , , , -*/ -BigInteger.prototype.subtract = function(n) { - if (this._s === 0) { - return BigInteger(n).negate(); - } - - n = BigInteger(n); - if (n._s === 0) { - return this; - } - if (this._s !== n._s) { - n = n.negate(); - return this.add(n); - } - - var m = this; - // negative - negative => -|a| - -|b| => -|a| + |b| => |b| - |a| - if (this._s < 0) { - m = new BigInteger(n._d, 1, CONSTRUCT); - n = new BigInteger(this._d, 1, CONSTRUCT); - } - - // Both are positive => a - b - var sign = m.compareAbs(n); - if (sign === 0) { - return ZERO; - } - else if (sign < 0) { - // swap m and n - var t = n; - n = m; - m = t; - } - - // a > b - var a = m._d; - var b = n._d; - var al = a.length; - var bl = b.length; - var diff = new Array(al); // al >= bl since a > b - var borrow = 0; - var i; - var digit; - - for (i = 0; i < bl; i++) { - digit = a[i] - borrow - b[i]; - if (digit < 0) { - digit += BigInteger_base; - borrow = 1; - } - else { - borrow = 0; - } - diff[i] = digit; - } - for (i = bl; i < al; i++) { - digit = a[i] - borrow; - if (digit < 0) { - digit += BigInteger_base; - } - else { - diff[i++] = digit; - break; - } - diff[i] = digit; - } - for ( ; i < al; i++) { - diff[i] = a[i]; - } - - return new BigInteger(diff, sign, CONSTRUCT); -}; - -(function() { - function addOne(n, sign) { - var a = n._d; - var sum = a.slice(); - var carry = true; - var i = 0; - - while (true) { - var digit = (a[i] || 0) + 1; - sum[i] = digit % BigInteger_base; - if (digit <= BigInteger_base - 1) { - break; - } - ++i; - } - - return new BigInteger(sum, sign, CONSTRUCT); - } - - function subtractOne(n, sign) { - var a = n._d; - var sum = a.slice(); - var borrow = true; - var i = 0; - - while (true) { - var digit = (a[i] || 0) - 1; - if (digit < 0) { - sum[i] = digit + BigInteger_base; - } - else { - sum[i] = digit; - break; - } - ++i; - } - - return new BigInteger(sum, sign, CONSTRUCT); - } - - /* - Function: next - Get the next (add one). - - Returns: - - *this* + 1. - - See Also: - - , - */ - BigInteger.prototype.next = function() { - switch (this._s) { - case 0: - return ONE; - case -1: - return subtractOne(this, -1); - // case 1: - default: - return addOne(this, 1); - } - }; - - /* - Function: prev - Get the previous (subtract one). - - Returns: - - *this* - 1. - - See Also: - - , - */ - BigInteger.prototype.prev = function() { - switch (this._s) { - case 0: - return M_ONE; - case -1: - return addOne(this, -1); - // case 1: - default: - return subtractOne(this, 1); - } - }; -})(); - -/* - Function: compareAbs - Compare the absolute value of two . - - Calling is faster than calling twice, then . - - Parameters: - - n - The number to compare to *this*. Will be converted to a . - - Returns: - - -1, 0, or +1 if *|this|* is less than, equal to, or greater than *|n|*. - - See Also: - - , -*/ -BigInteger.prototype.compareAbs = function(n) { - if (this === n) { - return 0; - } - - if (!(n instanceof BigInteger)) { - if (!isFinite(n)) { - return(isNaN(n) ? n : -1); - } - n = BigInteger(n); - } - - if (this._s === 0) { - return (n._s !== 0) ? -1 : 0; - } - if (n._s === 0) { - return 1; - } - - var l = this._d.length; - var nl = n._d.length; - if (l < nl) { - return -1; - } - else if (l > nl) { - return 1; - } - - var a = this._d; - var b = n._d; - for (var i = l-1; i >= 0; i--) { - if (a[i] !== b[i]) { - return a[i] < b[i] ? -1 : 1; - } - } - - return 0; -}; - -/* - Function: compare - Compare two . - - Parameters: - - n - The number to compare to *this*. Will be converted to a . - - Returns: - - -1, 0, or +1 if *this* is less than, equal to, or greater than *n*. - - See Also: - - , , , -*/ -BigInteger.prototype.compare = function(n) { - if (this === n) { - return 0; - } - - n = BigInteger(n); - - if (this._s === 0) { - return -n._s; - } - - if (this._s === n._s) { // both positive or both negative - var cmp = this.compareAbs(n); - return cmp * this._s; - } - else { - return this._s; - } -}; - -/* - Function: isUnit - Return true iff *this* is either 1 or -1. - - Returns: - - true if *this* compares equal to or . - - See Also: - - , , , , , - , -*/ -BigInteger.prototype.isUnit = function() { - return this === ONE || - this === M_ONE || - (this._d.length === 1 && this._d[0] === 1); -}; - -/* - Function: multiply - Multiply two . - - Parameters: - - n - The number to multiply *this* by. Will be converted to a - . - - Returns: - - The numbers multiplied together. - - See Also: - - , , , -*/ -BigInteger.prototype.multiply = function(n) { - // TODO: Consider adding Karatsuba multiplication for large numbers - if (this._s === 0) { - return ZERO; - } - - n = BigInteger(n); - if (n._s === 0) { - return ZERO; - } - if (this.isUnit()) { - if (this._s < 0) { - return n.negate(); - } - return n; - } - if (n.isUnit()) { - if (n._s < 0) { - return this.negate(); - } - return this; - } - if (this === n) { - return this.square(); - } - - var r = (this._d.length >= n._d.length); - var a = (r ? this : n)._d; // a will be longer than b - var b = (r ? n : this)._d; - var al = a.length; - var bl = b.length; - - var pl = al + bl; - var partial = new Array(pl); - var i; - for (i = 0; i < pl; i++) { - partial[i] = 0; - } - - for (i = 0; i < bl; i++) { - var carry = 0; - var bi = b[i]; - var jlimit = al + i; - var digit; - for (var j = i; j < jlimit; j++) { - digit = partial[j] + bi * a[j - i] + carry; - carry = (digit / BigInteger_base) | 0; - partial[j] = (digit % BigInteger_base) | 0; - } - if (carry) { - digit = partial[j] + carry; - carry = (digit / BigInteger_base) | 0; - partial[j] = digit % BigInteger_base; - } - } - return new BigInteger(partial, this._s * n._s, CONSTRUCT); -}; - -// Multiply a BigInteger by a single-digit native number -// Assumes that this and n are >= 0 -// This is not really intended to be used outside the library itself -BigInteger.prototype.multiplySingleDigit = function(n) { - if (n === 0 || this._s === 0) { - return ZERO; - } - if (n === 1) { - return this; - } - - var digit; - if (this._d.length === 1) { - digit = this._d[0] * n; - if (digit >= BigInteger_base) { - return new BigInteger([(digit % BigInteger_base)|0, - (digit / BigInteger_base)|0], 1, CONSTRUCT); - } - return new BigInteger([digit], 1, CONSTRUCT); - } - - if (n === 2) { - return this.add(this); - } - if (this.isUnit()) { - return new BigInteger([n], 1, CONSTRUCT); - } - - var a = this._d; - var al = a.length; - - var pl = al + 1; - var partial = new Array(pl); - for (var i = 0; i < pl; i++) { - partial[i] = 0; - } - - var carry = 0; - for (var j = 0; j < al; j++) { - digit = n * a[j] + carry; - carry = (digit / BigInteger_base) | 0; - partial[j] = (digit % BigInteger_base) | 0; - } - if (carry) { - partial[j] = carry; - } - - return new BigInteger(partial, 1, CONSTRUCT); -}; - -/* - Function: square - Multiply a by itself. - - This is slightly faster than regular multiplication, since it removes the - duplicated multiplcations. - - Returns: - - > this.multiply(this) - - See Also: - -*/ -BigInteger.prototype.square = function() { - // Normally, squaring a 10-digit number would take 100 multiplications. - // Of these 10 are unique diagonals, of the remaining 90 (100-10), 45 are repeated. - // This procedure saves (N*(N-1))/2 multiplications, (e.g., 45 of 100 multiplies). - // Based on code by Gary Darby, Intellitech Systems Inc., www.DelphiForFun.org - - if (this._s === 0) { - return ZERO; - } - if (this.isUnit()) { - return ONE; - } - - var digits = this._d; - var length = digits.length; - var imult1 = new Array(length + length + 1); - var product, carry, k; - var i; - - // Calculate diagonal - for (i = 0; i < length; i++) { - k = i * 2; - product = digits[i] * digits[i]; - carry = (product / BigInteger_base) | 0; - imult1[k] = product % BigInteger_base; - imult1[k + 1] = carry; - } - - // Calculate repeating part - for (i = 0; i < length; i++) { - carry = 0; - k = i * 2 + 1; - for (var j = i + 1; j < length; j++, k++) { - product = digits[j] * digits[i] * 2 + imult1[k] + carry; - carry = (product / BigInteger_base) | 0; - imult1[k] = product % BigInteger_base; - } - k = length + i; - var digit = carry + imult1[k]; - carry = (digit / BigInteger_base) | 0; - imult1[k] = digit % BigInteger_base; - imult1[k + 1] += carry; - } - - return new BigInteger(imult1, 1, CONSTRUCT); -}; - -/* - Function: quotient - Divide two and truncate towards zero. - - throws an exception if *n* is zero. - - Parameters: - - n - The number to divide *this* by. Will be converted to a . - - Returns: - - The *this* / *n*, truncated to an integer. - - See Also: - - , , , , -*/ -BigInteger.prototype.quotient = function(n) { - return this.divRem(n)[0]; -}; - -/* - Function: divide - Deprecated synonym for . -*/ -BigInteger.prototype.divide = BigInteger.prototype.quotient; - -/* - Function: remainder - Calculate the remainder of two . - - throws an exception if *n* is zero. - - Parameters: - - n - The remainder after *this* is divided *this* by *n*. Will be - converted to a . - - Returns: - - *this* % *n*. - - See Also: - - , -*/ -BigInteger.prototype.remainder = function(n) { - return this.divRem(n)[1]; -}; - -/* - Function: divRem - Calculate the integer quotient and remainder of two . - - throws an exception if *n* is zero. - - Parameters: - - n - The number to divide *this* by. Will be converted to a . - - Returns: - - A two-element array containing the quotient and the remainder. - - > a.divRem(b) - - is exactly equivalent to - - > [a.quotient(b), a.remainder(b)] - - except it is faster, because they are calculated at the same time. - - See Also: - - , -*/ -BigInteger.prototype.divRem = function(n) { - n = BigInteger(n); - if (n._s === 0) { - throw new Error("Divide by zero"); - } - if (this._s === 0) { - return [ZERO, ZERO]; - } - if (n._d.length === 1) { - return this.divRemSmall(n._s * n._d[0]); - } - - // Test for easy cases -- |n1| <= |n2| - switch (this.compareAbs(n)) { - case 0: // n1 == n2 - return [this._s === n._s ? ONE : M_ONE, ZERO]; - case -1: // |n1| < |n2| - return [ZERO, this]; - } - - var sign = this._s * n._s; - var a = n.abs(); - var b_digits = this._d; - var b_index = b_digits.length; - var digits = n._d.length; - var quot = []; - var guess; - - var part = new BigInteger([], 0, CONSTRUCT); - - while (b_index) { - part._d.unshift(b_digits[--b_index]); - part = new BigInteger(part._d, 1, CONSTRUCT); - - if (part.compareAbs(n) < 0) { - quot.push(0); - continue; - } - if (part._s === 0) { - guess = 0; - } - else { - var xlen = part._d.length, ylen = a._d.length; - var highx = part._d[xlen-1]*BigInteger_base + part._d[xlen-2]; - var highy = a._d[ylen-1]*BigInteger_base + a._d[ylen-2]; - if (part._d.length > a._d.length) { - // The length of part._d can either match a._d length, - // or exceed it by one. - highx = (highx+1)*BigInteger_base; - } - guess = Math.ceil(highx/highy); - } - do { - var check = a.multiplySingleDigit(guess); - if (check.compareAbs(part) <= 0) { - break; - } - guess--; - } while (guess); - - quot.push(guess); - if (!guess) { - continue; - } - var diff = part.subtract(check); - part._d = diff._d.slice(); - } - - return [new BigInteger(quot.reverse(), sign, CONSTRUCT), - new BigInteger(part._d, this._s, CONSTRUCT)]; -}; - -// Throws an exception if n is outside of (-BigInteger.base, -1] or -// [1, BigInteger.base). It's not necessary to call this, since the -// other division functions will call it if they are able to. -BigInteger.prototype.divRemSmall = function(n) { - var r; - n = +n; - if (n === 0) { - throw new Error("Divide by zero"); - } - - var n_s = n < 0 ? -1 : 1; - var sign = this._s * n_s; - n = Math.abs(n); - - if (n < 1 || n >= BigInteger_base) { - throw new Error("Argument out of range"); - } - - if (this._s === 0) { - return [ZERO, ZERO]; - } - - if (n === 1 || n === -1) { - return [(sign === 1) ? this.abs() : new BigInteger(this._d, sign, CONSTRUCT), ZERO]; - } - - // 2 <= n < BigInteger_base - - // divide a single digit by a single digit - if (this._d.length === 1) { - var q = new BigInteger([(this._d[0] / n) | 0], 1, CONSTRUCT); - r = new BigInteger([(this._d[0] % n) | 0], 1, CONSTRUCT); - if (sign < 0) { - q = q.negate(); - } - if (this._s < 0) { - r = r.negate(); - } - return [q, r]; - } - - var digits = this._d.slice(); - var quot = new Array(digits.length); - var part = 0; - var diff = 0; - var i = 0; - var guess; - - while (digits.length) { - part = part * BigInteger_base + digits[digits.length - 1]; - if (part < n) { - quot[i++] = 0; - digits.pop(); - diff = BigInteger_base * diff + part; - continue; - } - if (part === 0) { - guess = 0; - } - else { - guess = (part / n) | 0; - } - - var check = n * guess; - diff = part - check; - quot[i++] = guess; - if (!guess) { - digits.pop(); - continue; - } - - digits.pop(); - part = diff; - } - - r = new BigInteger([diff], 1, CONSTRUCT); - if (this._s < 0) { - r = r.negate(); - } - return [new BigInteger(quot.reverse(), sign, CONSTRUCT), r]; -}; - -/* - Function: isEven - Return true iff *this* is divisible by two. - - Note that is even. - - Returns: - - true if *this* is even, false otherwise. - - See Also: - - -*/ -BigInteger.prototype.isEven = function() { - var digits = this._d; - return this._s === 0 || digits.length === 0 || (digits[0] % 2) === 0; -}; - -/* - Function: isOdd - Return true iff *this* is not divisible by two. - - Returns: - - true if *this* is odd, false otherwise. - - See Also: - - -*/ -BigInteger.prototype.isOdd = function() { - return !this.isEven(); -}; - -/* - Function: sign - Get the sign of a . - - Returns: - - * -1 if *this* < 0 - * 0 if *this* == 0 - * +1 if *this* > 0 - - See Also: - - , , , , -*/ -BigInteger.prototype.sign = function() { - return this._s; -}; - -/* - Function: isPositive - Return true iff *this* > 0. - - Returns: - - true if *this*.compare() == 1. - - See Also: - - , , , , , -*/ -BigInteger.prototype.isPositive = function() { - return this._s > 0; -}; - -/* - Function: isNegative - Return true iff *this* < 0. - - Returns: - - true if *this*.compare() == -1. - - See Also: - - , , , , , -*/ -BigInteger.prototype.isNegative = function() { - return this._s < 0; -}; - -/* - Function: isZero - Return true iff *this* == 0. - - Returns: - - true if *this*.compare() == 0. - - See Also: - - , , , , -*/ -BigInteger.prototype.isZero = function() { - return this._s === 0; -}; - -/* - Function: exp10 - Multiply a by a power of 10. - - This is equivalent to, but faster than - - > if (n >= 0) { - > return this.multiply(BigInteger("1e" + n)); - > } - > else { // n <= 0 - > return this.quotient(BigInteger("1e" + -n)); - > } - - Parameters: - - n - The power of 10 to multiply *this* by. *n* is converted to a - javascipt number and must be no greater than - (0x7FFFFFFF), or an exception will be thrown. - - Returns: - - *this* * (10 ** *n*), truncated to an integer if necessary. - - See Also: - - , -*/ -BigInteger.prototype.exp10 = function(n) { - n = +n; - if (n === 0) { - return this; - } - if (Math.abs(n) > Number(MAX_EXP)) { - throw new Error("exponent too large in BigInteger.exp10"); - } - // Optimization for this == 0. This also keeps us from having to trim zeros in the positive n case - if (this._s === 0) { - return ZERO; - } - if (n > 0) { - var k = new BigInteger(this._d.slice(), this._s, CONSTRUCT); - - for (; n >= BigInteger_base_log10; n -= BigInteger_base_log10) { - k._d.unshift(0); - } - if (n == 0) - return k; - k._s = 1; - k = k.multiplySingleDigit(Math.pow(10, n)); - return (this._s < 0 ? k.negate() : k); - } else if (-n >= this._d.length*BigInteger_base_log10) { - return ZERO; - } else { - var k = new BigInteger(this._d.slice(), this._s, CONSTRUCT); - - for (n = -n; n >= BigInteger_base_log10; n -= BigInteger_base_log10) { - k._d.shift(); - } - return (n == 0) ? k : k.divRemSmall(Math.pow(10, n))[0]; - } -}; - -/* - Function: pow - Raise a to a power. - - In this implementation, 0**0 is 1. - - Parameters: - - n - The exponent to raise *this* by. *n* must be no greater than - (0x7FFFFFFF), or an exception will be thrown. - - Returns: - - *this* raised to the *nth* power. - - See Also: - - -*/ -BigInteger.prototype.pow = function(n) { - if (this.isUnit()) { - if (this._s > 0) { - return this; - } - else { - return BigInteger(n).isOdd() ? this : this.negate(); - } - } - - n = BigInteger(n); - if (n._s === 0) { - return ONE; - } - else if (n._s < 0) { - if (this._s === 0) { - throw new Error("Divide by zero"); - } - else { - return ZERO; - } - } - if (this._s === 0) { - return ZERO; - } - if (n.isUnit()) { - return this; - } - - if (n.compareAbs(MAX_EXP) > 0) { - throw new Error("exponent too large in BigInteger.pow"); - } - var x = this; - var aux = ONE; - var two = BigInteger.small[2]; - - while (n.isPositive()) { - if (n.isOdd()) { - aux = aux.multiply(x); - if (n.isUnit()) { - return aux; - } - } - x = x.square(); - n = n.quotient(two); - } - - return aux; -}; - -/* - Function: modPow - Raise a to a power (mod m). - - Because it is reduced by a modulus, is not limited by - like . - - Parameters: - - exponent - The exponent to raise *this* by. Must be positive. - modulus - The modulus. - - Returns: - - *this* ^ *exponent* (mod *modulus*). - - See Also: - - , -*/ -BigInteger.prototype.modPow = function(exponent, modulus) { - var result = ONE; - var base = this; - - while (exponent.isPositive()) { - if (exponent.isOdd()) { - result = result.multiply(base).remainder(modulus); - } - - exponent = exponent.quotient(BigInteger.small[2]); - if (exponent.isPositive()) { - base = base.square().remainder(modulus); - } - } - - return result; -}; - -/* - Function: log - Get the natural logarithm of a as a native JavaScript number. - - This is equivalent to - - > Math.log(this.toJSValue()) - - but handles values outside of the native number range. - - Returns: - - log( *this* ) - - See Also: - - -*/ -BigInteger.prototype.log = function() { - switch (this._s) { - case 0: return -Infinity; - case -1: return NaN; - default: // Fall through. - } - - var l = this._d.length; - - if (l*BigInteger_base_log10 < 30) { - return Math.log(this.valueOf()); - } - - var N = Math.ceil(30/BigInteger_base_log10); - var firstNdigits = this._d.slice(l - N); - return Math.log((new BigInteger(firstNdigits, 1, CONSTRUCT)).valueOf()) + (l - N) * Math.log(BigInteger_base); -}; - -/* - Function: valueOf - Convert a to a native JavaScript integer. - - This is called automatically by JavaScipt to convert a to a - native value. - - Returns: - - > parseInt(this.toString(), 10) - - See Also: - - , -*/ -BigInteger.prototype.valueOf = function() { - return parseInt(this.toString(), 10); -}; - -/* - Function: toJSValue - Convert a to a native JavaScript integer. - - This is the same as valueOf, but more explicitly named. - - Returns: - - > parseInt(this.toString(), 10) - - See Also: - - , -*/ -BigInteger.prototype.toJSValue = function() { - return parseInt(this.toString(), 10); -}; - -var MAX_EXP = BigInteger(0x7FFFFFFF); -// Constant: MAX_EXP -// The largest exponent allowed in and (0x7FFFFFFF or 2147483647). -BigInteger.MAX_EXP = MAX_EXP; - -(function() { - function makeUnary(fn) { - return function(a) { - return fn.call(BigInteger(a)); - }; - } - - function makeBinary(fn) { - return function(a, b) { - return fn.call(BigInteger(a), BigInteger(b)); - }; - } - - function makeTrinary(fn) { - return function(a, b, c) { - return fn.call(BigInteger(a), BigInteger(b), BigInteger(c)); - }; - } - - (function() { - var i, fn; - var unary = "toJSValue,isEven,isOdd,sign,isZero,isNegative,abs,isUnit,square,negate,isPositive,toString,next,prev,log".split(","); - var binary = "compare,remainder,divRem,subtract,add,quotient,divide,multiply,pow,compareAbs".split(","); - var trinary = ["modPow"]; - - for (i = 0; i < unary.length; i++) { - fn = unary[i]; - BigInteger[fn] = makeUnary(BigInteger.prototype[fn]); - } - - for (i = 0; i < binary.length; i++) { - fn = binary[i]; - BigInteger[fn] = makeBinary(BigInteger.prototype[fn]); - } - - for (i = 0; i < trinary.length; i++) { - fn = trinary[i]; - BigInteger[fn] = makeTrinary(BigInteger.prototype[fn]); - } - - BigInteger.exp10 = function(x, n) { - return BigInteger(x).exp10(n); - }; - })(); -})(); - -exports.BigInteger = BigInteger; -})(typeof exports !== 'undefined' ? exports : this); -- cgit v1.2.3