You're Invited:Meet the Socket Team at BlackHat and DEF CON in Las Vegas, Aug 7-8.RSVP →
Socket
Socket
Sign inDemoInstall

big-integer

Package Overview
Dependencies
Maintainers
1
Versions
102
Alerts
File Explorer

Advanced tools

npm Scripts
License
Socket logo

Install Socket

Detect and block malicious and high-risk dependencies

Install

Comparing version 1.4.6 to 1.4.7

1272

BigInteger.js

@@ -1,218 +0,409 @@

"use strict";
var bigInt = (function () {
var base = 10000000, logBase = 7, zeros = "0000000";
var sign = {
positive: false,
negative: true
};
var bigInt = (function (undefined) {
"use strict";
var BASE = 1e7,
LOG_BASE = 7,
MAX_INT = 9007199254740992,
MAX_INT_ARR = smallToArray(MAX_INT),
LOG_MAX_INT = Math.log(MAX_INT);
function BigInteger(value, sign) {
this.value = value;
this.sign = sign;
this.isSmall = false;
}
function trim(value) {
while (value[value.length - 1] === 0 && value.length > 1) value.pop();
return value;
function SmallInteger(value) {
this.value = value;
this.sign = value < 0;
this.isSmall = true;
}
function fastAdd(a, b) {
var sign = b < 0;
if (a.sign !== sign) {
if(sign) return fastSubtract(a.abs(), -b);
return fastSubtract(a.abs(), b).negate();
}
if (sign) b = -b;
var value = a.value,
result = [],
carry = 0;
for (var i = 0; i < value.length || carry > 0; i++) {
var sum = (value[i] || 0) + (i > 0 ? 0 : b) + carry;
carry = sum >= base ? 1 : 0;
result.push(sum % base);
}
return new BigInteger(trim(result), a.sign);
function isPrecise(n) {
return -MAX_INT < n && n < MAX_INT;
}
function fastSubtract(a, b) {
var value = a.value;
if (value.length === 1) {
value = value[0];
if (a.sign) value = -value;
return new BigInteger([Math.abs(value - b)], (value - b) < 0);
function smallToArray(n) { // For performance reasons doesn't reference BASE, need to change this function if BASE changes
if (n < 1e7)
return [n];
if (n < 1e14)
return [n % 1e7, Math.floor(n / 1e7)];
return [n % 1e7, Math.floor(n / 1e7) % 1e7, Math.floor(n / 1e14)];
}
function arrayToSmall(arr) { // If BASE changes this function may need to change
trim(arr);
var length = arr.length;
if (length < 4 && compareAbs(arr, MAX_INT_ARR) < 0) {
if (length < 2) return arr[0];
if (length < 3) return arr[0] + arr[1] * BASE;
return arr[0] + (arr[1] + arr[2] * BASE) * BASE;
}
if (a.sign !== (b < 0)) return fastAdd(a, -b);
var sign = false;
if (a.sign) sign = true;
if (value.length === 1 && value[0] < b) return new BigInteger([b - value[0]], !sign);
if (sign) b = -b;
var result = [],
borrow = 0;
for (var i = 0; i < value.length; i++) {
var tmp = value[i] - borrow - (i > 0 ? 0 : b);
borrow = tmp < 0 ? 1 : 0;
result.push((borrow * base) + tmp);
}
return arr;
}
return new BigInteger(trim(result), sign);
function trim(v) {
var i = v.length;
while (v[--i] === 0);
v.length = i + 1;
}
function fastMultiplyInternal(value, lambda) {
var result = [];
var carry = 0;
for (var i = 0; i < value.length; i++) {
carry += lambda * value[i];
var q = Math.floor(carry / base);
result[i] = (carry - q * base) | 0;
carry = q;
function createArray(length) { // function shamelessly stolen from Yaffle's library https://github.com/Yaffle/BigInteger
var x = new Array(length);
var i = -1;
while (++i < length) {
x[i] = 0;
}
result[value.length] = carry | 0;
return result;
return x;
}
function fastMultiply(a, b) {
var result = fastMultiplyInternal(a.value, b < 0 ? -b : b);
return new BigInteger(trim(result), b < 0 ? !a.sign : a.sign);
function truncate(n) {
if (n > 0) return Math.floor(n);
return Math.ceil(n);
}
function fastDivModInternal(value, lambda) {
var quotient = [];
for (var i = 0; i < value.length; i++) {
quotient[i] = 0;
function add(a, b) { // assumes a and b are arrays with a.length >= b.length
var l_a = a.length,
l_b = b.length,
r = new Array(l_a),
carry = 0,
base = BASE,
sum, i;
for (i = 0; i < l_b; i++) {
sum = a[i] + b[i] + carry;
carry = sum >= base ? 1 : 0;
r[i] = sum - carry * base;
}
var remainder = 0;
for (var i = value.length - 1; i >= 0; i--) {
var divisor = remainder * base + value[i];
var q = Math.floor(divisor / lambda);
remainder = divisor - q * lambda;
quotient[i] = q | 0;
while (i < l_a) {
sum = a[i] + carry;
carry = sum === base ? 1 : 0;
r[i++] = sum - carry * base;
}
return {
quotient: quotient,
remainder: remainder | 0
};
if (carry > 0) r.push(carry);
return r;
}
function fastDivMod(a, b) {
if (b === 0) throw new Error("Cannot divide by zero.");
var result = fastDivModInternal(a.value, b < 0 ? -b : b);
return {
quotient: new BigInteger(trim(result.quotient), b < 0 ? !a.sign : a.sign),
remainder: new BigInteger([result.remainder], a.sign)
};
function addAny(a, b) {
if (a.length >= b.length) return add(a, b);
return add(b, a);
}
function isSmall(n) {
return ((typeof n === "number" || typeof n === "string") && +Math.abs(n) <= base) ||
(n instanceof BigInteger && n.value.length <= 1);
function addSmall(a, carry) { // assumes a is array, carry is number with |carry| + BASE < MAX_INT
var l = a.length,
r = new Array(l),
base = BASE,
sum, i;
for (i = 0; i < l; i++) {
sum = a[i] + carry;
carry = Math.floor(sum / base);
r[i] = sum % base;
}
while (carry > 0) {
r[i++] = carry % base;
carry = Math.floor(carry / base);
}
return r;
}
BigInteger.prototype.negate = function () {
return new BigInteger(this.value, !this.sign);
};
BigInteger.prototype.abs = function () {
return new BigInteger(this.value, sign.positive);
};
BigInteger.prototype.add = function (n) {
if(isSmall(n)) return fastAdd(this, +n);
n = parseInput(n);
BigInteger.prototype.add = function (v) {
var value, n = parseValue(v);
if (this.sign !== n.sign) {
if (this.sign === sign.positive) return this.abs().subtract(n.abs());
return n.abs().subtract(this.abs());
return this.subtract(n.negate());
}
var a = this.value, b = n.value;
var result = [],
carry = 0,
length = Math.max(a.length, b.length);
for (var i = 0; i < length || carry > 0; i++) {
var sum = (a[i] || 0) + (b[i] || 0) + carry;
carry = sum >= base ? 1 : 0;
result.push(sum % base);
if (n.isSmall) {
return new BigInteger(addSmall(a, b), this.sign);
}
return new BigInteger(trim(result), this.sign);
return new BigInteger(addAny(a, b), this.sign);
};
BigInteger.prototype.plus = BigInteger.prototype.add;
BigInteger.prototype.subtract = function (n) {
if (isSmall(n)) return fastSubtract(this, +n);
n = parseInput(n);
if (this.sign !== n.sign) return this.add(n.negate());
if (this.sign === sign.negative) return n.negate().subtract(this.negate());
if (this.compare(n) < 0) return n.subtract(this).negate();
SmallInteger.prototype.add = function (v) {
var n = parseValue(v);
if (this.sign !== n.sign) {
return this.subtract(n.negate());
}
var a = this.value, b = n.value;
var result = [],
if (n.isSmall) {
if (isPrecise(a + b)) return new SmallInteger(a + b);
b = smallToArray(b);
}
return new BigInteger(addSmall(b, a), a < 0);
};
SmallInteger.prototype.plus = SmallInteger.prototype.add;
function subtract(a, b) { // assumes a and b are arrays with a >= b
var a_l = a.length,
b_l = b.length,
r = new Array(a_l),
borrow = 0,
length = Math.max(a.length, b.length);
for (var i = 0; i < length; i++) {
var ai = a[i] || 0, bi = b[i] || 0;
var tmp = ai - borrow;
borrow = tmp < bi ? 1 : 0;
result.push((borrow * base) + tmp - bi);
base = BASE,
i, difference;
for (i = 0; i < b_l; i++) {
difference = a[i] - borrow - b[i];
if (difference < 0) {
difference += base;
borrow = 1;
} else borrow = 0;
r[i] = difference;
}
return new BigInteger(trim(result), sign.positive);
for (i = b_l; i < a_l; i++) {
difference = a[i] - borrow;
if (difference < 0) difference += base;
else {
r[i++] = difference;
break;
}
r[i] = difference;
}
for (; i < a_l; i++) {
r[i] = a[i];
}
trim(r);
return r;
}
function subtractAny(a, b, sign) {
var value, isSmall;
if (compareAbs(a, b) >= 0) {
value = subtract(a,b);
} else {
value = subtract(b, a);
sign = !sign;
}
value = arrayToSmall(value);
if (typeof value === "number") {
if (sign) value = -value;
return new SmallInteger(value);
}
return new BigInteger(value, sign);
}
function subtractSmall(a, b, sign) { // assumes a is array, b is number with |b| < MAX_INT
var l = a.length,
r = new Array(l),
carry = -b,
base = BASE,
i, difference;
for (i = 0; i < l; i++) {
difference = a[i] + carry;
carry = Math.floor(difference / base);
r[i] = difference < 0 ? difference % base + base : difference;
}
r = arrayToSmall(r);
if (typeof r === "number") {
if (sign) r = -r;
return new SmallInteger(r);
} return new BigInteger(r, sign);
}
BigInteger.prototype.subtract = function (v) {
var n = parseValue(v);
if (this.sign !== n.sign) {
return this.add(n.negate());
}
var a = this.value, b = n.value;
if (n.isSmall)
return subtractSmall(a, Math.abs(b), this.sign);
return subtractAny(a, b, this.sign);
};
BigInteger.prototype.minus = BigInteger.prototype.subtract;
BigInteger.prototype.multiply = function (n) {
if (isSmall(n)) return fastMultiply(this, +n);
n = parseInput(n);
var sign = this.sign !== n.sign;
SmallInteger.prototype.subtract = function (v) {
var n = parseValue(v);
if (this.sign !== n.sign) {
return this.add(n.negate());
}
var a = this.value, b = n.value;
var result = [];
for (var i = a.length + b.length; i > 0; i--) {
result.push(0);
if (n.isSmall) {
return new SmallInteger(a - b);
}
for (var i = 0; i < a.length; i++) {
var x = a[i];
for (var j = 0; j < b.length; j++) {
var y = b[j];
var product = x * y + result[i+j];
var q = Math.floor(product / base);
result[i+j] = product - q * base;
result[i+j+1] += q;
return subtractSmall(b, Math.abs(a), a >= 0);
};
SmallInteger.prototype.minus = SmallInteger.prototype.subtract;
BigInteger.prototype.negate = function () {
return new BigInteger(this.value, !this.sign);
};
SmallInteger.prototype.negate = function () {
var sign = this.sign;
var small = new SmallInteger(-this.value);
small.sign = !sign;
return small;
};
BigInteger.prototype.abs = function () {
return new BigInteger(this.value, false);
};
SmallInteger.prototype.abs = function () {
return new SmallInteger(Math.abs(this.value));
};
function multiplyLong(a, b) {
var a_l = a.length,
b_l = b.length,
l = a_l + b_l,
r = createArray(l),
base = BASE,
product, carry, i, a_i, b_j;
for (i = 0; i < a_l; ++i) {
a_i = a[i];
for (var j = 0; j < b_l; ++j) {
b_j = b[j];
product = a_i * b_j + r[i + j];
carry = Math.floor(product / base);
r[i + j] = product - carry * base;
r[i + j + 1] += carry;
}
}
return new BigInteger(trim(result), sign);
trim(r);
return r;
}
function multiplySmall(a, b) { // assumes a is array, b is number with |b| < BASE
var l = a.length,
r = new Array(l),
base = BASE,
carry = 0,
product, i;
for (i = 0; i < l; i++) {
product = a[i] * b + carry;
carry = Math.floor(product / base);
r[i] = product - carry * base;
}
while (carry > 0) {
r[i++] = carry % base;
carry = Math.floor(carry / base);
}
return r;
}
function shiftLeft(x, n) {
var r = [];
while (n-- > 0) r.push(0);
return r.concat(x);
}
function multiplyKaratsuba(x, y) {
var n = Math.max(x.length, y.length);
if (n <= 400) return multiplyLong(x, y);
n = Math.ceil(n / 2);
var b = x.slice(n),
a = x.slice(0, n),
d = y.slice(n),
c = y.slice(0, n);
var ac = multiplyKaratsuba(a, c),
bd = multiplyKaratsuba(b, d),
abcd = multiplyKaratsuba(addAny(a, b), addAny(c, d));
return addAny(addAny(ac, shiftLeft(subtract(subtract(abcd, ac), bd), n)), shiftLeft(bd, 2 * n));
}
BigInteger.prototype.multiply = function (v) {
var value, n = parseValue(v),
a = this.value, b = n.value,
sign = this.sign !== n.sign,
abs;
if (n.isSmall) {
if (b === 0) return CACHE[0];
if (b === 1) return this;
if (b === -1) return this.negate();
abs = Math.abs(b);
if (abs < BASE) {
return new BigInteger(multiplySmall(a, abs), sign);
}
b = smallToArray(abs);
}
if (a.length + b.length > 4000) // Karatsuba is only faster for sufficiently large inputs
return new BigInteger(multiplyKaratsuba(a, b), sign);
return new BigInteger(multiplyLong(a, b), sign);
};
BigInteger.prototype.times = BigInteger.prototype.multiply;
BigInteger.prototype.divmod = function (n) {
if (isSmall(n)) return fastDivMod(this, +n);
n = parseInput(n);
var quotientSign = this.sign !== n.sign;
if (n.equals(ZERO)) throw new Error("Cannot divide by zero");
if (this.equals(ZERO)) return {
quotient: new BigInteger([0], sign.positive),
remainder: new BigInteger([0], sign.positive)
};
var a = this.value, b = n.value;
var result = [0];
for (var i = 0; i < b.length; i++) {
result[i] = 0;
SmallInteger.prototype.multiply = function (v) {
var n = parseValue(v),
a = this.value,
b = n.value;
if (a === 0) return CACHE[0];
if (a === 1) return n;
if (a === -1) return n.negate();
if (n.isSmall) {
if (isPrecise(a * b)) {
return new SmallInteger(a * b);
}
b = smallToArray(Math.abs(b));
}
var divisorMostSignificantDigit = b[b.length - 1];
// normalization
var lambda = Math.ceil(base / 2 / divisorMostSignificantDigit);
var remainder = fastMultiplyInternal(a, lambda);
var divisor = fastMultiplyInternal(b, lambda);
divisorMostSignificantDigit = divisor[b.length - 1];
for (var shift = a.length - b.length; shift >= 0; shift--) {
var quotientDigit = base - 1;
if (remainder[shift + b.length] !== divisorMostSignificantDigit) {
quotientDigit = Math.floor((remainder[shift + b.length] * base + remainder[shift + b.length - 1]) / divisorMostSignificantDigit);
var abs = Math.abs(a);
if (abs < BASE) {
return new BigInteger(multiplySmall(b, abs), this.sign !== n.sign);
}
return new BigInteger(multiplyLong(b, smallToArray(abs)), this.sign !== n.sign);
};
SmallInteger.prototype.times = SmallInteger.prototype.multiply;
function square(a) {
var l = a.length,
r = createArray(l + l),
base = BASE,
product, carry, i, a_i, a_j;
for (i = 0; i < l; i++) {
a_i = a[i];
for (var j = 0; j < l; j++) {
a_j = a[j];
product = a_i * a_j + r[i + j];
carry = Math.floor(product / base);
r[i + j] = product - carry * base;
r[i + j + 1] += carry;
}
// remainder -= quotientDigit * divisor
var carry = 0;
var borrow = 0;
for (var i = 0; i < divisor.length; i++) {
}
trim(r);
return r;
}
BigInteger.prototype.square = function () {
return new BigInteger(square(this.value), false);
};
SmallInteger.prototype.square = function () {
var value = this.value * this.value;
if (isPrecise(value)) return new SmallInteger(value);
return new BigInteger(square(smallToArray(Math.abs(this.value))), false);
};
function divMod1(a, b) { // Left over from previous version. Performs faster than divMod2 on smaller input sizes.
var a_l = a.length,
b_l = b.length,
base = BASE,
result = createArray(b.length),
divisorMostSignificantDigit = b[b_l - 1],
// normalization
lambda = Math.ceil(base / (2 * divisorMostSignificantDigit)),
remainder = multiplySmall(a, lambda),
divisor = multiplySmall(b, lambda),
quotientDigit, shift, carry, borrow, i, l, q;
if (remainder.length <= a_l) remainder.push(0);
if (divisor.length <= b_l) divisor.push(0);
divisorMostSignificantDigit = divisor[b_l - 1];
for (shift = a_l - b_l; shift >= 0; shift--) {
quotientDigit = base - 1;
if (remainder[shift + b_l] !== divisorMostSignificantDigit) {
quotientDigit = Math.floor((remainder[shift + b_l] * base + remainder[shift + b_l - 1]) / divisorMostSignificantDigit);
}
carry = 0;
borrow = 0;
l = divisor.length;
for (i = 0; i < l; i++) {
carry += quotientDigit * divisor[i];
var q = Math.floor(carry / base);
q = Math.floor(carry / base);
borrow += remainder[shift + i] - (carry - q * base);
carry = q;
if (borrow < 0) {
remainder[shift + i] = (borrow + base) | 0;
remainder[shift + i] = borrow + base;
borrow = -1;
} else {
remainder[shift + i] = borrow | 0;
remainder[shift + i] = borrow;
borrow = 0;

@@ -223,11 +414,11 @@ }

quotientDigit -= 1;
var carry = 0;
for (var i = 0; i < divisor.length; i++) {
carry = 0;
for (i = 0; i < l; i++) {
carry += remainder[shift + i] - base + divisor[i];
if (carry < 0) {
remainder[shift + i] = (carry + base) | 0;
remainder[shift + i] = carry + base;
carry = 0;
} else {
remainder[shift + i] = carry | 0;
carry = +1;
remainder[shift + i] = carry;
carry = 1;
}

@@ -237,44 +428,174 @@ }

}
result[shift] = quotientDigit | 0;
result[shift] = quotientDigit;
}
// denormalization
remainder = fastDivModInternal(remainder, lambda).quotient;
remainder = divModSmall(remainder, lambda)[0];
return [arrayToSmall(result), arrayToSmall(remainder)];
}
function divMod2(a, b) { // Implementation idea shamelessly stolen from Silent Matt's library http://silentmatt.com/biginteger/
// Performs faster than divMod1 on larger input sizes.
var a_l = a.length,
b_l = b.length,
result = [],
part = [],
base = BASE,
guess, xlen, highx, highy, check;
while (a_l) {
part.unshift(a[--a_l]);
if (compareAbs(part, b) < 0) {
result.push(0);
continue;
}
if (part.length === 1 && part[0] === 0) {
guess = 0;
} else {
xlen = part.length;
highx = part[xlen - 1] * base + part[xlen - 2];
highy = b[b_l - 1] * base + b[b_l - 2];
if (xlen > b_l) {
highx = (highx + 1) * base;
}
guess = Math.ceil(highx / highy);
}
do {
check = multiplySmall(b, guess);
if (compareAbs(check, part) <= 0) break;
guess--;
} while (guess);
result.push(guess);
if (!guess) continue;
part = subtract(part, check);
}
result.reverse();
return [arrayToSmall(result), arrayToSmall(part)];
}
function divModSmall(value, lambda) {
var length = value.length,
quotient = createArray(length),
base = BASE,
i, q, remainder, divisor;
remainder = 0;
for (i = length - 1; i >= 0; --i) {
divisor = remainder * base + value[i];
q = truncate(divisor / lambda);
remainder = divisor - q * lambda;
quotient[i] = q | 0;
}
return [quotient, remainder | 0];
}
function divModAny(self, v) {
var value, n = parseValue(v);
var a = self.value, b = n.value;
var quotient;
if (b === 0) throw new Error("Cannot divide by zero");
if (self.isSmall) {
if (n.isSmall) {
return [new SmallInteger(truncate(a / b)), new SmallInteger(a % b)];
}
return [CACHE[0], self];
}
if (n.isSmall) {
if (b === 1) return [self, CACHE[0]];
if (b == -1) return [self.negate(), CACHE[0]];
var abs = Math.abs(b);
if (abs < BASE) {
value = divModSmall(a, abs);
quotient = arrayToSmall(value[0]);
var remainder = value[1];
if (self.sign) remainder = -remainder;
if (typeof quotient === "number") {
if (self.sign !== n.sign) quotient = -quotient;
return [new SmallInteger(quotient), new SmallInteger(remainder)];
}
return [new BigInteger(quotient, self.sign !== n.sign), new SmallInteger(remainder)];
}
b = smallToArray(abs);
}
var comparison = compareAbs(a, b);
if (comparison === -1) return [CACHE[0], self];
if (comparison === 0) return [CACHE[1], CACHE[0]];
// divMod1 is faster on smaller input sizes
if (a.length + b.length <= 200)
value = divMod1(a, b);
else value = divMod2(a, b);
quotient = value[0];
var qSign = self.sign !== n.sign,
mod = value[1],
mSign = self.sign;
if (typeof quotient === "number") {
if (qSign) quotient = -quotient;
quotient = new SmallInteger(quotient);
} else quotient = new BigInteger(quotient, qSign);
if (typeof mod === "number") {
if (mSign) mod = -mod;
mod = new SmallInteger(mod);
} else mod = new BigInteger(mod, mSign);
return [quotient, mod];
}
BigInteger.prototype.divmod = function (v) {
var result = divModAny(this, v);
return {
quotient: new BigInteger(trim(result), quotientSign),
remainder: new BigInteger(trim(remainder), this.sign)
quotient: result[0],
remainder: result[1]
};
};
BigInteger.prototype.divide = function (n) {
return this.divmod(n).quotient;
SmallInteger.prototype.divmod = BigInteger.prototype.divmod;
BigInteger.prototype.divide = function (v) {
return divModAny(this, v)[0];
};
BigInteger.prototype.over = BigInteger.prototype.divide;
SmallInteger.prototype.over = SmallInteger.prototype.divide = BigInteger.prototype.over = BigInteger.prototype.divide;
BigInteger.prototype.mod = function (n) {
return this.divmod(n).remainder;
BigInteger.prototype.mod = function (v) {
return divModAny(this, v)[1];
};
BigInteger.prototype.remainder = BigInteger.prototype.mod;
SmallInteger.prototype.remainder = SmallInteger.prototype.mod = BigInteger.prototype.remainder = BigInteger.prototype.mod;
BigInteger.prototype.pow = function (n) {
n = parseInput(n);
var a = this, b = n, r = ONE;
if (b.equals(ZERO)) return r;
if (a.equals(ZERO) || b.lesser(ZERO)) return ZERO;
BigInteger.prototype.pow = function (v) {
var n = parseValue(v),
a = this.value,
b = n.value,
value, x, y;
if (b === 0) return CACHE[1];
if (n.sign) {
if (a === 1) return CACHE[1];
if (a === -1) return isEven(n) ? CACHE[1] : CACHE[-1];
return CACHE[0];
}
if (!n.isSmall) throw new Error("The exponent " + n.toString() + " is too large.");
if (this.isSmall) {
if (isPrecise(value = Math.pow(a, b)))
return new SmallInteger(truncate(value));
if (a === 0) return CACHE[0];
if (a === 1) return CACHE[1];
}
x = this;
y = CACHE[1];
while (true) {
if (b.isOdd()) {
r = r.times(a);
if (b & 1 === 1) {
y = y.times(x);
--b;
}
b = b.divide(2);
if (b.equals(ZERO)) break;
a = a.times(a);
if (b === 0) break;
b /= 2;
x = x.square();
}
return r;
return y;
};
SmallInteger.prototype.pow = BigInteger.prototype.pow;
BigInteger.prototype.modPow = function (exp, mod) {
exp = parseInput(exp);
mod = parseInput(mod);
if (mod.equals(ZERO)) throw new Error("Cannot take modPow with modulus 0");
var r = ONE,
exp = parseValue(exp);
mod = parseValue(mod);
if (mod.isZero()) throw new Error("Cannot take modPow with modulus 0");
var r = CACHE[1],
base = this.mod(mod);
if (base.equals(ZERO)) return ZERO;
while (exp.greater(0)) {
if (base.isZero()) return CACHE[0];
while (exp.isPositive()) {
if (exp.isOdd()) r = r.multiply(base).mod(mod);

@@ -286,116 +607,141 @@ exp = exp.divide(2);

};
BigInteger.prototype.square = function () {
return this.multiply(this);
};
function gcd(a, b) {
a = parseInput(a).abs();
b = parseInput(b).abs();
if (a.equals(b)) return a;
if (a.equals(ZERO)) return b;
if (b.equals(ZERO)) return a;
if (a.isEven()) {
if (b.isOdd()) {
return gcd(a.divide(2), b);
}
return gcd(a.divide(2), b.divide(2)).multiply(2);
SmallInteger.prototype.modPow = BigInteger.prototype.modPow;
function compareAbs(a, b) {
if (a.length !== b.length) {
return a.length > b.length ? 1 : -1;
}
if (b.isEven()) {
return gcd(a, b.divide(2));
for (var i = a.length - 1; i >= 0; i--) {
if (a[i] !== b[i]) return a[i] > b[i] ? 1 : -1;
}
if (a.greater(b)) {
return gcd(a.subtract(b).divide(2), b);
}
return gcd(b.subtract(a).divide(2), a);
return 0;
}
function lcm(a, b) {
a = parseInput(a).abs();
b = parseInput(b).abs();
return a.multiply(b).divide(gcd(a, b));
}
BigInteger.prototype.next = function () {
return fastAdd(this, 1);
BigInteger.prototype.compareAbs = function (v) {
var n = parseValue(v),
a = this.value,
b = n.value;
if (n.isSmall) return 1;
return compareAbs(a, b);
};
BigInteger.prototype.prev = function () {
return fastSubtract(this, 1);
SmallInteger.prototype.compareAbs = function (v) {
var n = parseValue(v),
a = Math.abs(this.value),
b = n.value;
if (n.isSmall) {
b = Math.abs(b);
return a === b ? 0 : a > b ? 1 : -1;
}
return -1;
};
BigInteger.prototype.compare = function (n) {
var first = this, second = parseInput(n);
if (first.value.length === 1 && second.value.length === 1 && first.value[0] === 0 && second.value[0] === 0) return 0;
if (second.sign !== first.sign) return first.sign === sign.positive ? 1 : -1;
var multiplier = first.sign === sign.positive ? 1 : -1;
var a = first.value, b = second.value,
length = Math.max(a.length, b.length) - 1;
for (var i = length; i >= 0; i--) {
var ai = (a[i] || 0), bi = (b[i] || 0);
if (ai > bi) return 1 * multiplier;
if (bi > ai) return -1 * multiplier;
BigInteger.prototype.compare = function (v) {
var n = parseValue(v),
a = this.value,
b = n.value;
if (this.sign !== n.sign) {
return n.sign ? 1 : -1;
}
return 0;
if (n.isSmall) {
return this.sign ? -1 : 1;
}
return compareAbs(a, b) * (this.sign ? -1 : 1);
};
BigInteger.prototype.compareTo = BigInteger.prototype.compare;
BigInteger.prototype.compareAbs = function (n) {
return this.abs().compare(n.abs());
SmallInteger.prototype.compare = function (v) {
var n = parseValue(v),
a = this.value,
b = n.value;
if (n.isSmall) {
return a == b ? 0 : a > b ? 1 : -1;
}
if (a < 0 !== n.sign) {
return a < 0 ? -1 : 1;
}
return a < 0 ? 1 : -1;
};
BigInteger.prototype.equals = function (n) {
return this.compare(n) === 0;
SmallInteger.prototype.compareTo = SmallInteger.prototype.compare;
BigInteger.prototype.equals = function (v) {
return this.compare(v) === 0;
};
BigInteger.prototype.notEquals = function (n) {
return !this.equals(n);
SmallInteger.prototype.eq = SmallInteger.prototype.equals = BigInteger.prototype.eq = BigInteger.prototype.equals;
BigInteger.prototype.notEquals = function (v) {
return this.compare(v) !== 0;
};
BigInteger.prototype.lesser = function (n) {
return this.compare(n) < 0;
SmallInteger.prototype.neq = SmallInteger.prototype.notEquals = BigInteger.prototype.neq = BigInteger.prototype.notEquals;
BigInteger.prototype.greater = function (v) {
return this.compare(v) > 0;
};
BigInteger.prototype.greater = function (n) {
return this.compare(n) > 0;
SmallInteger.prototype.gt = SmallInteger.prototype.greater = BigInteger.prototype.gt = BigInteger.prototype.greater;
BigInteger.prototype.lesser = function (v) {
return this.compare(v) < 0;
};
BigInteger.prototype.greaterOrEquals = function (n) {
return this.compare(n) >= 0;
SmallInteger.prototype.lt = SmallInteger.prototype.lesser = BigInteger.prototype.lt = BigInteger.prototype.lesser;
BigInteger.prototype.greaterOrEquals = function (v) {
return this.compare(v) >= 0;
};
BigInteger.prototype.lesserOrEquals = function (n) {
return this.compare(n) <= 0;
SmallInteger.prototype.geq = SmallInteger.prototype.greaterOrEquals = BigInteger.prototype.geq = BigInteger.prototype.greaterOrEquals;
BigInteger.prototype.lesserOrEquals = function (v) {
return this.compare(v) <= 0;
};
SmallInteger.prototype.leq = SmallInteger.prototype.lesserOrEquals = BigInteger.prototype.leq = BigInteger.prototype.lesserOrEquals;
BigInteger.prototype.compareTo = BigInteger.prototype.compare;
BigInteger.prototype.lt = BigInteger.prototype.lesser;
BigInteger.prototype.leq = BigInteger.prototype.lesserOrEquals;
BigInteger.prototype.gt = BigInteger.prototype.greater;
BigInteger.prototype.geq = BigInteger.prototype.greaterOrEquals;
BigInteger.prototype.eq = BigInteger.prototype.equals;
BigInteger.prototype.neq = BigInteger.prototype.notEquals;
BigInteger.prototype.isEven = function () {
return (this.value[0] & 1) === 0;
};
SmallInteger.prototype.isEven = function () {
return (this.value & 1) === 0;
};
function max (a, b) {
a = parseInput(a);
b = parseInput(b);
return a.greater(b) ? a : b;
}
function min (a, b) {
a = parseInput(a);
b = parseInput(b);
return a.lesser(b) ? a : b;
}
BigInteger.prototype.isOdd = function () {
return (this.value[0] & 1) === 1;
};
SmallInteger.prototype.isOdd = function () {
return (this.value & 1) === 1;
};
BigInteger.prototype.isPositive = function () {
if (this.value.length === 1 && this.value[0] === 0) return false;
return this.sign === sign.positive;
return !this.sign;
};
SmallInteger.prototype.isPositive = function () {
return this.value > 0;
};
BigInteger.prototype.isNegative = function () {
if (this.value.length === 1 && this.value[0] === 0) return false;
return this.sign === sign.negative;
return this.sign;
};
BigInteger.prototype.isEven = function () {
return this.value[0] % 2 === 0;
SmallInteger.prototype.isNegative = function () {
return this.value < 0;
};
BigInteger.prototype.isOdd = function () {
return this.value[0] % 2 === 1;
};
BigInteger.prototype.isUnit = function () {
return this.value.length === 1 && this.value[0] === 1;
return false;
};
SmallInteger.prototype.isUnit = function () {
return Math.abs(this.value) === 1;
};
BigInteger.prototype.isZero = function () {
return this.value.length === 1 && this.value[0] === 0;
return false;
};
BigInteger.prototype.isDivisibleBy = function (n) {
n = parseInput(n);
if (n.isZero()) return false;
return this.mod(n).equals(ZERO);
SmallInteger.prototype.isZero = function () {
return this.value === 0;
};
BigInteger.prototype.isDivisibleBy = function (v) {
var n = parseValue(v);
var value = n.value;
if (value === 0) return false;
if (value === 1) return true;
if (value === 2) return this.isEven();
return this.mod(n).equals(CACHE[0]);
};
SmallInteger.prototype.isDivisibleBy = BigInteger.prototype.isDivisibleBy;
BigInteger.prototype.isPrime = function () {

@@ -414,4 +760,4 @@ var n = this.abs(),

x = bigInt(a[i]).modPow(b, n);
if (x.equals(ONE) || x.equals(nPrev)) continue;
for (t = true, d = b; t && d.lesser(nPrev); d = d.multiply(2)) {
if (x.equals(CACHE[1]) || x.equals(nPrev)) continue;
for (t = true, d = b; t && d.lesser(nPrev) ; d = d.multiply(2)) {
x = x.square().mod(n);

@@ -424,26 +770,43 @@ if (x.equals(nPrev)) t = false;

};
function randBetween (a, b) {
a = parseInput(a);
b = parseInput(b);
var low = min(a, b), high = max(a, b);
var range = high.subtract(low);
var length = range.value.length - 1;
var result = [], restricted = true;
for (var i = length; i >= 0; i--) {
var top = restricted ? range.value[i] : base;
var digit = Math.floor(Math.random() * top);
result.unshift(digit);
if (digit < top) restricted = false;
SmallInteger.prototype.isPrime = BigInteger.prototype.isPrime;
BigInteger.prototype.next = function () {
var value = this.value;
if (this.sign) {
return subtractSmall(value, 1, this.sign);
}
return low.add(new BigInteger(result, false));
}
return new BigInteger(addSmall(value, 1), this.sign);
};
SmallInteger.prototype.next = function () {
var value = this.value;
if (value + 1 < MAX_INT) return new SmallInteger(value + 1);
return new BigInteger(MAX_INT_ARR, false);
};
BigInteger.prototype.prev = function () {
var value = this.value;
if (this.sign) {
return new BigInteger(addSmall(value, 1), true);
}
return subtractSmall(value, 1, this.sign);
};
SmallInteger.prototype.prev = function () {
var value = this.value;
if (value - 1 > -MAX_INT) return new SmallInteger(value - 1);
return new BigInteger(MAX_INT_ARR, true);
};
var powersOfTwo = [1];
while (powersOfTwo[powersOfTwo.length - 1] <= base) powersOfTwo.push(2 * powersOfTwo[powersOfTwo.length - 1]);
while (powersOfTwo[powersOfTwo.length - 1] <= BASE) powersOfTwo.push(2 * powersOfTwo[powersOfTwo.length - 1]);
var powers2Length = powersOfTwo.length, highestPower2 = powersOfTwo[powers2Length - 1];
function shift_isSmall(n) {
return ((typeof n === "number" || typeof n === "string") && +Math.abs(n) <= BASE) ||
(n instanceof BigInteger && n.value.length <= 1);
}
BigInteger.prototype.shiftLeft = function (n) {
if (!isSmall(n)) {
if (!shift_isSmall(n)) {
if (n.isNegative()) return this.shiftRight(n.abs());
return this.times(bigInt(2).pow(n));
return this.times(CACHE[2].pow(n));
}

@@ -454,14 +817,15 @@ n = +n;

while (n >= powers2Length) {
result = fastMultiply(result, highestPower2);
result = result.multiply(highestPower2);
n -= powers2Length - 1;
}
return fastMultiply(result, powersOfTwo[n]);
return result.multiply(powersOfTwo[n]);
};
SmallInteger.prototype.shiftLeft = BigInteger.prototype.shiftLeft;
BigInteger.prototype.shiftRight = function (n) {
var remQuo = undefined;
if (!isSmall(n)) {
var remQuo;
if (!shift_isSmall(n)) {
if (n.isNegative()) return this.shiftLeft(n.abs());
remQuo = this.divmod(bigInt(2).pow(n));
return remQuo.remainder.compareTo(ZERO) < 0 ? remQuo.quotient.subtract(ONE) : remQuo.quotient;
remQuo = this.divmod(CACHE[2].pow(n));
return remQuo.remainder.isNegative() ? remQuo.quotient.prev() : remQuo.quotient;
}

@@ -472,13 +836,14 @@ n = +n;

while (n >= powers2Length) {
if (result.equals(ZERO)) return result;
remQuo = fastDivMod(result, highestPower2);
result = remQuo.remainder.compareTo(ZERO) < 0 ? remQuo.quotient.subtract(ONE) : remQuo.quotient;
if (result.isZero()) return result;
remQuo = divModAny(result, highestPower2);
result = remQuo[1].isNegative() ? remQuo.quotient.prev() : remQuo[0];
n -= powers2Length - 1;
}
remQuo = fastDivMod(result, powersOfTwo[n]);
return remQuo.remainder.compareTo(ZERO) < 0 ? remQuo.quotient.subtract(ONE) : remQuo.quotient;
remQuo = divModAny(result, powersOfTwo[n]);
return remQuo[1].isNegative() ? remQuo[0].prev() : remQuo[0];
};
SmallInteger.prototype.shiftRight = BigInteger.prototype.shiftRight;
function bitwise(x, y, fn) {
y = parseInput(y);
y = parseValue(y);
var xSign = x.isNegative(), ySign = y.isNegative();

@@ -517,8 +882,10 @@ var xRem = xSign ? x.not() : x,

BigInteger.prototype.not = function () {
return this.negate().minus(1);
return this.negate().prev();
};
SmallInteger.prototype.not = BigInteger.prototype.not;
BigInteger.prototype.and = function (n) {
return bitwise(this, n, function (a, b) { return a & b });
return bitwise(this, n, function (a, b) { return a & b; });
};
SmallInteger.prototype.and = BigInteger.prototype.and;

@@ -528,107 +895,90 @@ BigInteger.prototype.or = function (n) {

};
SmallInteger.prototype.or = BigInteger.prototype.or;
BigInteger.prototype.xor = function (n) {
return bitwise(this, n, function (a, b) { return a ^ b });
return bitwise(this, n, function (a, b) { return a ^ b; });
};
SmallInteger.prototype.xor = BigInteger.prototype.xor;
BigInteger.prototype.toString = function (radix) {
if (radix === undefined) {
radix = 10;
function max(a, b) {
a = parseValue(a);
b = parseValue(b);
return a.greater(b) ? a : b;
}
function min(a,b) {
a = parseValue(a);
b = parseValue(b);
return a.lesser(b) ? a : b;
}
function gcd(a, b) {
a = parseValue(a).abs();
b = parseValue(b).abs();
if (a.equals(b)) return a;
if (a.isZero()) return b;
if (b.isZero()) return a;
if (a.isEven()) {
if (b.isOdd()) {
return gcd(a.divide(2), b);
}
return gcd(a.divide(2), b.divide(2)).multiply(2);
}
if (radix !== 10) return toBase(this, radix);
var first = this;
var str = "", len = first.value.length;
if (len === 0 || (len === 1 && first.value[0] === 0)) {
return "0";
if (b.isEven()) {
return gcd(a, b.divide(2));
}
len -= 1;
str = first.value[len].toString();
while (--len >= 0) {
var digit = first.value[len].toString();
str += zeros.slice(digit.length) + digit;
if (a.greater(b)) {
return gcd(a.subtract(b).divide(2), b);
}
var s = first.sign === sign.positive ? "" : "-";
return s + str;
};
BigInteger.prototype.toJSNumber = function () {
return this.valueOf();
};
BigInteger.prototype.valueOf = function () {
if (this.value.length === 1) return this.sign ? -this.value[0] : this.value[0];
return +this.toString();
};
var ZERO = new BigInteger([0], sign.positive);
var ONE = new BigInteger([1], sign.positive);
var MINUS_ONE = new BigInteger([1], sign.negative);
function parseInput(text) {
if (text instanceof BigInteger) return text;
if (Math.abs(+text) < base && +text === (+text | 0)) {
var value = +text;
return new BigInteger([Math.abs(value)], (value < 0 || (1 / value) === -Infinity));
return gcd(b.subtract(a).divide(2), a);
}
function lcm(a, b) {
a = parseValue(a).abs();
b = parseValue(b).abs();
return a.multiply(b).divide(gcd(a, b));
}
function randBetween(a, b) {
a = parseValue(a);
b = parseValue(b);
if (a.isSmall) a = smallToArray(a);
if (b.isSmall) b = smallToArray(b);
var low = min(a, b), high = max(a, b);
var range = high.subtract(low);
var length = range.value.length - 1;
var result = [], restricted = true;
for (var i = length; i >= 0; i--) {
var top = restricted ? range.value[i] : BASE;
var digit = truncate(Math.random() * top);
result.unshift(digit);
if (digit < top) restricted = false;
}
text += "";
var s = sign.positive, value = [];
if (text[0] === "-") {
s = sign.negative;
text = text.slice(1);
}
var text = text.split(/e/i);
if (text.length > 2) throw new Error("Invalid integer: " + text.join("e"));
if (text[1]) {
var exp = text[1];
if (exp[0] === "+") exp = exp.slice(1);
exp = parseInput(exp);
var decimalPlace = text[0].indexOf(".");
if (decimalPlace >= 0) {
exp = exp.minus(text[0].length - decimalPlace);
text[0] = text[0].slice(0, decimalPlace) + text[0].slice(decimalPlace + 1);
result = arrayToSmall(result);
return low.add(new BigInteger(result, false, typeof result === "number"));
}
var parseBase = function (text, base) {
var val = CACHE[0], pow = CACHE[1],
length = text.length;
if (2 <= base && base <= 36) {
if (length <= LOG_MAX_INT / Math.log(base)) {
return parseInt(text, base);
}
if (exp.lesser(0)) throw new Error("Cannot include negative exponent part for integers");
while (exp.notEquals(0)) {
text[0] += "0";
exp = exp.prev();
}
}
text = text[0];
if (text === "-0") text = "0";
var isValid = /^([0-9][0-9]*)$/.test(text);
if (!isValid) throw new Error("Invalid integer: " + text);
while (text.length) {
var divider = text.length > logBase ? text.length - logBase : 0;
value.push(+text.slice(divider));
text = text.slice(0, divider);
}
return new BigInteger(trim(value), s);
}
var parseBase = function (text, base) {
base = parseInput(base);
var val = ZERO;
base = parseValue(base);
var digits = [];
var i;
var isNegative = false;
function parseToken(text) {
var c = text[i].toLowerCase();
if (i === 0 && text[i] === "-") {
isNegative = true;
return;
}
if (/[0-9]/.test(c)) digits.push(parseInput(c));
else if (/[a-z]/.test(c)) digits.push(parseInput(c.charCodeAt(0) - 87));
var isNegative = text[0] === "-";
for (i = isNegative ? 1 : 0; i < text.length; i++) {
var c = text[i].toLowerCase(),
charCode = c.charCodeAt(0);
if (48 <= charCode && charCode <= 57) digits.push(parseValue(c));
else if (97 <= charCode && charCode <= 122) digits.push(parseValue(c.charCodeAt(0) - 87));
else if (c === "<") {
var start = i;
do { i++; } while (text[i] !== ">");
digits.push(parseInput(text.slice(start + 1, i)));
digits.push(parseValue(text.slice(start + 1, i)));
}
else throw new Error(c + " is not a valid character");
}
for (i = 0; i < text.length; i++) {
parseToken(text);
}
digits.reverse();
for (i = 0; i < digits.length; i++) {
val = val.add(digits[i].times(base.pow(i)));
val = val.add(digits[i].times(pow));
pow = pow.times(base);
}

@@ -640,2 +990,3 @@ return isNegative ? val.negate() : val;

var v = digit.value;
if (typeof v === "number") v = [v];
if (v.length === 1 && v[0] <= 36) {

@@ -646,13 +997,12 @@ return "0123456789abcdefghijklmnopqrstuvwxyz".charAt(v[0]);

}
function toBase(n, base) {
base = bigInt(base);
if (base.equals(0)) {
if (n.equals(0)) return "0";
if (base.isZero()) {
if (n.isZero()) return "0";
throw new Error("Cannot convert nonzero numbers to base 0.");
}
if (base.equals(-1)) {
if (n.equals(0)) return "0";
if (n.lesser(0)) return Array(1 - n).join("10");
return "1" + Array(+n).join("01");
if (n.isZero()) return "0";
if (n.isNegative()) return new Array(1 - n).join("10");
return "1" + new Array(+n).join("01");
}

@@ -665,12 +1015,12 @@ var minusSign = "";

if (base.equals(1)) {
if (n.equals(0)) return "0";
return minusSign + Array(+n + 1).join(1);
if (n.isZero()) return "0";
return minusSign + new Array(+n + 1).join(1);
}
var out = [];
var left = n, divmod;
while (left.lesser(0) || left.compareAbs(base) >= 0) {
while (left.isNegative() || left.compareAbs(base) >= 0) {
divmod = left.divmod(base);
left = divmod.quotient;
var digit = divmod.remainder;
if (digit.lesser(0)) {
if (digit.isNegative()) {
digit = base.minus(digit).abs();

@@ -685,21 +1035,95 @@ left = left.next();

var fnReturn = function (a, b) {
if (typeof a === "undefined") return ZERO;
if (typeof b !== "undefined") return parseBase(a, b);
return parseInput(a);
BigInteger.prototype.toString = function (radix) {
if (radix === undefined) radix = 10;
if (radix !== 10) return toBase(this, radix);
var v = this.value, l = v.length, str = String(v[--l]), zeros = "0000000", digit;
while (--l >= 0) {
digit = String(v[l]);
str += zeros.slice(digit.length) + digit;
}
var sign = this.sign ? "-" : "";
return sign + str;
};
fnReturn.zero = ZERO;
fnReturn.one = ONE;
fnReturn.minusOne = MINUS_ONE;
fnReturn.randBetween = randBetween;
fnReturn.isInstance = function (x) { return x instanceof BigInteger; };
fnReturn.min = min;
fnReturn.max = max;
fnReturn.gcd = gcd;
fnReturn.lcm = lcm;
return fnReturn;
SmallInteger.prototype.toString = function (radix) {
if (radix === undefined) radix = 10;
if (radix != 10) return toBase(this, radix);
return String(this.value);
};
BigInteger.prototype.valueOf = function () {
if (this.isSmall) return this.value;
return +this.toString();
};
BigInteger.prototype.toJSNumber = BigInteger.prototype.valueOf;
function parseValue(v) {
if (v instanceof BigInteger || v instanceof SmallInteger) return v;
if (typeof v === "number") {
if (isPrecise(v)) return new SmallInteger(v);
v = String(v);
}
if (typeof v === "string") {
if (isPrecise(+v)) {
var x = +v;
if (x === truncate(x))
return new SmallInteger(x);
throw "Invalid integer: " + v;
}
var sign = v[0] === "-";
if (sign) v = v.slice(1);
var split = v.split(/e/i);
if (split.length > 2) throw new Error("Invalid integer: " + text.join("e"));
if (split.length === 2) {
var exp = split[1];
if (exp[0] === "+") exp = exp.slice(1);
exp = +exp;
if (exp !== truncate(exp) || !isPrecise(exp)) throw new Error("Invalid integer: " + exp + " is not a valid exponent.");
var text = split[0];
var decimalPlace = text.indexOf(".");
if (decimalPlace >= 0) {
exp -= text.length - decimalPlace;
text = text.slice(0, decimalPlace) + text.slice(decimalPlace + 1);
}
if (exp < 0) throw new Error("Cannot include negative exponent part for integers");
text += (new Array(exp + 1)).join("0");
v = text;
}
var isValid = /^([0-9][0-9]*)$/.test(v);
if (!isValid) throw new Error("Invalid integer: " + v);
var r = [], max = v.length, l = LOG_BASE, min = max - l;
while (max > 0) {
r.push(+v.slice(min, max));
min -= l;
if (min < 0) min = 0;
max -= l;
}
trim(r);
return new BigInteger(r, sign);
}
}
// Pre-define numbers in range [-999,999]
var CACHE = function (v, radix) {
if (typeof v === "undefined") return CACHE[0];
if (typeof radix !== "undefined") return +radix === 10 ? parseValue(v) : parseBase(v, radix);
return parseValue(v);
};
for (var i = 0; i < 1000; i++) {
CACHE[i] = new SmallInteger(i);
if (i > 0) CACHE[-i] = new SmallInteger(-i);
}
// Backwards compatibility
CACHE.one = CACHE[1];
CACHE.zero = CACHE[0];
CACHE.minusOne = CACHE[-1];
CACHE.max = max;
CACHE.min = min;
CACHE.gcd = gcd;
CACHE.lcm = lcm;
CACHE.isInstance = function (x) { return x instanceof BigInteger || x instanceof SmallInteger; };
return CACHE;
})();
// Node.js check
if (typeof module !== "undefined") {
module.exports = bigInt;
}
}

2

BigInteger.min.js

@@ -1,1 +0,1 @@

"use strict";var bigInt=function(){function i(e,t){this.value=e,this.sign=t}function s(e){while(e[e.length-1]===0&&e.length>1)e.pop();return e}function o(t,n){var r=n<0;if(t.sign!==r)return r?u(t.abs(),-n):u(t.abs(),n).negate();r&&(n=-n);var o=t.value,a=[],f=0;for(var l=0;l<o.length||f>0;l++){var c=(o[l]||0)+(l>0?0:n)+f;f=c>=e?1:0,a.push(c%e)}return new i(s(a),t.sign)}function u(t,n){var r=t.value;if(r.length===1)return r=r[0],t.sign&&(r=-r),new i([Math.abs(r-n)],r-n<0);if(t.sign!==n<0)return o(t,-n);var u=!1;t.sign&&(u=!0);if(r.length===1&&r[0]<n)return new i([n-r[0]],!u);u&&(n=-n);var a=[],f=0;for(var l=0;l<r.length;l++){var c=r[l]-f-(l>0?0:n);f=c<0?1:0,a.push(f*e+c)}return new i(s(a),u)}function a(t,n){var r=[],i=0;for(var s=0;s<t.length;s++){i+=n*t[s];var o=Math.floor(i/e);r[s]=i-o*e|0,i=o}return r[t.length]=i|0,r}function f(e,t){var n=a(e.value,t<0?-t:t);return new i(s(n),t<0?!e.sign:e.sign)}function l(t,n){var r=[];for(var i=0;i<t.length;i++)r[i]=0;var s=0;for(var i=t.length-1;i>=0;i--){var o=s*e+t[i],u=Math.floor(o/n);s=o-u*n,r[i]=u|0}return{quotient:r,remainder:s|0}}function c(e,t){if(t===0)throw new Error("Cannot divide by zero.");var n=l(e.value,t<0?-t:t);return{quotient:new i(s(n.quotient),t<0?!e.sign:e.sign),remainder:new i([n.remainder],e.sign)}}function h(t){return(typeof t=="number"||typeof t=="string")&&+Math.abs(t)<=e||t instanceof i&&t.value.length<=1}function p(e,t){return e=N(e).abs(),t=N(t).abs(),e.equals(t)?e:e.equals(S)?t:t.equals(S)?e:e.isEven()?t.isOdd()?p(e.divide(2),t):p(e.divide(2),t.divide(2)).multiply(2):t.isEven()?p(e,t.divide(2)):e.greater(t)?p(e.subtract(t).divide(2),t):p(t.subtract(e).divide(2),e)}function d(e,t){return e=N(e).abs(),t=N(t).abs(),e.multiply(t).divide(p(e,t))}function v(e,t){return e=N(e),t=N(t),e.greater(t)?e:t}function m(e,t){return e=N(e),t=N(t),e.lesser(t)?e:t}function g(t,n){t=N(t),n=N(n);var r=m(t,n),s=v(t,n),o=s.subtract(r),u=o.value.length-1,a=[],f=!0;for(var l=u;l>=0;l--){var c=f?o.value[l]:e,h=Math.floor(Math.random()*c);a.unshift(h),h<c&&(f=!1)}return r.add(new i(a,!1))}function E(e,t,n){t=N(t);var r=e.isNegative(),i=t.isNegative(),s=r?e.not():e,o=i?t.not():t,u=[],a=[],f=!1,l=!1;while(!f||!l)s.isZero()?(f=!0,u.push(r?1:0)):r?u.push(s.isEven()?1:0):u.push(s.isEven()?0:1),o.isZero()?(l=!0,a.push(i?1:0)):i?a.push(o.isEven()?1:0):a.push(o.isEven()?0:1),s=s.over(2),o=o.over(2);var c=[];for(var h=0;h<u.length;h++)c.push(n(u[h],a[h]));var p=bigInt(c.pop()).negate().times(bigInt(2).pow(c.length));while(c.length)p=p.add(bigInt(c.pop()).times(bigInt(2).pow(c.length)));return p}function N(n){if(n instanceof i)return n;if(Math.abs(+n)<e&&+n===(+n|0)){var o=+n;return new i([Math.abs(o)],o<0||1/o===-Infinity)}n+="";var u=r.positive,o=[];n[0]==="-"&&(u=r.negative,n=n.slice(1));var n=n.split(/e/i);if(n.length>2)throw new Error("Invalid integer: "+n.join("e"));if(n[1]){var a=n[1];a[0]==="+"&&(a=a.slice(1)),a=N(a);var f=n[0].indexOf(".");f>=0&&(a=a.minus(n[0].length-f),n[0]=n[0].slice(0,f)+n[0].slice(f+1));if(a.lesser(0))throw new Error("Cannot include negative exponent part for integers");while(a.notEquals(0))n[0]+="0",a=a.prev()}n=n[0],n==="-0"&&(n="0");var l=/^([0-9][0-9]*)$/.test(n);if(!l)throw new Error("Invalid integer: "+n);while(n.length){var c=n.length>t?n.length-t:0;o.push(+n.slice(c)),n=n.slice(0,c)}return new i(s(o),u)}function k(e){var t=e.value;return t.length===1&&t[0]<=36?"0123456789abcdefghijklmnopqrstuvwxyz".charAt(t[0]):"<"+t+">"}function L(e,t){t=bigInt(t);if(t.equals(0)){if(e.equals(0))return"0";throw new Error("Cannot convert nonzero numbers to base 0.")}if(t.equals(-1))return e.equals(0)?"0":e.lesser(0)?Array(1-e).join("10"):"1"+Array(+e).join("01");var n="";e.isNegative()&&t.isPositive()&&(n="-",e=e.abs());if(t.equals(1))return e.equals(0)?"0":n+Array(+e+1).join(1);var r=[],i=e,s;while(i.lesser(0)||i.compareAbs(t)>=0){s=i.divmod(t),i=s.quotient;var o=s.remainder;o.lesser(0)&&(o=t.minus(o).abs(),i=i.next()),r.push(k(o))}return r.push(k(i)),n+r.reverse().join("")}var e=1e7,t=7,n="0000000",r={positive:!1,negative:!0};i.prototype.negate=function(){return new i(this.value,!this.sign)},i.prototype.abs=function(){return new i(this.value,r.positive)},i.prototype.add=function(t){if(h(t))return o(this,+t);t=N(t);if(this.sign!==t.sign)return this.sign===r.positive?this.abs().subtract(t.abs()):t.abs().subtract(this.abs());var n=this.value,u=t.value,a=[],f=0,l=Math.max(n.length,u.length);for(var c=0;c<l||f>0;c++){var p=(n[c]||0)+(u[c]||0)+f;f=p>=e?1:0,a.push(p%e)}return new i(s(a),this.sign)},i.prototype.plus=i.prototype.add,i.prototype.subtract=function(t){if(h(t))return u(this,+t);t=N(t);if(this.sign!==t.sign)return this.add(t.negate());if(this.sign===r.negative)return t.negate().subtract(this.negate());if(this.compare(t)<0)return t.subtract(this).negate();var n=this.value,o=t.value,a=[],f=0,l=Math.max(n.length,o.length);for(var c=0;c<l;c++){var p=n[c]||0,d=o[c]||0,v=p-f;f=v<d?1:0,a.push(f*e+v-d)}return new i(s(a),r.positive)},i.prototype.minus=i.prototype.subtract,i.prototype.multiply=function(t){if(h(t))return f(this,+t);t=N(t);var n=this.sign!==t.sign,r=this.value,o=t.value,u=[];for(var a=r.length+o.length;a>0;a--)u.push(0);for(var a=0;a<r.length;a++){var l=r[a];for(var c=0;c<o.length;c++){var p=o[c],d=l*p+u[a+c],v=Math.floor(d/e);u[a+c]=d-v*e,u[a+c+1]+=v}}return new i(s(u),n)},i.prototype.times=i.prototype.multiply,i.prototype.divmod=function(t){if(h(t))return c(this,+t);t=N(t);var n=this.sign!==t.sign;if(t.equals(S))throw new Error("Cannot divide by zero");if(this.equals(S))return{quotient:new i([0],r.positive),remainder:new i([0],r.positive)};var o=this.value,u=t.value,f=[0];for(var p=0;p<u.length;p++)f[p]=0;var d=u[u.length-1],v=Math.ceil(e/2/d),m=a(o,v),g=a(u,v);d=g[u.length-1];for(var y=o.length-u.length;y>=0;y--){var b=e-1;m[y+u.length]!==d&&(b=Math.floor((m[y+u.length]*e+m[y+u.length-1])/d));var w=0,E=0;for(var p=0;p<g.length;p++){w+=b*g[p];var x=Math.floor(w/e);E+=m[y+p]-(w-x*e),w=x,E<0?(m[y+p]=E+e|0,E=-1):(m[y+p]=E|0,E=0)}while(E!==0){b-=1;var w=0;for(var p=0;p<g.length;p++)w+=m[y+p]-e+g[p],w<0?(m[y+p]=w+e|0,w=0):(m[y+p]=w|0,w=1);E+=w}f[y]=b|0}return m=l(m,v).quotient,{quotient:new i(s(f),n),remainder:new i(s(m),this.sign)}},i.prototype.divide=function(e){return this.divmod(e).quotient},i.prototype.over=i.prototype.divide,i.prototype.mod=function(e){return this.divmod(e).remainder},i.prototype.remainder=i.prototype.mod,i.prototype.pow=function(e){e=N(e);var t=this,n=e,r=x;if(n.equals(S))return r;if(t.equals(S)||n.lesser(S))return S;for(;;){n.isOdd()&&(r=r.times(t)),n=n.divide(2);if(n.equals(S))break;t=t.times(t)}return r},i.prototype.modPow=function(e,t){e=N(e),t=N(t);if(t.equals(S))throw new Error("Cannot take modPow with modulus 0");var n=x,r=this.mod(t);if(r.equals(S))return S;while(e.greater(0))e.isOdd()&&(n=n.multiply(r).mod(t)),e=e.divide(2),r=r.square().mod(t);return n},i.prototype.square=function(){return this.multiply(this)},i.prototype.next=function(){return o(this,1)},i.prototype.prev=function(){return u(this,1)},i.prototype.compare=function(e){var t=this,n=N(e);if(t.value.length===1&&n.value.length===1&&t.value[0]===0&&n.value[0]===0)return 0;if(n.sign!==t.sign)return t.sign===r.positive?1:-1;var i=t.sign===r.positive?1:-1,s=t.value,o=n.value,u=Math.max(s.length,o.length)-1;for(var a=u;a>=0;a--){var f=s[a]||0,l=o[a]||0;if(f>l)return 1*i;if(l>f)return-1*i}return 0},i.prototype.compareAbs=function(e){return this.abs().compare(e.abs())},i.prototype.equals=function(e){return this.compare(e)===0},i.prototype.notEquals=function(e){return!this.equals(e)},i.prototype.lesser=function(e){return this.compare(e)<0},i.prototype.greater=function(e){return this.compare(e)>0},i.prototype.greaterOrEquals=function(e){return this.compare(e)>=0},i.prototype.lesserOrEquals=function(e){return this.compare(e)<=0},i.prototype.compareTo=i.prototype.compare,i.prototype.lt=i.prototype.lesser,i.prototype.leq=i.prototype.lesserOrEquals,i.prototype.gt=i.prototype.greater,i.prototype.geq=i.prototype.greaterOrEquals,i.prototype.eq=i.prototype.equals,i.prototype.neq=i.prototype.notEquals,i.prototype.isPositive=function(){return this.value.length===1&&this.value[0]===0?!1:this.sign===r.positive},i.prototype.isNegative=function(){return this.value.length===1&&this.value[0]===0?!1:this.sign===r.negative},i.prototype.isEven=function(){return this.value[0]%2===0},i.prototype.isOdd=function(){return this.value[0]%2===1},i.prototype.isUnit=function(){return this.value.length===1&&this.value[0]===1},i.prototype.isZero=function(){return this.value.length===1&&this.value[0]===0},i.prototype.isDivisibleBy=function(e){return e=N(e),e.isZero()?!1:this.mod(e).equals(S)},i.prototype.isPrime=function(){var e=this.abs(),t=e.prev();if(e.isUnit())return!1;if(e.equals(2)||e.equals(3)||e.equals(5))return!0;if(e.isEven()||e.isDivisibleBy(3)||e.isDivisibleBy(5))return!1;if(e.lesser(25))return!0;var n=[2,3,5,7,11,13,17,19],r=t,i,s,o,u;while(r.isEven())r=r.divide(2);for(o=0;o<n.length;o++){u=bigInt(n[o]).modPow(r,e);if(u.equals(x)||u.equals(t))continue;for(s=!0,i=r;s&&i.lesser(t);i=i.multiply(2))u=u.square().mod(e),u.equals(t)&&(s=!1);if(s)return!1}return!0};var y=[1];while(y[y.length-1]<=e)y.push(2*y[y.length-1]);var b=y.length,w=y[b-1];i.prototype.shiftLeft=function(e){if(!h(e))return e.isNegative()?this.shiftRight(e.abs()):this.times(bigInt(2).pow(e));e=+e;if(e<0)return this.shiftRight(-e);var t=this;while(e>=b)t=f(t,w),e-=b-1;return f(t,y[e])},i.prototype.shiftRight=function(e){var t=undefined;if(!h(e))return e.isNegative()?this.shiftLeft(e.abs()):(t=this.divmod(bigInt(2).pow(e)),t.remainder.compareTo(S)<0?t.quotient.subtract(x):t.quotient);e=+e;if(e<0)return this.shiftLeft(-e);var n=this;while(e>=b){if(n.equals(S))return n;t=c(n,w),n=t.remainder.compareTo(S)<0?t.quotient.subtract(x):t.quotient,e-=b-1}return t=c(n,y[e]),t.remainder.compareTo(S)<0?t.quotient.subtract(x):t.quotient},i.prototype.not=function(){return this.negate().minus(1)},i.prototype.and=function(e){return E(this,e,function(e,t){return e&t})},i.prototype.or=function(e){return E(this,e,function(e,t){return e|t})},i.prototype.xor=function(e){return E(this,e,function(e,t){return e^t})},i.prototype.toString=function(e){e===undefined&&(e=10);if(e!==10)return L(this,e);var t=this,i="",s=t.value.length;if(s===0||s===1&&t.value[0]===0)return"0";s-=1,i=t.value[s].toString();while(--s>=0){var o=t.value[s].toString();i+=n.slice(o.length)+o}var u=t.sign===r.positive?"":"-";return u+i},i.prototype.toJSNumber=function(){return this.valueOf()},i.prototype.valueOf=function(){return this.value.length===1?this.sign?-this.value[0]:this.value[0]:+this.toString()};var S=new i([0],r.positive),x=new i([1],r.positive),T=new i([1],r.negative),C=function(e,t){function o(e){var t=e[i].toLowerCase();if(i===0&&e[i]==="-"){s=!0;return}if(/[0-9]/.test(t))r.push(N(t));else if(/[a-z]/.test(t))r.push(N(t.charCodeAt(0)-87));else{if(t!=="<")throw new Error(t+" is not a valid character");var n=i;do i++;while(e[i]!==">");r.push(N(e.slice(n+1,i)))}}t=N(t);var n=S,r=[],i,s=!1;for(i=0;i<e.length;i++)o(e);r.reverse();for(i=0;i<r.length;i++)n=n.add(r[i].times(t.pow(i)));return s?n.negate():n},A=function(e,t){return typeof e=="undefined"?S:typeof t!="undefined"?C(e,t):N(e)};return A.zero=S,A.one=x,A.minusOne=T,A.randBetween=g,A.isInstance=function(e){return e instanceof i},A.min=m,A.max=v,A.gcd=p,A.lcm=d,A}();typeof module!="undefined"&&(module.exports=bigInt);
var bigInt=function(e){"use strict";function o(e,t){this.value=e,this.sign=t,this.isSmall=!1}function u(e){this.value=e,this.sign=e<0,this.isSmall=!0}function a(e){return-r<e&&e<r}function f(e){return e<1e7?[e]:e<1e14?[e%1e7,Math.floor(e/1e7)]:[e%1e7,Math.floor(e/1e7)%1e7,Math.floor(e/1e14)]}function l(e){c(e);var n=e.length;return n<4&&A(e,i)<0?n<2?e[0]:n<3?e[0]+e[1]*t:e[0]+(e[1]+e[2]*t)*t:e}function c(e){var t=e.length;while(e[--t]===0);e.length=t+1}function h(e){var t=new Array(e),n=-1;while(++n<e)t[n]=0;return t}function p(e){return e>0?Math.floor(e):Math.ceil(e)}function d(e,n){var r=e.length,i=n.length,s=new Array(r),o=0,u=t,a,f;for(f=0;f<i;f++)a=e[f]+n[f]+o,o=a>=u?1:0,s[f]=a-o*u;while(f<r)a=e[f]+o,o=a===u?1:0,s[f++]=a-o*u;return o>0&&s.push(o),s}function v(e,t){return e.length>=t.length?d(e,t):d(t,e)}function m(e,n){var r=e.length,i=new Array(r),s=t,o,u;for(u=0;u<r;u++)o=e[u]+n,n=Math.floor(o/s),i[u]=o%s;while(n>0)i[u++]=n%s,n=Math.floor(n/s);return i}function g(e,n){var r=e.length,i=n.length,s=new Array(r),o=0,u=t,a,f;for(a=0;a<i;a++)f=e[a]-o-n[a],f<0?(f+=u,o=1):o=0,s[a]=f;for(a=i;a<r;a++){f=e[a]-o;if(!(f<0)){s[a++]=f;break}f+=u,s[a]=f}for(;a<r;a++)s[a]=e[a];return c(s),s}function y(e,t,n){var r,i;return A(e,t)>=0?r=g(e,t):(r=g(t,e),n=!n),r=l(r),typeof r=="number"?(n&&(r=-r),new u(r)):new o(r,n)}function b(e,n,r){var i=e.length,s=new Array(i),a=-n,f=t,c,h;for(c=0;c<i;c++)h=e[c]+a,a=Math.floor(h/f),s[c]=h<0?h%f+f:h;return s=l(s),typeof s=="number"?(r&&(s=-s),new u(s)):new o(s,r)}function w(e,n){var r=e.length,i=n.length,s=r+i,o=h(s),u=t,a,f,l,p,d;for(l=0;l<r;++l){p=e[l];for(var v=0;v<i;++v)d=n[v],a=p*d+o[l+v],f=Math.floor(a/u),o[l+v]=a-f*u,o[l+v+1]+=f}return c(o),o}function E(e,n){var r=e.length,i=new Array(r),s=t,o=0,u,a;for(a=0;a<r;a++)u=e[a]*n+o,o=Math.floor(u/s),i[a]=u-o*s;while(o>0)i[a++]=o%s,o=Math.floor(o/s);return i}function S(e,t){var n=[];while(t-->0)n.push(0);return n.concat(e)}function x(e,t){var n=Math.max(e.length,t.length);if(n<=400)return w(e,t);n=Math.ceil(n/2);var r=e.slice(n),i=e.slice(0,n),s=t.slice(n),o=t.slice(0,n),u=x(i,o),a=x(r,s),f=x(v(i,r),v(o,s));return v(v(u,S(g(g(f,u),a),n)),S(a,2*n))}function T(e){var n=e.length,r=h(n+n),i=t,s,o,u,a,f;for(u=0;u<n;u++){a=e[u];for(var l=0;l<n;l++)f=e[l],s=a*f+r[u+l],o=Math.floor(s/i),r[u+l]=s-o*i,r[u+l+1]+=o}return c(r),r}function N(e,n){var r=e.length,i=n.length,s=t,o=h(n.length),u=n[i-1],a=Math.ceil(s/(2*u)),f=E(e,a),c=E(n,a),p,d,v,m,g,y,b;f.length<=r&&f.push(0),c.length<=i&&c.push(0),u=c[i-1];for(d=r-i;d>=0;d--){p=s-1,f[d+i]!==u&&(p=Math.floor((f[d+i]*s+f[d+i-1])/u)),v=0,m=0,y=c.length;for(g=0;g<y;g++)v+=p*c[g],b=Math.floor(v/s),m+=f[d+g]-(v-b*s),v=b,m<0?(f[d+g]=m+s,m=-1):(f[d+g]=m,m=0);while(m!==0){p-=1,v=0;for(g=0;g<y;g++)v+=f[d+g]-s+c[g],v<0?(f[d+g]=v+s,v=0):(f[d+g]=v,v=1);m+=v}o[d]=p}return f=k(f,a)[0],[l(o),l(f)]}function C(e,n){var r=e.length,i=n.length,s=[],o=[],u=t,a,f,c,h,p;while(r){o.unshift(e[--r]);if(A(o,n)<0){s.push(0);continue}o.length===1&&o[0]===0?a=0:(f=o.length,c=o[f-1]*u+o[f-2],h=n[i-1]*u+n[i-2],f>i&&(c=(c+1)*u),a=Math.ceil(c/h));do{p=E(n,a);if(A(p,o)<=0)break;a--}while(a);s.push(a);if(!a)continue;o=g(o,p)}return s.reverse(),[l(s),l(o)]}function k(e,n){var r=e.length,i=h(r),s=t,o,u,a,f;a=0;for(o=r-1;o>=0;--o)f=a*s+e[o],u=p(f/n),a=f-u*n,i[o]=u|0;return[i,a|0]}function L(e,n){var r,i=z(n),s=e.value,a=i.value,c;if(a===0)throw new Error("Cannot divide by zero");if(e.isSmall)return i.isSmall?[new u(p(s/a)),new u(s%a)]:[W[0],e];if(i.isSmall){if(a===1)return[e,W[0]];if(a==-1)return[e.negate(),W[0]];var h=Math.abs(a);if(h<t){r=k(s,h),c=l(r[0]);var d=r[1];return e.sign&&(d=-d),typeof c=="number"?(e.sign!==i.sign&&(c=-c),[new u(c),new u(d)]):[new o(c,e.sign!==i.sign),new u(d)]}a=f(h)}var v=A(s,a);if(v===-1)return[W[0],e];if(v===0)return[W[1],W[0]];s.length+a.length<=200?r=N(s,a):r=C(s,a),c=r[0];var m=e.sign!==i.sign,g=r[1],y=e.sign;return typeof c=="number"?(m&&(c=-c),c=new u(c)):c=new o(c,m),typeof g=="number"?(y&&(g=-g),g=new u(g)):g=new o(g,y),[c,g]}function A(e,t){if(e.length!==t.length)return e.length>t.length?1:-1;for(var n=e.length-1;n>=0;n--)if(e[n]!==t[n])return e[n]>t[n]?1:-1;return 0}function D(e){return(typeof e=="number"||typeof e=="string")&&+Math.abs(e)<=t||e instanceof o&&e.value.length<=1}function P(e,t,n){t=z(t);var r=e.isNegative(),i=t.isNegative(),s=r?e.not():e,o=i?t.not():t,u=[],a=[],f=!1,l=!1;while(!f||!l)s.isZero()?(f=!0,u.push(r?1:0)):r?u.push(s.isEven()?1:0):u.push(s.isEven()?0:1),o.isZero()?(l=!0,a.push(i?1:0)):i?a.push(o.isEven()?1:0):a.push(o.isEven()?0:1),s=s.over(2),o=o.over(2);var c=[];for(var h=0;h<u.length;h++)c.push(n(u[h],a[h]));var p=bigInt(c.pop()).negate().times(bigInt(2).pow(c.length));while(c.length)p=p.add(bigInt(c.pop()).times(bigInt(2).pow(c.length)));return p}function H(e,t){return e=z(e),t=z(t),e.greater(t)?e:t}function B(e,t){return e=z(e),t=z(t),e.lesser(t)?e:t}function j(e,t){return e=z(e).abs(),t=z(t).abs(),e.equals(t)?e:e.isZero()?t:t.isZero()?e:e.isEven()?t.isOdd()?j(e.divide(2),t):j(e.divide(2),t.divide(2)).multiply(2):t.isEven()?j(e,t.divide(2)):e.greater(t)?j(e.subtract(t).divide(2),t):j(t.subtract(e).divide(2),e)}function F(e,t){return e=z(e).abs(),t=z(t).abs(),e.multiply(t).divide(j(e,t))}function I(e,n){e=z(e),n=z(n),e.isSmall&&(e=f(e)),n.isSmall&&(n=f(n));var r=B(e,n),i=H(e,n),s=i.subtract(r),u=s.value.length-1,a=[],c=!0;for(var h=u;h>=0;h--){var d=c?s.value[h]:t,v=p(Math.random()*d);a.unshift(v),v<d&&(c=!1)}return a=l(a),r.add(new o(a,!1,typeof a=="number"))}function R(e){var t=e.value;return typeof t=="number"&&(t=[t]),t.length===1&&t[0]<=36?"0123456789abcdefghijklmnopqrstuvwxyz".charAt(t[0]):"<"+t+">"}function U(e,t){t=bigInt(t);if(t.isZero()){if(e.isZero())return"0";throw new Error("Cannot convert nonzero numbers to base 0.")}if(t.equals(-1))return e.isZero()?"0":e.isNegative()?(new Array(1-e)).join("10"):"1"+(new Array(+e)).join("01");var n="";e.isNegative()&&t.isPositive()&&(n="-",e=e.abs());if(t.equals(1))return e.isZero()?"0":n+(new Array(+e+1)).join(1);var r=[],i=e,s;while(i.isNegative()||i.compareAbs(t)>=0){s=i.divmod(t),i=s.quotient;var o=s.remainder;o.isNegative()&&(o=t.minus(o).abs(),i=i.next()),r.push(R(o))}return r.push(R(i)),n+r.reverse().join("")}function z(e){if(e instanceof o||e instanceof u)return e;if(typeof e=="number"){if(a(e))return new u(e);e=String(e)}if(typeof e=="string"){if(a(+e)){var t=+e;if(t===p(t))return new u(t);throw"Invalid integer: "+e}var r=e[0]==="-";r&&(e=e.slice(1));var i=e.split(/e/i);if(i.length>2)throw new Error("Invalid integer: "+f.join("e"));if(i.length===2){var s=i[1];s[0]==="+"&&(s=s.slice(1)),s=+s;if(s!==p(s)||!a(s))throw new Error("Invalid integer: "+s+" is not a valid exponent.");var f=i[0],l=f.indexOf(".");l>=0&&(s-=f.length-l,f=f.slice(0,l)+f.slice(l+1));if(s<0)throw new Error("Cannot include negative exponent part for integers");f+=(new Array(s+1)).join("0"),e=f}var h=/^([0-9][0-9]*)$/.test(e);if(!h)throw new Error("Invalid integer: "+e);var d=[],v=e.length,m=n,g=v-m;while(v>0)d.push(+e.slice(g,v)),g-=m,g<0&&(g=0),v-=m;return c(d),new o(d,r)}}var t=1e7,n=7,r=9007199254740992,i=f(r),s=Math.log(r);o.prototype.add=function(e){var t,n=z(e);if(this.sign!==n.sign)return this.subtract(n.negate());var r=this.value,i=n.value;return n.isSmall?new o(m(r,i),this.sign):new o(v(r,i),this.sign)},o.prototype.plus=o.prototype.add,u.prototype.add=function(e){var t=z(e);if(this.sign!==t.sign)return this.subtract(t.negate());var n=this.value,r=t.value;if(t.isSmall){if(a(n+r))return new u(n+r);r=f(r)}return new o(m(r,n),n<0)},u.prototype.plus=u.prototype.add,o.prototype.subtract=function(e){var t=z(e);if(this.sign!==t.sign)return this.add(t.negate());var n=this.value,r=t.value;return t.isSmall?b(n,Math.abs(r),this.sign):y(n,r,this.sign)},o.prototype.minus=o.prototype.subtract,u.prototype.subtract=function(e){var t=z(e);if(this.sign!==t.sign)return this.add(t.negate());var n=this.value,r=t.value;return t.isSmall?new u(n-r):b(r,Math.abs(n),n>=0)},u.prototype.minus=u.prototype.subtract,o.prototype.negate=function(){return new o(this.value,!this.sign)},u.prototype.negate=function(){var e=this.sign,t=new u(-this.value);return t.sign=!e,t},o.prototype.abs=function(){return new o(this.value,!1)},u.prototype.abs=function(){return new u(Math.abs(this.value))},o.prototype.multiply=function(e){var n,r=z(e),i=this.value,s=r.value,u=this.sign!==r.sign,a;if(r.isSmall){if(s===0)return W[0];if(s===1)return this;if(s===-1)return this.negate();a=Math.abs(s);if(a<t)return new o(E(i,a),u);s=f(a)}return i.length+s.length>4e3?new o(x(i,s),u):new o(w(i,s),u)},o.prototype.times=o.prototype.multiply,u.prototype.multiply=function(e){var n=z(e),r=this.value,i=n.value;if(r===0)return W[0];if(r===1)return n;if(r===-1)return n.negate();if(n.isSmall){if(a(r*i))return new u(r*i);i=f(Math.abs(i))}var s=Math.abs(r);return s<t?new o(E(i,s),this.sign!==n.sign):new o(w(i,f(s)),this.sign!==n.sign)},u.prototype.times=u.prototype.multiply,o.prototype.square=function(){return new o(T(this.value),!1)},u.prototype.square=function(){var e=this.value*this.value;return a(e)?new u(e):new o(T(f(Math.abs(this.value))),!1)},o.prototype.divmod=function(e){var t=L(this,e);return{quotient:t[0],remainder:t[1]}},u.prototype.divmod=o.prototype.divmod,o.prototype.divide=function(e){return L(this,e)[0]},u.prototype.over=u.prototype.divide=o.prototype.over=o.prototype.divide,o.prototype.mod=function(e){return L(this,e)[1]},u.prototype.remainder=u.prototype.mod=o.prototype.remainder=o.prototype.mod,o.prototype.pow=function(e){var t=z(e),n=this.value,r=t.value,i,s,o;if(r===0)return W[1];if(t.sign)return n===1?W[1]:n===-1?isEven(t)?W[1]:W[-1]:W[0];if(!t.isSmall)throw new Error("The exponent "+t.toString()+" is too large.");if(this.isSmall){if(a(i=Math.pow(n,r)))return new u(p(i));if(n===0)return W[0];if(n===1)return W[1]}s=this,o=W[1];for(;;){r&!0&&(o=o.times(s),--r);if(r===0)break;r/=2,s=s.square()}return o},u.prototype.pow=o.prototype.pow,o.prototype.modPow=function(e,t){e=z(e),t=z(t);if(t.isZero())throw new Error("Cannot take modPow with modulus 0");var n=W[1],r=this.mod(t);if(r.isZero())return W[0];while(e.isPositive())e.isOdd()&&(n=n.multiply(r).mod(t)),e=e.divide(2),r=r.square().mod(t);return n},u.prototype.modPow=o.prototype.modPow,o.prototype.compareAbs=function(e){var t=z(e),n=this.value,r=t.value;return t.isSmall?1:A(n,r)},u.prototype.compareAbs=function(e){var t=z(e),n=Math.abs(this.value),r=t.value;return t.isSmall?(r=Math.abs(r),n===r?0:n>r?1:-1):-1},o.prototype.compare=function(e){var t=z(e),n=this.value,r=t.value;return this.sign!==t.sign?t.sign?1:-1:t.isSmall?this.sign?-1:1:A(n,r)*(this.sign?-1:1)},o.prototype.compareTo=o.prototype.compare,u.prototype.compare=function(e){var t=z(e),n=this.value,r=t.value;return t.isSmall?n==r?0:n>r?1:-1:n<0!==t.sign?n<0?-1:1:n<0?1:-1},u.prototype.compareTo=u.prototype.compare,o.prototype.equals=function(e){return this.compare(e)===0},u.prototype.eq=u.prototype.equals=o.prototype.eq=o.prototype.equals,o.prototype.notEquals=function(e){return this.compare(e)!==0},u.prototype.neq=u.prototype.notEquals=o.prototype.neq=o.prototype.notEquals,o.prototype.greater=function(e){return this.compare(e)>0},u.prototype.gt=u.prototype.greater=o.prototype.gt=o.prototype.greater,o.prototype.lesser=function(e){return this.compare(e)<0},u.prototype.lt=u.prototype.lesser=o.prototype.lt=o.prototype.lesser,o.prototype.greaterOrEquals=function(e){return this.compare(e)>=0},u.prototype.geq=u.prototype.greaterOrEquals=o.prototype.geq=o.prototype.greaterOrEquals,o.prototype.lesserOrEquals=function(e){return this.compare(e)<=0},u.prototype.leq=u.prototype.lesserOrEquals=o.prototype.leq=o.prototype.lesserOrEquals,o.prototype.isEven=function(){return(this.value[0]&1)===0},u.prototype.isEven=function(){return(this.value&1)===0},o.prototype.isOdd=function(){return(this.value[0]&1)===1},u.prototype.isOdd=function(){return(this.value&1)===1},o.prototype.isPositive=function(){return!this.sign},u.prototype.isPositive=function(){return this.value>0},o.prototype.isNegative=function(){return this.sign},u.prototype.isNegative=function(){return this.value<0},o.prototype.isUnit=function(){return!1},u.prototype.isUnit=function(){return Math.abs(this.value)===1},o.prototype.isZero=function(){return!1},u.prototype.isZero=function(){return this.value===0},o.prototype.isDivisibleBy=function(e){var t=z(e),n=t.value;return n===0?!1:n===1?!0:n===2?this.isEven():this.mod(t).equals(W[0])},u.prototype.isDivisibleBy=o.prototype.isDivisibleBy,o.prototype.isPrime=function(){var e=this.abs(),t=e.prev();if(e.isUnit())return!1;if(e.equals(2)||e.equals(3)||e.equals(5))return!0;if(e.isEven()||e.isDivisibleBy(3)||e.isDivisibleBy(5))return!1;if(e.lesser(25))return!0;var n=[2,3,5,7,11,13,17,19],r=t,i,s,o,u;while(r.isEven())r=r.divide(2);for(o=0;o<n.length;o++){u=bigInt(n[o]).modPow(r,e);if(u.equals(W[1])||u.equals(t))continue;for(s=!0,i=r;s&&i.lesser(t);i=i.multiply(2))u=u.square().mod(e),u.equals(t)&&(s=!1);if(s)return!1}return!0},u.prototype.isPrime=o.prototype.isPrime,o.prototype.next=function(){var e=this.value;return this.sign?b(e,1,this.sign):new o(m(e,1),this.sign)},u.prototype.next=function(){var e=this.value;return e+1<r?new u(e+1):new o(i,!1)},o.prototype.prev=function(){var e=this.value;return this.sign?new o(m(e,1),!0):b(e,1,this.sign)},u.prototype.prev=function(){var e=this.value;return e-1>-r?new u(e-1):new o(i,!0)};var O=[1];while(O[O.length-1]<=t)O.push(2*O[O.length-1]);var M=O.length,_=O[M-1];o.prototype.shiftLeft=function(e){if(!D(e))return e.isNegative()?this.shiftRight(e.abs()):this.times(W[2].pow(e));e=+e;if(e<0)return this.shiftRight(-e);var t=this;while(e>=M)t=t.multiply(_),e-=M-1;return t.multiply(O[e])},u.prototype.shiftLeft=o.prototype.shiftLeft,o.prototype.shiftRight=function(e){var t;if(!D(e))return e.isNegative()?this.shiftLeft(e.abs()):(t=this.divmod(W[2].pow(e)),t.remainder.isNegative()?t.quotient.prev():t.quotient);e=+e;if(e<0)return this.shiftLeft(-e);var n=this;while(e>=M){if(n.isZero())return n;t=L(n,_),n=t[1].isNegative()?t.quotient.prev():t[0],e-=M-1}return t=L(n,O[e]),t[1].isNegative()?t[0].prev():t[0]},u.prototype.shiftRight=o.prototype.shiftRight,o.prototype.not=function(){return this.negate().prev()},u.prototype.not=o.prototype.not,o.prototype.and=function(e){return P(this,e,function(e,t){return e&t})},u.prototype.and=o.prototype.and,o.prototype.or=function(e){return P(this,e,function(e,t){return e|t})},u.prototype.or=o.prototype.or,o.prototype.xor=function(e){return P(this,e,function(e,t){return e^t})},u.prototype.xor=o.prototype.xor;var q=function(e,t){var n=W[0],r=W[1],i=e.length;if(2<=t&&t<=36&&i<=s/Math.log(t))return parseInt(e,t);t=z(t);var o=[],u,a=e[0]==="-";for(u=a?1:0;u<e.length;u++){var f=e[u].toLowerCase(),l=f.charCodeAt(0);if(48<=l&&l<=57)o.push(z(f));else if(97<=l&&l<=122)o.push(z(f.charCodeAt(0)-87));else{if(f!=="<")throw new Error(f+" is not a valid character");var c=u;do u++;while(e[u]!==">");o.push(z(e.slice(c+1,u)))}}o.reverse();for(u=0;u<o.length;u++)n=n.add(o[u].times(r)),r=r.times(t);return a?n.negate():n};o.prototype.toString=function(t){t===e&&(t=10);if(t!==10)return U(this,t);var n=this.value,r=n.length,i=String(n[--r]),s="0000000",o;while(--r>=0)o=String(n[r]),i+=s.slice(o.length)+o;var u=this.sign?"-":"";return u+i},u.prototype.toString=function(t){return t===e&&(t=10),t!=10?U(this,t):String(this.value)},o.prototype.valueOf=function(){return this.isSmall?this.value:+this.toString()},o.prototype.toJSNumber=o.prototype.valueOf;var W=function(e,t){return typeof e=="undefined"?W[0]:typeof t!="undefined"?+t===10?z(e):q(e,t):z(e)};for(var X=0;X<1e3;X++)W[X]=new u(X),X>0&&(W[-X]=new u(-X));return W.one=W[1],W.zero=W[0],W.minusOne=W[-1],W.max=H,W.min=B,W.gcd=j,W.lcm=F,W.isInstance=function(e){return e instanceof o||e instanceof u},W}();typeof module!="undefined"&&(module.exports=bigInt);

2

package.json
{
"name": "big-integer",
"version": "1.4.6",
"version": "1.4.7",
"author": "Peter Olson <peter.e.c.olson+npm@gmail.com>",

@@ -5,0 +5,0 @@ "description": "An arbitrary length integer library for Javascript",

spec/spec.js

Sorry, the diff of this file is too big to display

SocketSocket SOC 2 Logo

Product

  • Package Alerts
  • Integrations
  • Docs
  • Pricing
  • FAQ
  • Roadmap
  • Changelog

About

Packages

Stay in touch

Get open source security insights delivered straight into your inbox.

  • Terms
  • Privacy
  • Security

Made with ⚡️ by Socket Inc