time-to-botec

Benchmark sampling in different programming languages
Log | Files | Refs | README

BigInteger.js (51934B)

      1 var bigInt = (function (undefined) {
      2     "use strict";
      3 
      4     var BASE = 1e7,
      5         LOG_BASE = 7,
      6         MAX_INT = 9007199254740992,
      7         MAX_INT_ARR = smallToArray(MAX_INT),
      8         DEFAULT_ALPHABET = "0123456789abcdefghijklmnopqrstuvwxyz";
      9 
     10     var supportsNativeBigInt = typeof BigInt === "function";
     11 
     12     function Integer(v, radix, alphabet, caseSensitive) {
     13         if (typeof v === "undefined") return Integer[0];
     14         if (typeof radix !== "undefined") return +radix === 10 && !alphabet ? parseValue(v) : parseBase(v, radix, alphabet, caseSensitive);
     15         return parseValue(v);
     16     }
     17 
     18     function BigInteger(value, sign) {
     19         this.value = value;
     20         this.sign = sign;
     21         this.isSmall = false;
     22     }
     23     BigInteger.prototype = Object.create(Integer.prototype);
     24 
     25     function SmallInteger(value) {
     26         this.value = value;
     27         this.sign = value < 0;
     28         this.isSmall = true;
     29     }
     30     SmallInteger.prototype = Object.create(Integer.prototype);
     31 
     32     function NativeBigInt(value) {
     33         this.value = value;
     34     }
     35     NativeBigInt.prototype = Object.create(Integer.prototype);
     36 
     37     function isPrecise(n) {
     38         return -MAX_INT < n && n < MAX_INT;
     39     }
     40 
     41     function smallToArray(n) { // For performance reasons doesn't reference BASE, need to change this function if BASE changes
     42         if (n < 1e7)
     43             return [n];
     44         if (n < 1e14)
     45             return [n % 1e7, Math.floor(n / 1e7)];
     46         return [n % 1e7, Math.floor(n / 1e7) % 1e7, Math.floor(n / 1e14)];
     47     }
     48 
     49     function arrayToSmall(arr) { // If BASE changes this function may need to change
     50         trim(arr);
     51         var length = arr.length;
     52         if (length < 4 && compareAbs(arr, MAX_INT_ARR) < 0) {
     53             switch (length) {
     54                 case 0: return 0;
     55                 case 1: return arr[0];
     56                 case 2: return arr[0] + arr[1] * BASE;
     57                 default: return arr[0] + (arr[1] + arr[2] * BASE) * BASE;
     58             }
     59         }
     60         return arr;
     61     }
     62 
     63     function trim(v) {
     64         var i = v.length;
     65         while (v[--i] === 0);
     66         v.length = i + 1;
     67     }
     68 
     69     function createArray(length) { // function shamelessly stolen from Yaffle's library https://github.com/Yaffle/BigInteger
     70         var x = new Array(length);
     71         var i = -1;
     72         while (++i < length) {
     73             x[i] = 0;
     74         }
     75         return x;
     76     }
     77 
     78     function truncate(n) {
     79         if (n > 0) return Math.floor(n);
     80         return Math.ceil(n);
     81     }
     82 
     83     function add(a, b) { // assumes a and b are arrays with a.length >= b.length
     84         var l_a = a.length,
     85             l_b = b.length,
     86             r = new Array(l_a),
     87             carry = 0,
     88             base = BASE,
     89             sum, i;
     90         for (i = 0; i < l_b; i++) {
     91             sum = a[i] + b[i] + carry;
     92             carry = sum >= base ? 1 : 0;
     93             r[i] = sum - carry * base;
     94         }
     95         while (i < l_a) {
     96             sum = a[i] + carry;
     97             carry = sum === base ? 1 : 0;
     98             r[i++] = sum - carry * base;
     99         }
    100         if (carry > 0) r.push(carry);
    101         return r;
    102     }
    103 
    104     function addAny(a, b) {
    105         if (a.length >= b.length) return add(a, b);
    106         return add(b, a);
    107     }
    108 
    109     function addSmall(a, carry) { // assumes a is array, carry is number with 0 <= carry < MAX_INT
    110         var l = a.length,
    111             r = new Array(l),
    112             base = BASE,
    113             sum, i;
    114         for (i = 0; i < l; i++) {
    115             sum = a[i] - base + carry;
    116             carry = Math.floor(sum / base);
    117             r[i] = sum - carry * base;
    118             carry += 1;
    119         }
    120         while (carry > 0) {
    121             r[i++] = carry % base;
    122             carry = Math.floor(carry / base);
    123         }
    124         return r;
    125     }
    126 
    127     BigInteger.prototype.add = function (v) {
    128         var n = parseValue(v);
    129         if (this.sign !== n.sign) {
    130             return this.subtract(n.negate());
    131         }
    132         var a = this.value, b = n.value;
    133         if (n.isSmall) {
    134             return new BigInteger(addSmall(a, Math.abs(b)), this.sign);
    135         }
    136         return new BigInteger(addAny(a, b), this.sign);
    137     };
    138     BigInteger.prototype.plus = BigInteger.prototype.add;
    139 
    140     SmallInteger.prototype.add = function (v) {
    141         var n = parseValue(v);
    142         var a = this.value;
    143         if (a < 0 !== n.sign) {
    144             return this.subtract(n.negate());
    145         }
    146         var b = n.value;
    147         if (n.isSmall) {
    148             if (isPrecise(a + b)) return new SmallInteger(a + b);
    149             b = smallToArray(Math.abs(b));
    150         }
    151         return new BigInteger(addSmall(b, Math.abs(a)), a < 0);
    152     };
    153     SmallInteger.prototype.plus = SmallInteger.prototype.add;
    154 
    155     NativeBigInt.prototype.add = function (v) {
    156         return new NativeBigInt(this.value + parseValue(v).value);
    157     }
    158     NativeBigInt.prototype.plus = NativeBigInt.prototype.add;
    159 
    160     function subtract(a, b) { // assumes a and b are arrays with a >= b
    161         var a_l = a.length,
    162             b_l = b.length,
    163             r = new Array(a_l),
    164             borrow = 0,
    165             base = BASE,
    166             i, difference;
    167         for (i = 0; i < b_l; i++) {
    168             difference = a[i] - borrow - b[i];
    169             if (difference < 0) {
    170                 difference += base;
    171                 borrow = 1;
    172             } else borrow = 0;
    173             r[i] = difference;
    174         }
    175         for (i = b_l; i < a_l; i++) {
    176             difference = a[i] - borrow;
    177             if (difference < 0) difference += base;
    178             else {
    179                 r[i++] = difference;
    180                 break;
    181             }
    182             r[i] = difference;
    183         }
    184         for (; i < a_l; i++) {
    185             r[i] = a[i];
    186         }
    187         trim(r);
    188         return r;
    189     }
    190 
    191     function subtractAny(a, b, sign) {
    192         var value;
    193         if (compareAbs(a, b) >= 0) {
    194             value = subtract(a, b);
    195         } else {
    196             value = subtract(b, a);
    197             sign = !sign;
    198         }
    199         value = arrayToSmall(value);
    200         if (typeof value === "number") {
    201             if (sign) value = -value;
    202             return new SmallInteger(value);
    203         }
    204         return new BigInteger(value, sign);
    205     }
    206 
    207     function subtractSmall(a, b, sign) { // assumes a is array, b is number with 0 <= b < MAX_INT
    208         var l = a.length,
    209             r = new Array(l),
    210             carry = -b,
    211             base = BASE,
    212             i, difference;
    213         for (i = 0; i < l; i++) {
    214             difference = a[i] + carry;
    215             carry = Math.floor(difference / base);
    216             difference %= base;
    217             r[i] = difference < 0 ? difference + base : difference;
    218         }
    219         r = arrayToSmall(r);
    220         if (typeof r === "number") {
    221             if (sign) r = -r;
    222             return new SmallInteger(r);
    223         } return new BigInteger(r, sign);
    224     }
    225 
    226     BigInteger.prototype.subtract = function (v) {
    227         var n = parseValue(v);
    228         if (this.sign !== n.sign) {
    229             return this.add(n.negate());
    230         }
    231         var a = this.value, b = n.value;
    232         if (n.isSmall)
    233             return subtractSmall(a, Math.abs(b), this.sign);
    234         return subtractAny(a, b, this.sign);
    235     };
    236     BigInteger.prototype.minus = BigInteger.prototype.subtract;
    237 
    238     SmallInteger.prototype.subtract = function (v) {
    239         var n = parseValue(v);
    240         var a = this.value;
    241         if (a < 0 !== n.sign) {
    242             return this.add(n.negate());
    243         }
    244         var b = n.value;
    245         if (n.isSmall) {
    246             return new SmallInteger(a - b);
    247         }
    248         return subtractSmall(b, Math.abs(a), a >= 0);
    249     };
    250     SmallInteger.prototype.minus = SmallInteger.prototype.subtract;
    251 
    252     NativeBigInt.prototype.subtract = function (v) {
    253         return new NativeBigInt(this.value - parseValue(v).value);
    254     }
    255     NativeBigInt.prototype.minus = NativeBigInt.prototype.subtract;
    256 
    257     BigInteger.prototype.negate = function () {
    258         return new BigInteger(this.value, !this.sign);
    259     };
    260     SmallInteger.prototype.negate = function () {
    261         var sign = this.sign;
    262         var small = new SmallInteger(-this.value);
    263         small.sign = !sign;
    264         return small;
    265     };
    266     NativeBigInt.prototype.negate = function () {
    267         return new NativeBigInt(-this.value);
    268     }
    269 
    270     BigInteger.prototype.abs = function () {
    271         return new BigInteger(this.value, false);
    272     };
    273     SmallInteger.prototype.abs = function () {
    274         return new SmallInteger(Math.abs(this.value));
    275     };
    276     NativeBigInt.prototype.abs = function () {
    277         return new NativeBigInt(this.value >= 0 ? this.value : -this.value);
    278     }
    279 
    280 
    281     function multiplyLong(a, b) {
    282         var a_l = a.length,
    283             b_l = b.length,
    284             l = a_l + b_l,
    285             r = createArray(l),
    286             base = BASE,
    287             product, carry, i, a_i, b_j;
    288         for (i = 0; i < a_l; ++i) {
    289             a_i = a[i];
    290             for (var j = 0; j < b_l; ++j) {
    291                 b_j = b[j];
    292                 product = a_i * b_j + r[i + j];
    293                 carry = Math.floor(product / base);
    294                 r[i + j] = product - carry * base;
    295                 r[i + j + 1] += carry;
    296             }
    297         }
    298         trim(r);
    299         return r;
    300     }
    301 
    302     function multiplySmall(a, b) { // assumes a is array, b is number with |b| < BASE
    303         var l = a.length,
    304             r = new Array(l),
    305             base = BASE,
    306             carry = 0,
    307             product, i;
    308         for (i = 0; i < l; i++) {
    309             product = a[i] * b + carry;
    310             carry = Math.floor(product / base);
    311             r[i] = product - carry * base;
    312         }
    313         while (carry > 0) {
    314             r[i++] = carry % base;
    315             carry = Math.floor(carry / base);
    316         }
    317         return r;
    318     }
    319 
    320     function shiftLeft(x, n) {
    321         var r = [];
    322         while (n-- > 0) r.push(0);
    323         return r.concat(x);
    324     }
    325 
    326     function multiplyKaratsuba(x, y) {
    327         var n = Math.max(x.length, y.length);
    328 
    329         if (n <= 30) return multiplyLong(x, y);
    330         n = Math.ceil(n / 2);
    331 
    332         var b = x.slice(n),
    333             a = x.slice(0, n),
    334             d = y.slice(n),
    335             c = y.slice(0, n);
    336 
    337         var ac = multiplyKaratsuba(a, c),
    338             bd = multiplyKaratsuba(b, d),
    339             abcd = multiplyKaratsuba(addAny(a, b), addAny(c, d));
    340 
    341         var product = addAny(addAny(ac, shiftLeft(subtract(subtract(abcd, ac), bd), n)), shiftLeft(bd, 2 * n));
    342         trim(product);
    343         return product;
    344     }
    345 
    346     // The following function is derived from a surface fit of a graph plotting the performance difference
    347     // between long multiplication and karatsuba multiplication versus the lengths of the two arrays.
    348     function useKaratsuba(l1, l2) {
    349         return -0.012 * l1 - 0.012 * l2 + 0.000015 * l1 * l2 > 0;
    350     }
    351 
    352     BigInteger.prototype.multiply = function (v) {
    353         var n = parseValue(v),
    354             a = this.value, b = n.value,
    355             sign = this.sign !== n.sign,
    356             abs;
    357         if (n.isSmall) {
    358             if (b === 0) return Integer[0];
    359             if (b === 1) return this;
    360             if (b === -1) return this.negate();
    361             abs = Math.abs(b);
    362             if (abs < BASE) {
    363                 return new BigInteger(multiplySmall(a, abs), sign);
    364             }
    365             b = smallToArray(abs);
    366         }
    367         if (useKaratsuba(a.length, b.length)) // Karatsuba is only faster for certain array sizes
    368             return new BigInteger(multiplyKaratsuba(a, b), sign);
    369         return new BigInteger(multiplyLong(a, b), sign);
    370     };
    371 
    372     BigInteger.prototype.times = BigInteger.prototype.multiply;
    373 
    374     function multiplySmallAndArray(a, b, sign) { // a >= 0
    375         if (a < BASE) {
    376             return new BigInteger(multiplySmall(b, a), sign);
    377         }
    378         return new BigInteger(multiplyLong(b, smallToArray(a)), sign);
    379     }
    380     SmallInteger.prototype._multiplyBySmall = function (a) {
    381         if (isPrecise(a.value * this.value)) {
    382             return new SmallInteger(a.value * this.value);
    383         }
    384         return multiplySmallAndArray(Math.abs(a.value), smallToArray(Math.abs(this.value)), this.sign !== a.sign);
    385     };
    386     BigInteger.prototype._multiplyBySmall = function (a) {
    387         if (a.value === 0) return Integer[0];
    388         if (a.value === 1) return this;
    389         if (a.value === -1) return this.negate();
    390         return multiplySmallAndArray(Math.abs(a.value), this.value, this.sign !== a.sign);
    391     };
    392     SmallInteger.prototype.multiply = function (v) {
    393         return parseValue(v)._multiplyBySmall(this);
    394     };
    395     SmallInteger.prototype.times = SmallInteger.prototype.multiply;
    396 
    397     NativeBigInt.prototype.multiply = function (v) {
    398         return new NativeBigInt(this.value * parseValue(v).value);
    399     }
    400     NativeBigInt.prototype.times = NativeBigInt.prototype.multiply;
    401 
    402     function square(a) {
    403         //console.assert(2 * BASE * BASE < MAX_INT);
    404         var l = a.length,
    405             r = createArray(l + l),
    406             base = BASE,
    407             product, carry, i, a_i, a_j;
    408         for (i = 0; i < l; i++) {
    409             a_i = a[i];
    410             carry = 0 - a_i * a_i;
    411             for (var j = i; j < l; j++) {
    412                 a_j = a[j];
    413                 product = 2 * (a_i * a_j) + r[i + j] + carry;
    414                 carry = Math.floor(product / base);
    415                 r[i + j] = product - carry * base;
    416             }
    417             r[i + l] = carry;
    418         }
    419         trim(r);
    420         return r;
    421     }
    422 
    423     BigInteger.prototype.square = function () {
    424         return new BigInteger(square(this.value), false);
    425     };
    426 
    427     SmallInteger.prototype.square = function () {
    428         var value = this.value * this.value;
    429         if (isPrecise(value)) return new SmallInteger(value);
    430         return new BigInteger(square(smallToArray(Math.abs(this.value))), false);
    431     };
    432 
    433     NativeBigInt.prototype.square = function (v) {
    434         return new NativeBigInt(this.value * this.value);
    435     }
    436 
    437     function divMod1(a, b) { // Left over from previous version. Performs faster than divMod2 on smaller input sizes.
    438         var a_l = a.length,
    439             b_l = b.length,
    440             base = BASE,
    441             result = createArray(b.length),
    442             divisorMostSignificantDigit = b[b_l - 1],
    443             // normalization
    444             lambda = Math.ceil(base / (2 * divisorMostSignificantDigit)),
    445             remainder = multiplySmall(a, lambda),
    446             divisor = multiplySmall(b, lambda),
    447             quotientDigit, shift, carry, borrow, i, l, q;
    448         if (remainder.length <= a_l) remainder.push(0);
    449         divisor.push(0);
    450         divisorMostSignificantDigit = divisor[b_l - 1];
    451         for (shift = a_l - b_l; shift >= 0; shift--) {
    452             quotientDigit = base - 1;
    453             if (remainder[shift + b_l] !== divisorMostSignificantDigit) {
    454                 quotientDigit = Math.floor((remainder[shift + b_l] * base + remainder[shift + b_l - 1]) / divisorMostSignificantDigit);
    455             }
    456             // quotientDigit <= base - 1
    457             carry = 0;
    458             borrow = 0;
    459             l = divisor.length;
    460             for (i = 0; i < l; i++) {
    461                 carry += quotientDigit * divisor[i];
    462                 q = Math.floor(carry / base);
    463                 borrow += remainder[shift + i] - (carry - q * base);
    464                 carry = q;
    465                 if (borrow < 0) {
    466                     remainder[shift + i] = borrow + base;
    467                     borrow = -1;
    468                 } else {
    469                     remainder[shift + i] = borrow;
    470                     borrow = 0;
    471                 }
    472             }
    473             while (borrow !== 0) {
    474                 quotientDigit -= 1;
    475                 carry = 0;
    476                 for (i = 0; i < l; i++) {
    477                     carry += remainder[shift + i] - base + divisor[i];
    478                     if (carry < 0) {
    479                         remainder[shift + i] = carry + base;
    480                         carry = 0;
    481                     } else {
    482                         remainder[shift + i] = carry;
    483                         carry = 1;
    484                     }
    485                 }
    486                 borrow += carry;
    487             }
    488             result[shift] = quotientDigit;
    489         }
    490         // denormalization
    491         remainder = divModSmall(remainder, lambda)[0];
    492         return [arrayToSmall(result), arrayToSmall(remainder)];
    493     }
    494 
    495     function divMod2(a, b) { // Implementation idea shamelessly stolen from Silent Matt's library http://silentmatt.com/biginteger/
    496         // Performs faster than divMod1 on larger input sizes.
    497         var a_l = a.length,
    498             b_l = b.length,
    499             result = [],
    500             part = [],
    501             base = BASE,
    502             guess, xlen, highx, highy, check;
    503         while (a_l) {
    504             part.unshift(a[--a_l]);
    505             trim(part);
    506             if (compareAbs(part, b) < 0) {
    507                 result.push(0);
    508                 continue;
    509             }
    510             xlen = part.length;
    511             highx = part[xlen - 1] * base + part[xlen - 2];
    512             highy = b[b_l - 1] * base + b[b_l - 2];
    513             if (xlen > b_l) {
    514                 highx = (highx + 1) * base;
    515             }
    516             guess = Math.ceil(highx / highy);
    517             do {
    518                 check = multiplySmall(b, guess);
    519                 if (compareAbs(check, part) <= 0) break;
    520                 guess--;
    521             } while (guess);
    522             result.push(guess);
    523             part = subtract(part, check);
    524         }
    525         result.reverse();
    526         return [arrayToSmall(result), arrayToSmall(part)];
    527     }
    528 
    529     function divModSmall(value, lambda) {
    530         var length = value.length,
    531             quotient = createArray(length),
    532             base = BASE,
    533             i, q, remainder, divisor;
    534         remainder = 0;
    535         for (i = length - 1; i >= 0; --i) {
    536             divisor = remainder * base + value[i];
    537             q = truncate(divisor / lambda);
    538             remainder = divisor - q * lambda;
    539             quotient[i] = q | 0;
    540         }
    541         return [quotient, remainder | 0];
    542     }
    543 
    544     function divModAny(self, v) {
    545         var value, n = parseValue(v);
    546         if (supportsNativeBigInt) {
    547             return [new NativeBigInt(self.value / n.value), new NativeBigInt(self.value % n.value)];
    548         }
    549         var a = self.value, b = n.value;
    550         var quotient;
    551         if (b === 0) throw new Error("Cannot divide by zero");
    552         if (self.isSmall) {
    553             if (n.isSmall) {
    554                 return [new SmallInteger(truncate(a / b)), new SmallInteger(a % b)];
    555             }
    556             return [Integer[0], self];
    557         }
    558         if (n.isSmall) {
    559             if (b === 1) return [self, Integer[0]];
    560             if (b == -1) return [self.negate(), Integer[0]];
    561             var abs = Math.abs(b);
    562             if (abs < BASE) {
    563                 value = divModSmall(a, abs);
    564                 quotient = arrayToSmall(value[0]);
    565                 var remainder = value[1];
    566                 if (self.sign) remainder = -remainder;
    567                 if (typeof quotient === "number") {
    568                     if (self.sign !== n.sign) quotient = -quotient;
    569                     return [new SmallInteger(quotient), new SmallInteger(remainder)];
    570                 }
    571                 return [new BigInteger(quotient, self.sign !== n.sign), new SmallInteger(remainder)];
    572             }
    573             b = smallToArray(abs);
    574         }
    575         var comparison = compareAbs(a, b);
    576         if (comparison === -1) return [Integer[0], self];
    577         if (comparison === 0) return [Integer[self.sign === n.sign ? 1 : -1], Integer[0]];
    578 
    579         // divMod1 is faster on smaller input sizes
    580         if (a.length + b.length <= 200)
    581             value = divMod1(a, b);
    582         else value = divMod2(a, b);
    583 
    584         quotient = value[0];
    585         var qSign = self.sign !== n.sign,
    586             mod = value[1],
    587             mSign = self.sign;
    588         if (typeof quotient === "number") {
    589             if (qSign) quotient = -quotient;
    590             quotient = new SmallInteger(quotient);
    591         } else quotient = new BigInteger(quotient, qSign);
    592         if (typeof mod === "number") {
    593             if (mSign) mod = -mod;
    594             mod = new SmallInteger(mod);
    595         } else mod = new BigInteger(mod, mSign);
    596         return [quotient, mod];
    597     }
    598 
    599     BigInteger.prototype.divmod = function (v) {
    600         var result = divModAny(this, v);
    601         return {
    602             quotient: result[0],
    603             remainder: result[1]
    604         };
    605     };
    606     NativeBigInt.prototype.divmod = SmallInteger.prototype.divmod = BigInteger.prototype.divmod;
    607 
    608 
    609     BigInteger.prototype.divide = function (v) {
    610         return divModAny(this, v)[0];
    611     };
    612     NativeBigInt.prototype.over = NativeBigInt.prototype.divide = function (v) {
    613         return new NativeBigInt(this.value / parseValue(v).value);
    614     };
    615     SmallInteger.prototype.over = SmallInteger.prototype.divide = BigInteger.prototype.over = BigInteger.prototype.divide;
    616 
    617     BigInteger.prototype.mod = function (v) {
    618         return divModAny(this, v)[1];
    619     };
    620     NativeBigInt.prototype.mod = NativeBigInt.prototype.remainder = function (v) {
    621         return new NativeBigInt(this.value % parseValue(v).value);
    622     };
    623     SmallInteger.prototype.remainder = SmallInteger.prototype.mod = BigInteger.prototype.remainder = BigInteger.prototype.mod;
    624 
    625     BigInteger.prototype.pow = function (v) {
    626         var n = parseValue(v),
    627             a = this.value,
    628             b = n.value,
    629             value, x, y;
    630         if (b === 0) return Integer[1];
    631         if (a === 0) return Integer[0];
    632         if (a === 1) return Integer[1];
    633         if (a === -1) return n.isEven() ? Integer[1] : Integer[-1];
    634         if (n.sign) {
    635             return Integer[0];
    636         }
    637         if (!n.isSmall) throw new Error("The exponent " + n.toString() + " is too large.");
    638         if (this.isSmall) {
    639             if (isPrecise(value = Math.pow(a, b)))
    640                 return new SmallInteger(truncate(value));
    641         }
    642         x = this;
    643         y = Integer[1];
    644         while (true) {
    645             if (b & 1 === 1) {
    646                 y = y.times(x);
    647                 --b;
    648             }
    649             if (b === 0) break;
    650             b /= 2;
    651             x = x.square();
    652         }
    653         return y;
    654     };
    655     SmallInteger.prototype.pow = BigInteger.prototype.pow;
    656 
    657     NativeBigInt.prototype.pow = function (v) {
    658         var n = parseValue(v);
    659         var a = this.value, b = n.value;
    660         var _0 = BigInt(0), _1 = BigInt(1), _2 = BigInt(2);
    661         if (b === _0) return Integer[1];
    662         if (a === _0) return Integer[0];
    663         if (a === _1) return Integer[1];
    664         if (a === BigInt(-1)) return n.isEven() ? Integer[1] : Integer[-1];
    665         if (n.isNegative()) return new NativeBigInt(_0);
    666         var x = this;
    667         var y = Integer[1];
    668         while (true) {
    669             if ((b & _1) === _1) {
    670                 y = y.times(x);
    671                 --b;
    672             }
    673             if (b === _0) break;
    674             b /= _2;
    675             x = x.square();
    676         }
    677         return y;
    678     }
    679 
    680     BigInteger.prototype.modPow = function (exp, mod) {
    681         exp = parseValue(exp);
    682         mod = parseValue(mod);
    683         if (mod.isZero()) throw new Error("Cannot take modPow with modulus 0");
    684         var r = Integer[1],
    685             base = this.mod(mod);
    686         if (exp.isNegative()) {
    687             exp = exp.multiply(Integer[-1]);
    688             base = base.modInv(mod);
    689         }
    690         while (exp.isPositive()) {
    691             if (base.isZero()) return Integer[0];
    692             if (exp.isOdd()) r = r.multiply(base).mod(mod);
    693             exp = exp.divide(2);
    694             base = base.square().mod(mod);
    695         }
    696         return r;
    697     };
    698     NativeBigInt.prototype.modPow = SmallInteger.prototype.modPow = BigInteger.prototype.modPow;
    699 
    700     function compareAbs(a, b) {
    701         if (a.length !== b.length) {
    702             return a.length > b.length ? 1 : -1;
    703         }
    704         for (var i = a.length - 1; i >= 0; i--) {
    705             if (a[i] !== b[i]) return a[i] > b[i] ? 1 : -1;
    706         }
    707         return 0;
    708     }
    709 
    710     BigInteger.prototype.compareAbs = function (v) {
    711         var n = parseValue(v),
    712             a = this.value,
    713             b = n.value;
    714         if (n.isSmall) return 1;
    715         return compareAbs(a, b);
    716     };
    717     SmallInteger.prototype.compareAbs = function (v) {
    718         var n = parseValue(v),
    719             a = Math.abs(this.value),
    720             b = n.value;
    721         if (n.isSmall) {
    722             b = Math.abs(b);
    723             return a === b ? 0 : a > b ? 1 : -1;
    724         }
    725         return -1;
    726     };
    727     NativeBigInt.prototype.compareAbs = function (v) {
    728         var a = this.value;
    729         var b = parseValue(v).value;
    730         a = a >= 0 ? a : -a;
    731         b = b >= 0 ? b : -b;
    732         return a === b ? 0 : a > b ? 1 : -1;
    733     }
    734 
    735     BigInteger.prototype.compare = function (v) {
    736         // See discussion about comparison with Infinity:
    737         // https://github.com/peterolson/BigInteger.js/issues/61
    738         if (v === Infinity) {
    739             return -1;
    740         }
    741         if (v === -Infinity) {
    742             return 1;
    743         }
    744 
    745         var n = parseValue(v),
    746             a = this.value,
    747             b = n.value;
    748         if (this.sign !== n.sign) {
    749             return n.sign ? 1 : -1;
    750         }
    751         if (n.isSmall) {
    752             return this.sign ? -1 : 1;
    753         }
    754         return compareAbs(a, b) * (this.sign ? -1 : 1);
    755     };
    756     BigInteger.prototype.compareTo = BigInteger.prototype.compare;
    757 
    758     SmallInteger.prototype.compare = function (v) {
    759         if (v === Infinity) {
    760             return -1;
    761         }
    762         if (v === -Infinity) {
    763             return 1;
    764         }
    765 
    766         var n = parseValue(v),
    767             a = this.value,
    768             b = n.value;
    769         if (n.isSmall) {
    770             return a == b ? 0 : a > b ? 1 : -1;
    771         }
    772         if (a < 0 !== n.sign) {
    773             return a < 0 ? -1 : 1;
    774         }
    775         return a < 0 ? 1 : -1;
    776     };
    777     SmallInteger.prototype.compareTo = SmallInteger.prototype.compare;
    778 
    779     NativeBigInt.prototype.compare = function (v) {
    780         if (v === Infinity) {
    781             return -1;
    782         }
    783         if (v === -Infinity) {
    784             return 1;
    785         }
    786         var a = this.value;
    787         var b = parseValue(v).value;
    788         return a === b ? 0 : a > b ? 1 : -1;
    789     }
    790     NativeBigInt.prototype.compareTo = NativeBigInt.prototype.compare;
    791 
    792     BigInteger.prototype.equals = function (v) {
    793         return this.compare(v) === 0;
    794     };
    795     NativeBigInt.prototype.eq = NativeBigInt.prototype.equals = SmallInteger.prototype.eq = SmallInteger.prototype.equals = BigInteger.prototype.eq = BigInteger.prototype.equals;
    796 
    797     BigInteger.prototype.notEquals = function (v) {
    798         return this.compare(v) !== 0;
    799     };
    800     NativeBigInt.prototype.neq = NativeBigInt.prototype.notEquals = SmallInteger.prototype.neq = SmallInteger.prototype.notEquals = BigInteger.prototype.neq = BigInteger.prototype.notEquals;
    801 
    802     BigInteger.prototype.greater = function (v) {
    803         return this.compare(v) > 0;
    804     };
    805     NativeBigInt.prototype.gt = NativeBigInt.prototype.greater = SmallInteger.prototype.gt = SmallInteger.prototype.greater = BigInteger.prototype.gt = BigInteger.prototype.greater;
    806 
    807     BigInteger.prototype.lesser = function (v) {
    808         return this.compare(v) < 0;
    809     };
    810     NativeBigInt.prototype.lt = NativeBigInt.prototype.lesser = SmallInteger.prototype.lt = SmallInteger.prototype.lesser = BigInteger.prototype.lt = BigInteger.prototype.lesser;
    811 
    812     BigInteger.prototype.greaterOrEquals = function (v) {
    813         return this.compare(v) >= 0;
    814     };
    815     NativeBigInt.prototype.geq = NativeBigInt.prototype.greaterOrEquals = SmallInteger.prototype.geq = SmallInteger.prototype.greaterOrEquals = BigInteger.prototype.geq = BigInteger.prototype.greaterOrEquals;
    816 
    817     BigInteger.prototype.lesserOrEquals = function (v) {
    818         return this.compare(v) <= 0;
    819     };
    820     NativeBigInt.prototype.leq = NativeBigInt.prototype.lesserOrEquals = SmallInteger.prototype.leq = SmallInteger.prototype.lesserOrEquals = BigInteger.prototype.leq = BigInteger.prototype.lesserOrEquals;
    821 
    822     BigInteger.prototype.isEven = function () {
    823         return (this.value[0] & 1) === 0;
    824     };
    825     SmallInteger.prototype.isEven = function () {
    826         return (this.value & 1) === 0;
    827     };
    828     NativeBigInt.prototype.isEven = function () {
    829         return (this.value & BigInt(1)) === BigInt(0);
    830     }
    831 
    832     BigInteger.prototype.isOdd = function () {
    833         return (this.value[0] & 1) === 1;
    834     };
    835     SmallInteger.prototype.isOdd = function () {
    836         return (this.value & 1) === 1;
    837     };
    838     NativeBigInt.prototype.isOdd = function () {
    839         return (this.value & BigInt(1)) === BigInt(1);
    840     }
    841 
    842     BigInteger.prototype.isPositive = function () {
    843         return !this.sign;
    844     };
    845     SmallInteger.prototype.isPositive = function () {
    846         return this.value > 0;
    847     };
    848     NativeBigInt.prototype.isPositive = SmallInteger.prototype.isPositive;
    849 
    850     BigInteger.prototype.isNegative = function () {
    851         return this.sign;
    852     };
    853     SmallInteger.prototype.isNegative = function () {
    854         return this.value < 0;
    855     };
    856     NativeBigInt.prototype.isNegative = SmallInteger.prototype.isNegative;
    857 
    858     BigInteger.prototype.isUnit = function () {
    859         return false;
    860     };
    861     SmallInteger.prototype.isUnit = function () {
    862         return Math.abs(this.value) === 1;
    863     };
    864     NativeBigInt.prototype.isUnit = function () {
    865         return this.abs().value === BigInt(1);
    866     }
    867 
    868     BigInteger.prototype.isZero = function () {
    869         return false;
    870     };
    871     SmallInteger.prototype.isZero = function () {
    872         return this.value === 0;
    873     };
    874     NativeBigInt.prototype.isZero = function () {
    875         return this.value === BigInt(0);
    876     }
    877 
    878     BigInteger.prototype.isDivisibleBy = function (v) {
    879         var n = parseValue(v);
    880         if (n.isZero()) return false;
    881         if (n.isUnit()) return true;
    882         if (n.compareAbs(2) === 0) return this.isEven();
    883         return this.mod(n).isZero();
    884     };
    885     NativeBigInt.prototype.isDivisibleBy = SmallInteger.prototype.isDivisibleBy = BigInteger.prototype.isDivisibleBy;
    886 
    887     function isBasicPrime(v) {
    888         var n = v.abs();
    889         if (n.isUnit()) return false;
    890         if (n.equals(2) || n.equals(3) || n.equals(5)) return true;
    891         if (n.isEven() || n.isDivisibleBy(3) || n.isDivisibleBy(5)) return false;
    892         if (n.lesser(49)) return true;
    893         // we don't know if it's prime: let the other functions figure it out
    894     }
    895 
    896     function millerRabinTest(n, a) {
    897         var nPrev = n.prev(),
    898             b = nPrev,
    899             r = 0,
    900             d, t, i, x;
    901         while (b.isEven()) b = b.divide(2), r++;
    902         next: for (i = 0; i < a.length; i++) {
    903             if (n.lesser(a[i])) continue;
    904             x = bigInt(a[i]).modPow(b, n);
    905             if (x.isUnit() || x.equals(nPrev)) continue;
    906             for (d = r - 1; d != 0; d--) {
    907                 x = x.square().mod(n);
    908                 if (x.isUnit()) return false;
    909                 if (x.equals(nPrev)) continue next;
    910             }
    911             return false;
    912         }
    913         return true;
    914     }
    915 
    916     // Set "strict" to true to force GRH-supported lower bound of 2*log(N)^2
    917     BigInteger.prototype.isPrime = function (strict) {
    918         var isPrime = isBasicPrime(this);
    919         if (isPrime !== undefined) return isPrime;
    920         var n = this.abs();
    921         var bits = n.bitLength();
    922         if (bits <= 64)
    923             return millerRabinTest(n, [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]);
    924         var logN = Math.log(2) * bits.toJSNumber();
    925         var t = Math.ceil((strict === true) ? (2 * Math.pow(logN, 2)) : logN);
    926         for (var a = [], i = 0; i < t; i++) {
    927             a.push(bigInt(i + 2));
    928         }
    929         return millerRabinTest(n, a);
    930     };
    931     NativeBigInt.prototype.isPrime = SmallInteger.prototype.isPrime = BigInteger.prototype.isPrime;
    932 
    933     BigInteger.prototype.isProbablePrime = function (iterations, rng) {
    934         var isPrime = isBasicPrime(this);
    935         if (isPrime !== undefined) return isPrime;
    936         var n = this.abs();
    937         var t = iterations === undefined ? 5 : iterations;
    938         for (var a = [], i = 0; i < t; i++) {
    939             a.push(bigInt.randBetween(2, n.minus(2), rng));
    940         }
    941         return millerRabinTest(n, a);
    942     };
    943     NativeBigInt.prototype.isProbablePrime = SmallInteger.prototype.isProbablePrime = BigInteger.prototype.isProbablePrime;
    944 
    945     BigInteger.prototype.modInv = function (n) {
    946         var t = bigInt.zero, newT = bigInt.one, r = parseValue(n), newR = this.abs(), q, lastT, lastR;
    947         while (!newR.isZero()) {
    948             q = r.divide(newR);
    949             lastT = t;
    950             lastR = r;
    951             t = newT;
    952             r = newR;
    953             newT = lastT.subtract(q.multiply(newT));
    954             newR = lastR.subtract(q.multiply(newR));
    955         }
    956         if (!r.isUnit()) throw new Error(this.toString() + " and " + n.toString() + " are not co-prime");
    957         if (t.compare(0) === -1) {
    958             t = t.add(n);
    959         }
    960         if (this.isNegative()) {
    961             return t.negate();
    962         }
    963         return t;
    964     };
    965 
    966     NativeBigInt.prototype.modInv = SmallInteger.prototype.modInv = BigInteger.prototype.modInv;
    967 
    968     BigInteger.prototype.next = function () {
    969         var value = this.value;
    970         if (this.sign) {
    971             return subtractSmall(value, 1, this.sign);
    972         }
    973         return new BigInteger(addSmall(value, 1), this.sign);
    974     };
    975     SmallInteger.prototype.next = function () {
    976         var value = this.value;
    977         if (value + 1 < MAX_INT) return new SmallInteger(value + 1);
    978         return new BigInteger(MAX_INT_ARR, false);
    979     };
    980     NativeBigInt.prototype.next = function () {
    981         return new NativeBigInt(this.value + BigInt(1));
    982     }
    983 
    984     BigInteger.prototype.prev = function () {
    985         var value = this.value;
    986         if (this.sign) {
    987             return new BigInteger(addSmall(value, 1), true);
    988         }
    989         return subtractSmall(value, 1, this.sign);
    990     };
    991     SmallInteger.prototype.prev = function () {
    992         var value = this.value;
    993         if (value - 1 > -MAX_INT) return new SmallInteger(value - 1);
    994         return new BigInteger(MAX_INT_ARR, true);
    995     };
    996     NativeBigInt.prototype.prev = function () {
    997         return new NativeBigInt(this.value - BigInt(1));
    998     }
    999 
   1000     var powersOfTwo = [1];
   1001     while (2 * powersOfTwo[powersOfTwo.length - 1] <= BASE) powersOfTwo.push(2 * powersOfTwo[powersOfTwo.length - 1]);
   1002     var powers2Length = powersOfTwo.length, highestPower2 = powersOfTwo[powers2Length - 1];
   1003 
   1004     function shift_isSmall(n) {
   1005         return Math.abs(n) <= BASE;
   1006     }
   1007 
   1008     BigInteger.prototype.shiftLeft = function (v) {
   1009         var n = parseValue(v).toJSNumber();
   1010         if (!shift_isSmall(n)) {
   1011             throw new Error(String(n) + " is too large for shifting.");
   1012         }
   1013         if (n < 0) return this.shiftRight(-n);
   1014         var result = this;
   1015         if (result.isZero()) return result;
   1016         while (n >= powers2Length) {
   1017             result = result.multiply(highestPower2);
   1018             n -= powers2Length - 1;
   1019         }
   1020         return result.multiply(powersOfTwo[n]);
   1021     };
   1022     NativeBigInt.prototype.shiftLeft = SmallInteger.prototype.shiftLeft = BigInteger.prototype.shiftLeft;
   1023 
   1024     BigInteger.prototype.shiftRight = function (v) {
   1025         var remQuo;
   1026         var n = parseValue(v).toJSNumber();
   1027         if (!shift_isSmall(n)) {
   1028             throw new Error(String(n) + " is too large for shifting.");
   1029         }
   1030         if (n < 0) return this.shiftLeft(-n);
   1031         var result = this;
   1032         while (n >= powers2Length) {
   1033             if (result.isZero() || (result.isNegative() && result.isUnit())) return result;
   1034             remQuo = divModAny(result, highestPower2);
   1035             result = remQuo[1].isNegative() ? remQuo[0].prev() : remQuo[0];
   1036             n -= powers2Length - 1;
   1037         }
   1038         remQuo = divModAny(result, powersOfTwo[n]);
   1039         return remQuo[1].isNegative() ? remQuo[0].prev() : remQuo[0];
   1040     };
   1041     NativeBigInt.prototype.shiftRight = SmallInteger.prototype.shiftRight = BigInteger.prototype.shiftRight;
   1042 
   1043     function bitwise(x, y, fn) {
   1044         y = parseValue(y);
   1045         var xSign = x.isNegative(), ySign = y.isNegative();
   1046         var xRem = xSign ? x.not() : x,
   1047             yRem = ySign ? y.not() : y;
   1048         var xDigit = 0, yDigit = 0;
   1049         var xDivMod = null, yDivMod = null;
   1050         var result = [];
   1051         while (!xRem.isZero() || !yRem.isZero()) {
   1052             xDivMod = divModAny(xRem, highestPower2);
   1053             xDigit = xDivMod[1].toJSNumber();
   1054             if (xSign) {
   1055                 xDigit = highestPower2 - 1 - xDigit; // two's complement for negative numbers
   1056             }
   1057 
   1058             yDivMod = divModAny(yRem, highestPower2);
   1059             yDigit = yDivMod[1].toJSNumber();
   1060             if (ySign) {
   1061                 yDigit = highestPower2 - 1 - yDigit; // two's complement for negative numbers
   1062             }
   1063 
   1064             xRem = xDivMod[0];
   1065             yRem = yDivMod[0];
   1066             result.push(fn(xDigit, yDigit));
   1067         }
   1068         var sum = fn(xSign ? 1 : 0, ySign ? 1 : 0) !== 0 ? bigInt(-1) : bigInt(0);
   1069         for (var i = result.length - 1; i >= 0; i -= 1) {
   1070             sum = sum.multiply(highestPower2).add(bigInt(result[i]));
   1071         }
   1072         return sum;
   1073     }
   1074 
   1075     BigInteger.prototype.not = function () {
   1076         return this.negate().prev();
   1077     };
   1078     NativeBigInt.prototype.not = SmallInteger.prototype.not = BigInteger.prototype.not;
   1079 
   1080     BigInteger.prototype.and = function (n) {
   1081         return bitwise(this, n, function (a, b) { return a & b; });
   1082     };
   1083     NativeBigInt.prototype.and = SmallInteger.prototype.and = BigInteger.prototype.and;
   1084 
   1085     BigInteger.prototype.or = function (n) {
   1086         return bitwise(this, n, function (a, b) { return a | b; });
   1087     };
   1088     NativeBigInt.prototype.or = SmallInteger.prototype.or = BigInteger.prototype.or;
   1089 
   1090     BigInteger.prototype.xor = function (n) {
   1091         return bitwise(this, n, function (a, b) { return a ^ b; });
   1092     };
   1093     NativeBigInt.prototype.xor = SmallInteger.prototype.xor = BigInteger.prototype.xor;
   1094 
   1095     var LOBMASK_I = 1 << 30, LOBMASK_BI = (BASE & -BASE) * (BASE & -BASE) | LOBMASK_I;
   1096     function roughLOB(n) { // get lowestOneBit (rough)
   1097         // SmallInteger: return Min(lowestOneBit(n), 1 << 30)
   1098         // BigInteger: return Min(lowestOneBit(n), 1 << 14) [BASE=1e7]
   1099         var v = n.value,
   1100             x = typeof v === "number" ? v | LOBMASK_I :
   1101                 typeof v === "bigint" ? v | BigInt(LOBMASK_I) :
   1102                     v[0] + v[1] * BASE | LOBMASK_BI;
   1103         return x & -x;
   1104     }
   1105 
   1106     function integerLogarithm(value, base) {
   1107         if (base.compareTo(value) <= 0) {
   1108             var tmp = integerLogarithm(value, base.square(base));
   1109             var p = tmp.p;
   1110             var e = tmp.e;
   1111             var t = p.multiply(base);
   1112             return t.compareTo(value) <= 0 ? { p: t, e: e * 2 + 1 } : { p: p, e: e * 2 };
   1113         }
   1114         return { p: bigInt(1), e: 0 };
   1115     }
   1116 
   1117     BigInteger.prototype.bitLength = function () {
   1118         var n = this;
   1119         if (n.compareTo(bigInt(0)) < 0) {
   1120             n = n.negate().subtract(bigInt(1));
   1121         }
   1122         if (n.compareTo(bigInt(0)) === 0) {
   1123             return bigInt(0);
   1124         }
   1125         return bigInt(integerLogarithm(n, bigInt(2)).e).add(bigInt(1));
   1126     }
   1127     NativeBigInt.prototype.bitLength = SmallInteger.prototype.bitLength = BigInteger.prototype.bitLength;
   1128 
   1129     function max(a, b) {
   1130         a = parseValue(a);
   1131         b = parseValue(b);
   1132         return a.greater(b) ? a : b;
   1133     }
   1134     function min(a, b) {
   1135         a = parseValue(a);
   1136         b = parseValue(b);
   1137         return a.lesser(b) ? a : b;
   1138     }
   1139     function gcd(a, b) {
   1140         a = parseValue(a).abs();
   1141         b = parseValue(b).abs();
   1142         if (a.equals(b)) return a;
   1143         if (a.isZero()) return b;
   1144         if (b.isZero()) return a;
   1145         var c = Integer[1], d, t;
   1146         while (a.isEven() && b.isEven()) {
   1147             d = min(roughLOB(a), roughLOB(b));
   1148             a = a.divide(d);
   1149             b = b.divide(d);
   1150             c = c.multiply(d);
   1151         }
   1152         while (a.isEven()) {
   1153             a = a.divide(roughLOB(a));
   1154         }
   1155         do {
   1156             while (b.isEven()) {
   1157                 b = b.divide(roughLOB(b));
   1158             }
   1159             if (a.greater(b)) {
   1160                 t = b; b = a; a = t;
   1161             }
   1162             b = b.subtract(a);
   1163         } while (!b.isZero());
   1164         return c.isUnit() ? a : a.multiply(c);
   1165     }
   1166     function lcm(a, b) {
   1167         a = parseValue(a).abs();
   1168         b = parseValue(b).abs();
   1169         return a.divide(gcd(a, b)).multiply(b);
   1170     }
   1171     function randBetween(a, b, rng) {
   1172         a = parseValue(a);
   1173         b = parseValue(b);
   1174         var usedRNG = rng || Math.random;
   1175         var low = min(a, b), high = max(a, b);
   1176         var range = high.subtract(low).add(1);
   1177         if (range.isSmall) return low.add(Math.floor(usedRNG() * range));
   1178         var digits = toBase(range, BASE).value;
   1179         var result = [], restricted = true;
   1180         for (var i = 0; i < digits.length; i++) {
   1181             var top = restricted ? digits[i] + (i + 1 < digits.length ? digits[i + 1] / BASE : 0) : BASE;
   1182             var digit = truncate(usedRNG() * top);
   1183             result.push(digit);
   1184             if (digit < digits[i]) restricted = false;
   1185         }
   1186         return low.add(Integer.fromArray(result, BASE, false));
   1187     }
   1188 
   1189     var parseBase = function (text, base, alphabet, caseSensitive) {
   1190         alphabet = alphabet || DEFAULT_ALPHABET;
   1191         text = String(text);
   1192         if (!caseSensitive) {
   1193             text = text.toLowerCase();
   1194             alphabet = alphabet.toLowerCase();
   1195         }
   1196         var length = text.length;
   1197         var i;
   1198         var absBase = Math.abs(base);
   1199         var alphabetValues = {};
   1200         for (i = 0; i < alphabet.length; i++) {
   1201             alphabetValues[alphabet[i]] = i;
   1202         }
   1203         for (i = 0; i < length; i++) {
   1204             var c = text[i];
   1205             if (c === "-") continue;
   1206             if (c in alphabetValues) {
   1207                 if (alphabetValues[c] >= absBase) {
   1208                     if (c === "1" && absBase === 1) continue;
   1209                     throw new Error(c + " is not a valid digit in base " + base + ".");
   1210                 }
   1211             }
   1212         }
   1213         base = parseValue(base);
   1214         var digits = [];
   1215         var isNegative = text[0] === "-";
   1216         for (i = isNegative ? 1 : 0; i < text.length; i++) {
   1217             var c = text[i];
   1218             if (c in alphabetValues) digits.push(parseValue(alphabetValues[c]));
   1219             else if (c === "<") {
   1220                 var start = i;
   1221                 do { i++; } while (text[i] !== ">" && i < text.length);
   1222                 digits.push(parseValue(text.slice(start + 1, i)));
   1223             }
   1224             else throw new Error(c + " is not a valid character");
   1225         }
   1226         return parseBaseFromArray(digits, base, isNegative);
   1227     };
   1228 
   1229     function parseBaseFromArray(digits, base, isNegative) {
   1230         var val = Integer[0], pow = Integer[1], i;
   1231         for (i = digits.length - 1; i >= 0; i--) {
   1232             val = val.add(digits[i].times(pow));
   1233             pow = pow.times(base);
   1234         }
   1235         return isNegative ? val.negate() : val;
   1236     }
   1237 
   1238     function stringify(digit, alphabet) {
   1239         alphabet = alphabet || DEFAULT_ALPHABET;
   1240         if (digit < alphabet.length) {
   1241             return alphabet[digit];
   1242         }
   1243         return "<" + digit + ">";
   1244     }
   1245 
   1246     function toBase(n, base) {
   1247         base = bigInt(base);
   1248         if (base.isZero()) {
   1249             if (n.isZero()) return { value: [0], isNegative: false };
   1250             throw new Error("Cannot convert nonzero numbers to base 0.");
   1251         }
   1252         if (base.equals(-1)) {
   1253             if (n.isZero()) return { value: [0], isNegative: false };
   1254             if (n.isNegative())
   1255                 return {
   1256                     value: [].concat.apply([], Array.apply(null, Array(-n.toJSNumber()))
   1257                         .map(Array.prototype.valueOf, [1, 0])
   1258                     ),
   1259                     isNegative: false
   1260                 };
   1261 
   1262             var arr = Array.apply(null, Array(n.toJSNumber() - 1))
   1263                 .map(Array.prototype.valueOf, [0, 1]);
   1264             arr.unshift([1]);
   1265             return {
   1266                 value: [].concat.apply([], arr),
   1267                 isNegative: false
   1268             };
   1269         }
   1270 
   1271         var neg = false;
   1272         if (n.isNegative() && base.isPositive()) {
   1273             neg = true;
   1274             n = n.abs();
   1275         }
   1276         if (base.isUnit()) {
   1277             if (n.isZero()) return { value: [0], isNegative: false };
   1278 
   1279             return {
   1280                 value: Array.apply(null, Array(n.toJSNumber()))
   1281                     .map(Number.prototype.valueOf, 1),
   1282                 isNegative: neg
   1283             };
   1284         }
   1285         var out = [];
   1286         var left = n, divmod;
   1287         while (left.isNegative() || left.compareAbs(base) >= 0) {
   1288             divmod = left.divmod(base);
   1289             left = divmod.quotient;
   1290             var digit = divmod.remainder;
   1291             if (digit.isNegative()) {
   1292                 digit = base.minus(digit).abs();
   1293                 left = left.next();
   1294             }
   1295             out.push(digit.toJSNumber());
   1296         }
   1297         out.push(left.toJSNumber());
   1298         return { value: out.reverse(), isNegative: neg };
   1299     }
   1300 
   1301     function toBaseString(n, base, alphabet) {
   1302         var arr = toBase(n, base);
   1303         return (arr.isNegative ? "-" : "") + arr.value.map(function (x) {
   1304             return stringify(x, alphabet);
   1305         }).join('');
   1306     }
   1307 
   1308     BigInteger.prototype.toArray = function (radix) {
   1309         return toBase(this, radix);
   1310     };
   1311 
   1312     SmallInteger.prototype.toArray = function (radix) {
   1313         return toBase(this, radix);
   1314     };
   1315 
   1316     NativeBigInt.prototype.toArray = function (radix) {
   1317         return toBase(this, radix);
   1318     };
   1319 
   1320     BigInteger.prototype.toString = function (radix, alphabet) {
   1321         if (radix === undefined) radix = 10;
   1322         if (radix !== 10) return toBaseString(this, radix, alphabet);
   1323         var v = this.value, l = v.length, str = String(v[--l]), zeros = "0000000", digit;
   1324         while (--l >= 0) {
   1325             digit = String(v[l]);
   1326             str += zeros.slice(digit.length) + digit;
   1327         }
   1328         var sign = this.sign ? "-" : "";
   1329         return sign + str;
   1330     };
   1331 
   1332     SmallInteger.prototype.toString = function (radix, alphabet) {
   1333         if (radix === undefined) radix = 10;
   1334         if (radix != 10) return toBaseString(this, radix, alphabet);
   1335         return String(this.value);
   1336     };
   1337 
   1338     NativeBigInt.prototype.toString = SmallInteger.prototype.toString;
   1339 
   1340     NativeBigInt.prototype.toJSON = BigInteger.prototype.toJSON = SmallInteger.prototype.toJSON = function () { return this.toString(); }
   1341 
   1342     BigInteger.prototype.valueOf = function () {
   1343         return parseInt(this.toString(), 10);
   1344     };
   1345     BigInteger.prototype.toJSNumber = BigInteger.prototype.valueOf;
   1346 
   1347     SmallInteger.prototype.valueOf = function () {
   1348         return this.value;
   1349     };
   1350     SmallInteger.prototype.toJSNumber = SmallInteger.prototype.valueOf;
   1351     NativeBigInt.prototype.valueOf = NativeBigInt.prototype.toJSNumber = function () {
   1352         return parseInt(this.toString(), 10);
   1353     }
   1354 
   1355     function parseStringValue(v) {
   1356         if (isPrecise(+v)) {
   1357             var x = +v;
   1358             if (x === truncate(x))
   1359                 return supportsNativeBigInt ? new NativeBigInt(BigInt(x)) : new SmallInteger(x);
   1360             throw new Error("Invalid integer: " + v);
   1361         }
   1362         var sign = v[0] === "-";
   1363         if (sign) v = v.slice(1);
   1364         var split = v.split(/e/i);
   1365         if (split.length > 2) throw new Error("Invalid integer: " + split.join("e"));
   1366         if (split.length === 2) {
   1367             var exp = split[1];
   1368             if (exp[0] === "+") exp = exp.slice(1);
   1369             exp = +exp;
   1370             if (exp !== truncate(exp) || !isPrecise(exp)) throw new Error("Invalid integer: " + exp + " is not a valid exponent.");
   1371             var text = split[0];
   1372             var decimalPlace = text.indexOf(".");
   1373             if (decimalPlace >= 0) {
   1374                 exp -= text.length - decimalPlace - 1;
   1375                 text = text.slice(0, decimalPlace) + text.slice(decimalPlace + 1);
   1376             }
   1377             if (exp < 0) throw new Error("Cannot include negative exponent part for integers");
   1378             text += (new Array(exp + 1)).join("0");
   1379             v = text;
   1380         }
   1381         var isValid = /^([0-9][0-9]*)$/.test(v);
   1382         if (!isValid) throw new Error("Invalid integer: " + v);
   1383         if (supportsNativeBigInt) {
   1384             return new NativeBigInt(BigInt(sign ? "-" + v : v));
   1385         }
   1386         var r = [], max = v.length, l = LOG_BASE, min = max - l;
   1387         while (max > 0) {
   1388             r.push(+v.slice(min, max));
   1389             min -= l;
   1390             if (min < 0) min = 0;
   1391             max -= l;
   1392         }
   1393         trim(r);
   1394         return new BigInteger(r, sign);
   1395     }
   1396 
   1397     function parseNumberValue(v) {
   1398         if (supportsNativeBigInt) {
   1399             return new NativeBigInt(BigInt(v));
   1400         }
   1401         if (isPrecise(v)) {
   1402             if (v !== truncate(v)) throw new Error(v + " is not an integer.");
   1403             return new SmallInteger(v);
   1404         }
   1405         return parseStringValue(v.toString());
   1406     }
   1407 
   1408     function parseValue(v) {
   1409         if (typeof v === "number") {
   1410             return parseNumberValue(v);
   1411         }
   1412         if (typeof v === "string") {
   1413             return parseStringValue(v);
   1414         }
   1415         if (typeof v === "bigint") {
   1416             return new NativeBigInt(v);
   1417         }
   1418         return v;
   1419     }
   1420     // Pre-define numbers in range [-999,999]
   1421     for (var i = 0; i < 1000; i++) {
   1422         Integer[i] = parseValue(i);
   1423         if (i > 0) Integer[-i] = parseValue(-i);
   1424     }
   1425     // Backwards compatibility
   1426     Integer.one = Integer[1];
   1427     Integer.zero = Integer[0];
   1428     Integer.minusOne = Integer[-1];
   1429     Integer.max = max;
   1430     Integer.min = min;
   1431     Integer.gcd = gcd;
   1432     Integer.lcm = lcm;
   1433     Integer.isInstance = function (x) { return x instanceof BigInteger || x instanceof SmallInteger || x instanceof NativeBigInt; };
   1434     Integer.randBetween = randBetween;
   1435 
   1436     Integer.fromArray = function (digits, base, isNegative) {
   1437         return parseBaseFromArray(digits.map(parseValue), parseValue(base || 10), isNegative);
   1438     };
   1439 
   1440     return Integer;
   1441 })();
   1442 
   1443 // Node.js check
   1444 if (typeof module !== "undefined" && module.hasOwnProperty("exports")) {
   1445     module.exports = bigInt;
   1446 }
   1447 
   1448 //amd check
   1449 if (typeof define === "function" && define.amd) {
   1450     define( function () {
   1451         return bigInt;
   1452     });
   1453 }