Big Integer Library Test
JavaScript performance comparison
Info
This test compares performance of arbitrary length integer Javascript libraries. Some of them can handle also decimals.
Preparation code
<script>
// http://www-cs-students.stanford.edu/~tjw/jsbn/
// Copyright (c) 2005 Tom Wu
// All Rights Reserved.
// See "LICENSE" for details.
// Basic JavaScript BN library - subset useful for RSA encryption.
(function() {
// Bits per digit
var dbits;
// JavaScript engine analysis
var canary = 0xdeadbeefcafe;
var j_lm = ((canary & 0xffffff) == 0xefcafe);
// (public) Constructor
function BigInteger(a, b, c) {
if (a != null) if ("number" == typeof a) this.fromNumber(a, b, c);
else if (b == null && "string" != typeof a) this.fromString(a, 256);
else this.fromString(a, b);
}
// return new, unset BigInteger
function nbi() {
return new BigInteger(null);
}
// am: Compute w_j += (x*this_i), propagate carries,
// c is initial carry, returns final carry.
// c < 3*dvalue, x < 2*dvalue, this_i < dvalue
// We need to select the fastest one that works in this environment.
// am1: use a single mult and divide to get the high bits,
// max digit bits should be 26 because
// max internal value = 2*dvalue^2-2*dvalue (< 2^53)
function am1(i, x, w, j, c, n) {
while (--n >= 0) {
var v = x * this[i++] + w[j] + c;
c = Math.floor(v / 0x4000000);
w[j++] = v & 0x3ffffff;
}
return c;
}
// am2 avoids a big mult-and-extract completely.
// Max digit bits should be <= 30 because we do bitwise ops
// on values up to 2*hdvalue^2-hdvalue-1 (< 2^31)
function am2(i, x, w, j, c, n) {
var xl = x & 0x7fff,
xh = x >> 15;
while (--n >= 0) {
var l = this[i] & 0x7fff;
var h = this[i++] >> 15;
var m = xh * l + h * xl;
l = xl * l + ((m & 0x7fff) << 15) + w[j] + (c & 0x3fffffff);
c = (l >>> 30) + (m >>> 15) + xh * h + (c >>> 30);
w[j++] = l & 0x3fffffff;
}
return c;
}
// Alternately, set max digit bits to 28 since some
// browsers slow down when dealing with 32-bit numbers.
function am3(i, x, w, j, c, n) {
var xl = x & 0x3fff,
xh = x >> 14;
while (--n >= 0) {
var l = this[i] & 0x3fff;
var h = this[i++] >> 14;
var m = xh * l + h * xl;
l = xl * l + ((m & 0x3fff) << 14) + w[j] + c;
c = (l >> 28) + (m >> 14) + xh * h;
w[j++] = l & 0xfffffff;
}
return c;
}
if (j_lm && (navigator.appName == "Microsoft Internet Explorer")) {
BigInteger.prototype.am = am2;
dbits = 30;
} else if (j_lm && (navigator.appName != "Netscape")) {
BigInteger.prototype.am = am1;
dbits = 26;
} else { // Mozilla/Netscape seems to prefer am3
BigInteger.prototype.am = am3;
dbits = 28;
}
BigInteger.prototype.DB = dbits;
BigInteger.prototype.DM = ((1 << dbits) - 1);
BigInteger.prototype.DV = (1 << dbits);
var BI_FP = 52;
BigInteger.prototype.FV = Math.pow(2, BI_FP);
BigInteger.prototype.F1 = BI_FP - dbits;
BigInteger.prototype.F2 = 2 * dbits - BI_FP;
// Digit conversions
var BI_RM = "0123456789abcdefghijklmnopqrstuvwxyz";
var BI_RC = new Array();
var rr, vv;
rr = "0".charCodeAt(0);
for (vv = 0; vv <= 9; ++vv) BI_RC[rr++] = vv;
rr = "a".charCodeAt(0);
for (vv = 10; vv < 36; ++vv) BI_RC[rr++] = vv;
rr = "A".charCodeAt(0);
for (vv = 10; vv < 36; ++vv) BI_RC[rr++] = vv;
function int2char(n) {
return BI_RM.charAt(n);
}
function intAt(s, i) {
var c = BI_RC[s.charCodeAt(i)];
return (c == null) ? -1 : c;
}
// (protected) copy this to r
function bnpCopyTo(r) {
for (var i = this.t - 1; i >= 0; --i) r[i] = this[i];
r.t = this.t;
r.s = this.s;
}
// (protected) set from integer value x, -DV <= x < DV
function bnpFromInt(x) {
this.t = 1;
this.s = (x < 0) ? -1 : 0;
if (x > 0) this[0] = x;
else if (x < -1) this[0] = x + DV;
else this.t = 0;
}
// return bigint initialized to value
function nbv(i) {
var r = nbi();
r.fromInt(i);
return r;
}
// (protected) set from string and radix
function bnpFromString(s, b) {
var k;
if (b == 16) k = 4;
else if (b == 8) k = 3;
else if (b == 256) k = 8; // byte array
else if (b == 2) k = 1;
else if (b == 32) k = 5;
else if (b == 4) k = 2;
else {
this.fromRadix(s, b);
return;
}
this.t = 0;
this.s = 0;
var i = s.length,
mi = false,
sh = 0;
while (--i >= 0) {
var x = (k == 8) ? s[i] & 0xff : intAt(s, i);
if (x < 0) {
if (s.charAt(i) == "-") mi = true;
continue;
}
mi = false;
if (sh == 0) this[this.t++] = x;
else if (sh + k > this.DB) {
this[this.t - 1] |= (x & ((1 << (this.DB - sh)) - 1)) << sh;
this[this.t++] = (x >> (this.DB - sh));
} else this[this.t - 1] |= x << sh;
sh += k;
if (sh >= this.DB) sh -= this.DB;
}
if (k == 8 && (s[0] & 0x80) != 0) {
this.s = -1;
if (sh > 0) this[this.t - 1] |= ((1 << (this.DB - sh)) - 1) << sh;
}
this.clamp();
if (mi) BigInteger.ZERO.subTo(this, this);
}
// (protected) clamp off excess high words
function bnpClamp() {
var c = this.s & this.DM;
while (this.t > 0 && this[this.t - 1] == c)--this.t;
}
// (public) return string representation in given radix
function bnToString(b) {
if (this.s < 0) return "-" + this.negate().toString(b);
var k;
if (b == 16) k = 4;
else if (b == 8) k = 3;
else if (b == 2) k = 1;
else if (b == 32) k = 5;
else if (b == 4) k = 2;
else return this.toRadix(b);
var km = (1 << k) - 1,
d, m = false,
r = "",
i = this.t;
var p = this.DB - (i * this.DB) % k;
if (i-- > 0) {
if (p < this.DB && (d = this[i] >> p) > 0) {
m = true;
r = int2char(d);
}
while (i >= 0) {
if (p < k) {
d = (this[i] & ((1 << p) - 1)) << (k - p);
d |= this[--i] >> (p += this.DB - k);
} else {
d = (this[i] >> (p -= k)) & km;
if (p <= 0) {
p += this.DB;
--i;
}
}
if (d > 0) m = true;
if (m) r += int2char(d);
}
}
return m ? r : "0";
}
// (public) -this
function bnNegate() {
var r = nbi();
BigInteger.ZERO.subTo(this, r);
return r;
}
// (public) |this|
function bnAbs() {
return (this.s < 0) ? this.negate() : this;
}
// (public) return + if this > a, - if this < a, 0 if equal
function bnCompareTo(a) {
var r = this.s - a.s;
if (r != 0) return r;
var i = this.t;
r = i - a.t;
if (r != 0) return (this.s < 0) ? -r : r;
while (--i >= 0) if ((r = this[i] - a[i]) != 0) return r;
return 0;
}
// returns bit length of the integer x
function nbits(x) {
var r = 1,
t;
if ((t = x >>> 16) != 0) {
x = t;
r += 16;
}
if ((t = x >> 8) != 0) {
x = t;
r += 8;
}
if ((t = x >> 4) != 0) {
x = t;
r += 4;
}
if ((t = x >> 2) != 0) {
x = t;
r += 2;
}
if ((t = x >> 1) != 0) {
x = t;
r += 1;
}
return r;
}
// (public) return the number of bits in "this"
function bnBitLength() {
if (this.t <= 0) return 0;
return this.DB * (this.t - 1) + nbits(this[this.t - 1] ^ (this.s & this.DM));
}
// (protected) r = this << n*DB
function bnpDLShiftTo(n, r) {
var i;
for (i = this.t - 1; i >= 0; --i) r[i + n] = this[i];
for (i = n - 1; i >= 0; --i) r[i] = 0;
r.t = this.t + n;
r.s = this.s;
}
// (protected) r = this >> n*DB
function bnpDRShiftTo(n, r) {
for (var i = n; i < this.t; ++i) r[i - n] = this[i];
r.t = Math.max(this.t - n, 0);
r.s = this.s;
}
// (protected) r = this << n
function bnpLShiftTo(n, r) {
var bs = n % this.DB;
var cbs = this.DB - bs;
var bm = (1 << cbs) - 1;
var ds = Math.floor(n / this.DB),
c = (this.s << bs) & this.DM,
i;
for (i = this.t - 1; i >= 0; --i) {
r[i + ds + 1] = (this[i] >> cbs) | c;
c = (this[i] & bm) << bs;
}
for (i = ds - 1; i >= 0; --i) r[i] = 0;
r[ds] = c;
r.t = this.t + ds + 1;
r.s = this.s;
r.clamp();
}
// (protected) r = this >> n
function bnpRShiftTo(n, r) {
r.s = this.s;
var ds = Math.floor(n / this.DB);
if (ds >= this.t) {
r.t = 0;
return;
}
var bs = n % this.DB;
var cbs = this.DB - bs;
var bm = (1 << bs) - 1;
r[0] = this[ds] >> bs;
for (var i = ds + 1; i < this.t; ++i) {
r[i - ds - 1] |= (this[i] & bm) << cbs;
r[i - ds] = this[i] >> bs;
}
if (bs > 0) r[this.t - ds - 1] |= (this.s & bm) << cbs;
r.t = this.t - ds;
r.clamp();
}
// (protected) r = this - a
function bnpSubTo(a, r) {
var i = 0,
c = 0,
m = Math.min(a.t, this.t);
while (i < m) {
c += this[i] - a[i];
r[i++] = c & this.DM;
c >>= this.DB;
}
if (a.t < this.t) {
c -= a.s;
while (i < this.t) {
c += this[i];
r[i++] = c & this.DM;
c >>= this.DB;
}
c += this.s;
} else {
c += this.s;
while (i < a.t) {
c -= a[i];
r[i++] = c & this.DM;
c >>= this.DB;
}
c -= a.s;
}
r.s = (c < 0) ? -1 : 0;
if (c < -1) r[i++] = this.DV + c;
else if (c > 0) r[i++] = c;
r.t = i;
r.clamp();
}
// (protected) r = this * a, r != this,a (HAC 14.12)
// "this" should be the larger one if appropriate.
function bnpMultiplyTo(a, r) {
var x = this.abs(),
y = a.abs();
var i = x.t;
r.t = i + y.t;
while (--i >= 0) r[i] = 0;
for (i = 0; i < y.t; ++i) r[i + x.t] = x.am(0, y[i], r, i, 0, x.t);
r.s = 0;
r.clamp();
if (this.s != a.s) BigInteger.ZERO.subTo(r, r);
}
// (protected) r = this^2, r != this (HAC 14.16)
function bnpSquareTo(r) {
var x = this.abs();
var i = r.t = 2 * x.t;
while (--i >= 0) r[i] = 0;
for (i = 0; i < x.t - 1; ++i) {
var c = x.am(i, x[i], r, 2 * i, 0, 1);
if ((r[i + x.t] += x.am(i + 1, 2 * x[i], r, 2 * i + 1, c, x.t - i - 1)) >= x.DV) {
r[i + x.t] -= x.DV;
r[i + x.t + 1] = 1;
}
}
if (r.t > 0) r[r.t - 1] += x.am(i, x[i], r, 2 * i, 0, 1);
r.s = 0;
r.clamp();
}
// (protected) divide this by m, quotient and remainder to q, r (HAC 14.20)
// r != q, this != m. q or r may be null.
function bnpDivRemTo(m, q, r) {
var pm = m.abs();
if (pm.t <= 0) return;
var pt = this.abs();
if (pt.t < pm.t) {
if (q != null) q.fromInt(0);
if (r != null) this.copyTo(r);
return;
}
if (r == null) r = nbi();
var y = nbi(),
ts = this.s,
ms = m.s;
var nsh = this.DB - nbits(pm[pm.t - 1]); // normalize modulus
if (nsh > 0) {
pm.lShiftTo(nsh, y);
pt.lShiftTo(nsh, r);
} else {
pm.copyTo(y);
pt.copyTo(r);
}
var ys = y.t;
var y0 = y[ys - 1];
if (y0 == 0) return;
var yt = y0 * (1 << this.F1) + ((ys > 1) ? y[ys - 2] >> this.F2 : 0);
var d1 = this.FV / yt,
d2 = (1 << this.F1) / yt,
e = 1 << this.F2;
var i = r.t,
j = i - ys,
t = (q == null) ? nbi() : q;
y.dlShiftTo(j, t);
if (r.compareTo(t) >= 0) {
r[r.t++] = 1;
r.subTo(t, r);
}
BigInteger.ONE.dlShiftTo(ys, t);
t.subTo(y, y); // "negative" y so we can replace sub with am later
while (y.t < ys) y[y.t++] = 0;
while (--j >= 0) {
// Estimate quotient digit
var qd = (r[--i] == y0) ? this.DM : Math.floor(r[i] * d1 + (r[i - 1] + e) * d2);
if ((r[i] += y.am(0, qd, r, j, 0, ys)) < qd) { // Try it out
y.dlShiftTo(j, t);
r.subTo(t, r);
while (r[i] < --qd) r.subTo(t, r);
}
}
if (q != null) {
r.drShiftTo(ys, q);
if (ts != ms) BigInteger.ZERO.subTo(q, q);
}
r.t = ys;
r.clamp();
if (nsh > 0) r.rShiftTo(nsh, r); // Denormalize remainder
if (ts < 0) BigInteger.ZERO.subTo(r, r);
}
// (public) this mod a
function bnMod(a) {
var r = nbi();
this.abs().divRemTo(a, null, r);
if (this.s < 0 && r.compareTo(BigInteger.ZERO) > 0) a.subTo(r, r);
return r;
}
// Modular reduction using "classic" algorithm
function Classic(m) {
this.m = m;
}
function cConvert(x) {
if (x.s < 0 || x.compareTo(this.m) >= 0) return x.mod(this.m);
else return x;
}
function cRevert(x) {
return x;
}
function cReduce(x) {
x.divRemTo(this.m, null, x);
}
function cMulTo(x, y, r) {
x.multiplyTo(y, r);
this.reduce(r);
}
function cSqrTo(x, r) {
x.squareTo(r);
this.reduce(r);
}
Classic.prototype.convert = cConvert;
Classic.prototype.revert = cRevert;
Classic.prototype.reduce = cReduce;
Classic.prototype.mulTo = cMulTo;
Classic.prototype.sqrTo = cSqrTo;
// (protected) return "-1/this % 2^DB"; useful for Mont. reduction
// justification:
// xy == 1 (mod m)
// xy = 1+km
// xy(2-xy) = (1+km)(1-km)
// x[y(2-xy)] = 1-k^2m^2
// x[y(2-xy)] == 1 (mod m^2)
// if y is 1/x mod m, then y(2-xy) is 1/x mod m^2
// should reduce x and y(2-xy) by m^2 at each step to keep size bounded.
// JS multiply "overflows" differently from C/C++, so care is needed here.
function bnpInvDigit() {
if (this.t < 1) return 0;
var x = this[0];
if ((x & 1) == 0) return 0;
var y = x & 3; // y == 1/x mod 2^2
y = (y * (2 - (x & 0xf) * y)) & 0xf; // y == 1/x mod 2^4
y = (y * (2 - (x & 0xff) * y)) & 0xff; // y == 1/x mod 2^8
y = (y * (2 - (((x & 0xffff) * y) & 0xffff))) & 0xffff; // y == 1/x mod 2^16
// last step - calculate inverse mod DV directly;
// assumes 16 < DB <= 32 and assumes ability to handle 48-bit ints
y = (y * (2 - x * y % this.DV)) % this.DV; // y == 1/x mod 2^dbits
// we really want the negative inverse, and -DV < y < DV
return (y > 0) ? this.DV - y : -y;
}
// Montgomery reduction
function Montgomery(m) {
this.m = m;
this.mp = m.invDigit();
this.mpl = this.mp & 0x7fff;
this.mph = this.mp >> 15;
this.um = (1 << (m.DB - 15)) - 1;
this.mt2 = 2 * m.t;
}
// xR mod m
function montConvert(x) {
var r = nbi();
x.abs().dlShiftTo(this.m.t, r);
r.divRemTo(this.m, null, r);
if (x.s < 0 && r.compareTo(BigInteger.ZERO) > 0) this.m.subTo(r, r);
return r;
}
// x/R mod m
function montRevert(x) {
var r = nbi();
x.copyTo(r);
this.reduce(r);
return r;
}
// x = x/R mod m (HAC 14.32)
function montReduce(x) {
while (x.t <= this.mt2) // pad x so am has enough room later
x[x.t++] = 0;
for (var i = 0; i < this.m.t; ++i) {
// faster way of calculating u0 = x[i]*mp mod DV
var j = x[i] & 0x7fff;
var u0 = (j * this.mpl + (((j * this.mph + (x[i] >> 15) * this.mpl) & this.um) << 15)) & x.DM;
// use am to combine the multiply-shift-add into one call
j = i + this.m.t;
x[j] += this.m.am(0, u0, x, i, 0, this.m.t);
// propagate carry
while (x[j] >= x.DV) {
x[j] -= x.DV;
x[++j]++;
}
}
x.clamp();
x.drShiftTo(this.m.t, x);
if (x.compareTo(this.m) >= 0) x.subTo(this.m, x);
}
// r = "x^2/R mod m"; x != r
function montSqrTo(x, r) {
x.squareTo(r);
this.reduce(r);
}
// r = "xy/R mod m"; x,y != r
function montMulTo(x, y, r) {
x.multiplyTo(y, r);
this.reduce(r);
}
Montgomery.prototype.convert = montConvert;
Montgomery.prototype.revert = montRevert;
Montgomery.prototype.reduce = montReduce;
Montgomery.prototype.mulTo = montMulTo;
Montgomery.prototype.sqrTo = montSqrTo;
// (protected) true iff this is even
function bnpIsEven() {
return ((this.t > 0) ? (this[0] & 1) : this.s) == 0;
}
// (protected) this^e, e < 2^32, doing sqr and mul with "r" (HAC 14.79)
function bnpExp(e, z) {
if (e > 0xffffffff || e < 1) return BigInteger.ONE;
var r = nbi(),
r2 = nbi(),
g = z.convert(this),
i = nbits(e) - 1;
g.copyTo(r);
while (--i >= 0) {
z.sqrTo(r, r2);
if ((e & (1 << i)) > 0) z.mulTo(r2, g, r);
else {
var t = r;
r = r2;
r2 = t;
}
}
return z.revert(r);
}
// (public) this^e % m, 0 <= e < 2^32
function bnModPowInt(e, m) {
var z;
if (e < 256 || m.isEven()) z = new Classic(m);
else z = new Montgomery(m);
return this.exp(e, z);
}
// protected
BigInteger.prototype.copyTo = bnpCopyTo;
BigInteger.prototype.fromInt = bnpFromInt;
BigInteger.prototype.fromString = bnpFromString;
BigInteger.prototype.clamp = bnpClamp;
BigInteger.prototype.dlShiftTo = bnpDLShiftTo;
BigInteger.prototype.drShiftTo = bnpDRShiftTo;
BigInteger.prototype.lShiftTo = bnpLShiftTo;
BigInteger.prototype.rShiftTo = bnpRShiftTo;
BigInteger.prototype.subTo = bnpSubTo;
BigInteger.prototype.multiplyTo = bnpMultiplyTo;
BigInteger.prototype.squareTo = bnpSquareTo;
BigInteger.prototype.divRemTo = bnpDivRemTo;
BigInteger.prototype.invDigit = bnpInvDigit;
BigInteger.prototype.isEven = bnpIsEven;
BigInteger.prototype.exp = bnpExp;
// public
BigInteger.prototype.toString = bnToString;
BigInteger.prototype.negate = bnNegate;
BigInteger.prototype.abs = bnAbs;
BigInteger.prototype.compareTo = bnCompareTo;
BigInteger.prototype.bitLength = bnBitLength;
BigInteger.prototype.mod = bnMod;
BigInteger.prototype.modPowInt = bnModPowInt;
// "constants"
BigInteger.ZERO = nbv(0);
BigInteger.ONE = nbv(1);
// Copyright (c) 2005-2009 Tom Wu
// All Rights Reserved.
// See "LICENSE" for details.
// Extended JavaScript BN functions, required for RSA private ops.
// Version 1.1: new BigInteger("0", 10) returns "proper" zero
// Version 1.2: square() API, isProbablePrime fix
// (public)
function bnClone() {
var r = nbi();
this.copyTo(r);
return r;
}
// (public) return value as integer
function bnIntValue() {
if (this.s < 0) {
if (this.t == 1) return this[0] - this.DV;
else if (this.t == 0) return -1;
} else if (this.t == 1) return this[0];
else if (this.t == 0) return 0;
// assumes 16 < DB < 32
return ((this[1] & ((1 << (32 - this.DB)) - 1)) << this.DB) | this[0];
}
// (public) return value as byte
function bnByteValue() {
return (this.t == 0) ? this.s : (this[0] << 24) >> 24;
}
// (public) return value as short (assumes DB>=16)
function bnShortValue() {
return (this.t == 0) ? this.s : (this[0] << 16) >> 16;
}
// (protected) return x s.t. r^x < DV
function bnpChunkSize(r) {
return Math.floor(Math.LN2 * this.DB / Math.log(r));
}
// (public) 0 if this == 0, 1 if this > 0
function bnSigNum() {
if (this.s < 0) return -1;
else if (this.t <= 0 || (this.t == 1 && this[0] <= 0)) return 0;
else return 1;
}
// (protected) convert to radix string
function bnpToRadix(b) {
if (b == null) b = 10;
if (this.signum() == 0 || b < 2 || b > 36) return "0";
var cs = this.chunkSize(b);
var a = Math.pow(b, cs);
var d = nbv(a),
y = nbi(),
z = nbi(),
r = "";
this.divRemTo(d, y, z);
while (y.signum() > 0) {
r = (a + z.intValue()).toString(b).substr(1) + r;
y.divRemTo(d, y, z);
}
return z.intValue().toString(b) + r;
}
// (protected) convert from radix string
function bnpFromRadix(s, b) {
this.fromInt(0);
if (b == null) b = 10;
var cs = this.chunkSize(b);
var d = Math.pow(b, cs),
mi = false,
j = 0,
w = 0;
for (var i = 0; i < s.length; ++i) {
var x = intAt(s, i);
if (x < 0) {
if (s.charAt(i) == "-" && this.signum() == 0) mi = true;
continue;
}
w = b * w + x;
if (++j >= cs) {
this.dMultiply(d);
this.dAddOffset(w, 0);
j = 0;
w = 0;
}
}
if (j > 0) {
this.dMultiply(Math.pow(b, j));
this.dAddOffset(w, 0);
}
if (mi) BigInteger.ZERO.subTo(this, this);
}
// (protected) alternate constructor
function bnpFromNumber(a, b, c) {
if ("number" == typeof b) {
// new BigInteger(int,int,RNG)
if (a < 2) this.fromInt(1);
else {
this.fromNumber(a, c);
if (!this.testBit(a - 1)) // force MSB set
this.bitwiseTo(BigInteger.ONE.shiftLeft(a - 1), op_or, this);
if (this.isEven()) this.dAddOffset(1, 0); // force odd
while (!this.isProbablePrime(b)) {
this.dAddOffset(2, 0);
if (this.bitLength() > a) this.subTo(BigInteger.ONE.shiftLeft(a - 1), this);
}
}
} else {
// new BigInteger(int,RNG)
var x = new Array(),
t = a & 7;
x.length = (a >> 3) + 1;
b.nextBytes(x);
if (t > 0) x[0] &= ((1 << t) - 1);
else x[0] = 0;
this.fromString(x, 256);
}
}
// (public) convert to bigendian byte array
function bnToByteArray() {
var i = this.t,
r = new Array();
r[0] = this.s;
var p = this.DB - (i * this.DB) % 8,
d, k = 0;
if (i-- > 0) {
if (p < this.DB && (d = this[i] >> p) != (this.s & this.DM) >> p) r[k++] = d | (this.s << (this.DB - p));
while (i >= 0) {
if (p < 8) {
d = (this[i] & ((1 << p) - 1)) << (8 - p);
d |= this[--i] >> (p += this.DB - 8);
} else {
d = (this[i] >> (p -= 8)) & 0xff;
if (p <= 0) {
p += this.DB;
--i;
}
}
if ((d & 0x80) != 0) d |= -256;
if (k == 0 && (this.s & 0x80) != (d & 0x80))++k;
if (k > 0 || d != this.s) r[k++] = d;
}
}
return r;
}
function bnEquals(a) {
return (this.compareTo(a) == 0);
}
function bnMin(a) {
return (this.compareTo(a) < 0) ? this : a;
}
function bnMax(a) {
return (this.compareTo(a) > 0) ? this : a;
}
// (protected) r = this op a (bitwise)
function bnpBitwiseTo(a, op, r) {
var i, f, m = Math.min(a.t, this.t);
for (i = 0; i < m; ++i) r[i] = op(this[i], a[i]);
if (a.t < this.t) {
f = a.s & this.DM;
for (i = m; i < this.t; ++i) r[i] = op(this[i], f);
r.t = this.t;
} else {
f = this.s & this.DM;
for (i = m; i < a.t; ++i) r[i] = op(f, a[i]);
r.t = a.t;
}
r.s = op(this.s, a.s);
r.clamp();
}
// (public) this & a
function op_and(x, y) {
return x & y;
}
function bnAnd(a) {
var r = nbi();
this.bitwiseTo(a, op_and, r);
return r;
}
// (public) this | a
function op_or(x, y) {
return x | y;
}
function bnOr(a) {
var r = nbi();
this.bitwiseTo(a, op_or, r);
return r;
}
// (public) this ^ a
function op_xor(x, y) {
return x ^ y;
}
function bnXor(a) {
var r = nbi();
this.bitwiseTo(a, op_xor, r);
return r;
}
// (public) this & ~a
function op_andnot(x, y) {
return x & ~y;
}
function bnAndNot(a) {
var r = nbi();
this.bitwiseTo(a, op_andnot, r);
return r;
}
// (public) ~this
function bnNot() {
var r = nbi();
for (var i = 0; i < this.t; ++i) r[i] = this.DM & ~this[i];
r.t = this.t;
r.s = ~this.s;
return r;
}
// (public) this << n
function bnShiftLeft(n) {
var r = nbi();
if (n < 0) this.rShiftTo(-n, r);
else this.lShiftTo(n, r);
return r;
}
// (public) this >> n
function bnShiftRight(n) {
var r = nbi();
if (n < 0) this.lShiftTo(-n, r);
else this.rShiftTo(n, r);
return r;
}
// return index of lowest 1-bit in x, x < 2^31
function lbit(x) {
if (x == 0) return -1;
var r = 0;
if ((x & 0xffff) == 0) {
x >>= 16;
r += 16;
}
if ((x & 0xff) == 0) {
x >>= 8;
r += 8;
}
if ((x & 0xf) == 0) {
x >>= 4;
r += 4;
}
if ((x & 3) == 0) {
x >>= 2;
r += 2;
}
if ((x & 1) == 0)++r;
return r;
}
// (public) returns index of lowest 1-bit (or -1 if none)
function bnGetLowestSetBit() {
for (var i = 0; i < this.t; ++i)
if (this[i] != 0) return i * this.DB + lbit(this[i]);
if (this.s < 0) return this.t * this.DB;
return -1;
}
// return number of 1 bits in x
function cbit(x) {
var r = 0;
while (x != 0) {
x &= x - 1;
++r;
}
return r;
}
// (public) return number of set bits
function bnBitCount() {
var r = 0,
x = this.s & this.DM;
for (var i = 0; i < this.t; ++i) r += cbit(this[i] ^ x);
return r;
}
// (public) true iff nth bit is set
function bnTestBit(n) {
var j = Math.floor(n / this.DB);
if (j >= this.t) return (this.s != 0);
return ((this[j] & (1 << (n % this.DB))) != 0);
}
// (protected) this op (1<<n)
function bnpChangeBit(n, op) {
var r = BigInteger.ONE.shiftLeft(n);
this.bitwiseTo(r, op, r);
return r;
}
// (public) this | (1<<n)
function bnSetBit(n) {
return this.changeBit(n, op_or);
}
// (public) this & ~(1<<n)
function bnClearBit(n) {
return this.changeBit(n, op_andnot);
}
// (public) this ^ (1<<n)
function bnFlipBit(n) {
return this.changeBit(n, op_xor);
}
// (protected) r = this + a
function bnpAddTo(a, r) {
var i = 0,
c = 0,
m = Math.min(a.t, this.t);
while (i < m) {
c += this[i] + a[i];
r[i++] = c & this.DM;
c >>= this.DB;
}
if (a.t < this.t) {
c += a.s;
while (i < this.t) {
c += this[i];
r[i++] = c & this.DM;
c >>= this.DB;
}
c += this.s;
} else {
c += this.s;
while (i < a.t) {
c += a[i];
r[i++] = c & this.DM;
c >>= this.DB;
}
c += a.s;
}
r.s = (c < 0) ? -1 : 0;
if (c > 0) r[i++] = c;
else if (c < -1) r[i++] = this.DV + c;
r.t = i;
r.clamp();
}
// (public) this + a
function bnAdd(a) {
var r = nbi();
this.addTo(a, r);
return r;
}
// (public) this - a
function bnSubtract(a) {
var r = nbi();
this.subTo(a, r);
return r;
}
// (public) this * a
function bnMultiply(a) {
var r = nbi();
this.multiplyTo(a, r);
return r;
}
// (public) this^2
function bnSquare() {
var r = nbi();
this.squareTo(r);
return r;
}
// (public) this / a
function bnDivide(a) {
var r = nbi();
this.divRemTo(a, r, null);
return r;
}
// (public) this % a
function bnRemainder(a) {
var r = nbi();
this.divRemTo(a, null, r);
return r;
}
// (public) [this/a,this%a]
function bnDivideAndRemainder(a) {
var q = nbi(),
r = nbi();
this.divRemTo(a, q, r);
return new Array(q, r);
}
// (protected) this *= n, this >= 0, 1 < n < DV
function bnpDMultiply(n) {
this[this.t] = this.am(0, n - 1, this, 0, 0, this.t);
++this.t;
this.clamp();
}
// (protected) this += n << w words, this >= 0
function bnpDAddOffset(n, w) {
if (n == 0) return;
while (this.t <= w) this[this.t++] = 0;
this[w] += n;
while (this[w] >= this.DV) {
this[w] -= this.DV;
if (++w >= this.t) this[this.t++] = 0;
++this[w];
}
}
// A "null" reducer
function NullExp() {}
function nNop(x) {
return x;
}
function nMulTo(x, y, r) {
x.multiplyTo(y, r);
}
function nSqrTo(x, r) {
x.squareTo(r);
}
NullExp.prototype.convert = nNop;
NullExp.prototype.revert = nNop;
NullExp.prototype.mulTo = nMulTo;
NullExp.prototype.sqrTo = nSqrTo;
// (public) this^e
function bnPow(e) {
return this.exp(e, new NullExp());
}
// (protected) r = lower n words of "this * a", a.t <= n
// "this" should be the larger one if appropriate.
function bnpMultiplyLowerTo(a, n, r) {
var i = Math.min(this.t + a.t, n);
r.s = 0; // assumes a,this >= 0
r.t = i;
while (i > 0) r[--i] = 0;
var j;
for (j = r.t - this.t; i < j; ++i) r[i + this.t] = this.am(0, a[i], r, i, 0, this.t);
for (j = Math.min(a.t, n); i < j; ++i) this.am(0, a[i], r, i, 0, n - i);
r.clamp();
}
// (protected) r = "this * a" without lower n words, n > 0
// "this" should be the larger one if appropriate.
function bnpMultiplyUpperTo(a, n, r) {
--n;
var i = r.t = this.t + a.t - n;
r.s = 0; // assumes a,this >= 0
while (--i >= 0) r[i] = 0;
for (i = Math.max(n - this.t, 0); i < a.t; ++i)
r[this.t + i - n] = this.am(n - i, a[i], r, 0, 0, this.t + i - n);
r.clamp();
r.drShiftTo(1, r);
}
// Barrett modular reduction
function Barrett(m) {
// setup Barrett
this.r2 = nbi();
this.q3 = nbi();
BigInteger.ONE.dlShiftTo(2 * m.t, this.r2);
this.mu = this.r2.divide(m);
this.m = m;
}
function barrettConvert(x) {
if (x.s < 0 || x.t > 2 * this.m.t) return x.mod(this.m);
else if (x.compareTo(this.m) < 0) return x;
else {
var r = nbi();
x.copyTo(r);
this.reduce(r);
return r;
}
}
function barrettRevert(x) {
return x;
}
// x = x mod m (HAC 14.42)
function barrettReduce(x) {
x.drShiftTo(this.m.t - 1, this.r2);
if (x.t > this.m.t + 1) {
x.t = this.m.t + 1;
x.clamp();
}
this.mu.multiplyUpperTo(this.r2, this.m.t + 1, this.q3);
this.m.multiplyLowerTo(this.q3, this.m.t + 1, this.r2);
while (x.compareTo(this.r2) < 0) x.dAddOffset(1, this.m.t + 1);
x.subTo(this.r2, x);
while (x.compareTo(this.m) >= 0) x.subTo(this.m, x);
}
// r = x^2 mod m; x != r
function barrettSqrTo(x, r) {
x.squareTo(r);
this.reduce(r);
}
// r = x*y mod m; x,y != r
function barrettMulTo(x, y, r) {
x.multiplyTo(y, r);
this.reduce(r);
}
Barrett.prototype.convert = barrettConvert;
Barrett.prototype.revert = barrettRevert;
Barrett.prototype.reduce = barrettReduce;
Barrett.prototype.mulTo = barrettMulTo;
Barrett.prototype.sqrTo = barrettSqrTo;
// (public) this^e % m (HAC 14.85)
function bnModPow(e, m) {
var i = e.bitLength(),
k, r = nbv(1),
z;
if (i <= 0) return r;
else if (i < 18) k = 1;
else if (i < 48) k = 3;
else if (i < 144) k = 4;
else if (i < 768) k = 5;
else k = 6;
if (i < 8) z = new Classic(m);
else if (m.isEven()) z = new Barrett(m);
else z = new Montgomery(m);
// precomputation
var g = new Array(),
n = 3,
k1 = k - 1,
km = (1 << k) - 1;
g[1] = z.convert(this);
if (k > 1) {
var g2 = nbi();
z.sqrTo(g[1], g2);
while (n <= km) {
g[n] = nbi();
z.mulTo(g2, g[n - 2], g[n]);
n += 2;
}
}
var j = e.t - 1,
w, is1 = true,
r2 = nbi(),
t;
i = nbits(e[j]) - 1;
while (j >= 0) {
if (i >= k1) w = (e[j] >> (i - k1)) & km;
else {
w = (e[j] & ((1 << (i + 1)) - 1)) << (k1 - i);
if (j > 0) w |= e[j - 1] >> (this.DB + i - k1);
}
n = k;
while ((w & 1) == 0) {
w >>= 1;
--n;
}
if ((i -= n) < 0) {
i += this.DB;
--j;
}
if (is1) { // ret == 1, don't bother squaring or multiplying it
g[w].copyTo(r);
is1 = false;
} else {
while (n > 1) {
z.sqrTo(r, r2);
z.sqrTo(r2, r);
n -= 2;
}
if (n > 0) z.sqrTo(r, r2);
else {
t = r;
r = r2;
r2 = t;
}
z.mulTo(r2, g[w], r);
}
while (j >= 0 && (e[j] & (1 << i)) == 0) {
z.sqrTo(r, r2);
t = r;
r = r2;
r2 = t;
if (--i < 0) {
i = this.DB - 1;
--j;
}
}
}
return z.revert(r);
}
// (public) gcd(this,a) (HAC 14.54)
function bnGCD(a) {
var x = (this.s < 0) ? this.negate() : this.clone();
var y = (a.s < 0) ? a.negate() : a.clone();
if (x.compareTo(y) < 0) {
var t = x;
x = y;
y = t;
}
var i = x.getLowestSetBit(),
g = y.getLowestSetBit();
if (g < 0) return x;
if (i < g) g = i;
if (g > 0) {
x.rShiftTo(g, x);
y.rShiftTo(g, y);
}
while (x.signum() > 0) {
if ((i = x.getLowestSetBit()) > 0) x.rShiftTo(i, x);
if ((i = y.getLowestSetBit()) > 0) y.rShiftTo(i, y);
if (x.compareTo(y) >= 0) {
x.subTo(y, x);
x.rShiftTo(1, x);
} else {
y.subTo(x, y);
y.rShiftTo(1, y);
}
}
if (g > 0) y.lShiftTo(g, y);
return y;
}
// (protected) this % n, n < 2^26
function bnpModInt(n) {
if (n <= 0) return 0;
var d = this.DV % n,
r = (this.s < 0) ? n - 1 : 0;
if (this.t > 0) if (d == 0) r = this[0] % n;
else for (var i = this.t - 1; i >= 0; --i) r = (d * r + this[i]) % n;
return r;
}
// (public) 1/this % m (HAC 14.61)
function bnModInverse(m) {
var ac = m.isEven();
if ((this.isEven() && ac) || m.signum() == 0) return BigInteger.ZERO;
var u = m.clone(),
v = this.clone();
var a = nbv(1),
b = nbv(0),
c = nbv(0),
d = nbv(1);
while (u.signum() != 0) {
while (u.isEven()) {
u.rShiftTo(1, u);
if (ac) {
if (!a.isEven() || !b.isEven()) {
a.addTo(this, a);
b.subTo(m, b);
}
a.rShiftTo(1, a);
} else if (!b.isEven()) b.subTo(m, b);
b.rShiftTo(1, b);
}
while (v.isEven()) {
v.rShiftTo(1, v);
if (ac) {
if (!c.isEven() || !d.isEven()) {
c.addTo(this, c);
d.subTo(m, d);
}
c.rShiftTo(1, c);
} else if (!d.isEven()) d.subTo(m, d);
d.rShiftTo(1, d);
}
if (u.compareTo(v) >= 0) {
u.subTo(v, u);
if (ac) a.subTo(c, a);
b.subTo(d, b);
} else {
v.subTo(u, v);
if (ac) c.subTo(a, c);
d.subTo(b, d);
}
}
if (v.compareTo(BigInteger.ONE) != 0) return BigInteger.ZERO;
if (d.compareTo(m) >= 0) return d.subtract(m);
if (d.signum() < 0) d.addTo(m, d);
else return d;
if (d.signum() < 0) return d.add(m);
else return d;
}
var lowprimes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997];
var lplim = (1 << 26) / lowprimes[lowprimes.length - 1];
// (public) test primality with certainty >= 1-.5^t
function bnIsProbablePrime(t) {
var i, x = this.abs();
if (x.t == 1 && x[0] <= lowprimes[lowprimes.length - 1]) {
for (i = 0; i < lowprimes.length; ++i)
if (x[0] == lowprimes[i]) return true;
return false;
}
if (x.isEven()) return false;
i = 1;
while (i < lowprimes.length) {
var m = lowprimes[i],
j = i + 1;
while (j < lowprimes.length && m < lplim) m *= lowprimes[j++];
m = x.modInt(m);
while (i < j) if (m % lowprimes[i++] == 0) return false;
}
return x.millerRabin(t);
}
// (protected) true if probably prime (HAC 4.24, Miller-Rabin)
function bnpMillerRabin(t) {
var n1 = this.subtract(BigInteger.ONE);
var k = n1.getLowestSetBit();
if (k <= 0) return false;
var r = n1.shiftRight(k);
t = (t + 1) >> 1;
if (t > lowprimes.length) t = lowprimes.length;
var a = nbi();
for (var i = 0; i < t; ++i) {
//Pick bases at random, instead of starting at 2
a.fromInt(lowprimes[Math.floor(Math.random() * lowprimes.length)]);
var y = a.modPow(r, this);
if (y.compareTo(BigInteger.ONE) != 0 && y.compareTo(n1) != 0) {
var j = 1;
while (j++ < k && y.compareTo(n1) != 0) {
y = y.modPowInt(2, this);
if (y.compareTo(BigInteger.ONE) == 0) return false;
}
if (y.compareTo(n1) != 0) return false;
}
}
return true;
}
// protected
BigInteger.prototype.chunkSize = bnpChunkSize;
BigInteger.prototype.toRadix = bnpToRadix;
BigInteger.prototype.fromRadix = bnpFromRadix;
BigInteger.prototype.fromNumber = bnpFromNumber;
BigInteger.prototype.bitwiseTo = bnpBitwiseTo;
BigInteger.prototype.changeBit = bnpChangeBit;
BigInteger.prototype.addTo = bnpAddTo;
BigInteger.prototype.dMultiply = bnpDMultiply;
BigInteger.prototype.dAddOffset = bnpDAddOffset;
BigInteger.prototype.multiplyLowerTo = bnpMultiplyLowerTo;
BigInteger.prototype.multiplyUpperTo = bnpMultiplyUpperTo;
BigInteger.prototype.modInt = bnpModInt;
BigInteger.prototype.millerRabin = bnpMillerRabin;
// public
BigInteger.prototype.clone = bnClone;
BigInteger.prototype.intValue = bnIntValue;
BigInteger.prototype.byteValue = bnByteValue;
BigInteger.prototype.shortValue = bnShortValue;
BigInteger.prototype.signum = bnSigNum;
BigInteger.prototype.toByteArray = bnToByteArray;
BigInteger.prototype.equals = bnEquals;
BigInteger.prototype.min = bnMin;
BigInteger.prototype.max = bnMax;
BigInteger.prototype.and = bnAnd;
BigInteger.prototype.or = bnOr;
BigInteger.prototype.xor = bnXor;
BigInteger.prototype.andNot = bnAndNot;
BigInteger.prototype.not = bnNot;
BigInteger.prototype.shiftLeft = bnShiftLeft;
BigInteger.prototype.shiftRight = bnShiftRight;
BigInteger.prototype.getLowestSetBit = bnGetLowestSetBit;
BigInteger.prototype.bitCount = bnBitCount;
BigInteger.prototype.testBit = bnTestBit;
BigInteger.prototype.setBit = bnSetBit;
BigInteger.prototype.clearBit = bnClearBit;
BigInteger.prototype.flipBit = bnFlipBit;
BigInteger.prototype.add = bnAdd;
BigInteger.prototype.subtract = bnSubtract;
BigInteger.prototype.multiply = bnMultiply;
BigInteger.prototype.divide = bnDivide;
BigInteger.prototype.remainder = bnRemainder;
BigInteger.prototype.divideAndRemainder = bnDivideAndRemainder;
BigInteger.prototype.modPow = bnModPow;
BigInteger.prototype.modInverse = bnModInverse;
BigInteger.prototype.pow = bnPow;
BigInteger.prototype.gcd = bnGCD;
BigInteger.prototype.isProbablePrime = bnIsProbablePrime;
// JSBN-specific extension
BigInteger.prototype.square = bnSquare;
// BigInteger interfaces not implemented in jsbn:
// BigInteger(int signum, byte[] magnitude)
// double doubleValue()
// float floatValue()
// int hashCode()
// long longValue()
// static BigInteger valueOf(long val)
window.BigInteger = BigInteger;
})(window.BigInteger)
</script>
<script>
//+ Jonas Raoni Soares Silva
//@ http://jsfromhell.com/classes/bignumber [rev. #4]
BigNumber = function(n, p, r) {
var o = this,
i;
if (n instanceof BigNumber) {
for (i in {
precision: 0,
roundType: 0,
_s: 0,
_f: 0
}) o[i] = n[i];
o._d = n._d.slice();
return;
}
o.precision = isNaN(p = Math.abs(p)) ? BigNumber.defaultPrecision : p;
o.roundType = isNaN(r = Math.abs(r)) ? BigNumber.defaultRoundType : r;
o._s = (n += "").charAt(0) == "-";
o._f = ((n = n.replace(/[^\d.]/g, "").split(".", 2))[0] = n[0].replace(/^0+/, "") || "0").length;
for (i = (n = o._d = (n.join("") || "0").split("")).length; i; n[--i] = +n[i]);
o.round();
};
with({
$: BigNumber,
o: BigNumber.prototype
}) {
$.ROUND_HALF_EVEN = ($.ROUND_HALF_DOWN = ($.ROUND_HALF_UP = ($.ROUND_FLOOR = ($.ROUND_CEIL = ($.ROUND_DOWN = ($.ROUND_UP = 0) + 1) + 1) + 1) + 1) + 1) + 1;
$.defaultPrecision = 1;
$.defaultRoundType = $.ROUND_HALF_UP;
o.add = function(n) {
if (this._s != (n = new BigNumber(n))._s) return n._s ^= 1, this.subtract(n);
var o = new BigNumber(this),
a = o._d,
b = n._d,
la = o._f,
lb = n._f,
n = Math.max(la, lb),
i, r;
la != lb && ((lb = la - lb) > 0 ? o._zeroes(b, lb, 1) : o._zeroes(a, -lb, 1));
i = (la = a.length) == (lb = b.length) ? a.length : ((lb = la - lb) > 0 ? o._zeroes(b, lb) : o._zeroes(a, -lb)).length;
for (r = 0; i; r = (a[--i] = a[i] + b[i] + r) / 10 >>> 0, a[i] %= 10);
return r && ++n && a.unshift(r), o._f = n, o.round();
};
o.subtract = function(n) {
if (this._s != (n = new BigNumber(n))._s) return n._s ^= 1, this.add(n);
var o = new BigNumber(this),
c = o.abs().compare(n.abs()) + 1,
a = c ? o : n,
b = c ? n : o,
la = a._f,
lb = b._f,
d = la,
i, j;
a = a._d, b = b._d, la != lb && ((lb = la - lb) > 0 ? o._zeroes(b, lb, 1) : o._zeroes(a, -lb, 1));
for (i = (la = a.length) == (lb = b.length) ? a.length : ((lb = la - lb) > 0 ? o._zeroes(b, lb) : o._zeroes(a, -lb)).length; i;) {
if (a[--i] < b[i]) {
for (j = i; j && !a[--j]; a[j] = 9);
--a[j], a[i] += 10;
}
b[i] = a[i] - b[i];
}
return c || (o._s ^= 1), o._f = d, o._d = b, o.round();
};
o.multiply = function(n) {
var o = new BigNumber(this),
r = o._d.length >= (n = new BigNumber(n))._d.length,
a = (r ? o : n)._d,
b = (r ? n : o)._d,
la = a.length,
lb = b.length,
x = new BigNumber,
i, j, s;
for (i = lb; i; r && s.unshift(r), x.set(x.add(new BigNumber(s.join("")))))
for (s = (new Array(lb - --i)).join("0").split(""), r = 0, j = la; j; r += a[--j] * b[i], s.unshift(r % 10), r = (r / 10) >>> 0);
return o._s = o._s != n._s, o._f = ((r = la + lb - o._f - n._f) >= (j = (o._d = x._d).length) ? this._zeroes(o._d, r - j + 1, 1).length : j) - r, o.round();
};
o.divide = function(n) {
if ((n = new BigNumber(n)) == "0") return "Division by 0";
else if (this == "0") return new BigNumber;
var o = new BigNumber(this),
a = o._d,
b = n._d,
la = a.length - o._f,
lb = b.length - n._f,
r = new BigNumber,
i = 0,
j, s, l, f = 1,
c = 0,
e = 0;
r._s = o._s != n._s, r.precision = Math.max(o.precision, n.precision), r._f = +r._d.pop(), la != lb && o._zeroes(la > lb ? b : a, Math.abs(la - lb));
n._f = b.length, b = n, b._s = false, b = b.round();
for (n = new BigNumber; a[0] == "0"; a.shift());
out: do {
for (l = c = 0, n == "0" && (n._d = [], n._f = 0); i < a.length && n.compare(b) == -1; ++i) {
(l = i + 1 == a.length, (!f && ++c > 1 || (e = l && n == "0" && a[i] == "0"))) && (r._f == r._d.length && ++r._f, r._d.push(0));
(a[i] == "0" && n == "0") || (n._d.push(a[i]), ++n._f);
if (e) break out;
if ((l && n.compare(b) == -1 && (r._f == r._d.length && ++r._f, 1)) || (l = 0)) while (r._d.push(0), n._d.push(0), ++n._f, n.compare(b) == -1);
}
if (f = 0, n.compare(b) == -1 && !(l = 0)) while (l ? r._d.push(0) : l = 1, n._d.push(0), ++n._f, n.compare(b) == -1);
for (s = new BigNumber, j = 0; n.compare(y = s.add(b)) + 1 && ++j; s.set(y));
n.set(n.subtract(s)), !l && r._f == r._d.length && ++r._f, r._d.push(j);
}
while ((i < a.length || n != "0") && (r._d.length - r._f) <= r.precision);
return r.round();
};
o.mod = function(n) {
return this.subtract(this.divide(n).intPart().multiply(n));
};
o.pow = function(n) {
var o = new BigNumber(this),
i;
if ((n = (new BigNumber(n)).intPart()) == 0) return o.set(1);
for (i = Math.abs(n); --i; o.set(o.multiply(this)));
return n < 0 ? o.set((new BigNumber(1)).divide(o)) : o;
};
o.set = function(n) {
return this.constructor(n), this;
};
o.compare = function(n) {
var a = this,
la = this._f,
b = new BigNumber(n),
lb = b._f,
r = [-1, 1],
i, l;
if (a._s != b._s) return a._s ? -1 : 1;
if (la != lb) return r[(la > lb) ^ a._s];
for (la = (a = a._d).length, lb = (b = b._d).length, i = -1, l = Math.min(la, lb); ++i < l;)
if (a[i] != b[i]) return r[(a[i] > b[i]) ^ a._s];
return la != lb ? r[(la > lb) ^ a._s] : 0;
};
o.negate = function() {
var n = new BigNumber(this);
return n._s ^= 1, n;
};
o.abs = function() {
var n = new BigNumber(this);
return n._s = 0, n;
};
o.intPart = function() {
return new BigNumber((this._s ? "-" : "") + (this._d.slice(0, this._f).join("") || "0"));
};
o.valueOf = o.toString = function() {
var o = this;
return (o._s ? "-" : "") + (o._d.slice(0, o._f).join("") || "0") + (o._f != o._d.length ? "." + o._d.slice(o._f).join("") : "");
};
o._zeroes = function(n, l, t) {
var s = ["push", "unshift"][t || 0];
for (++l; --l; n[s](0));
return n;
};
o.round = function() {
if ("_rounding" in this) return this;
var $ = BigNumber,
r = this.roundType,
b = this._d,
d, p, n, x;
for (this._rounding = true; this._f > 1 && !b[0]; --this._f, b.shift());
for (d = this._f, p = this.precision + d, n = b[p]; b.length > d && !b[b.length - 1]; b.pop());
x = (this._s ? "-" : "") + (p - d ? "0." + this._zeroes([], p - d - 1).join("") : "") + 1;
if (b.length > p) {
n && (r == $.DOWN ? false : r == $.UP ? true : r == $.CEIL ? !this._s : r == $.FLOOR ? this._s : r == $.HALF_UP ? n >= 5 : r == $.HALF_DOWN ? n > 5 : r == $.HALF_EVEN ? n >= 5 && b[p - 1] & 1 : false) && this.add(x);
b.splice(p, b.length - p);
}
return delete this._rounding, this;
};
}
</script>
<script>
// https://github.com/dtrebbien/BigDecimal.js/blob/master/build/BigDecimal-all-last.min.js
(function() {
var m, k = function() {
this.form = this.digits = 0;
this.lostDigits = !1;
this.roundingMode = 0;
var a = this.DEFAULT_FORM,
b = this.DEFAULT_LOSTDIGITS,
c = this.DEFAULT_ROUNDINGMODE;
if (4 == k.arguments.length) {
a = k.arguments[1], b = k.arguments[2], c = k.arguments[3]
} else {
if (3 == k.arguments.length) {
a = k.arguments[1], b = k.arguments[2]
} else {
if (2 == k.arguments.length) {
a = k.arguments[1]
} else {
if (1 != k.arguments.length) {
throw "MathContext(): " + k.arguments.length + " arguments given; expected 1 to 4";
}
}
}
}
var d = k.arguments[0];
if (d != this.DEFAULT_DIGITS) {
if (d < this.MIN_DIGITS) {
throw "MathContext(): Digits too small: " + d;
}
if (d > this.MAX_DIGITS) {
throw "MathContext(): Digits too large: " + d;
}
}
if (a != this.SCIENTIFIC && a != this.ENGINEERING && a != this.PLAIN) {
throw "MathContext() Bad form value: " + a;
}
if (!this.isValidRound(c)) {
throw "MathContext(): Bad roundingMode value: " + c;
}
this.digits = d;
this.form = a;
this.lostDigits = b;
this.roundingMode = c
};
k.prototype.getDigits = function() {
return this.digits
};
k.prototype.getForm = function() {
return this.form
};
k.prototype.getLostDigits = function() {
return this.lostDigits
};
k.prototype.getRoundingMode = function() {
return this.roundingMode
};
k.prototype.toString = function() {
var a = null,
b = 0,
c = null,
a = this.form == this.SCIENTIFIC ? "SCIENTIFIC" : this.form == this.ENGINEERING ? "ENGINEERING" : "PLAIN",
d = this.ROUNDS.length,
b = 0;
a: for (; 0 < d; d--, b++) {
if (this.roundingMode == this.ROUNDS[b]) {
c = this.ROUNDWORDS[b];
break a
}
}
return "digits=" + this.digits + " form=" + a + " lostDigits=" + (this.lostDigits ? "1" : "0") + " roundingMode=" + c
};
k.prototype.isValidRound = function(a) {
var b = 0,
c = this.ROUNDS.length,
b = 0;
for (; 0 < c; c--, b++) {
if (a == this.ROUNDS[b]) {
return !0
}
}
return !1
};
k.PLAIN = k.prototype.PLAIN = 0;
k.SCIENTIFIC = k.prototype.SCIENTIFIC = 1;
k.ENGINEERING = k.prototype.ENGINEERING = 2;
k.ROUND_CEILING = k.prototype.ROUND_CEILING = 2;
k.ROUND_DOWN = k.prototype.ROUND_DOWN = 1;
k.ROUND_FLOOR = k.prototype.ROUND_FLOOR = 3;
k.ROUND_HALF_DOWN = k.prototype.ROUND_HALF_DOWN = 5;
k.ROUND_HALF_EVEN = k.prototype.ROUND_HALF_EVEN = 6;
k.ROUND_HALF_UP = k.prototype.ROUND_HALF_UP = 4;
k.ROUND_UNNECESSARY = k.prototype.ROUND_UNNECESSARY = 7;
k.ROUND_UP = k.prototype.ROUND_UP = 0;
k.prototype.DEFAULT_FORM = k.prototype.SCIENTIFIC;
k.prototype.DEFAULT_DIGITS = 9;
k.prototype.DEFAULT_LOSTDIGITS = !1;
k.prototype.DEFAULT_ROUNDINGMODE = k.prototype.ROUND_HALF_UP;
k.prototype.MIN_DIGITS = 0;
k.prototype.MAX_DIGITS = 999999999;
k.prototype.ROUNDS = [k.prototype.ROUND_HALF_UP, k.prototype.ROUND_UNNECESSARY, k.prototype.ROUND_CEILING, k.prototype.ROUND_DOWN, k.prototype.ROUND_FLOOR, k.prototype.ROUND_HALF_DOWN, k.prototype.ROUND_HALF_EVEN, k.prototype.ROUND_UP];
k.prototype.ROUNDWORDS = "ROUND_HALF_UP ROUND_UNNECESSARY ROUND_CEILING ROUND_DOWN ROUND_FLOOR ROUND_HALF_DOWN ROUND_HALF_EVEN ROUND_UP".split(" ");
k.prototype.DEFAULT = new k(k.prototype.DEFAULT_DIGITS, k.prototype.DEFAULT_FORM, k.prototype.DEFAULT_LOSTDIGITS, k.prototype.DEFAULT_ROUNDINGMODE);
m = k;
var v, G = function(a, b) {
return (a - a % b) / b
},
K = function(a) {
var b = Array(a),
c;
for (c = 0; c < a; ++c) {
b[c] = 0
}
return b
},
h = function() {
this.ind = 0;
this.form = m.prototype.PLAIN;
this.mant = null;
this.exp = 0;
if (0 != h.arguments.length) {
var a, b, c;
1 == h.arguments.length ? (a = h.arguments[0], b = 0, c = a.length) : (a = h.arguments[0], b = h.arguments[1], c = h.arguments[2]);
"string" == typeof a && (a = a.split(""));
var d, e, i, f, g, j = 0,
l = 0;
e = !1;
var k = l = l = j = 0,
q = 0;
f = 0;
0 >= c && this.bad("BigDecimal(): ", a);
this.ind = this.ispos;
"-" == a[0] ? (c--, 0 == c && this.bad("BigDecimal(): ", a), this.ind = this.isneg, b++) : "+" == a[0] && (c--, 0 == c && this.bad("BigDecimal(): ", a), b++);
e = d = !1;
i = 0;
g = f = -1;
k = c;
j = b;
a: for (; 0 < k; k--, j++) {
l = a[j];
if ("0" <= l && "9" >= l) {
g = j;
i++;
continue a
}
if ("." == l) {
0 <= f && this.bad("BigDecimal(): ", a);
f = j - b;
continue a
}
if ("e" != l && "E" != l) {
("0" > l || "9" < l) && this.bad("BigDecimal(): ", a);
d = !0;
g = j;
i++;
continue a
}
j - b > c - 2 && this.bad("BigDecimal(): ", a);
e = !1;
"-" == a[j + 1] ? (e = !0, j += 2) : j = "+" == a[j + 1] ? j + 2 : j + 1;
l = c - (j - b);
(0 == l || 9 < l) && this.bad("BigDecimal(): ", a);
c = l;
l = j;
for (; 0 < c; c--, l++) {
k = a[l], "0" > k && this.bad("BigDecimal(): ", a), "9" < k ? this.bad("BigDecimal(): ", a) : q = k - 0, this.exp = 10 * this.exp + q
}
e && (this.exp = -this.exp);
e = !0;
break a
}
0 == i && this.bad("BigDecimal(): ", a);
0 <= f && (this.exp = this.exp + f - i);
q = g - 1;
j = b;
a: for (; j <= q; j++) {
if (l = a[j], "0" == l) {
b++, f--, i--
} else {
if ("." == l) {
b++, f--
} else {
break a
}
}
}
this.mant = Array(i);
l = b;
if (d) {
b = i;
j = 0;
for (; 0 < b; b--, j++) {
j == f && l++, k = a[l], "9" >= k ? this.mant[j] = k - 0 : this.bad("BigDecimal(): ", a), l++
}
} else {
b = i;
j = 0;
for (; 0 < b; b--, j++) {
j == f && l++, this.mant[j] = a[l] - 0, l++
}
}
0 == this.mant[0] ? (this.ind = this.iszero, 0 < this.exp && (this.exp = 0), e && (this.mant = this.ZERO.mant, this.exp = 0)) : e && (this.form = m.prototype.SCIENTIFIC, f = this.exp + this.mant.length - 1, (f < this.MinExp || f > this.MaxExp) && this.bad("BigDecimal(): ", a))
}
},
H = function() {
var a;
if (1 == H.arguments.length) {
a = H.arguments[0]
} else {
if (0 == H.arguments.length) {
a = this.plainMC
} else {
throw "abs(): " + H.arguments.length + " arguments given; expected 0 or 1";
}
}
return this.ind == this.isneg ? this.negate(a) : this.plus(a)
},
w = function() {
var a;
if (2 == w.arguments.length) {
a = w.arguments[1]
} else {
if (1 == w.arguments.length) {
a = this.plainMC
} else {
throw "add(): " + w.arguments.length + " arguments given; expected 1 or 2";
}
}
var b = w.arguments[0],
c, d, e, i, f, g, j, l = 0;
d = l = 0;
var l = null,
k = l = 0,
q = 0,
t = 0,
s = 0,
n = 0;
a.lostDigits && this.checkdigits(b, a.digits);
c = this;
if (0 == c.ind && a.form != m.prototype.PLAIN) {
return b.plus(a)
}
if (0 == b.ind && a.form != m.prototype.PLAIN) {
return c.plus(a)
}
d = a.digits;
0 < d && (c.mant.length > d && (c = this.clone(c).round(a)), b.mant.length > d && (b = this.clone(b).round(a)));
e = new h;
i = c.mant;
f = c.mant.length;
g = b.mant;
j = b.mant.length;
if (c.exp == b.exp) {
e.exp = c.exp
} else {
if (c.exp > b.exp) {
l = f + c.exp - b.exp;
if (l >= j + d + 1 && 0 < d) {
return e.mant = i, e.exp = c.exp, e.ind = c.ind, f < d && (e.mant = this.extend(c.mant, d), e.exp -= d - f), e.finish(a, !1)
}
e.exp = b.exp;
l > d + 1 && 0 < d && (l = l - d - 1, j -= l, e.exp += l, l = d + 1);
l > f && (f = l)
} else {
l = j + b.exp - c.exp;
if (l >= f + d + 1 && 0 < d) {
return e.mant = g, e.exp = b.exp, e.ind = b.ind, j < d && (e.mant = this.extend(b.mant, d), e.exp -= d - j), e.finish(a, !1)
}
e.exp = c.exp;
l > d + 1 && 0 < d && (l = l - d - 1, f -= l, e.exp += l, l = d + 1);
l > j && (j = l)
}
}
e.ind = c.ind == this.iszero ? this.ispos : c.ind;
if ((c.ind == this.isneg ? 1 : 0) == (b.ind == this.isneg ? 1 : 0)) {
d = 1
} else {
do {
d = -1;
do {
if (b.ind != this.iszero) {
if (f < j || c.ind == this.iszero) {
l = i, i = g, g = l, l = f, f = j, j = l, e.ind = -e.ind
} else {
if (!(f > j)) {
k = l = 0;
q = i.length - 1;
t = g.length - 1;
c: for (;;) {
if (l <= q) {
s = i[l]
} else {
if (k > t) {
if (a.form != m.prototype.PLAIN) {
return this.ZERO
}
break c
}
s = 0
}
n = k <= t ? g[k] : 0;
if (s != n) {
s < n && (l = i, i = g, g = l, l = f, f = j, j = l, e.ind = -e.ind);
break c
}
l++;
k++
}
}
}
}
} while (0)
} while (0)
}
e.mant = this.byteaddsub(i, f, g, j, d, !1);
return e.finish(a, !1)
},
x = function() {
var a;
if (2 == x.arguments.length) {
a = x.arguments[1]
} else {
if (1 == x.arguments.length) {
a = this.plainMC
} else {
throw "compareTo(): " + x.arguments.length + " arguments given; expected 1 or 2";
}
}
var b = x.arguments[0],
c = 0,
c = 0;
a.lostDigits && this.checkdigits(b, a.digits);
if (this.ind == b.ind && this.exp == b.exp) {
c = this.mant.length;
if (c < b.mant.length) {
return -this.ind
}
if (c > b.mant.length) {
return this.ind
}
if (c <= a.digits || 0 == a.digits) {
a = c;
c = 0;
for (; 0 < a; a--, c++) {
if (this.mant[c] < b.mant[c]) {
return -this.ind
}
if (this.mant[c] > b.mant[c]) {
return this.ind
}
}
return 0
}
} else {
if (this.ind < b.ind) {
return -1
}
if (this.ind > b.ind) {
return 1
}
}
b = this.clone(b);
b.ind = -b.ind;
return this.add(b, a).ind
},
p = function() {
var a, b = -1;
if (2 == p.arguments.length) {
a = "number" == typeof p.arguments[1] ? new m(0, m.prototype.PLAIN, !1, p.arguments[1]) : p.arguments[1]
} else {
if (3 == p.arguments.length) {
b = p.arguments[1];
if (0 > b) {
throw "divide(): Negative scale: " + b;
}
a = new m(0, m.prototype.PLAIN, !1, p.arguments[2])
} else {
if (1 == p.arguments.length) {
a = this.plainMC
} else {
throw "divide(): " + p.arguments.length + " arguments given; expected between 1 and 3";
}
}
}
return this.dodivide("D", p.arguments[0], a, b)
},
y = function() {
var a;
if (2 == y.arguments.length) {
a = y.arguments[1]
} else {
if (1 == y.arguments.length) {
a = this.plainMC
} else {
throw "divideInteger(): " + y.arguments.length + " arguments given; expected 1 or 2";
}
}
return this.dodivide("I", y.arguments[0], a, 0)
},
z = function() {
var a;
if (2 == z.arguments.length) {
a = z.arguments[1]
} else {
if (1 == z.arguments.length) {
a = this.plainMC
} else {
throw "max(): " + z.arguments.length + " arguments given; expected 1 or 2";
}
}
var b = z.arguments[0];
return 0 <= this.compareTo(b, a) ? this.plus(a) : b.plus(a)
},
A = function() {
var a;
if (2 == A.arguments.length) {
a = A.arguments[1]
} else {
if (1 == A.arguments.length) {
a = this.plainMC
} else {
throw "min(): " + A.arguments.length + " arguments given; expected 1 or 2";
}
}
var b = A.arguments[0];
return 0 >= this.compareTo(b, a) ? this.plus(a) : b.plus(a)
},
B = function() {
var a;
if (2 == B.arguments.length) {
a = B.arguments[1]
} else {
if (1 == B.arguments.length) {
a = this.plainMC
} else {
throw "multiply(): " + B.arguments.length + " arguments given; expected 1 or 2";
}
}
var b = B.arguments[0],
c, d, e, i = e = null,
f, g = 0,
j, l = 0,
k = 0;
a.lostDigits && this.checkdigits(b, a.digits);
c = this;
d = 0;
e = a.digits;
0 < e ? (c.mant.length > e && (c = this.clone(c).round(a)), b.mant.length > e && (b = this.clone(b).round(a))) : (0 < c.exp && (d += c.exp), 0 < b.exp && (d += b.exp));
c.mant.length < b.mant.length ? (e = c.mant, i = b.mant) : (e = b.mant, i = c.mant);
f = e.length + i.length - 1;
g = 9 < e[0] * i[0] ? f + 1 : f;
j = new h;
var g = this.createArrayWithZeros(g),
m = e.length,
l = 0;
for (; 0 < m; m--, l++) {
k = e[l], 0 != k && (g = this.byteaddsub(g, g.length, i, f, k, !0)), f--
}
j.ind = c.ind * b.ind;
j.exp = c.exp + b.exp - d;
j.mant = 0 == d ? g : this.extend(g, g.length + d);
return j.finish(a, !1)
},
I = function() {
var a;
if (1 == I.arguments.length) {
a = I.arguments[0]
} else {
if (0 == I.arguments.length) {
a = this.plainMC
} else {
throw "negate(): " + I.arguments.length + " arguments given; expected 0 or 1";
}
}
var b;
a.lostDigits && this.checkdigits(null, a.digits);
b = this.clone(this);
b.ind = -b.ind;
return b.finish(a, !1)
},
J = function() {
var a;
if (1 == J.arguments.length) {
a = J.arguments[0]
} else {
if (0 == J.arguments.length) {
a = this.plainMC
} else {
throw "plus(): " + J.arguments.length + " arguments given; expected 0 or 1";
}
}
a.lostDigits && this.checkdigits(null, a.digits);
return a.form == m.prototype.PLAIN && this.form == m.prototype.PLAIN && (this.mant.length <= a.digits || 0 == a.digits) ? this : this.clone(this).finish(a, !1)
},
C = function() {
var a;
if (2 == C.arguments.length) {
a = C.arguments[1]
} else {
if (1 == C.arguments.length) {
a = this.plainMC
} else {
throw "pow(): " + C.arguments.length + " arguments given; expected 1 or 2";
}
}
var b = C.arguments[0],
c, d, e, i = e = 0,
f, g = 0;
a.lostDigits && this.checkdigits(b, a.digits);
c = b.intcheck(this.MinArg, this.MaxArg);
d = this;
e = a.digits;
if (0 == e) {
if (b.ind == this.isneg) {
throw "pow(): Negative power: " + b.toString();
}
e = 0
} else {
if (b.mant.length + b.exp > e) {
throw "pow(): Too many digits: " + b.toString();
}
d.mant.length > e && (d = this.clone(d).round(a));
i = b.mant.length + b.exp;
e = e + i + 1
}
e = new m(e, a.form, !1, a.roundingMode);
i = this.ONE;
if (0 == c) {
return i
}
0 > c && (c = -c);
f = !1;
g = 1;
a: for (;; g++) {
c <<= 1;
0 > c && (f = !0, i = i.multiply(d, e));
if (31 == g) {
break a
}
if (!f) {
continue a
}
i = i.multiply(i, e)
}
0 > b.ind && (i = this.ONE.divide(i, e));
return i.finish(a, !0)
},
D = function() {
var a;
if (2 == D.arguments.length) {
a = D.arguments[1]
} else {
if (1 == D.arguments.length) {
a = this.plainMC
} else {
throw "remainder(): " + D.arguments.length + " arguments given; expected 1 or 2";
}
}
return this.dodivide("R", D.arguments[0], a, -1)
},
E = function() {
var a;
if (2 == E.arguments.length) {
a = E.arguments[1]
} else {
if (1 == E.arguments.length) {
a = this.plainMC
} else {
throw "subtract(): " + E.arguments.length + " arguments given; expected 1 or 2";
}
}
var b = E.arguments[0];
a.lostDigits && this.checkdigits(b, a.digits);
b = this.clone(b);
b.ind = -b.ind;
return this.add(b, a)
},
r = function() {
var a, b, c, d;
if (6 == r.arguments.length) {
a = r.arguments[2], b = r.arguments[3], c = r.arguments[4], d = r.arguments[5]
} else {
if (2 == r.arguments.length) {
b = a = -1, c = m.prototype.SCIENTIFIC, d = this.ROUND_HALF_UP
} else {
throw "format(): " + r.arguments.length + " arguments given; expected 2 or 6";
}
}
var e = r.arguments[0],
i = r.arguments[1],
f, g = 0,
g = g = 0,
j = null,
l = j = g = 0;
f = 0;
g = null;
l = j = 0;
(-1 > e || 0 == e) && this.badarg("format", 1, e); - 1 > i && this.badarg("format", 2, i);
(-1 > a || 0 == a) && this.badarg("format", 3, a); - 1 > b && this.badarg("format", 4, b);
c != m.prototype.SCIENTIFIC && c != m.prototype.ENGINEERING && (-1 == c ? c = m.prototype.SCIENTIFIC : this.badarg("format", 5, c));
if (d != this.ROUND_HALF_UP) {
try {
-1 == d ? d = this.ROUND_HALF_UP : new m(9, m.prototype.SCIENTIFIC, !1, d)
} catch (h) {
this.badarg("format", 6, d)
}
}
f = this.clone(this); - 1 == b ? f.form = m.prototype.PLAIN : f.ind == this.iszero ? f.form = m.prototype.PLAIN : (g = f.exp + f.mant.length, f.form = g > b ? c : -5 > g ? c : m.prototype.PLAIN);
if (0 <= i) {
a: for (;;) {
f.form == m.prototype.PLAIN ? g = -f.exp : f.form == m.prototype.SCIENTIFIC ? g = f.mant.length - 1 : (g = (f.exp + f.mant.length - 1) % 3, 0 > g && (g = 3 + g), g++, g = g >= f.mant.length ? 0 : f.mant.length - g);
if (g == i) {
break a
}
if (g < i) {
j = this.extend(f.mant, f.mant.length + i - g);
f.mant = j;
f.exp -= i - g;
if (f.exp < this.MinExp) {
throw "format(): Exponent Overflow: " + f.exp;
}
break a
}
g -= i;
if (g > f.mant.length) {
f.mant = this.ZERO.mant;
f.ind = this.iszero;
f.exp = 0;
continue a
}
j = f.mant.length - g;
l = f.exp;
f.round(j, d);
if (f.exp - l == g) {
break a
}
}
}
b = f.layout();
if (0 < e) {
c = b.length;
f = 0;
a: for (; 0 < c; c--, f++) {
if ("." == b[f]) {
break a
}
if ("E" == b[f]) {
break a
}
}
f > e && this.badarg("format", 1, e);
if (f < e) {
g = Array(b.length + e - f);
e -= f;
j = 0;
for (; 0 < e; e--, j++) {
g[j] = " "
}
this.arraycopy(b, 0, g, j, b.length);
b = g
}
}
if (0 < a) {
e = b.length - 1;
f = b.length - 1;
a: for (; 0 < e; e--, f--) {
if ("E" == b[f]) {
break a
}
}
if (0 == f) {
g = Array(b.length + a + 2);
this.arraycopy(b, 0, g, 0, b.length);
a += 2;
j = b.length;
for (; 0 < a; a--, j++) {
g[j] = " "
}
b = g
} else {
if (l = b.length - f - 2, l > a && this.badarg("format", 3, a), l < a) {
g = Array(b.length + a - l);
this.arraycopy(b, 0, g, 0, f + 2);
a -= l;
j = f + 2;
for (; 0 < a; a--, j++) {
g[j] = "0"
}
this.arraycopy(b, f + 2, g, j, l);
b = g
}
}
}
return b.join("")
},
F = function() {
var a;
if (2 == F.arguments.length) {
a = F.arguments[1]
} else {
if (1 == F.arguments.length) {
a = this.ROUND_UNNECESSARY
} else {
throw "setScale(): " + F.arguments.length + " given; expected 1 or 2";
}
}
var b = F.arguments[0],
c, d;
c = c = 0;
c = this.scale();
if (c == b && this.form == m.prototype.PLAIN) {
return this
}
d = this.clone(this);
if (c <= b) {
c = 0 == c ? d.exp + b : b - c, d.mant = this.extend(d.mant, d.mant.length + c), d.exp = -b
} else {
if (0 > b) {
throw "setScale(): Negative scale: " + b;
}
c = d.mant.length - (c - b);
d = d.round(c, a);
d.exp != -b && (d.mant = this.extend(d.mant, d.mant.length + 1), d.exp -= 1)
}
d.form = m.prototype.PLAIN;
return d
};
v = function() {
var a, b = 0,
c = 0;
a = Array(190);
b = 0;
a: for (; 189 >= b; b++) {
c = b - 90;
if (0 <= c) {
a[b] = c % 10;
h.prototype.bytecar[b] = G(c, 10);
continue a
}
c += 100;
a[b] = c % 10;
h.prototype.bytecar[b] = G(c, 10) - 10
}
return a
};
var u = function() {
var a, b;
if (2 == u.arguments.length) {
a = u.arguments[0], b = u.arguments[1]
} else {
if (1 == u.arguments.length) {
b = u.arguments[0], a = b.digits, b = b.roundingMode
} else {
throw "round(): " + u.arguments.length + " arguments given; expected 1 or 2";
}
}
var c, d, e = !1,
i = 0,
f;
c = null;
c = this.mant.length - a;
if (0 >= c) {
return this
}
this.exp += c;
c = this.ind;
d = this.mant;
0 < a ? (this.mant = Array(a), this.arraycopy(d, 0, this.mant, 0, a), e = !0, i = d[a]) : (this.mant = this.ZERO.mant, this.ind = this.iszero, e = !1, i = 0 == a ? d[0] : 0);
f = 0;
if (b == this.ROUND_HALF_UP) {
5 <= i && (f = c)
} else {
if (b == this.ROUND_UNNECESSARY) {
if (!this.allzero(d, a)) {
throw "round(): Rounding necessary";
}
} else {
if (b == this.ROUND_HALF_DOWN) {
5 < i ? f = c : 5 == i && (this.allzero(d, a + 1) || (f = c))
} else {
if (b == this.ROUND_HALF_EVEN) {
5 < i ? f = c : 5 == i && (this.allzero(d, a + 1) ? 1 == this.mant[this.mant.length - 1] % 2 && (f = c) : f = c)
} else {
if (b != this.ROUND_DOWN) {
if (b == this.ROUND_UP) {
this.allzero(d, a) || (f = c)
} else {
if (b == this.ROUND_CEILING) {
0 < c && (this.allzero(d, a) || (f = c))
} else {
if (b == this.ROUND_FLOOR) {
0 > c && (this.allzero(d, a) || (f = c))
} else {
throw "round(): Bad round value: " + b;
}
}
}
}
}
}
}
}
0 != f && (this.ind == this.iszero ? (this.mant = this.ONE.mant, this.ind = f) : (this.ind == this.isneg && (f = -f), c = this.byteaddsub(this.mant, this.mant.length, this.ONE.mant, 1, f, e), c.length > this.mant.length ? (this.exp++, this.arraycopy(c, 0, this.mant, 0, this.mant.length)) : this.mant = c));
if (this.exp > this.MaxExp) {
throw "round(): Exponent Overflow: " + this.exp;
}
return this
};
h.prototype.div = G;
h.prototype.arraycopy = function(a, b, c, d, e) {
var i;
if (d > b) {
for (i = e - 1; 0 <= i; --i) {
c[i + d] = a[i + b]
}
} else {
for (i = 0; i < e; ++i) {
c[i + d] = a[i + b]
}
}
};
h.prototype.createArrayWithZeros = K;
h.prototype.abs = H;
h.prototype.add = w;
h.prototype.compareTo = x;
h.prototype.divide = p;
h.prototype.divideInteger = y;
h.prototype.max = z;
h.prototype.min = A;
h.prototype.multiply = B;
h.prototype.negate = I;
h.prototype.plus = J;
h.prototype.pow = C;
h.prototype.remainder = D;
h.prototype.subtract = E;
h.prototype.equals = function(a) {
var b = 0,
c = null,
d = null;
if (null == a || !(a instanceof h) || this.ind != a.ind) {
return !1
}
if (this.mant.length == a.mant.length && this.exp == a.exp && this.form == a.form) {
c = this.mant.length;
b = 0;
for (; 0 < c; c--, b++) {
if (this.mant[b] != a.mant[b]) {
return !1
}
}
} else {
c = this.layout();
d = a.layout();
if (c.length != d.length) {
return !1
}
a = c.length;
b = 0;
for (; 0 < a; a--, b++) {
if (c[b] != d[b]) {
return !1
}
}
}
return !0
};
h.prototype.format = r;
h.prototype.intValueExact = function() {
var a, b = 0,
c, d = 0;
a = 0;
if (this.ind == this.iszero) {
return 0
}
a = this.mant.length - 1;
if (0 > this.exp) {
a += this.exp;
if (!this.allzero(this.mant, a + 1)) {
throw "intValueExact(): Decimal part non-zero: " + this.toString();
}
if (0 > a) {
return 0
}
b = 0
} else {
if (9 < this.exp + a) {
throw "intValueExact(): Conversion overflow: " + this.toString();
}
b = this.exp
}
c = 0;
var e = a + b,
d = 0;
for (; d <= e; d++) {
c *= 10, d <= a && (c += this.mant[d])
}
if (9 == a + b && (a = G(c, 1E9), a != this.mant[0])) {
if (-2147483648 == c && this.ind == this.isneg && 2 == this.mant[0]) {
return c
}
throw "intValueExact(): Conversion overflow: " + this.toString();
}
return this.ind == this.ispos ? c : -c
};
h.prototype.movePointLeft = function(a) {
var b;
b = this.clone(this);
b.exp -= a;
return b.finish(this.plainMC, !1)
};
h.prototype.movePointRight = function(a) {
var b;
b = this.clone(this);
b.exp += a;
return b.finish(this.plainMC, !1)
};
h.prototype.scale = function() {
return 0 <= this.exp ? 0 : -this.exp
};
h.prototype.setScale = F;
h.prototype.signum = function() {
return this.ind
};
h.prototype.toString = function() {
return this.layout().join("")
};
h.prototype.layout = function() {
var a, b = 0,
b = null,
c = 0,
d = 0;
a = 0;
var d = null,
e, b = 0;
a = Array(this.mant.length);
c = this.mant.length;
b = 0;
for (; 0 < c; c--, b++) {
a[b] = this.mant[b] + ""
}
if (this.form != m.prototype.PLAIN) {
b = "";
this.ind == this.isneg && (b += "-");
c = this.exp + a.length - 1;
if (this.form == m.prototype.SCIENTIFIC) {
b += a[0], 1 < a.length && (b += "."), b += a.slice(1).join("")
} else {
if (d = c % 3, 0 > d && (d = 3 + d), c -= d, d++, d >= a.length) {
b += a.join("");
for (a = d - a.length; 0 < a; a--) {
b += "0"
}
} else {
b += a.slice(0, d).join(""), b = b + "." + a.slice(d).join("")
}
}
0 != c && (0 > c ? (a = "-", c = -c) : a = "+", b += "E", b += a, b += c);
return b.split("")
}
if (0 == this.exp) {
if (0 <= this.ind) {
return a
}
d = Array(a.length + 1);
d[0] = "-";
this.arraycopy(a, 0, d, 1, a.length);
return d
}
c = this.ind == this.isneg ? 1 : 0;
e = this.exp + a.length;
if (1 > e) {
b = c + 2 - this.exp;
d = Array(b);
0 != c && (d[0] = "-");
d[c] = "0";
d[c + 1] = ".";
var i = -e,
b = c + 2;
for (; 0 < i; i--, b++) {
d[b] = "0"
}
this.arraycopy(a, 0, d, c + 2 - e, a.length);
return d
}
if (e > a.length) {
d = Array(c + e);
0 != c && (d[0] = "-");
this.arraycopy(a, 0, d, c, a.length);
e -= a.length;
b = c + a.length;
for (; 0 < e; e--, b++) {
d[b] = "0"
}
return d
}
b = c + 1 + a.length;
d = Array(b);
0 != c && (d[0] = "-");
this.arraycopy(a, 0, d, c, e);
d[c + e] = ".";
this.arraycopy(a, e, d, c + e + 1, a.length - e);
return d
};
h.prototype.intcheck = function(a, b) {
var c;
c = this.intValueExact();
if (c < a || c > b) {
throw "intcheck(): Conversion overflow: " + c;
}
return c
};
h.prototype.dodivide = function(a, b, c, d) {
var e, i, f, g, j, l, k, q, t, s = 0,
n = 0,
p = 0;
i = i = n = n = n = 0;
e = null;
e = e = 0;
e = null;
c.lostDigits && this.checkdigits(b, c.digits);
e = this;
if (0 == b.ind) {
throw "dodivide(): Divide by 0";
}
if (0 == e.ind) {
return c.form != m.prototype.PLAIN ? this.ZERO : -1 == d ? e : e.setScale(d)
}
i = c.digits;
0 < i ? (e.mant.length > i && (e = this.clone(e).round(c)), b.mant.length > i && (b = this.clone(b).round(c))) : (-1 == d && (d = e.scale()), i = e.mant.length, d != -e.exp && (i = i + d + e.exp), i = i - (b.mant.length - 1) - b.exp, i < e.mant.length && (i = e.mant.length), i < b.mant.length && (i = b.mant.length));
f = e.exp - b.exp + e.mant.length - b.mant.length;
if (0 > f && "D" != a) {
return "I" == a ? this.ZERO : this.clone(e).finish(c, !1)
}
g = new h;
g.ind = e.ind * b.ind;
g.exp = f;
g.mant = this.createArrayWithZeros(i + 1);
j = i + i + 1;
f = this.extend(e.mant, j);
l = j;
k = b.mant;
q = j;
t = 10 * k[0] + 1;
1 < k.length && (t += k[1]);
j = 0;
a: for (;;) {
s = 0;
b: for (;;) {
if (l < q) {
break b
}
if (l == q) {
c: do {
var r = l,
n = 0;
for (; 0 < r; r--, n++) {
p = n < k.length ? k[n] : 0;
if (f[n] < p) {
break b
}
if (f[n] > p) {
break c
}
}
s++;
g.mant[j] = s;
j++;
f[0] = 0;
break a
} while (0);
n = f[0]
} else {
n = 10 * f[0], 1 < l && (n += f[1])
}
n = G(10 * n, t);
0 == n && (n = 1);
s += n;
f = this.byteaddsub(f, l, k, q, -n, !0);
if (0 != f[0]) {
continue b
}
p = l - 2;
n = 0;
c: for (; n <= p; n++) {
if (0 != f[n]) {
break c
}
l--
}
if (0 == n) {
continue b
}
this.arraycopy(f, n, f, 0, l)
}
if (0 != j || 0 != s) {
g.mant[j] = s;
j++;
if (j == i + 1) {
break a
}
if (0 == f[0]) {
break a
}
}
if (0 <= d && -g.exp > d) {
break a
}
if ("D" != a && 0 >= g.exp) {
break a
}
g.exp -= 1;
q--
}
0 == j && (j = 1);
if ("I" == a || "R" == a) {
if (j + g.exp > i) {
throw "dodivide(): Integer overflow";
}
if ("R" == a) {
do {
if (0 == g.mant[0]) {
return this.clone(e).finish(c, !1)
}
if (0 == f[0]) {
return this.ZERO
}
g.ind = e.ind;
i = i + i + 1 - e.mant.length;
g.exp = g.exp - i + e.exp;
i = l;
n = i - 1;
b: for (; 1 <= n && g.exp < e.exp && g.exp < b.exp; n--) {
if (0 != f[n]) {
break b
}
i--;
g.exp += 1
}
i < f.length && (e = Array(i), this.arraycopy(f, 0, e, 0, i), f = e);
g.mant = f;
return g.finish(c, !1)
}
while (0)
}
} else {
0 != f[0] && (e = g.mant[j - 1], 0 == e % 5 && (g.mant[j - 1] = e + 1))
}
if (0 <= d) {
return j != g.mant.length && (g.exp -= g.mant.length - j), e = g.mant.length - (-g.exp - d), g.round(e, c.roundingMode), g.exp != -d && (g.mant = this.extend(g.mant, g.mant.length + 1), g.exp -= 1), g.finish(c, !0)
}
if (j == g.mant.length) {
g.round(c)
} else {
if (0 == g.mant[0]) {
return this.ZERO
}
e = Array(j);
this.arraycopy(g.mant, 0, e, 0, j);
g.mant = e
}
return g.finish(c, !0)
};
h.prototype.bad = function(a, b) {
throw a + "Not a number: " + b;
};
h.prototype.badarg = function(a, b, c) {
throw "Bad argument " + b + " to " + a + ": " + c;
};
h.prototype.extend = function(a, b) {
var c;
if (a.length == b) {
return a
}
c = K(b);
this.arraycopy(a, 0, c, 0, a.length);
return c
};
h.prototype.byteaddsub = function(a, b, c, d, e, i) {
var f, g, j, h, k, m, p = 0;
f = m = 0;
f = a.length;
g = c.length;
b -= 1;
h = j = d - 1;
h < b && (h = b);
d = null;
i && h + 1 == f && (d = a);
null == d && (d = this.createArrayWithZeros(h + 1));
k = !1;
1 == e ? k = !0 : -1 == e && (k = !0);
m = 0;
p = h;
a: for (; 0 <= p; p--) {
0 <= b && (b < f && (m += a[b]), b--);
0 <= j && (j < g && (m = k ? 0 < e ? m + c[j] : m - c[j] : m + c[j] * e), j--);
if (10 > m && 0 <= m) {
do {
d[p] = m;
m = 0;
continue a
} while (0)
}
m += 90;
d[p] = this.bytedig[m];
m = this.bytecar[m]
}
if (0 == m) {
return d
}
c = null;
i && h + 2 == a.length && (c = a);
null == c && (c = Array(h + 2));
c[0] = m;
a = h + 1;
f = 0;
for (; 0 < a; a--, f++) {
c[f + 1] = d[f]
}
return c
};
h.prototype.diginit = v;
h.prototype.clone = function(a) {
var b;
b = new h;
b.ind = a.ind;
b.exp = a.exp;
b.form = a.form;
b.mant = a.mant;
return b
};
h.prototype.checkdigits = function(a, b) {
if (0 != b) {
if (this.mant.length > b && !this.allzero(this.mant, b)) {
throw "Too many digits: " + this.toString();
}
if (null != a && a.mant.length > b && !this.allzero(a.mant, b)) {
throw "Too many digits: " + a.toString();
}
}
};
h.prototype.round = u;
h.prototype.allzero = function(a, b) {
var c = 0;
0 > b && (b = 0);
var d = a.length - 1,
c = b;
for (; c <= d; c++) {
if (0 != a[c]) {
return !1
}
}
return !0
};
h.prototype.finish = function(a, b) {
var c = 0,
d = 0,
e = null,
c = d = 0;
0 != a.digits && this.mant.length > a.digits && this.round(a);
if (b && a.form != m.prototype.PLAIN) {
c = this.mant.length;
d = c - 1;
a: for (; 1 <= d; d--) {
if (0 != this.mant[d]) {
break a
}
c--;
this.exp++
}
c < this.mant.length && (e = Array(c), this.arraycopy(this.mant, 0, e, 0, c), this.mant = e)
}
this.form = m.prototype.PLAIN;
c = this.mant.length;
d = 0;
for (; 0 < c; c--, d++) {
if (0 != this.mant[d]) {
0 < d && (e = Array(this.mant.length - d), this.arraycopy(this.mant, d, e, 0, this.mant.length - d), this.mant = e);
d = this.exp + this.mant.length;
if (0 < d) {
if (d > a.digits && 0 != a.digits && (this.form = a.form), d - 1 <= this.MaxExp) {
return this
}
} else {
-5 > d && (this.form = a.form)
}
d--;
if (d < this.MinExp || d > this.MaxExp) {
b: do {
if (this.form == m.prototype.ENGINEERING && (c = d % 3, 0 > c && (c = 3 + c), d -= c, d >= this.MinExp && d <= this.MaxExp)) {
break b
}
throw "finish(): Exponent Overflow: " + d;
} while (0)
}
return this
}
}
this.ind = this.iszero;
if (a.form != m.prototype.PLAIN) {
this.exp = 0
} else {
if (0 < this.exp) {
this.exp = 0
} else {
if (this.exp < this.MinExp) {
throw "finish(): Exponent Overflow: " + this.exp;
}
}
}
this.mant = this.ZERO.mant;
return this
};
h.prototype.isGreaterThan = function(a) {
return 0 < this.compareTo(a)
};
h.prototype.isLessThan = function(a) {
return 0 > this.compareTo(a)
};
h.prototype.isGreaterThanOrEqualTo = function(a) {
return 0 <= this.compareTo(a)
};
h.prototype.isLessThanOrEqualTo = function(a) {
return 0 >= this.compareTo(a)
};
h.prototype.isPositive = function() {
return 0 < this.compareTo(h.prototype.ZERO)
};
h.prototype.isNegative = function() {
return 0 > this.compareTo(h.prototype.ZERO)
};
h.prototype.isZero = function() {
return this.equals(h.prototype.ZERO)
};
h.ROUND_CEILING = h.prototype.ROUND_CEILING = m.prototype.ROUND_CEILING;
h.ROUND_DOWN = h.prototype.ROUND_DOWN = m.prototype.ROUND_DOWN;
h.ROUND_FLOOR = h.prototype.ROUND_FLOOR = m.prototype.ROUND_FLOOR;
h.ROUND_HALF_DOWN = h.prototype.ROUND_HALF_DOWN = m.prototype.ROUND_HALF_DOWN;
h.ROUND_HALF_EVEN = h.prototype.ROUND_HALF_EVEN = m.prototype.ROUND_HALF_EVEN;
h.ROUND_HALF_UP = h.prototype.ROUND_HALF_UP = m.prototype.ROUND_HALF_UP;
h.ROUND_UNNECESSARY = h.prototype.ROUND_UNNECESSARY = m.prototype.ROUND_UNNECESSARY;
h.ROUND_UP = h.prototype.ROUND_UP = m.prototype.ROUND_UP;
h.prototype.ispos = 1;
h.prototype.iszero = 0;
h.prototype.isneg = -1;
h.prototype.MinExp = -999999999;
h.prototype.MaxExp = 999999999;
h.prototype.MinArg = -999999999;
h.prototype.MaxArg = 999999999;
h.prototype.plainMC = new m(0, m.prototype.PLAIN);
h.prototype.bytecar = Array(190);
h.prototype.bytedig = v();
h.ZERO = h.prototype.ZERO = new h("0");
h.ONE = h.prototype.ONE = new h("1");
h.TEN = h.prototype.TEN = new h("10");
v = h;
"function" === typeof define && null != define.amd ? define({
BigDecimal: v,
MathContext: m
}) : "object" === typeof this && (this.BigDecimal = v, this.MathContext = m)
}).call(this);
</script>
<script>
/* big.js v1.0.1 https://github.com/MikeMcl/big.js/LICENCE */
;
(function(global) {
'use strict';
/*
big.js v1.0.1
A small, fast Javascript library for arbitrary-precision arithmetic with decimal numbers.
https://github.com/MikeMcl/big.js/
Copyright (c) 2012 Michael Mclaughlin <M8ch88l@gmail.com>
MIT Expat Licence
*/
/****************************** EDITABLE DEFAULTS **********************************/
// The default values below must be integers within the stated ranges (inclusive).
/*
* The maximum number of decimal places of the results of methods involving
* division, i.e. 'div' and 'sqrt', and 'pow' with negative exponents.
*/
Big['DP'] = 20; // 0 to MAX_DP
/*
* The rounding mode used when rounding to the above decimal places.
*
* 0 Round towards zero (i.e. truncate, no rounding). (ROUND_DOWN )
* 1 Round to nearest neighbour. If equidistant, round up. (ROUND_HALF_UP )
* 2 Round to nearest neighbour. If equidistant, to even neighbour. (ROUND_HALF_EVEN)
*/
Big['RM'] = 1; // 0, 1 or 2
// The maximum value of 'Big.DP'.
var MAX_DP = 1E6,
// 0 to 1e+6
// The maximum magnitude of the exponent argument to the 'pow' method.
MAX_POWER = 1E6,
// 1 to 1e+6
/*
* The exponent value at and beneath which 'toString' returns exponential notation.
* Javascript's Number type: -7
* -1e+6 is the minimum recommended exponent value of a 'Big'.
*/
TO_EXP_NEG = -7,
// 0 to -1e+6
/*
* The exponent value at and above which 'toString' returns exponential notation.
* Javascript's Number type: 21
* 1e+6 is the maximum recommended exponent value of a 'Big', though there is no
* enforcing or checking of a limit.
*/
TO_EXP_POS = 21,
// 0 to 1e+6
/***********************************************************************************/
P = Big.prototype,
isValid = /^-?\d+(?:\.\d+)?(?:e[+-]?\d+)?$/i,
ONE = new Big(1);
// CONSTRUCTOR
/*
* The exported function.
* Create and return a new instance of a 'Big' object.
*
* n {number|string|Big} A numeric value.
*/
function Big(n) {
var i, j, nL, x = this;
// Enable constructor usage without new.
if (!(x instanceof Big)) {
return new Big(n)
}
// Duplicate.
if (n instanceof Big) {
x['s'] = n['s'];
x['e'] = n['e'];
x['c'] = n['c'].slice();
return
}
// Minus zero?
if (n === 0 && 1 / n < 0) {
n = '-0'
// Ensure 'n' is string and check validity.
} else if (!isValid.test(n += '')) {
throw NaN
}
// Determine sign.
x['s'] = n.charAt(0) == '-' ? (n = n.slice(1), -1) : 1;
// Decimal point?
if ((i = n.indexOf('.')) > -1) {
n = n.replace('.', '')
}
// Exponential form?
if ((j = n.search(/e/i)) > 0) {
// Determine exponent.
if (i < 0) {
i = j
}
i += +n.slice(j + 1);
n = n.substring(0, j)
} else if (i < 0) {
// Integer.
i = n.length
}
// Determine leading zeros.
for (j = 0; n.charAt(j) == '0'; j++) {}
if (j == (nL = n.length)) {
// Zero.
x['c'] = [x['e'] = 0]
} else {
// Determine trailing zeros.
for (; n.charAt(--nL) == '0';) {}
x['e'] = i - j - 1;
x['c'] = [];
// Convert string to array of digits (without leading and trailing zeros).
for (i = 0; j <= nL; x['c'][i++] = +n.charAt(j++)) {}
}
}
// PRIVATE FUNCTIONS
/*
* Round 'Big' 'x' to a maximum of 'dp' decimal places using rounding mode
* 'rm'. (Called by 'div', 'sqrt' and 'round'.)
*
* x {Big} The 'Big' to round.
* dp {number} Integer, 0 to MAX_DP inclusive.
* rm {number} 0, 1 or 2 ( ROUND_DOWN, ROUND_HALF_UP or ROUND_HALF_EVEN )
* [more] {boolean} Whether the result of division was truncated.
*/
function rnd(x, dp, rm, more) {
var xc = x['c'],
i = x['e'] + dp + 1;
if (rm !== 0 && rm !== 1 && rm !== 2) {
throw '!Big.RM!'
}
// 'xc[i]' is the digit after the digit that may be rounded up.
rm = rm && (xc[i] > 5 || xc[i] == 5 && (rm == 1 || more || i < 0 || xc[i + 1] != null || xc[i - 1] & 1));
if (i < 1 || !xc[0]) {
x['c'] = rm
// 1, 0.1, 0.01, 0.001, 0.0001 etc.
? (x['e'] = -dp, [1])
// Zero.
: [x['e'] = 0];
} else {
// Remove any digits after the required decimal places.
xc.length = i--;
// Round up?
if (rm) {
// Rounding up may mean the previous digit has to be rounded up and so on.
for (; ++xc[i] > 9;) {
xc[i] = 0;
if (!i--) {
++x['e'];
xc.unshift(1)
}
}
}
// Remove trailing zeros.
for (i = xc.length; !xc[--i]; xc.pop()) {}
}
return x
}
// PROTOTYPE/INSTANCE METHODS
/*
* Return
* 1 if the value of this 'Big' is greater than the value of 'Big' 'y',
* -1 if the value of this 'Big' is less than the value of 'Big' 'y', or
* 0 if they have the same value,
*/
P['cmp'] = function(y) {
var xNeg, x = this,
xc = x['c'],
yc = (y = new Big(y))['c'],
i = x['s'],
j = y['s'],
k = x['e'],
l = y['e'];
// Either zero?
if (!xc[0] || !yc[0]) {
return !xc[0] ? !yc[0] ? 0 : -j : i
}
// Signs differ?
if (i != j) {
return i
}
xNeg = i < 0;
// Compare exponents.
if (k != l) {
return k > l ^ xNeg ? 1 : -1
}
// Compare digit by digit.
for (i = -1, j = (k = xc.length) < (l = yc.length) ? k : l; ++i < j;) {
if (xc[i] != yc[i]) {
return xc[i] > yc[i] ^ xNeg ? 1 : -1
}
}
// Compare lengths.
return k == l ? 0 : k > l ^ xNeg ? 1 : -1
};
/*
* Return a new 'Big' whose value is the value of this 'Big' divided by the
* value of 'Big' 'y', rounded, if necessary, to a maximum of 'Big.DP'
* decimal places using rounding mode 'Big.RM'.
*/
P['div'] = function(y) {
var x = this,
dvd = x['c'],
dvs = (y = new Big(y))['c'],
s = x['s'] == y['s'] ? 1 : -1,
dp = Big['DP'];
if (dp !== ~~dp || dp < 0 || dp > MAX_DP) {
throw '!Big.DP!'
}
// Either 0?
if (!dvd[0] || !dvs[0]) {
// Both 0?
if (dvd[0] == dvs[0]) {
throw NaN
}
// 'dvs' is 0?
if (!dvs[0]) {
// Throw +-Infinity.
throw s / 0
}
// 'dvd' is 0. Return +-0.
return new Big(s * 0)
}
var dvsL, dvsT, next, cmp, remI, dvsZ = dvs.slice(),
dvdI = dvsL = dvs.length,
dvdL = dvd.length,
rem = dvd.slice(0, dvsL),
remL = rem.length,
quo = new Big(ONE),
qc = quo['c'] = [],
qi = 0,
digits = dp + (quo['e'] = x['e'] - y['e']) + 1;
quo['s'] = s;
s = digits < 0 ? 0 : digits;
// Create version of divisor with leading zero.
dvsZ.unshift(0);
// Add zeros to make remainder as long as divisor.
for (; remL++ < dvsL; rem.push(0)) {}
do {
// 'next' is how many times the divisor goes into the current remainder.
for (next = 0; next < 10; next++) {
// Compare divisor and remainder.
if (dvsL != (remL = rem.length)) {
cmp = dvsL > remL ? 1 : -1
} else {
for (remI = -1, cmp = 0; ++remI < dvsL;) {
if (dvs[remI] != rem[remI]) {
cmp = dvs[remI] > rem[remI] ? 1 : -1;
break
}
}
}
// Subtract divisor from remainder (if divisor < remainder).
if (cmp < 0) {
// Remainder cannot be more than one digit longer than divisor.
// Equalise lengths using divisor with extra leading zero?
for (dvsT = remL == dvsL ? dvs : dvsZ; remL;) {
if (rem[--remL] < dvsT[remL]) {
for (remI = remL;
remI && !rem[--remI];
rem[remI] = 9) {}--rem[remI];
rem[remL] += 10
}
rem[remL] -= dvsT[remL]
}
for (; !rem[0]; rem.shift()) {}
} else {
break
}
}
// Add the 'next' digit to the result array.
qc[qi++] = cmp ? next : ++next;
// Update the remainder.
rem[0] && cmp ? (rem[remL] = dvd[dvdI] || 0) : (rem = [dvd[dvdI]])
} while ((dvdI++ < dvdL || rem[0] != null) && s--);
// Leading zero? Do not remove if result is simply zero (qi == 1).
if (!qc[0] && qi != 1) {
// There can't be more than one zero.
qc.shift();
quo['e']--;
}
// Round?
if (qi > digits) {
rnd(quo, dp, Big['RM'], rem[0] != null)
}
return quo
}
/*
* Return a new 'Big' whose value is the value of this 'Big' minus the value
* of 'Big' 'y'.
*/
P['minus'] = function(y) {
var d, i, j, xLTy, x = this,
a = x['s'],
b = (y = new Big(y))['s'];
// Signs differ?
if (a != b) {
return y['s'] = -b, x['plus'](y)
}
var xc = x['c'],
xe = x['e'],
yc = y['c'],
ye = y['e'];
// Either zero?
if (!xc[0] || !yc[0]) {
// 'y' is non-zero?
return yc[0] ? (y['s'] = -b, y)
// 'x' is non-zero?
: new Big(xc[0] ? x
// Both are zero.
: 0)
}
// Determine which is the bigger number.
// Prepend zeros to equalise exponents.
if (xc = xc.slice(), a = xe - ye) {
d = (xLTy = a < 0) ? (a = -a, xc) : (ye = xe, yc);
for (d.reverse(), b = a; b--; d.push(0)) {}
d.reverse()
} else {
// Exponents equal. Check digit by digit.
j = ((xLTy = xc.length < yc.length) ? xc : yc).length;
for (a = b = 0; b < j; b++) {
if (xc[b] != yc[b]) {
xLTy = xc[b] < yc[b];
break
}
}
}
// 'x' < 'y'? Point 'xc' to the array of the bigger number.
if (xLTy) {
d = xc, xc = yc, yc = d;
y['s'] = -y['s']
}
/*
* Append zeros to 'xc' if shorter. No need to add zeros to 'yc' if shorter
* as subtraction only needs to start at 'yc.length'.
*/
if ((b = -((j = xc.length) - yc.length)) > 0) {
for (; b--; xc[j++] = 0) {}
}
// Subtract 'yc' from 'xc'.
for (b = yc.length; b > a;) {
if (xc[--b] < yc[b]) {
for (i = b; i && !xc[--i]; xc[i] = 9) {}--xc[i];
xc[b] += 10
}
xc[b] -= yc[b]
}
// Remove trailing zeros.
for (; xc[--j] == 0; xc.pop()) {}
// Remove leading zeros and adbust exponent accordingly.
for (; xc[0] == 0; xc.shift(), --ye) {}
if (!xc[0]) {
// Result must be zero.
xc = [ye = 0]
}
return y['c'] = xc, y['e'] = ye, y
};
/*
* Return a new 'Big' whose value is the value of this 'Big' modulo the
* value of 'Big' 'y'.
*/
P['mod'] = function(y) {
y = new Big(y);
var c, x = this,
i = x['s'],
j = y['s'];
if (!y['c'][0]) {
throw NaN
}
x['s'] = y['s'] = 1;
c = y['cmp'](x) == 1;
x['s'] = i, y['s'] = j;
return c ? new Big(x) : (i = Big['DP'], j = Big['RM'], Big['DP'] = Big['RM'] = 0, x = x['div'](y), Big['DP'] = i, Big['RM'] = j, this['minus'](x['times'](y)))
};
/*
* Return a new 'Big' whose value is the value of this 'Big' plus the value
* of 'Big' 'y'.
*/
P['plus'] = function(y) {
var d, x = this,
a = x['s'],
b = (y = new Big(y))['s'];
// Signs differ?
if (a != b) {
return y['s'] = -b, x['minus'](y)
}
var xe = x['e'],
xc = x['c'],
ye = y['e'],
yc = y['c'];
// Either zero?
if (!xc[0] || !yc[0]) {
// 'y' is non-zero?
return yc[0] ? y : new Big(xc[0]
// 'x' is non-zero?
? x
// Both are zero. Return zero.
: a * 0)
}
// Prepend zeros to equalise exponents.
// Note: Faster to use reverse then do unshifts.
if (xc = xc.slice(), a = xe - ye) {
d = a > 0 ? (ye = xe, yc) : (a = -a, xc);
for (d.reverse(); a--; d.push(0)) {}
d.reverse()
}
// Point 'xc' to the longer array.
if (xc.length - yc.length < 0) {
d = yc, yc = xc, xc = d
}
/*
* Only start adding at 'yc.length - 1' as the
* further digits of 'xc' can be left as they are.
*/
for (a = yc.length, b = 0; a;
b = (xc[--a] = xc[a] + yc[a] + b) / 10 ^ 0, xc[a] %= 10) {}
// No need to check for zero, as +x + +y != 0 && -x + -y != 0
if (b) {
xc.unshift(b);
++ye
}
// Remove trailing zeros.
for (a = xc.length; xc[--a] == 0; xc.pop()) {}
return y['c'] = xc, y['e'] = ye, y
};
/*
* Return a 'Big' whose value is the value of this 'Big' raised to the power
* 'e'. If 'e' is negative, round, if necessary, to a maximum of 'Big.DP'
* decimal places using rounding mode 'Big.RM'.
*
* e {number} Integer, -MAX_POWER to MAX_POWER inclusive.
*/
P['pow'] = function(e) {
var isNeg = e < 0,
x = new Big(this),
y = ONE;
if (e !== ~~e || e < -MAX_POWER || e > MAX_POWER) {
throw '!pow!'
}
for (e = isNeg ? -e : e;;) {
if (e & 1) {
y = y['times'](x)
}
e >>= 1;
if (!e) {
break
}
x = x['times'](x)
}
return isNeg ? ONE['div'](y) : y
};
/*
* Return a new 'Big' whose value is the value of this 'Big' rounded, if
* necessary, to a maximum of 'dp' decimal places using rounding mode 'rm'.
* If 'dp' is not specified, round to 0 decimal places.
* If 'rm' is not specified, use 'Big.RM'.
*
* [dp] {number} Integer, 0 to MAX_DP inclusive.
* [rm] 0, 1 or 2 ( i.e. ROUND_DOWN, ROUND_HALF_UP or ROUND_HALF_EVEN )
*/
P['round'] = function(dp, rm) {
var x = new Big(this);
if (dp == null) {
dp = 0
} else if (dp !== ~~dp || dp < 0 || dp > MAX_DP) {
throw '!round!'
}
rnd(x, dp, rm == null ? Big['RM'] : rm);
return x
};
/*
* Return a new 'Big' whose value is the square root of the value of this
* 'Big', rounded, if necessary, to a maximum of 'Big.DP' decimal places
* using rounding mode 'Big.RM'.
*/
P['sqrt'] = function() {
var estimate, r, approx, x = this,
xc = x['c'],
i = x['s'],
e = x['e'],
half = new Big('0.5');
// Zero?
if (!xc[0]) {
return new Big(x)
}
// Negative?
if (i < 0) {
throw NaN
}
// Estimate.
i = Math.sqrt(x.toString());
// Math.sqrt underflow/overflow?
// Pass 'x' to Math.sqrt as integer, then adjust the exponent of the result.
if (i == 0 || i == 1 / 0) {
estimate = xc.join('');
if (!(estimate.length + e & 1)) {
estimate += '0'
}
r = new Big(Math.sqrt(estimate).toString());
r['e'] = (((e + 1) / 2) | 0) - (e < 0 || e & 1)
} else {
r = new Big(i.toString())
}
i = r['e'] + (Big['DP'] += 4);
// Newton-Raphson loop.
do {
approx = r;
r = half['times'](approx['plus'](x['div'](approx)))
} while (approx['c'].slice(0, i).join('') !== r['c'].slice(0, i).join(''));
rnd(r, Big['DP'] -= 4, Big['RM']);
return r
};
/*
* Return a new 'Big' whose value is the value of this 'Big' times the value
* of 'Big' 'y'.
*/
P['times'] = function(y) {
var c, x = this,
xc = x['c'],
yc = (y = new Big(y))['c'],
a = xc.length,
b = yc.length,
i = x['e'],
j = y['e'];
y['s'] = x['s'] == y['s'] ? 1 : -1;
// Either 0?
if (!xc[0] || !yc[0]) {
return new Big(y['s'] * 0)
}
y['e'] = i + j;
if (a < b) {
c = xc, xc = yc, yc = c, j = a, a = b, b = j
}
for (j = a + b, c = []; j--; c.push(0)) {}
// Multiply!
for (i = b - 1; i > -1; i--) {
for (b = 0, j = a + i;
j > i;
b = c[j] + yc[i] * xc[j - i - 1] + b, c[j--] = b % 10 | 0, b = b / 10 | 0) {}
if (b) {
c[j] = (c[j] + b) % 10
}
}
b && ++y['e'];
// Remove any leading zero.
!c[0] && c.shift();
// Remove trailing zeros.
for (j = c.length; !c[--j]; c.pop()) {}
return y['c'] = c, y
};
/*
* Return a string representing the value of this 'Big'.
* Return exponential notation if this 'Big' has a positive exponent equal
* to or greater than 'TO_EXP_POS', or a negative exponent equal to or less
* than 'TO_EXP_NEG'.
*/
P['toString'] = P['valueOf'] = function() {
var x = this,
e = x['e'],
str = x['c'].join(''),
strL = str.length;
// Exponential notation?
if (e <= TO_EXP_NEG || e >= TO_EXP_POS) {
str = str.charAt(0) + (strL > 1 ? '.' + str.slice(1) : '') + (e < 0 ? 'e' : 'e+') + e
// Negative exponent?
} else if (e < 0) {
// Prepend zeros.
for (; ++e; str = '0' + str) {}
str = '0.' + str
// Positive exponent?
} else if (e > 0) {
if (++e > strL) {
// Append zeros.
for (e -= strL; e--; str += '0') {}
} else if (e < strL) {
str = str.slice(0, e) + '.' + str.slice(e)
}
// Exponent zero.
} else if (strL > 1) {
str = str.charAt(0) + '.' + str.slice(1)
}
// Avoid '-0'
return x['s'] < 0 && x['c'][0] ? '-' + str : str
};
/*
***************************************************************************
*
* If 'toExponential', 'toFixed', 'toPrecision' and 'format' are not
* required they can safely be commented-out or deleted. No redundant code
* will be left. 'format' is used only by 'toExponential', 'toFixed' and
* 'toPrecision'.
*
***************************************************************************
*/
/*
* PRIVATE FUNCTION
*
* Return a string representing the value of 'Big' 'x' in normal or
* exponential notation to a fixed number of decimal places or significant
* digits 'dp'.
* (Called by toString, toExponential, toFixed and toPrecision.)
*
* x {Big} The 'Big' to format.
* dp {number} Integer, 0 to MAX_DP inclusive.
* toE {number} undefined (toFixed), 1 (toExponential) or 2 (toPrecision).
*/
function format(x, dp, toE) {
// The index (in normal notation) of the digit that may be rounded up.
var i = dp - (x = new Big(x))['e'],
c = x['c'];
// Round?
if (c.length > ++dp) {
rnd(x, i, Big['RM'])
}
// Recalculate 'i' if toFixed as 'x.e' may have changed if value rounded up.
i = !c[0] ? i + 1 : toE ? dp : (c = x['c'], x['e'] + i + 1);
// Append zeros?
for (; c.length < i; c.push(0)) {}
i = x['e'];
/*
* 'toPrecision' returns exponential notation if the number of
* significant digits specified is less than the number of digits
* necessary to represent the integer part of the value in normal
* notation.
*/
return toE == 1 || toE == 2 && (dp <= i || i <= TO_EXP_NEG)
// Exponential notation.
? (x['s'] < 0 && c[0] ? '-' : '') + (c.length > 1 ? (c.splice(1, 0, '.'), c.join('')) : c[0]) + (i < 0 ? 'e' : 'e+') + i
// Normal notation.
: x.toString()
}
/*
* Return a string representing the value of this 'Big' in exponential
* notation to 'dp' fixed decimal places and rounded, if necessary, using
* 'Big.RM'.
*
* [dp] {number} Integer, 0 to MAX_DP inclusive.
*/
P['toExponential'] = function(dp) {
if (dp == null) {
dp = this['c'].length - 1
} else if (dp !== ~~dp || dp < 0 || dp > MAX_DP) {
throw '!toExp!'
}
return format(this, dp, 1)
};
/*
* Return a string representing the value of this 'Big' in normal notation
* to 'dp' fixed decimal places and rounded, if necessary, using 'Big.RM'.
*
* [dp] {number} Integer, 0 to MAX_DP inclusive.
*/
P['toFixed'] = function(dp) {
var str, x = this,
neg = TO_EXP_NEG,
pos = TO_EXP_POS;
TO_EXP_NEG = -(TO_EXP_POS = 1 / 0);
if (dp == null) {
str = x.toString()
} else if (dp === ~~dp && dp >= 0 && dp <= MAX_DP) {
str = format(x, x['e'] + dp);
// (-0).toFixed() is '0', but (-0.1).toFixed() is '-0'.
// (-0).toFixed(1) is '0.0', but (-0.01).toFixed(1) is '-0.0'.
if (x['s'] < 0 && x['c'][0] && str.indexOf('-') < 0) {
// As e.g. -0.5 if rounded to -0 will cause toString to omit the minus sign.
str = '-' + str
}
}
TO_EXP_NEG = neg, TO_EXP_POS = pos;
if (!str) {
throw '!toFix!'
}
return str
};
/*
* Return a string representing the value of this 'Big' to 'sd' significant
* digits and rounded, if necessary, using 'Big.RM'. If 'sd' is less than
* the number of digits necessary to represent the integer part of the value
* in normal notation, then use exponential notation.
*
* sd {number} Integer, 1 to MAX_DP inclusive.
*/
P['toPrecision'] = function(sd) {
if (sd == null) {
return this.toString()
} else if (sd !== ~~sd || sd < 1 || sd > MAX_DP) {
throw '!toPre!'
}
return format(this, sd - 1, 2)
};
// EXPORT
// Node and other CommonJS-like environments that support module.exports.
if (typeof module !== 'undefined' && module.exports) {
module.exports = Big
//AMD.
} else if (typeof define == 'function' && define.amd) {
define(function() {
return Big
})
//Browser.
} else {
global['Big'] = Big
}
})(this);
</script>
<script>
// BigNumberMike.js v1.0.0 https://github.com/MikeMcl/BigNumberMike.js/LICENCE */
(function(global) {
var MAX = 1E9,
MAX_POWER = 1E6,
DECIMAL_PLACES = 20,
ROUNDING_MODE = 4,
TO_EXP_NEG = -7,
TO_EXP_POS = 21,
MIN_EXP = -MAX,
MAX_EXP = MAX,
ERRORS = true,
parse = parseInt,
P = BigNumberMike.prototype,
DIGITS = "0123456789abcdefghijklmnopqrstuvwxyz",
outOfRange, id = 0,
isValid = /^-?\d+(?:\.\d+)?(?:e[+-]?\d+)?$/i,
trim = String.prototype.trim ||
function() {
return this.replace(/^\s+|\s+$/g, "")
}, ONE = BigNumberMike(1);
function BigNumberMike(n, b) {
var isNum, i, j, x = this;
if (!(x instanceof BigNumberMike)) {
return new BigNumberMike(n, b)
}
if (n instanceof BigNumberMike) {
if (b !== i) {
n = n["toS"]()
} else {
x["s"] = n["s"];
x["e"] = n["e"];
x["c"] = (n = n["c"]) ? n.slice() : n;
return
}
}
if (typeof n != "string") {
n = (isNum = Object.prototype.toString.call(n) == "[object Number]") && n === 0 && 1 / n < 0 ? "-0" : n + ""
}
if (b === i && isValid.test(n)) {
x["s"] = n.charAt(0) == "-" ? (n = n.slice(1), -1) : 1
} else {
if (b == 10) {
return (new BigNumberMike(n))["div"](ONE)
}
n = trim.call(n).replace(/^\+([^-])/, "$1").replace(/^(-?)\./, "$10.");
x["s"] = n.charAt(0) == "-" ? (n = n.replace(/^-([^-])/, "$1"), -1) : 1;
if (b != null) {
if ((b == (b | 0) || !ERRORS) && !(outOfRange = !(b >= 2 && b <= 36))) {
i = "[" + DIGITS.slice(0, b = b | 0) + "]+";
if (j = (new RegExp("^" + i + "(?:\\." + i + ")?$", "i")).test(n)) {
if (isNum) {
if (n.replace(".", "").length > 15) {
ifExceptionsThrow(n, 0)
}
isNum = !isNum
}
n = convert(n, 10, b, x["s"])
} else {
if (n != "Infinity" && n != "NaN") {
ifExceptionsThrow(n, 1, b);
n = "NaN"
}
}
} else {
ifExceptionsThrow(b, 2);
j = isValid.test(n)
}
} else {
j = isValid.test(n)
}
if (!j) {
x["c"] = x["e"] = null;
if (n != "Infinity") {
if (n != "NaN") {
ifExceptionsThrow(n, 3)
}
x["s"] = null
}
return
}
}
if ((i = n.indexOf(".")) > -1) {
n = n.replace(".", "")
}
if ((j = n.search(/e/i)) > 0) {
if (i < 0) {
i = j
}
i += +n.slice(j + 1);
n = n.substring(0, j)
} else {
if (i < 0) {
i = n.length
}
}
if (b = n.length, isNum && b > 15) {
ifExceptionsThrow(n, 0)
}
for (j = 0; n.charAt(j) == "0"; j++) {}
if ((i -= j + 1) > MAX_EXP) {
x["c"] = x["e"] = null
} else {
if (j == b || i < MIN_EXP) {
x["c"] = [x["e"] = 0]
} else {
for (; n.charAt(--b) == "0";) {}
x["e"] = i;
x["c"] = [];
for (i = 0; j <= b; x["c"][i++] = +n.charAt(j++)) {}
}
}
}
BigNumberMike["ROUND_UP"] = 0;
BigNumberMike["ROUND_DOWN"] = 1;
BigNumberMike["ROUND_CEIL"] = 2;
BigNumberMike["ROUND_FLOOR"] = 3;
BigNumberMike["ROUND_HALF_UP"] = 4;
BigNumberMike["ROUND_HALF_DOWN"] = 5;
BigNumberMike["ROUND_HALF_EVEN"] = 6;
BigNumberMike["ROUND_HALF_CEIL"] = 7;
BigNumberMike["ROUND_HALF_FLOOR"] = 8;
BigNumberMike["config"] = function() {
var v, p, i = 0,
r = {},
a = arguments,
o = a[0],
c = "config",
inRange = function(n, lo, hi) {
return !((outOfRange = n < lo || n > hi) || parse(n) != n && n !== 0)
},
has = o && typeof o == "object" ?
function() {
if (o.hasOwnProperty(p)) {
return (v = o[p]) != null
}
} : function() {
if (a.length > i) {
return (v = a[i++]) != null
}
};
if (has(p = "DECIMAL_PLACES")) {
if (inRange(v, 0, MAX)) {
DECIMAL_PLACES = v | 0
} else {
ifExceptionsThrow(v, p, c)
}
}
r[p] = DECIMAL_PLACES;
if (has(p = "ROUNDING_MODE")) {
if (inRange(v, 0, 8)) {
ROUNDING_MODE = v | 0
} else {
ifExceptionsThrow(v, p, c)
}
}
r[p] = ROUNDING_MODE;
if (has(p = "EXPONENTIAL_AT")) {
if (inRange(v, -MAX, MAX)) {
TO_EXP_NEG = -(TO_EXP_POS = ~~ (v < 0 ? -v : +v))
} else {
if (!outOfRange && v && inRange(v[0], -MAX, 0) && inRange(v[1], 0, MAX)) {
TO_EXP_NEG = ~~v[0], TO_EXP_POS = ~~v[1]
} else {
ifExceptionsThrow(v, p, c, 1)
}
}
}
r[p] = [TO_EXP_NEG, TO_EXP_POS];
if (has(p = "RANGE")) {
if (inRange(v, -MAX, MAX) && ~~v) {
MIN_EXP = -(MAX_EXP = ~~ (v < 0 ? -v : +v))
} else {
if (!outOfRange && v && inRange(v[0], -MAX, -1) && inRange(v[1], 1, MAX)) {
MIN_EXP = ~~v[0], MAX_EXP = ~~v[1]
} else {
ifExceptionsThrow(v, p, c, 1, 1)
}
}
}
r[p] = [MIN_EXP, MAX_EXP];
if (has(p = "ERRORS")) {
if (v === !! v || v === 1 || v === 0) {
parse = (outOfRange = id = 0, ERRORS = !! v) ? parseInt : parseFloat
} else {
ifExceptionsThrow(v, p, c, 0, 0, 1)
}
}
r[p] = ERRORS;
return r
};
function ifExceptionsThrow(arg, i, j, isArray, isRange, isErrors) {
if (ERRORS) {
var method = ["new BigNumberMike", "cmp", "div", "eq", "gt", "gte", "lt", "lte", "minus", "mod", "plus", "times", "toFr"][id ? id < 0 ? -id : id : 1 / id < 0 ? 1 : 0] + "()",
error = outOfRange ? " out of range" : " not a" + (isRange ? " non-zero" : "n") + " integer";
error = ([method + " number type has more than 15 significant digits", method + " not a base " + j + " number", method + " base" + error, method + " not a number"][i] || j + "() " + i + (isErrors ? " not a boolean or binary digit" : error + (isArray ? " or not [" + (outOfRange ? " negative, positive" : " integer, integer") + " ]" : ""))) + ": " + arg;
outOfRange = id = 0;
throw {
name: "BigNumberMike Error",
message: error,
toString: function() {
return this.name + ": " + this.message
}
};
}
}
function convert(nStr, baseOut, baseIn, sign) {
var e, dvs, dvd, nArr, fracArr, fracBN;
function strToArr(str, bIn) {
var j, i = 0,
strL = str.length,
arrL, arr = [0];
for (bIn = bIn || baseIn; i < strL; i++) {
for (arrL = arr.length, j = 0; j < arrL; arr[j] *= bIn, j++) {}
for (arr[0] += DIGITS.indexOf(str.charAt(i)), j = 0; j < arr.length; j++) {
if (arr[j] > baseOut - 1) {
if (arr[j + 1] == null) {
arr[j + 1] = 0
}
arr[j + 1] += arr[j] / baseOut ^ 0;
arr[j] %= baseOut
}
}
}
return arr.reverse()
}
function arrToStr(arr) {
var i = 0,
arrL = arr.length,
str = "";
for (; i < arrL; str += DIGITS.charAt(arr[i++])) {}
return str
}
nStr = nStr.toLowerCase();
if ((e = nStr.indexOf(".")) > -1) {
e = nStr.length - e - 1;
dvs = strToArr((new BigNumberMike(baseIn))["pow"](e)["toF"](), 10);
nArr = nStr.split(".");
dvd = strToArr(nArr[1]);
nArr = strToArr(nArr[0]);
fracBN = divide(dvd, dvs, dvd.length - dvs.length, sign, baseOut, nArr[nArr.length - 1] & 1);
fracArr = fracBN["c"];
if (e = fracBN["e"]) {
for (; ++e; fracArr.unshift(0)) {}
nStr = arrToStr(nArr) + "." + arrToStr(fracArr)
} else {
if (fracArr[0]) {
if (nArr[e = nArr.length - 1] < baseOut - 1) {
++nArr[e];
nStr = arrToStr(nArr)
} else {
nStr = (new BigNumberMike(arrToStr(nArr), baseOut))["plus"](ONE)["toS"](baseOut)
}
} else {
nStr = arrToStr(nArr)
}
}
} else {
nStr = arrToStr(strToArr(nStr))
}
return nStr
}
function divide(dvd, dvs, exp, s, base, isOdd) {
var dvsL, dvsT, next, cmp, remI, dvsZ = dvs.slice(),
dvdI = dvsL = dvs.length,
dvdL = dvd.length,
rem = dvd.slice(0, dvsL),
remL = rem.length,
quo = new BigNumberMike(ONE),
qc = quo["c"] = [],
qi = 0,
dig = DECIMAL_PLACES + (quo["e"] = exp) + 1;
quo["s"] = s;
s = dig < 0 ? 0 : dig;
for (; remL++ < dvsL; rem.push(0)) {}
dvsZ.unshift(0);
do {
for (next = 0; next < base; next++) {
if (dvsL != (remL = rem.length)) {
cmp = dvsL > remL ? 1 : -1
} else {
for (remI = -1, cmp = 0; ++remI < dvsL;) {
if (dvs[remI] != rem[remI]) {
cmp = dvs[remI] > rem[remI] ? 1 : -1;
break
}
}
}
if (cmp < 0) {
for (dvsT = remL == dvsL ? dvs : dvsZ; remL;) {
if (rem[--remL] < dvsT[remL]) {
for (remI = remL; remI && !rem[--remI]; rem[remI] = base - 1) {}--rem[remI];
rem[remL] += base
}
rem[remL] -= dvsT[remL]
}
for (; !rem[0]; rem.shift()) {}
} else {
break
}
}
qc[qi++] = cmp ? next : ++next;
rem[0] && cmp ? rem[remL] = dvd[dvdI] || 0 : rem = [dvd[dvdI]]
} while ((dvdI++ < dvdL || rem[0] != null) && s--);
if (!qc[0] && qi != 1) {
--quo["e"];
qc.shift()
}
if (qi > dig) {
rnd(quo, DECIMAL_PLACES, base, isOdd, rem[0] != null)
}
if (quo["e"] > MAX_EXP) {
quo["c"] = quo["e"] = null
} else {
if (quo["e"] < MIN_EXP) {
quo["c"] = [quo["e"] = 0]
}
}
return quo
}
function format(n, d, exp) {
var i = d - (n = new BigNumberMike(n))["e"],
c = n["c"];
if (!c) {
return n["toS"]()
}
if (c.length > ++d) {
rnd(n, i, 10)
}
i = c[0] == 0 ? i + 1 : exp ? d : n["e"] + i + 1;
for (; c.length < i; c.push(0)) {}
i = n["e"];
return exp == 1 || exp == 2 && (--d < i || i <= TO_EXP_NEG) ? (n["s"] < 0 && c[0] ? "-" : "") + (c.length > 1 ? (c.splice(1, 0, "."), c.join("")) : c[0]) + (i < 0 ? "e" : "e+") + i : n["toS"]()
}
function rnd(x, dp, base, isOdd, r) {
var xc = x["c"],
isNeg = x["s"] < 0,
half = base / 2,
i = x["e"] + dp + 1,
next = xc[i],
more = r || i < 0 || xc[i + 1] != null;
r = ROUNDING_MODE < 4 ? (next != null || more) && (ROUNDING_MODE == 0 || ROUNDING_MODE == 2 && !isNeg || ROUNDING_MODE == 3 && isNeg) : next > half || next == half && (ROUNDING_MODE == 4 || more || ROUNDING_MODE == 6 && (xc[i - 1] & 1 || !dp && isOdd) || ROUNDING_MODE == 7 && !isNeg || ROUNDING_MODE == 8 && isNeg);
if (i < 1 || !xc[0]) {
xc.length = 0;
xc.push(0);
if (r) {
xc[0] = 1;
x["e"] = -dp
} else {
x["e"] = 0
}
return x
}
xc.length = i--;
if (r) {
for (--base; ++xc[i] > base;) {
xc[i] = 0;
if (!i--) {
++x["e"];
xc.unshift(1)
}
}
}
for (i = xc.length; !xc[--i]; xc.pop()) {}
return x
}
function setMode(x, dp, rm) {
var r = ROUNDING_MODE;
ROUNDING_MODE = rm;
x = new BigNumberMike(x);
x["c"] && rnd(x, dp, 10);
ROUNDING_MODE = r;
return x
}
P["abs"] = P["absoluteValue"] = function() {
var x = new BigNumberMike(this);
if (x["s"] < 0) {
x["s"] = 1
}
return x
};
P["ceil"] = function() {
return setMode(this, 0, 2)
};
P["comparedTo"] = P["cmp"] = function(y, b) {
var a, x = this,
xc = x["c"],
yc = (id = -id, y = new BigNumberMike(y, b))["c"],
i = x["s"],
j = y["s"],
k = x["e"],
l = y["e"];
if (!i || !j) {
return null
}
a = xc && !xc[0], b = yc && !yc[0];
if (a || b) {
return a ? b ? 0 : -j : i
}
if (i != j) {
return i
}
if (a = i < 0, b = k == l, !xc || !yc) {
return b ? 0 : !xc ^ a ? 1 : -1
}
if (!b) {
return k > l ^ a ? 1 : -1
}
for (i = -1, j = (k = xc.length) < (l = yc.length) ? k : l; ++i < j;) {
if (xc[i] != yc[i]) {
return xc[i] > yc[i] ^ a ? 1 : -1
}
}
return k == l ? 0 : k > l ^ a ? 1 : -1
};
P["dividedBy"] = P["div"] = function(y, b) {
var xc = this["c"],
xe = this["e"],
xs = this["s"],
yc = (id = 2, y = new BigNumberMike(y, b))["c"],
ye = y["e"],
ys = y["s"],
s = xs == ys ? 1 : -1;
return !xe && (!xc || !xc[0]) || !ye && (!yc || !yc[0]) ? new BigNumberMike(!xs || !ys || (xc ? yc && xc[0] == yc[0] : !yc) ? NaN : xc && xc[0] == 0 || !yc ? s * 0 : s / 0) : divide(xc, yc, xe - ye, s, 10)
};
P["equals"] = P["eq"] = function(n, b) {
id = 3;
return this["cmp"](n, b) === 0
};
P["floor"] = function() {
return setMode(this, 0, 3)
};
P["greaterThan"] = P["gt"] = function(n, b) {
id = 4;
return this["cmp"](n, b) > 0
};
P["greaterThanOrEqualTo"] = P["gte"] = function(n, b) {
id = 5;
return (b = this["cmp"](n, b)) == 1 || b === 0
};
P["isFinite"] = P["isF"] = function() {
return !!this["c"]
};
P["isNaN"] = function() {
return !this["s"]
};
P["isNegative"] = P["isNeg"] = function() {
return this["s"] < 0
};
P["isZero"] = P["isZ"] = function() {
return !!this["c"] && this["c"][0] == 0
};
P["lessThan"] = P["lt"] = function(n, b) {
id = 6;
return this["cmp"](n, b) < 0
};
P["lessThanOrEqualTo"] = P["lte"] = function(n, b) {
id = 7;
return (b = this["cmp"](n, b)) == -1 || b === 0
};
P["minus"] = function(y, b) {
var d, i, j, xLTy, x = this,
a = x["s"];
b = (id = 8, y = new BigNumberMike(y, b))["s"];
if (!a || !b) {
return new BigNumberMike(NaN)
}
if (a != b) {
return y["s"] = -b, x["plus"](y)
}
var xc = x["c"],
xe = x["e"],
yc = y["c"],
ye = y["e"];
if (!xe || !ye) {
if (!xc || !yc) {
return xc ? (y["s"] = -b, y) : new BigNumberMike(yc ? x : NaN)
}
if (!xc[0] || !yc[0]) {
return yc[0] ? (y["s"] = -b, y) : new BigNumberMike(xc[0] ? x : 0)
}
}
if (xc = xc.slice(), a = xe - ye) {
d = (xLTy = a < 0) ? (a = -a, xc) : (ye = xe, yc);
for (d.reverse(), b = a; b--; d.push(0)) {}
d.reverse()
} else {
j = ((xLTy = xc.length < yc.length) ? xc : yc).length;
for (a = b = 0; b < j; b++) {
if (xc[b] != yc[b]) {
xLTy = xc[b] < yc[b];
break
}
}
}
if (xLTy) {
d = xc, xc = yc, yc = d;
y["s"] = -y["s"]
}
if ((b = -((j = xc.length) - yc.length)) > 0) {
for (; b--; xc[j++] = 0) {}
}
for (b = yc.length; b > a;) {
if (xc[--b] < yc[b]) {
for (i = b; i && !xc[--i]; xc[i] = 9) {}--xc[i];
xc[b] += 10
}
xc[b] -= yc[b]
}
for (; xc[--j] == 0; xc.pop()) {}
for (; xc[0] == 0; xc.shift(), --ye) {}
if (ye < MIN_EXP || !xc[0]) {
xc = [ye = 0]
}
return y["c"] = xc, y["e"] = ye, y
};
P["modulo"] = P["mod"] = function(y, b) {
var x = this,
xc = x["c"],
yc = (id = 9, y = new BigNumberMike(y, b))["c"],
i = x["s"],
j = y["s"];
b = !i || !j || yc && !yc[0];
if (b || xc && !xc[0]) {
return new BigNumberMike(b ? NaN : x)
}
x["s"] = y["s"] = 1;
b = y["cmp"](x) == 1;
x["s"] = i, y["s"] = j;
return b ? new BigNumberMike(x) : (i = DECIMAL_PLACES, j = ROUNDING_MODE, DECIMAL_PLACES = 0, ROUNDING_MODE = 1, x = x["div"](y), DECIMAL_PLACES = i, ROUNDING_MODE = j, this["minus"](x["times"](y)))
};
P["negated"] = P["neg"] = function() {
var x = new BigNumberMike(this);
return x["s"] = -x["s"] || null, x
};
P["plus"] = function(y, b) {
var d, x = this,
a = x["s"];
b = (id = 10, y = new BigNumberMike(y, b))["s"];
if (!a || !b) {
return new BigNumberMike(NaN)
}
if (a != b) {
return y["s"] = -b, x["minus"](y)
}
var xe = x["e"],
xc = x["c"],
ye = y["e"],
yc = y["c"];
if (!xe || !ye) {
if (!xc || !yc) {
return new BigNumberMike(a / 0)
}
if (!xc[0] || !yc[0]) {
return yc[0] ? y : new BigNumberMike(xc[0] ? x : a * 0)
}
}
if (xc = xc.slice(), a = xe - ye) {
d = a > 0 ? (ye = xe, yc) : (a = -a, xc);
for (d.reverse(); a--; d.push(0)) {}
d.reverse()
}
if (xc.length - yc.length < 0) {
d = yc, yc = xc, xc = d
}
for (a = yc.length, b = 0; a; b = (xc[--a] = xc[a] + yc[a] + b) / 10 ^ 0, xc[a] %= 10) {}
if (b) {
xc.unshift(b);
if (++ye > MAX_EXP) {
xc = ye = null
}
}
for (a = xc.length; xc[--a] == 0; xc.pop()) {}
return y["c"] = xc, y["e"] = ye, y
};
P["toPower"] = P["pow"] = function(e) {
var y, i = e * 0 == 0 ? e | 0 : e,
x = new BigNumberMike(this),
y = new BigNumberMike(ONE);
if (((outOfRange = e < -MAX_POWER || e > MAX_POWER) && (i = e * 1 / 0) || parse(e) != e && e !== 0 && !(i = NaN)) && !ifExceptionsThrow(e, "exponent", "pow") || !i) {
return new BigNumberMike(Math.pow(x["toS"](), i))
}
for (i = i < 0 ? -i : i;;) {
if (i & 1) {
y = y["times"](x)
}
i >>= 1;
if (!i) {
break
}
x = x["times"](x)
}
return e < 0 ? ONE["div"](y) : y
};
P["round"] = function(dp, rm) {
dp = dp == null || ((outOfRange = dp < 0 || dp > MAX) || parse(dp) != dp) && !ifExceptionsThrow(dp, "decimal places", "round") ? 0 : dp | 0;
rm = rm == null || ((outOfRange = rm < 0 || rm > 8) || parse(rm) != rm && rm !== 0) && !ifExceptionsThrow(rm, "mode", "round") ? ROUNDING_MODE : rm | 0;
return setMode(this, dp, rm)
};
P["squareRoot"] = P["sqrt"] = function() {
var estimate, r, approx, x = this,
xc = x["c"],
i = x["s"],
e = x["e"],
half = new BigNumberMike("0.5");
if (i !== 1 || !xc || !xc[0]) {
return new BigNumberMike(!i || i < 0 && (!xc || xc[0]) ? NaN : xc ? x : 1 / 0)
}
i = Math.sqrt(x["toS"]());
if (i == 0 || i == 1 / 0) {
estimate = xc.join("");
if (!(estimate.length + e & 1)) {
estimate += "0"
}
r = new BigNumberMike(Math.sqrt(estimate).toString());
r["e"] = ((e + 1) / 2 | 0) - (e < 0 || e & 1)
} else {
r = new BigNumberMike(i.toString())
}
i = r["e"] + (DECIMAL_PLACES += 4);
do {
approx = r;
r = half["times"](approx["plus"](x["div"](approx)))
} while (approx["c"].slice(0, i).join("") !== r["c"].slice(0, i).join(""));
rnd(r, DECIMAL_PLACES -= 4, 10);
return r
};
P["times"] = function(y, b) {
var c, x = this,
xc = x["c"],
yc = (id = 11, y = new BigNumberMike(y, b))["c"],
i = x["e"],
j = y["e"],
a = x["s"];
y["s"] = a == (b = y["s"]) ? 1 : -1;
if (!i && (!xc || !xc[0]) || !j && (!yc || !yc[0])) {
return new BigNumberMike(!a || !b || xc && !xc[0] && !yc || yc && !yc[0] && !xc ? NaN : !xc || !yc ? y["s"] / 0 : y["s"] * 0)
}
y["e"] = i + j;
if ((a = xc.length) < (b = yc.length)) {
c = xc, xc = yc, yc = c, j = a, a = b, b = j
}
for (j = a + b, c = []; j--; c.push(0)) {}
for (i = b - 1; i > -1; i--) {
for (b = 0, j = a + i; j > i; b = c[j] + yc[i] * xc[j - i - 1] + b, c[j--] = b % 10 | 0, b = b / 10 | 0) {}
if (b) {
c[j] = (c[j] + b) % 10
}
}
b && ++y["e"];
!c[0] && c.shift();
for (j = c.length; !c[--j]; c.pop()) {}
y["c"] = y["e"] > MAX_EXP ? y["e"] = null : y["e"] < MIN_EXP ? [y["e"] = 0] : c;
return y
};
P["toExponential"] = P["toE"] = function(dp) {
return format(this, (dp == null || ((outOfRange = dp < 0 || dp > MAX) || parse(dp) != dp && dp !== 0) && !ifExceptionsThrow(dp, "decimal places", "toE")) && this["c"] ? this["c"].length - 1 : dp | 0, 1)
};
P["toFixed"] = P["toF"] = function(dp) {
var n, str, d, x = this;
if (!(dp == null || ((outOfRange = dp < 0 || dp > MAX) || parse(dp) != dp && dp !== 0) && !ifExceptionsThrow(dp, "decimal places", "toF"))) {
d = x["e"] + (dp | 0)
}
n = TO_EXP_NEG, dp = TO_EXP_POS;
TO_EXP_NEG = -(TO_EXP_POS = 1 / 0);
if (d == str) {
str = x["toS"]()
} else {
str = format(x, d);
if (x["s"] < 0 && x["c"]) {
if (!x["c"][0]) {
str = str.replace(/^-/, "")
} else {
if (str.indexOf("-") < 0) {
str = "-" + str
}
}
}
}
TO_EXP_NEG = n, TO_EXP_POS = dp;
return str
};
P["toFraction"] = P["toFr"] = function(maxD) {
var q, frac, n0, d0, d2, n, e, n1 = d0 = new BigNumberMike(ONE),
d1 = n0 = new BigNumberMike("0"),
x = this,
xc = x["c"],
exp = MAX_EXP,
dp = DECIMAL_PLACES,
rm = ROUNDING_MODE,
d = new BigNumberMike(ONE);
if (!xc) {
return x["toS"]()
}
e = d["e"] = xc.length - x["e"] - 1;
if (maxD == null || (!(id = 12, n = new BigNumberMike(maxD))["s"] || (outOfRange = n["cmp"](n1) < 0 || !n["c"]) || ERRORS && n["e"] < n["c"].length - 1) && !ifExceptionsThrow(maxD, "max denominator", "toFr") || (maxD = n)["cmp"](d) > 0) {
maxD = e > 0 ? d : n1
}
MAX_EXP = 1 / 0;
n = new BigNumberMike(xc.join(""));
for (DECIMAL_PLACES = 0, ROUNDING_MODE = 1;;) {
q = n["div"](d);
d2 = d0["plus"](q["times"](d1));
if (d2["cmp"](maxD) == 1) {
break
}
d0 = d1, d1 = d2;
n1 = n0["plus"](q["times"](d2 = n1));
n0 = d2;
d = n["minus"](q["times"](d2 = d));
n = d2
}
d2 = maxD["minus"](d0)["div"](d1);
n0 = n0["plus"](d2["times"](n1));
d0 = d0["plus"](d2["times"](d1));
n0["s"] = n1["s"] = x["s"];
DECIMAL_PLACES = e * 2;
ROUNDING_MODE = rm;
frac = n1["div"](d1)["minus"](x)["abs"]()["cmp"](n0["div"](d0)["minus"](x)["abs"]()) < 1 ? [n1["toS"](), d1["toS"]()] : [n0["toS"](), d0["toS"]()];
return MAX_EXP = exp, DECIMAL_PLACES = dp, frac
};
P["toPrecision"] = P["toP"] = function(sd) {
return sd == null || ((outOfRange = sd < 1 || sd > MAX) || parse(sd) != sd) && !ifExceptionsThrow(sd, "precision", "toP") ? this["toS"]() : format(this, --sd | 0, 2)
};
P["toString"] = P["toS"] = function(b) {
var u, str, strL, x = this,
xe = x["e"];
if (xe === null) {
str = x["s"] ? "Infinity" : "NaN"
} else {
if (b === u && (xe <= TO_EXP_NEG || xe >= TO_EXP_POS)) {
return format(x, x["c"].length - 1, 1)
} else {
str = x["c"].join("");
if (xe < 0) {
for (; ++xe; str = "0" + str) {}
str = "0." + str
} else {
if (strL = str.length, xe > 0) {
if (++xe > strL) {
for (xe -= strL; xe--; str += "0") {}
} else {
if (xe < strL) {
str = str.slice(0, xe) + "." + str.slice(xe)
}
}
} else {
if (u = str.charAt(0), strL > 1) {
str = u + "." + str.slice(1)
} else {
if (u == "0") {
return u
}
}
}
}
if (b != null) {
if (!(outOfRange = !(b >= 2 && b <= 36)) && (b == (b | 0) || !ERRORS)) {
str = convert(str, b | 0, 10, x["s"]);
if (str == "0") {
return str
}
} else {
ifExceptionsThrow(b, "base", "toS")
}
}
}
}
return x["s"] < 0 ? "-" + str : str
};
P["valueOf"] = function() {
return this["toS"]()
};
if (typeof module !== "undefined" && module.exports) {
module.exports = BigNumberMike
} else {
if (typeof define == "function" && define.amd) {
define(function() {
return BigNumberMike
})
} else {
global["BigNumberMike"] = BigNumberMike
}
}
})(this);
</script>
<script>
/*
JavaScript silentBigInteger library version 0.9
http://silentmatt.com/biginteger/
Copyright (c) 2009 Matthew Crumley <email@matthewcrumley.com>
Copyright (c) 2010,2011 by John Tobey <John.Tobey@gmail.com>
Licensed under the MIT license.
Support for arbitrary internal representation base was added by
Vitaly Magerya.
*/
/*
File: biginteger.js
Exports:
<silentBigInteger>
*/
(function(exports) {
"use strict";
/*
Class: silentBigInteger
An arbitrarily-large integer.
<silentBigInteger> 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 <silentBigInteger> instances can be called "statically". The
static versions are convenient if you don't already have a <silentBigInteger>
object.
As an example, these calls are equivalent.
> silentBigInteger(4).multiply(5); // returns silentBigInteger(20);
> silentBigInteger.multiply(4, 5); // returns silentBigInteger(20);
> var a = 42;
> var a = silentBigInteger.toJSValue("0b101010"); // Not completely useless...
*/
// IE doesn't support Array.prototype.map
if (!Array.prototype.map) {
Array.prototype.map = function(fun /*, thisp*/ ) {
var len = this.length >>> 0;
if (typeof fun !== "function") {
throw new TypeError();
}
var res = new Array(len);
var thisp = arguments[1];
for (var i = 0; i < len; i++) {
if (i in this) {
res[i] = fun.call(thisp, this[i], i, this);
}
}
return res;
};
}
var CONSTRUCT = {}; // Unique token to call "private" version of constructor
/*
Constructor: silentBigInteger()
Convert a value to a <silentBigInteger>.
Although <silentBigInteger()> is the constructor for <silentBigInteger> objects, it is
best not to call it as a constructor. If *n* is a <silentBigInteger> object, it is
simply returned as-is. Otherwise, <silentBigInteger()> is equivalent to <parse>
without a radix argument.
> var n0 = silentBigInteger(); // Same as <silentBigInteger.ZERO>
> var n1 = silentBigInteger("123"); // Create a new <silentBigInteger> with value 123
> var n2 = silentBigInteger(123); // Create a new <silentBigInteger> with value 123
> var n3 = silentBigInteger(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 silentBigInteger.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 silentBigInteger([5], -1): create a new silentBigInteger with value -5
Parameters:
n - Value to convert to a <silentBigInteger>.
Returns:
A <silentBigInteger> value.
See Also:
<parse>, <silentBigInteger>
*/
function silentBigInteger(n, s, token) {
if (token !== CONSTRUCT) {
if (n instanceof silentBigInteger) {
return n;
} else if (typeof n === "undefined") {
return ZERO;
}
return silentBigInteger.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;
}
silentBigInteger._construct = function(n, s) {
return new silentBigInteger(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;
silentBigInteger.base = BigInteger_base;
silentBigInteger.base_log10 = BigInteger_base_log10;
var ZERO = new silentBigInteger([], 0, CONSTRUCT);
// Constant: ZERO
// <silentBigInteger> 0.
silentBigInteger.ZERO = ZERO;
var ONE = new silentBigInteger([1], 1, CONSTRUCT);
// Constant: ONE
// <silentBigInteger> 1.
silentBigInteger.ONE = ONE;
var M_ONE = new silentBigInteger(ONE._d, -1, CONSTRUCT);
// Constant: M_ONE
// <silentBigInteger> -1.
silentBigInteger.M_ONE = M_ONE;
// Constant: _0
// Shortcut for <ZERO>.
silentBigInteger._0 = ZERO;
// Constant: _1
// Shortcut for <ONE>.
silentBigInteger._1 = ONE;
/*
Constant: small
Array of <BigIntegers> from 0 to 36.
These are used internally for parsing, but useful when you need a "small"
<silentBigInteger>.
See Also:
<ZERO>, <ONE>, <_0>, <_1>
*/
silentBigInteger.small = [
ZERO, ONE, /* Assuming BigInteger_base > 36 */
new silentBigInteger([2], 1, CONSTRUCT), new silentBigInteger([3], 1, CONSTRUCT), new silentBigInteger([4], 1, CONSTRUCT), new silentBigInteger([5], 1, CONSTRUCT), new silentBigInteger([6], 1, CONSTRUCT), new silentBigInteger([7], 1, CONSTRUCT), new silentBigInteger([8], 1, CONSTRUCT), new silentBigInteger([9], 1, CONSTRUCT), new silentBigInteger([10], 1, CONSTRUCT), new silentBigInteger([11], 1, CONSTRUCT), new silentBigInteger([12], 1, CONSTRUCT), new silentBigInteger([13], 1, CONSTRUCT), new silentBigInteger([14], 1, CONSTRUCT), new silentBigInteger([15], 1, CONSTRUCT), new silentBigInteger([16], 1, CONSTRUCT), new silentBigInteger([17], 1, CONSTRUCT), new silentBigInteger([18], 1, CONSTRUCT), new silentBigInteger([19], 1, CONSTRUCT), new silentBigInteger([20], 1, CONSTRUCT), new silentBigInteger([21], 1, CONSTRUCT), new silentBigInteger([22], 1, CONSTRUCT), new silentBigInteger([23], 1, CONSTRUCT), new silentBigInteger([24], 1, CONSTRUCT), new silentBigInteger([25], 1, CONSTRUCT), new silentBigInteger([26], 1, CONSTRUCT), new silentBigInteger([27], 1, CONSTRUCT), new silentBigInteger([28], 1, CONSTRUCT), new silentBigInteger([29], 1, CONSTRUCT), new silentBigInteger([30], 1, CONSTRUCT), new silentBigInteger([31], 1, CONSTRUCT), new silentBigInteger([32], 1, CONSTRUCT), new silentBigInteger([33], 1, CONSTRUCT), new silentBigInteger([34], 1, CONSTRUCT), new silentBigInteger([35], 1, CONSTRUCT), new silentBigInteger([36], 1, CONSTRUCT)];
// Used for parsing/radix conversion
silentBigInteger.digits = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ".split("");
/*
Method: toString
Convert a <silentBigInteger> 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 <silentBigInteger>.
*/
silentBigInteger.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 = silentBigInteger.digits;
base = silentBigInteger.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
silentBigInteger.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 <silentBigInteger>.
*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:
> silentBigInteger.parse("1e9"); // Same as "1000000000"
> silentBigInteger.parse("1.234*10^3"); // Same as 1234
> silentBigInteger.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 <silentBigInteger> instance.
*/
silentBigInteger.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 (!(silentBigInteger.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 - silentBigInteger.base_log10, silentBigInteger.base_log10).join(''), 10));
}
d.push(parseInt(digits.join(''), 10));
return new silentBigInteger(d, sign, CONSTRUCT);
}
// Optimize base
if (base === BigInteger_base) {
return new silentBigInteger(digits.map(Number).reverse(), sign, CONSTRUCT);
}
// Do the conversion
var d = ZERO;
base = silentBigInteger.small[base];
var small = silentBigInteger.small;
for (var i = 0; i < digits.length; i++) {
d = d.multiply(base).add(small[parseInt(digits[i], 36)]);
}
return new silentBigInteger(d._d, sign, CONSTRUCT);
} else {
throw new Error("Invalid silentBigInteger format: " + s);
}
};
/*
Function: add
Add two <BigIntegers>.
Parameters:
n - The number to add to *this*. Will be converted to a <silentBigInteger>.
Returns:
The numbers added together.
See Also:
<subtract>, <multiply>, <quotient>, <next>
*/
silentBigInteger.prototype.add = function(n) {
if (this._s === 0) {
return silentBigInteger(n);
}
n = silentBigInteger(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 silentBigInteger(sum, this._s, CONSTRUCT);
};
/*
Function: negate
Get the additive inverse of a <silentBigInteger>.
Returns:
A <silentBigInteger> with the same magnatude, but with the opposite sign.
See Also:
<abs>
*/
silentBigInteger.prototype.negate = function() {
return new silentBigInteger(this._d, (-this._s) | 0, CONSTRUCT);
};
/*
Function: abs
Get the absolute value of a <silentBigInteger>.
Returns:
A <silentBigInteger> with the same magnatude, but always positive (or zero).
See Also:
<negate>
*/
silentBigInteger.prototype.abs = function() {
return (this._s < 0) ? this.negate() : this;
};
/*
Function: subtract
Subtract two <BigIntegers>.
Parameters:
n - The number to subtract from *this*. Will be converted to a <silentBigInteger>.
Returns:
The *n* subtracted from *this*.
See Also:
<add>, <multiply>, <quotient>, <prev>
*/
silentBigInteger.prototype.subtract = function(n) {
if (this._s === 0) {
return silentBigInteger(n).negate();
}
n = silentBigInteger(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 silentBigInteger(n._d, 1, CONSTRUCT);
n = new silentBigInteger(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 silentBigInteger(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 silentBigInteger(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 silentBigInteger(sum, sign, CONSTRUCT);
}
/*
Function: next
Get the next <silentBigInteger> (add one).
Returns:
*this* + 1.
See Also:
<add>, <prev>
*/
silentBigInteger.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 <silentBigInteger> (subtract one).
Returns:
*this* - 1.
See Also:
<next>, <subtract>
*/
silentBigInteger.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 <BigIntegers>.
Calling <compareAbs> is faster than calling <abs> twice, then <compare>.
Parameters:
n - The number to compare to *this*. Will be converted to a <silentBigInteger>.
Returns:
-1, 0, or +1 if *|this|* is less than, equal to, or greater than *|n|*.
See Also:
<compare>, <abs>
*/
silentBigInteger.prototype.compareAbs = function(n) {
if (this === n) {
return 0;
}
if (!(n instanceof silentBigInteger)) {
if (!isFinite(n)) {
return (isNaN(n) ? n : -1);
}
n = silentBigInteger(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 <BigIntegers>.
Parameters:
n - The number to compare to *this*. Will be converted to a <silentBigInteger>.
Returns:
-1, 0, or +1 if *this* is less than, equal to, or greater than *n*.
See Also:
<compareAbs>, <isPositive>, <isNegative>, <isUnit>
*/
silentBigInteger.prototype.compare = function(n) {
if (this === n) {
return 0;
}
n = silentBigInteger(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 <silentBigInteger.ONE> or <silentBigInteger.M_ONE>.
See Also:
<isZero>, <isNegative>, <isPositive>, <compareAbs>, <compare>,
<silentBigInteger.ONE>, <silentBigInteger.M_ONE>
*/
silentBigInteger.