src/js/entropy.js

   1 window.Entropy = new (function() {
   2
   3     var matchers = {
   4         binary: /[0-1]/gi,
   5         base6: /[0-5]/gi,
   6         dice: /[1-6]/gi, // ie dice numbers
   7         base10: /[0-9]/gi,
   8         hex: /[0-9A-F]/gi,
   9     }
  10
  11     this.fromString = function(rawEntropyStr) {
  12         // Find type of entropy being used (binary, hex, dice etc)
  13         var base = getBase(rawEntropyStr);
  14         // Convert dice to base6 entropy (ie 1-6 to 0-5)
  15         if (base.str == "dice") {
  16             var newRawEntropyStr = "";
  17             for (var i=0; i<rawEntropyStr.length; i++) {
  18                 var c = rawEntropyStr[i];
  19                 if ("123456".indexOf(c) > -1) {
  20                     newRawEntropyStr += (parseInt(c) - 1).toString();
  21                 }
  22                 else {
  23                     newRawEntropyStr += c
  24                 }
  25             }
  26             rawEntropyStr = newRawEntropyStr;
  27             base.str = "base 6 (dice)";
  28             base.matcher = matchers.base6;
  29         }
  30         var entropyParts = rawEntropyStr.match(base.matcher) || [];
  31         var entropyStr = entropyParts.join("");
  32         // Detect empty entropy
  33         if (entropyStr.length == 0) {
  34             return {
  35                 binaryStr: "",
  36                 hexStr: "",
  37                 cleanStr: "",
  38                 base: base,
  39             };
  40         }
  41         // Pull leading zeros off
  42         var leadingZeros = "";
  43         while (entropyStr[0] == "0") {
  44             leadingZeros += "0";
  45             entropyStr = entropyStr.substring(1);
  46         }
  47         // Convert leading zeros to binary equivalent
  48         var numBinLeadingZeros = Math.ceil(Math.log2(base.asInt) * leadingZeros.length);
  49         var binLeadingZeros = "";
  50         for (var i=0; i<numBinLeadingZeros; i++) {
  51             binLeadingZeros += "0";
  52         }
  53         // Convert leading zeros to hex equivalent
  54         var numHexLeadingZeros = Math.floor(numBinLeadingZeros / 4);
  55         var hexLeadingZeros = "";
  56         for (var i=0; i<numHexLeadingZeros; i++) {
  57             hexLeadingZeros += "0";
  58         }
  59         // Handle entropy of zero
  60         if (entropyStr == "") {
  61             return {
  62                 binaryStr: binLeadingZeros,
  63                 hexStr: hexLeadingZeros || "0",
  64                 cleanStr: leadingZeros,
  65                 base: base,
  66             }
  67         }
  68         // If using hex, should always be multiples of 4 bits, which can get
  69         // out of sync if first number has leading 0 bits, eg 2 in hex is 0010
  70         // which would show up as 10, thus missing 2 bits it should have.
  71         if (base.asInt == 16) {
  72             var firstDigit = parseInt(entropyStr[0], 16);
  73             if (firstDigit >= 4 && firstDigit < 8) {
  74                 binLeadingZeros += "0";
  75             }
  76             else if (firstDigit >= 2 && firstDigit < 4) {
  77                 binLeadingZeros += "00";
  78             }
  79             else if (firstDigit >= 1 && firstDigit < 2) {
  80                 binLeadingZeros += "000";
  81             }
  82         }
  83         // Convert entropy to different foramts
  84         var entropyInt = BigInteger.parse(entropyStr, base.asInt);
  85         var entropyBin = binLeadingZeros + entropyInt.toString(2);
  86         var entropyHex = hexLeadingZeros + entropyInt.toString(16);
  87         var entropyClean = leadingZeros + entropyStr;
  88         var e = {
  89             binaryStr: entropyBin,
  90             hexStr: entropyHex,
  91             cleanStr: entropyClean,
  92             base: base,
  93         }
  94         return e;
  95     }
  96
  97     function getBase(str) {
  98         // Need to get the lowest base for the supplied entropy.
  99         // This prevents interpreting, say, dice rolls as hexadecimal.
 100         var binaryMatches = str.match(matchers.binary) || [];
 101         var base6Matches = str.match(matchers.base6) || [];
 102         var diceMatches = str.match(matchers.dice) || [];
 103         var base10Matches = str.match(matchers.base10) || [];
 104         var hexMatches = str.match(matchers.hex) || [];
 105         // Find the lowest base that can be used, whilst ignoring any irrelevant chars
 106         if (binaryMatches.length == hexMatches.length) {
 107             return {
 108                 matcher: matchers.binary,
 109                 asInt: 2,
 110                 str: "binary",
 111             }
 112         }
 113         if (diceMatches.length == hexMatches.length) {
 114             return {
 115                 matcher: matchers.dice,
 116                 asInt: 6,
 117                 str: "dice",
 118             }
 119         }
 120         if (base6Matches.length == hexMatches.length) {
 121             return {
 122                 matcher: matchers.base6,
 123                 asInt: 6,
 124                 str: "base 6",
 125             }
 126         }
 127         if (base10Matches.length == hexMatches.length) {
 128             return {
 129                 matcher: matchers.base10,
 130                 asInt: 10,
 131                 str: "base 10",
 132             }
 133         }
 134         return {
 135             matcher: matchers.hex,
 136             asInt: 16,
 137             str: "hexadecimal",
 138         }
 139     }
 140
 141     // Polyfill for Math.log2
 142     // See https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Math/log2#Polyfill
 143     Math.log2 = Math.log2 || function(x) {
 144         return Math.log(x) * Math.LOG2E;
 145     };
 146
 147 })();
 148
 149
 150 // BigInteger library included here because
 151 // only the entropy library depends on it
 152 // so if entropy detection is removed so is the dependency
 153
 154
 155 /*
 156         JavaScript BigInteger library version 0.9.1
 157         http://silentmatt.com/biginteger/
 158
 159         Copyright (c) 2009 Matthew Crumley <email@matthewcrumley.com>
 160         Copyright (c) 2010,2011 by John Tobey <John.Tobey@gmail.com>
 161         Licensed under the MIT license.
 162
 163         Support for arbitrary internal representation base was added by
 164         Vitaly Magerya.
 165 */
 166
 167 /*
 168         File: biginteger.js
 169
 170         Exports:
 171
 172                 <BigInteger>
 173 */
 174 (function(exports) {
 175 "use strict";
 176 /*
 177         Class: BigInteger
 178         An arbitrarily-large integer.
 179
 180         <BigInteger> objects should be considered immutable. None of the "built-in"
 181         methods modify *this* or their arguments. All properties should be
 182         considered private.
 183
 184         All the methods of <BigInteger> instances can be called "statically". The
 185         static versions are convenient if you don't already have a <BigInteger>
 186         object.
 187
 188         As an example, these calls are equivalent.
 189
 190         > BigInteger(4).multiply(5); // returns BigInteger(20);
 191         > BigInteger.multiply(4, 5); // returns BigInteger(20);
 192
 193         > var a = 42;
 194         > var a = BigInteger.toJSValue("0b101010"); // Not completely useless...
 195 */
 196
 197 var CONSTRUCT = {}; // Unique token to call "private" version of constructor
 198
 199 /*
 200         Constructor: BigInteger()
 201         Convert a value to a <BigInteger>.
 202
 203         Although <BigInteger()> is the constructor for <BigInteger> objects, it is
 204         best not to call it as a constructor. If *n* is a <BigInteger> object, it is
 205         simply returned as-is. Otherwise, <BigInteger()> is equivalent to <parse>
 206         without a radix argument.
 207
 208         > var n0 = BigInteger();      // Same as <BigInteger.ZERO>
 209         > var n1 = BigInteger("123"); // Create a new <BigInteger> with value 123
 210         > var n2 = BigInteger(123);   // Create a new <BigInteger> with value 123
 211         > var n3 = BigInteger(n2);    // Return n2, unchanged
 212
 213         The constructor form only takes an array and a sign. *n* must be an
 214         array of numbers in little-endian order, where each digit is between 0
 215         and BigInteger.base.  The second parameter sets the sign: -1 for
 216         negative, +1 for positive, or 0 for zero. The array is *not copied and
 217         may be modified*. If the array contains only zeros, the sign parameter
 218         is ignored and is forced to zero.
 219
 220         > new BigInteger([5], -1): create a new BigInteger with value -5
 221
 222         Parameters:
 223
 224                 n - Value to convert to a <BigInteger>.
 225
 226         Returns:
 227
 228                 A <BigInteger> value.
 229
 230         See Also:
 231
 232                 <parse>, <BigInteger>
 233 */
 234 function BigInteger(n, s, token) {
 235         if (token !== CONSTRUCT) {
 236                 if (n instanceof BigInteger) {
 237                         return n;
 238                 }
 239                 else if (typeof n === "undefined") {
 240                         return ZERO;
 241                 }
 242                 return BigInteger.parse(n);
 243         }
 244
 245         n = n || [];  // Provide the nullary constructor for subclasses.
 246         while (n.length && !n[n.length - 1]) {
 247                 --n.length;
 248         }
 249         this._d = n;
 250         this._s = n.length ? (s || 1) : 0;
 251 }
 252
 253 BigInteger._construct = function(n, s) {
 254         return new BigInteger(n, s, CONSTRUCT);
 255 };
 256
 257 // Base-10 speedup hacks in parse, toString, exp10 and log functions
 258 // require base to be a power of 10. 10^7 is the largest such power
 259 // that won't cause a precision loss when digits are multiplied.
 260 var BigInteger_base = 10000000;
 261 var BigInteger_base_log10 = 7;
 262
 263 BigInteger.base = BigInteger_base;
 264 BigInteger.base_log10 = BigInteger_base_log10;
 265
 266 var ZERO = new BigInteger([], 0, CONSTRUCT);
 267 // Constant: ZERO
 268 // <BigInteger> 0.
 269 BigInteger.ZERO = ZERO;
 270
 271 var ONE = new BigInteger([1], 1, CONSTRUCT);
 272 // Constant: ONE
 273 // <BigInteger> 1.
 274 BigInteger.ONE = ONE;
 275
 276 var M_ONE = new BigInteger(ONE._d, -1, CONSTRUCT);
 277 // Constant: M_ONE
 278 // <BigInteger> -1.
 279 BigInteger.M_ONE = M_ONE;
 280
 281 // Constant: _0
 282 // Shortcut for <ZERO>.
 283 BigInteger._0 = ZERO;
 284
 285 // Constant: _1
 286 // Shortcut for <ONE>.
 287 BigInteger._1 = ONE;
 288
 289 /*
 290         Constant: small
 291         Array of <BigIntegers> from 0 to 36.
 292
 293         These are used internally for parsing, but useful when you need a "small"
 294         <BigInteger>.
 295
 296         See Also:
 297
 298                 <ZERO>, <ONE>, <_0>, <_1>
 299 */
 300 BigInteger.small = [
 301         ZERO,
 302         ONE,
 303         /* Assuming BigInteger_base > 36 */
 304         new BigInteger( [2], 1, CONSTRUCT),
 305         new BigInteger( [3], 1, CONSTRUCT),
 306         new BigInteger( [4], 1, CONSTRUCT),
 307         new BigInteger( [5], 1, CONSTRUCT),
 308         new BigInteger( [6], 1, CONSTRUCT),
 309         new BigInteger( [7], 1, CONSTRUCT),
 310         new BigInteger( [8], 1, CONSTRUCT),
 311         new BigInteger( [9], 1, CONSTRUCT),
 312         new BigInteger([10], 1, CONSTRUCT),
 313         new BigInteger([11], 1, CONSTRUCT),
 314         new BigInteger([12], 1, CONSTRUCT),
 315         new BigInteger([13], 1, CONSTRUCT),
 316         new BigInteger([14], 1, CONSTRUCT),
 317         new BigInteger([15], 1, CONSTRUCT),
 318         new BigInteger([16], 1, CONSTRUCT),
 319         new BigInteger([17], 1, CONSTRUCT),
 320         new BigInteger([18], 1, CONSTRUCT),
 321         new BigInteger([19], 1, CONSTRUCT),
 322         new BigInteger([20], 1, CONSTRUCT),
 323         new BigInteger([21], 1, CONSTRUCT),
 324         new BigInteger([22], 1, CONSTRUCT),
 325         new BigInteger([23], 1, CONSTRUCT),
 326         new BigInteger([24], 1, CONSTRUCT),
 327         new BigInteger([25], 1, CONSTRUCT),
 328         new BigInteger([26], 1, CONSTRUCT),
 329         new BigInteger([27], 1, CONSTRUCT),
 330         new BigInteger([28], 1, CONSTRUCT),
 331         new BigInteger([29], 1, CONSTRUCT),
 332         new BigInteger([30], 1, CONSTRUCT),
 333         new BigInteger([31], 1, CONSTRUCT),
 334         new BigInteger([32], 1, CONSTRUCT),
 335         new BigInteger([33], 1, CONSTRUCT),
 336         new BigInteger([34], 1, CONSTRUCT),
 337         new BigInteger([35], 1, CONSTRUCT),
 338         new BigInteger([36], 1, CONSTRUCT)
 339 ];
 340
 341 // Used for parsing/radix conversion
 342 BigInteger.digits = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ".split("");
 343
 344 /*
 345         Method: toString
 346         Convert a <BigInteger> to a string.
 347
 348         When *base* is greater than 10, letters are upper case.
 349
 350         Parameters:
 351
 352                 base - Optional base to represent the number in (default is base 10).
 353                        Must be between 2 and 36 inclusive, or an Error will be thrown.
 354
 355         Returns:
 356
 357                 The string representation of the <BigInteger>.
 358 */
 359 BigInteger.prototype.toString = function(base) {
 360         base = +base || 10;
 361         if (base < 2 || base > 36) {
 362                 throw new Error("illegal radix " + base + ".");
 363         }
 364         if (this._s === 0) {
 365                 return "0";
 366         }
 367         if (base === 10) {
 368                 var str = this._s < 0 ? "-" : "";
 369                 str += this._d[this._d.length - 1].toString();
 370                 for (var i = this._d.length - 2; i >= 0; i--) {
 371                         var group = this._d[i].toString();
 372                         while (group.length < BigInteger_base_log10) group = '0' + group;
 373                         str += group;
 374                 }
 375                 return str;
 376         }
 377         else {
 378                 var numerals = BigInteger.digits;
 379                 base = BigInteger.small[base];
 380                 var sign = this._s;
 381
 382                 var n = this.abs();
 383                 var digits = [];
 384                 var digit;
 385
 386                 while (n._s !== 0) {
 387                         var divmod = n.divRem(base);
 388                         n = divmod[0];
 389                         digit = divmod[1];
 390                         // TODO: This could be changed to unshift instead of reversing at the end.
 391                         // Benchmark both to compare speeds.
 392                         digits.push(numerals[digit.valueOf()]);
 393                 }
 394                 return (sign < 0 ? "-" : "") + digits.reverse().join("");
 395         }
 396 };
 397
 398 // Verify strings for parsing
 399 BigInteger.radixRegex = [
 400         /^$/,
 401         /^$/,
 402         /^[01]*$/,
 403         /^[012]*$/,
 404         /^[0-3]*$/,
 405         /^[0-4]*$/,
 406         /^[0-5]*$/,
 407         /^[0-6]*$/,
 408         /^[0-7]*$/,
 409         /^[0-8]*$/,
 410         /^[0-9]*$/,
 411         /^[0-9aA]*$/,
 412         /^[0-9abAB]*$/,
 413         /^[0-9abcABC]*$/,
 414         /^[0-9a-dA-D]*$/,
 415         /^[0-9a-eA-E]*$/,
 416         /^[0-9a-fA-F]*$/,
 417         /^[0-9a-gA-G]*$/,
 418         /^[0-9a-hA-H]*$/,
 419         /^[0-9a-iA-I]*$/,
 420         /^[0-9a-jA-J]*$/,
 421         /^[0-9a-kA-K]*$/,
 422         /^[0-9a-lA-L]*$/,
 423         /^[0-9a-mA-M]*$/,
 424         /^[0-9a-nA-N]*$/,
 425         /^[0-9a-oA-O]*$/,
 426         /^[0-9a-pA-P]*$/,
 427         /^[0-9a-qA-Q]*$/,
 428         /^[0-9a-rA-R]*$/,
 429         /^[0-9a-sA-S]*$/,
 430         /^[0-9a-tA-T]*$/,
 431         /^[0-9a-uA-U]*$/,
 432         /^[0-9a-vA-V]*$/,
 433         /^[0-9a-wA-W]*$/,
 434         /^[0-9a-xA-X]*$/,
 435         /^[0-9a-yA-Y]*$/,
 436         /^[0-9a-zA-Z]*$/
 437 ];
 438
 439 /*
 440         Function: parse
 441         Parse a string into a <BigInteger>.
 442
 443         *base* is optional but, if provided, must be from 2 to 36 inclusive. If
 444         *base* is not provided, it will be guessed based on the leading characters
 445         of *s* as follows:
 446
 447         - "0x" or "0X": *base* = 16
 448         - "0c" or "0C": *base* = 8
 449         - "0b" or "0B": *base* = 2
 450         - else: *base* = 10
 451
 452         If no base is provided, or *base* is 10, the number can be in exponential
 453         form. For example, these are all valid:
 454
 455         > BigInteger.parse("1e9");              // Same as "1000000000"
 456         > BigInteger.parse("1.234*10^3");       // Same as 1234
 457         > BigInteger.parse("56789 * 10 ** -2"); // Same as 567
 458
 459         If any characters fall outside the range defined by the radix, an exception
 460         will be thrown.
 461
 462         Parameters:
 463
 464                 s - The string to parse.
 465                 base - Optional radix (default is to guess based on *s*).
 466
 467         Returns:
 468
 469                 a <BigInteger> instance.
 470 */
 471 BigInteger.parse = function(s, base) {
 472         // Expands a number in exponential form to decimal form.
 473         // expandExponential("-13.441*10^5") === "1344100";
 474         // expandExponential("1.12300e-1") === "0.112300";
 475         // expandExponential(1000000000000000000000000000000) === "1000000000000000000000000000000";
 476         function expandExponential(str) {
 477                 str = str.replace(/\s*[*xX]\s*10\s*(\^|\*\*)\s*/, "e");
 478
 479                 return str.replace(/^([+\-])?(\d+)\.?(\d*)[eE]([+\-]?\d+)$/, function(x, s, n, f, c) {
 480                         c = +c;
 481                         var l = c < 0;
 482                         var i = n.length + c;
 483                         x = (l ? n : f).length;
 484                         c = ((c = Math.abs(c)) >= x ? c - x + l : 0);
 485                         var z = (new Array(c + 1)).join("0");
 486                         var r = n + f;
 487                         return (s || "") + (l ? r = z + r : r += z).substr(0, i += l ? z.length : 0) + (i < r.length ? "." + r.substr(i) : "");
 488                 });
 489         }
 490
 491         s = s.toString();
 492         if (typeof base === "undefined" || +base === 10) {
 493                 s = expandExponential(s);
 494         }
 495
 496         var prefixRE;
 497         if (typeof base === "undefined") {
 498                 prefixRE = '0[xcb]';
 499         }
 500         else if (base == 16) {
 501                 prefixRE = '0x';
 502         }
 503         else if (base == 8) {
 504                 prefixRE = '0c';
 505         }
 506         else if (base == 2) {
 507                 prefixRE = '0b';
 508         }
 509         else {
 510                 prefixRE = '';
 511         }
 512         var parts = new RegExp('^([+\\-]?)(' + prefixRE + ')?([0-9a-z]*)(?:\\.\\d*)?$', 'i').exec(s);
 513         if (parts) {
 514                 var sign = parts[1] || "+";
 515                 var baseSection = parts[2] || "";
 516                 var digits = parts[3] || "";
 517
 518                 if (typeof base === "undefined") {
 519                         // Guess base
 520                         if (baseSection === "0x" || baseSection === "0X") { // Hex
 521                                 base = 16;
 522                         }
 523                         else if (baseSection === "0c" || baseSection === "0C") { // Octal
 524                                 base = 8;
 525                         }
 526                         else if (baseSection === "0b" || baseSection === "0B") { // Binary
 527                                 base = 2;
 528                         }
 529                         else {
 530                                 base = 10;
 531                         }
 532                 }
 533                 else if (base < 2 || base > 36) {
 534                         throw new Error("Illegal radix " + base + ".");
 535                 }
 536
 537                 base = +base;
 538
 539                 // Check for digits outside the range
 540                 if (!(BigInteger.radixRegex[base].test(digits))) {
 541                         throw new Error("Bad digit for radix " + base);
 542                 }
 543
 544                 // Strip leading zeros, and convert to array
 545                 digits = digits.replace(/^0+/, "").split("");
 546                 if (digits.length === 0) {
 547                         return ZERO;
 548                 }
 549
 550                 // Get the sign (we know it's not zero)
 551                 sign = (sign === "-") ? -1 : 1;
 552
 553                 // Optimize 10
 554                 if (base == 10) {
 555                         var d = [];
 556                         while (digits.length >= BigInteger_base_log10) {
 557                                 d.push(parseInt(digits.splice(digits.length-BigInteger.base_log10, BigInteger.base_log10).join(''), 10));
 558                         }
 559                         d.push(parseInt(digits.join(''), 10));
 560                         return new BigInteger(d, sign, CONSTRUCT);
 561                 }
 562
 563                 // Do the conversion
 564                 var d = ZERO;
 565                 base = BigInteger.small[base];
 566                 var small = BigInteger.small;
 567                 for (var i = 0; i < digits.length; i++) {
 568                         d = d.multiply(base).add(small[parseInt(digits[i], 36)]);
 569                 }
 570                 return new BigInteger(d._d, sign, CONSTRUCT);
 571         }
 572         else {
 573                 throw new Error("Invalid BigInteger format: " + s);
 574         }
 575 };
 576
 577 /*
 578         Function: add
 579         Add two <BigIntegers>.
 580
 581         Parameters:
 582
 583                 n - The number to add to *this*. Will be converted to a <BigInteger>.
 584
 585         Returns:
 586
 587                 The numbers added together.
 588
 589         See Also:
 590
 591                 <subtract>, <multiply>, <quotient>, <next>
 592 */
 593 BigInteger.prototype.add = function(n) {
 594         if (this._s === 0) {
 595                 return BigInteger(n);
 596         }
 597
 598         n = BigInteger(n);
 599         if (n._s === 0) {
 600                 return this;
 601         }
 602         if (this._s !== n._s) {
 603                 n = n.negate();
 604                 return this.subtract(n);
 605         }
 606
 607         var a = this._d;
 608         var b = n._d;
 609         var al = a.length;
 610         var bl = b.length;
 611         var sum = new Array(Math.max(al, bl) + 1);
 612         var size = Math.min(al, bl);
 613         var carry = 0;
 614         var digit;
 615
 616         for (var i = 0; i < size; i++) {
 617                 digit = a[i] + b[i] + carry;
 618                 sum[i] = digit % BigInteger_base;
 619                 carry = (digit / BigInteger_base) | 0;
 620         }
 621         if (bl > al) {
 622                 a = b;
 623                 al = bl;
 624         }
 625         for (i = size; carry && i < al; i++) {
 626                 digit = a[i] + carry;
 627                 sum[i] = digit % BigInteger_base;
 628                 carry = (digit / BigInteger_base) | 0;
 629         }
 630         if (carry) {
 631                 sum[i] = carry;
 632         }
 633
 634         for ( ; i < al; i++) {
 635                 sum[i] = a[i];
 636         }
 637
 638         return new BigInteger(sum, this._s, CONSTRUCT);
 639 };
 640
 641 /*
 642         Function: negate
 643         Get the additive inverse of a <BigInteger>.
 644
 645         Returns:
 646
 647                 A <BigInteger> with the same magnatude, but with the opposite sign.
 648
 649         See Also:
 650
 651                 <abs>
 652 */
 653 BigInteger.prototype.negate = function() {
 654         return new BigInteger(this._d, (-this._s) | 0, CONSTRUCT);
 655 };
 656
 657 /*
 658         Function: abs
 659         Get the absolute value of a <BigInteger>.
 660
 661         Returns:
 662
 663                 A <BigInteger> with the same magnatude, but always positive (or zero).
 664
 665         See Also:
 666
 667                 <negate>
 668 */
 669 BigInteger.prototype.abs = function() {
 670         return (this._s < 0) ? this.negate() : this;
 671 };
 672
 673 /*
 674         Function: subtract
 675         Subtract two <BigIntegers>.
 676
 677         Parameters:
 678
 679                 n - The number to subtract from *this*. Will be converted to a <BigInteger>.
 680
 681         Returns:
 682
 683                 The *n* subtracted from *this*.
 684
 685         See Also:
 686
 687                 <add>, <multiply>, <quotient>, <prev>
 688 */
 689 BigInteger.prototype.subtract = function(n) {
 690         if (this._s === 0) {
 691                 return BigInteger(n).negate();
 692         }
 693
 694         n = BigInteger(n);
 695         if (n._s === 0) {
 696                 return this;
 697         }
 698         if (this._s !== n._s) {
 699                 n = n.negate();
 700                 return this.add(n);
 701         }
 702
 703         var m = this;
 704         // negative - negative => -|a| - -|b| => -|a| + |b| => |b| - |a|
 705         if (this._s < 0) {
 706                 m = new BigInteger(n._d, 1, CONSTRUCT);
 707                 n = new BigInteger(this._d, 1, CONSTRUCT);
 708         }
 709
 710         // Both are positive => a - b
 711         var sign = m.compareAbs(n);
 712         if (sign === 0) {
 713                 return ZERO;
 714         }
 715         else if (sign < 0) {
 716                 // swap m and n
 717                 var t = n;
 718                 n = m;
 719                 m = t;
 720         }
 721
 722         // a > b
 723         var a = m._d;
 724         var b = n._d;
 725         var al = a.length;
 726         var bl = b.length;
 727         var diff = new Array(al); // al >= bl since a > b
 728         var borrow = 0;
 729         var i;
 730         var digit;
 731
 732         for (i = 0; i < bl; i++) {
 733                 digit = a[i] - borrow - b[i];
 734                 if (digit < 0) {
 735                         digit += BigInteger_base;
 736                         borrow = 1;
 737                 }
 738                 else {
 739                         borrow = 0;
 740                 }
 741                 diff[i] = digit;
 742         }
 743         for (i = bl; i < al; i++) {
 744                 digit = a[i] - borrow;
 745                 if (digit < 0) {
 746                         digit += BigInteger_base;
 747                 }
 748                 else {
 749                         diff[i++] = digit;
 750                         break;
 751                 }
 752                 diff[i] = digit;
 753         }
 754         for ( ; i < al; i++) {
 755                 diff[i] = a[i];
 756         }
 757
 758         return new BigInteger(diff, sign, CONSTRUCT);
 759 };
 760
 761 (function() {
 762         function addOne(n, sign) {
 763                 var a = n._d;
 764                 var sum = a.slice();
 765                 var carry = true;
 766                 var i = 0;
 767
 768                 while (true) {
 769                         var digit = (a[i] || 0) + 1;
 770                         sum[i] = digit % BigInteger_base;
 771                         if (digit <= BigInteger_base - 1) {
 772                                 break;
 773                         }
 774                         ++i;
 775                 }
 776
 777                 return new BigInteger(sum, sign, CONSTRUCT);
 778         }
 779
 780         function subtractOne(n, sign) {
 781                 var a = n._d;
 782                 var sum = a.slice();
 783                 var borrow = true;
 784                 var i = 0;
 785
 786                 while (true) {
 787                         var digit = (a[i] || 0) - 1;
 788                         if (digit < 0) {
 789                                 sum[i] = digit + BigInteger_base;
 790                         }
 791                         else {
 792                                 sum[i] = digit;
 793                                 break;
 794                         }
 795                         ++i;
 796                 }
 797
 798                 return new BigInteger(sum, sign, CONSTRUCT);
 799         }
 800
 801         /*
 802                 Function: next
 803                 Get the next <BigInteger> (add one).
 804
 805                 Returns:
 806
 807                         *this* + 1.
 808
 809                 See Also:
 810
 811                         <add>, <prev>
 812         */
 813         BigInteger.prototype.next = function() {
 814                 switch (this._s) {
 815                 case 0:
 816                         return ONE;
 817                 case -1:
 818                         return subtractOne(this, -1);
 819                 // case 1:
 820                 default:
 821                         return addOne(this, 1);
 822                 }
 823         };
 824
 825         /*
 826                 Function: prev
 827                 Get the previous <BigInteger> (subtract one).
 828
 829                 Returns:
 830
 831                         *this* - 1.
 832
 833                 See Also:
 834
 835                         <next>, <subtract>
 836         */
 837         BigInteger.prototype.prev = function() {
 838                 switch (this._s) {
 839                 case 0:
 840                         return M_ONE;
 841                 case -1:
 842                         return addOne(this, -1);
 843                 // case 1:
 844                 default:
 845                         return subtractOne(this, 1);
 846                 }
 847         };
 848 })();
 849
 850 /*
 851         Function: compareAbs
 852         Compare the absolute value of two <BigIntegers>.
 853
 854         Calling <compareAbs> is faster than calling <abs> twice, then <compare>.
 855
 856         Parameters:
 857
 858                 n - The number to compare to *this*. Will be converted to a <BigInteger>.
 859
 860         Returns:
 861
 862                 -1, 0, or +1 if *|this|* is less than, equal to, or greater than *|n|*.
 863
 864         See Also:
 865
 866                 <compare>, <abs>
 867 */
 868 BigInteger.prototype.compareAbs = function(n) {
 869         if (this === n) {
 870                 return 0;
 871         }
 872
 873         if (!(n instanceof BigInteger)) {
 874                 if (!isFinite(n)) {
 875                         return(isNaN(n) ? n : -1);
 876                 }
 877                 n = BigInteger(n);
 878         }
 879
 880         if (this._s === 0) {
 881                 return (n._s !== 0) ? -1 : 0;
 882         }
 883         if (n._s === 0) {
 884                 return 1;
 885         }
 886
 887         var l = this._d.length;
 888         var nl = n._d.length;
 889         if (l < nl) {
 890                 return -1;
 891         }
 892         else if (l > nl) {
 893                 return 1;
 894         }
 895
 896         var a = this._d;
 897         var b = n._d;
 898         for (var i = l-1; i >= 0; i--) {
 899                 if (a[i] !== b[i]) {
 900                         return a[i] < b[i] ? -1 : 1;
 901                 }
 902         }
 903
 904         return 0;
 905 };
 906
 907 /*
 908         Function: compare
 909         Compare two <BigIntegers>.
 910
 911         Parameters:
 912
 913                 n - The number to compare to *this*. Will be converted to a <BigInteger>.
 914
 915         Returns:
 916
 917                 -1, 0, or +1 if *this* is less than, equal to, or greater than *n*.
 918
 919         See Also:
 920
 921                 <compareAbs>, <isPositive>, <isNegative>, <isUnit>
 922 */
 923 BigInteger.prototype.compare = function(n) {
 924         if (this === n) {
 925                 return 0;
 926         }
 927
 928         n = BigInteger(n);
 929
 930         if (this._s === 0) {
 931                 return -n._s;
 932         }
 933
 934         if (this._s === n._s) { // both positive or both negative
 935                 var cmp = this.compareAbs(n);
 936                 return cmp * this._s;
 937         }
 938         else {
 939                 return this._s;
 940         }
 941 };
 942
 943 /*
 944         Function: isUnit
 945         Return true iff *this* is either 1 or -1.
 946
 947         Returns:
 948
 949                 true if *this* compares equal to <BigInteger.ONE> or <BigInteger.M_ONE>.
 950
 951         See Also:
 952
 953                 <isZero>, <isNegative>, <isPositive>, <compareAbs>, <compare>,
 954                 <BigInteger.ONE>, <BigInteger.M_ONE>
 955 */
 956 BigInteger.prototype.isUnit = function() {
 957         return this === ONE ||
 958                 this === M_ONE ||
 959                 (this._d.length === 1 && this._d[0] === 1);
 960 };
 961
 962 /*
 963         Function: multiply
 964         Multiply two <BigIntegers>.
 965
 966         Parameters:
 967
 968                 n - The number to multiply *this* by. Will be converted to a
 969                 <BigInteger>.
 970
 971         Returns:
 972
 973                 The numbers multiplied together.
 974
 975         See Also:
 976
 977                 <add>, <subtract>, <quotient>, <square>
 978 */
 979 BigInteger.prototype.multiply = function(n) {
 980         // TODO: Consider adding Karatsuba multiplication for large numbers
 981         if (this._s === 0) {
 982                 return ZERO;
 983         }
 984
 985         n = BigInteger(n);
 986         if (n._s === 0) {
 987                 return ZERO;
 988         }
 989         if (this.isUnit()) {
 990                 if (this._s < 0) {
 991                         return n.negate();
 992                 }
 993                 return n;
 994         }
 995         if (n.isUnit()) {
 996                 if (n._s < 0) {
 997                         return this.negate();
 998                 }
 999                 return this;
1000         }
1001         if (this === n) {
1002                 return this.square();
1003         }
1004
1005         var r = (this._d.length >= n._d.length);
1006         var a = (r ? this : n)._d; // a will be longer than b
1007         var b = (r ? n : this)._d;
1008         var al = a.length;
1009         var bl = b.length;
1010
1011         var pl = al + bl;
1012         var partial = new Array(pl);
1013         var i;
1014         for (i = 0; i < pl; i++) {
1015                 partial[i] = 0;
1016         }
1017
1018         for (i = 0; i < bl; i++) {
1019                 var carry = 0;
1020                 var bi = b[i];
1021                 var jlimit = al + i;
1022                 var digit;
1023                 for (var j = i; j < jlimit; j++) {
1024                         digit = partial[j] + bi * a[j - i] + carry;
1025                         carry = (digit / BigInteger_base) | 0;
1026                         partial[j] = (digit % BigInteger_base) | 0;
1027                 }
1028                 if (carry) {
1029                         digit = partial[j] + carry;
1030                         carry = (digit / BigInteger_base) | 0;
1031                         partial[j] = digit % BigInteger_base;
1032                 }
1033         }
1034         return new BigInteger(partial, this._s * n._s, CONSTRUCT);
1035 };
1036
1037 // Multiply a BigInteger by a single-digit native number
1038 // Assumes that this and n are >= 0
1039 // This is not really intended to be used outside the library itself
1040 BigInteger.prototype.multiplySingleDigit = function(n) {
1041         if (n === 0 || this._s === 0) {
1042                 return ZERO;
1043         }
1044         if (n === 1) {
1045                 return this;
1046         }
1047
1048         var digit;
1049         if (this._d.length === 1) {
1050                 digit = this._d[0] * n;
1051                 if (digit >= BigInteger_base) {
1052                         return new BigInteger([(digit % BigInteger_base)|0,
1053                                         (digit / BigInteger_base)|0], 1, CONSTRUCT);
1054                 }
1055                 return new BigInteger([digit], 1, CONSTRUCT);
1056         }
1057
1058         if (n === 2) {
1059                 return this.add(this);
1060         }
1061         if (this.isUnit()) {
1062                 return new BigInteger([n], 1, CONSTRUCT);
1063         }
1064
1065         var a = this._d;
1066         var al = a.length;
1067
1068         var pl = al + 1;
1069         var partial = new Array(pl);
1070         for (var i = 0; i < pl; i++) {
1071                 partial[i] = 0;
1072         }
1073
1074         var carry = 0;
1075         for (var j = 0; j < al; j++) {
1076                 digit = n * a[j] + carry;
1077                 carry = (digit / BigInteger_base) | 0;
1078                 partial[j] = (digit % BigInteger_base) | 0;
1079         }
1080         if (carry) {
1081                 partial[j] = carry;
1082         }
1083
1084         return new BigInteger(partial, 1, CONSTRUCT);
1085 };
1086
1087 /*
1088         Function: square
1089         Multiply a <BigInteger> by itself.
1090
1091         This is slightly faster than regular multiplication, since it removes the
1092         duplicated multiplcations.
1093
1094         Returns:
1095
1096                 > this.multiply(this)
1097
1098         See Also:
1099                 <multiply>
1100 */
1101 BigInteger.prototype.square = function() {
1102         // Normally, squaring a 10-digit number would take 100 multiplications.
1103         // Of these 10 are unique diagonals, of the remaining 90 (100-10), 45 are repeated.
1104         // This procedure saves (N*(N-1))/2 multiplications, (e.g., 45 of 100 multiplies).
1105         // Based on code by Gary Darby, Intellitech Systems Inc., www.DelphiForFun.org
1106
1107         if (this._s === 0) {
1108                 return ZERO;
1109         }
1110         if (this.isUnit()) {
1111                 return ONE;
1112         }
1113
1114         var digits = this._d;
1115         var length = digits.length;
1116         var imult1 = new Array(length + length + 1);
1117         var product, carry, k;
1118         var i;
1119
1120         // Calculate diagonal
1121         for (i = 0; i < length; i++) {
1122                 k = i * 2;
1123                 product = digits[i] * digits[i];
1124                 carry = (product / BigInteger_base) | 0;
1125                 imult1[k] = product % BigInteger_base;
1126                 imult1[k + 1] = carry;
1127         }
1128
1129         // Calculate repeating part
1130         for (i = 0; i < length; i++) {
1131                 carry = 0;
1132                 k = i * 2 + 1;
1133                 for (var j = i + 1; j < length; j++, k++) {
1134                         product = digits[j] * digits[i] * 2 + imult1[k] + carry;
1135                         carry = (product / BigInteger_base) | 0;
1136                         imult1[k] = product % BigInteger_base;
1137                 }
1138                 k = length + i;
1139                 var digit = carry + imult1[k];
1140                 carry = (digit / BigInteger_base) | 0;
1141                 imult1[k] = digit % BigInteger_base;
1142                 imult1[k + 1] += carry;
1143         }
1144
1145         return new BigInteger(imult1, 1, CONSTRUCT);
1146 };
1147
1148 /*
1149         Function: quotient
1150         Divide two <BigIntegers> and truncate towards zero.
1151
1152         <quotient> throws an exception if *n* is zero.
1153
1154         Parameters:
1155
1156                 n - The number to divide *this* by. Will be converted to a <BigInteger>.
1157
1158         Returns:
1159
1160                 The *this* / *n*, truncated to an integer.
1161
1162         See Also:
1163
1164                 <add>, <subtract>, <multiply>, <divRem>, <remainder>
1165 */
1166 BigInteger.prototype.quotient = function(n) {
1167         return this.divRem(n)[0];
1168 };
1169
1170 /*
1171         Function: divide
1172         Deprecated synonym for <quotient>.
1173 */
1174 BigInteger.prototype.divide = BigInteger.prototype.quotient;
1175
1176 /*
1177         Function: remainder
1178         Calculate the remainder of two <BigIntegers>.
1179
1180         <remainder> throws an exception if *n* is zero.
1181
1182         Parameters:
1183
1184                 n - The remainder after *this* is divided *this* by *n*. Will be
1185                     converted to a <BigInteger>.
1186
1187         Returns:
1188
1189                 *this* % *n*.
1190
1191         See Also:
1192
1193                 <divRem>, <quotient>
1194 */
1195 BigInteger.prototype.remainder = function(n) {
1196         return this.divRem(n)[1];
1197 };
1198
1199 /*
1200         Function: divRem
1201         Calculate the integer quotient and remainder of two <BigIntegers>.
1202
1203         <divRem> throws an exception if *n* is zero.
1204
1205         Parameters:
1206
1207                 n - The number to divide *this* by. Will be converted to a <BigInteger>.
1208
1209         Returns:
1210
1211                 A two-element array containing the quotient and the remainder.
1212
1213                 > a.divRem(b)
1214
1215                 is exactly equivalent to
1216
1217                 > [a.quotient(b), a.remainder(b)]
1218
1219                 except it is faster, because they are calculated at the same time.
1220
1221         See Also:
1222
1223                 <quotient>, <remainder>
1224 */
1225 BigInteger.prototype.divRem = function(n) {
1226         n = BigInteger(n);
1227         if (n._s === 0) {
1228                 throw new Error("Divide by zero");
1229         }
1230         if (this._s === 0) {
1231                 return [ZERO, ZERO];
1232         }
1233         if (n._d.length === 1) {
1234                 return this.divRemSmall(n._s * n._d[0]);
1235         }
1236
1237         // Test for easy cases -- |n1| <= |n2|
1238         switch (this.compareAbs(n)) {
1239         case 0: // n1 == n2
1240                 return [this._s === n._s ? ONE : M_ONE, ZERO];
1241         case -1: // |n1| < |n2|
1242                 return [ZERO, this];
1243         }
1244
1245         var sign = this._s * n._s;
1246         var a = n.abs();
1247         var b_digits = this._d;
1248         var b_index = b_digits.length;
1249         var digits = n._d.length;
1250         var quot = [];
1251         var guess;
1252
1253         var part = new BigInteger([], 0, CONSTRUCT);
1254
1255         while (b_index) {
1256                 part._d.unshift(b_digits[--b_index]);
1257                 part = new BigInteger(part._d, 1, CONSTRUCT);
1258
1259                 if (part.compareAbs(n) < 0) {
1260                         quot.push(0);
1261                         continue;
1262                 }
1263                 if (part._s === 0) {
1264                         guess = 0;
1265                 }
1266                 else {
1267                         var xlen = part._d.length, ylen = a._d.length;
1268                         var highx = part._d[xlen-1]*BigInteger_base + part._d[xlen-2];
1269                         var highy = a._d[ylen-1]*BigInteger_base + a._d[ylen-2];
1270                         if (part._d.length > a._d.length) {
1271                                 // The length of part._d can either match a._d length,
1272                                 // or exceed it by one.
1273                                 highx = (highx+1)*BigInteger_base;
1274                         }
1275                         guess = Math.ceil(highx/highy);
1276                 }
1277                 do {
1278                         var check = a.multiplySingleDigit(guess);
1279                         if (check.compareAbs(part) <= 0) {
1280                                 break;
1281                         }
1282                         guess--;
1283                 } while (guess);
1284
1285                 quot.push(guess);
1286                 if (!guess) {
1287                         continue;
1288                 }
1289                 var diff = part.subtract(check);
1290                 part._d = diff._d.slice();
1291         }
1292
1293         return [new BigInteger(quot.reverse(), sign, CONSTRUCT),
1294                    new BigInteger(part._d, this._s, CONSTRUCT)];
1295 };
1296
1297 // Throws an exception if n is outside of (-BigInteger.base, -1] or
1298 // [1, BigInteger.base).  It's not necessary to call this, since the
1299 // other division functions will call it if they are able to.
1300 BigInteger.prototype.divRemSmall = function(n) {
1301         var r;
1302         n = +n;
1303         if (n === 0) {
1304                 throw new Error("Divide by zero");
1305         }
1306
1307         var n_s = n < 0 ? -1 : 1;
1308         var sign = this._s * n_s;
1309         n = Math.abs(n);
1310
1311         if (n < 1 || n >= BigInteger_base) {
1312                 throw new Error("Argument out of range");
1313         }
1314
1315         if (this._s === 0) {
1316                 return [ZERO, ZERO];
1317         }
1318
1319         if (n === 1 || n === -1) {
1320                 return [(sign === 1) ? this.abs() : new BigInteger(this._d, sign, CONSTRUCT), ZERO];
1321         }
1322
1323         // 2 <= n < BigInteger_base
1324
1325         // divide a single digit by a single digit
1326         if (this._d.length === 1) {
1327                 var q = new BigInteger([(this._d[0] / n) | 0], 1, CONSTRUCT);
1328                 r = new BigInteger([(this._d[0] % n) | 0], 1, CONSTRUCT);
1329                 if (sign < 0) {
1330                         q = q.negate();
1331                 }
1332                 if (this._s < 0) {
1333                         r = r.negate();
1334                 }
1335                 return [q, r];
1336         }
1337
1338         var digits = this._d.slice();
1339         var quot = new Array(digits.length);
1340         var part = 0;
1341         var diff = 0;
1342         var i = 0;
1343         var guess;
1344
1345         while (digits.length) {
1346                 part = part * BigInteger_base + digits[digits.length - 1];
1347                 if (part < n) {
1348                         quot[i++] = 0;
1349                         digits.pop();
1350                         diff = BigInteger_base * diff + part;
1351                         continue;
1352                 }
1353                 if (part === 0) {
1354                         guess = 0;
1355                 }
1356                 else {
1357                         guess = (part / n) | 0;
1358                 }
1359
1360                 var check = n * guess;
1361                 diff = part - check;
1362                 quot[i++] = guess;
1363                 if (!guess) {
1364                         digits.pop();
1365                         continue;
1366                 }
1367
1368                 digits.pop();
1369                 part = diff;
1370         }
1371
1372         r = new BigInteger([diff], 1, CONSTRUCT);
1373         if (this._s < 0) {
1374                 r = r.negate();
1375         }
1376         return [new BigInteger(quot.reverse(), sign, CONSTRUCT), r];
1377 };
1378
1379 /*
1380         Function: isEven
1381         Return true iff *this* is divisible by two.
1382
1383         Note that <BigInteger.ZERO> is even.
1384
1385         Returns:
1386
1387                 true if *this* is even, false otherwise.
1388
1389         See Also:
1390
1391                 <isOdd>
1392 */
1393 BigInteger.prototype.isEven = function() {
1394         var digits = this._d;
1395         return this._s === 0 || digits.length === 0 || (digits[0] % 2) === 0;
1396 };
1397
1398 /*
1399         Function: isOdd
1400         Return true iff *this* is not divisible by two.
1401
1402         Returns:
1403
1404                 true if *this* is odd, false otherwise.
1405
1406         See Also:
1407
1408                 <isEven>
1409 */
1410 BigInteger.prototype.isOdd = function() {
1411         return !this.isEven();
1412 };
1413
1414 /*
1415         Function: sign
1416         Get the sign of a <BigInteger>.
1417
1418         Returns:
1419
1420                 * -1 if *this* < 0
1421                 * 0 if *this* == 0
1422                 * +1 if *this* > 0
1423
1424         See Also:
1425
1426                 <isZero>, <isPositive>, <isNegative>, <compare>, <BigInteger.ZERO>
1427 */
1428 BigInteger.prototype.sign = function() {
1429         return this._s;
1430 };
1431
1432 /*
1433         Function: isPositive
1434         Return true iff *this* > 0.
1435
1436         Returns:
1437
1438                 true if *this*.compare(<BigInteger.ZERO>) == 1.
1439
1440         See Also:
1441
1442                 <sign>, <isZero>, <isNegative>, <isUnit>, <compare>, <BigInteger.ZERO>
1443 */
1444 BigInteger.prototype.isPositive = function() {
1445         return this._s > 0;
1446 };
1447
1448 /*
1449         Function: isNegative
1450         Return true iff *this* < 0.
1451
1452         Returns:
1453
1454                 true if *this*.compare(<BigInteger.ZERO>) == -1.
1455
1456         See Also:
1457
1458                 <sign>, <isPositive>, <isZero>, <isUnit>, <compare>, <BigInteger.ZERO>
1459 */
1460 BigInteger.prototype.isNegative = function() {
1461         return this._s < 0;
1462 };
1463
1464 /*
1465         Function: isZero
1466         Return true iff *this* == 0.
1467
1468         Returns:
1469
1470                 true if *this*.compare(<BigInteger.ZERO>) == 0.
1471
1472         See Also:
1473
1474                 <sign>, <isPositive>, <isNegative>, <isUnit>, <BigInteger.ZERO>
1475 */
1476 BigInteger.prototype.isZero = function() {
1477         return this._s === 0;
1478 };
1479
1480 /*
1481         Function: exp10
1482         Multiply a <BigInteger> by a power of 10.
1483
1484         This is equivalent to, but faster than
1485
1486         > if (n >= 0) {
1487         >     return this.multiply(BigInteger("1e" + n));
1488         > }
1489         > else { // n <= 0
1490         >     return this.quotient(BigInteger("1e" + -n));
1491         > }
1492
1493         Parameters:
1494
1495                 n - The power of 10 to multiply *this* by. *n* is converted to a
1496                 javascipt number and must be no greater than <BigInteger.MAX_EXP>
1497                 (0x7FFFFFFF), or an exception will be thrown.
1498
1499         Returns:
1500
1501                 *this* * (10 ** *n*), truncated to an integer if necessary.
1502
1503         See Also:
1504
1505                 <pow>, <multiply>
1506 */
1507 BigInteger.prototype.exp10 = function(n) {
1508         n = +n;
1509         if (n === 0) {
1510                 return this;
1511         }
1512         if (Math.abs(n) > Number(MAX_EXP)) {
1513                 throw new Error("exponent too large in BigInteger.exp10");
1514         }
1515         // Optimization for this == 0. This also keeps us from having to trim zeros in the positive n case
1516         if (this._s === 0) {
1517                 return ZERO;
1518         }
1519         if (n > 0) {
1520                 var k = new BigInteger(this._d.slice(), this._s, CONSTRUCT);
1521
1522                 for (; n >= BigInteger_base_log10; n -= BigInteger_base_log10) {
1523                         k._d.unshift(0);
1524                 }
1525                 if (n == 0)
1526                         return k;
1527                 k._s = 1;
1528                 k = k.multiplySingleDigit(Math.pow(10, n));
1529                 return (this._s < 0 ? k.negate() : k);
1530         } else if (-n >= this._d.length*BigInteger_base_log10) {
1531                 return ZERO;
1532         } else {
1533                 var k = new BigInteger(this._d.slice(), this._s, CONSTRUCT);
1534
1535                 for (n = -n; n >= BigInteger_base_log10; n -= BigInteger_base_log10) {
1536                         k._d.shift();
1537                 }
1538                 return (n == 0) ? k : k.divRemSmall(Math.pow(10, n))[0];
1539         }
1540 };
1541
1542 /*
1543         Function: pow
1544         Raise a <BigInteger> to a power.
1545
1546         In this implementation, 0**0 is 1.
1547
1548         Parameters:
1549
1550                 n - The exponent to raise *this* by. *n* must be no greater than
1551                 <BigInteger.MAX_EXP> (0x7FFFFFFF), or an exception will be thrown.
1552
1553         Returns:
1554
1555                 *this* raised to the *nth* power.
1556
1557         See Also:
1558
1559                 <modPow>
1560 */
1561 BigInteger.prototype.pow = function(n) {
1562         if (this.isUnit()) {
1563                 if (this._s > 0) {
1564                         return this;
1565                 }
1566                 else {
1567                         return BigInteger(n).isOdd() ? this : this.negate();
1568                 }
1569         }
1570
1571         n = BigInteger(n);
1572         if (n._s === 0) {
1573                 return ONE;
1574         }
1575         else if (n._s < 0) {
1576                 if (this._s === 0) {
1577                         throw new Error("Divide by zero");
1578                 }
1579                 else {
1580                         return ZERO;
1581                 }
1582         }
1583         if (this._s === 0) {
1584                 return ZERO;
1585         }
1586         if (n.isUnit()) {
1587                 return this;
1588         }
1589
1590         if (n.compareAbs(MAX_EXP) > 0) {
1591                 throw new Error("exponent too large in BigInteger.pow");
1592         }
1593         var x = this;
1594         var aux = ONE;
1595         var two = BigInteger.small[2];
1596
1597         while (n.isPositive()) {
1598                 if (n.isOdd()) {
1599                         aux = aux.multiply(x);
1600                         if (n.isUnit()) {
1601                                 return aux;
1602                         }
1603                 }
1604                 x = x.square();
1605                 n = n.quotient(two);
1606         }
1607
1608         return aux;
1609 };
1610
1611 /*
1612         Function: modPow
1613         Raise a <BigInteger> to a power (mod m).
1614
1615         Because it is reduced by a modulus, <modPow> is not limited by
1616         <BigInteger.MAX_EXP> like <pow>.
1617
1618         Parameters:
1619
1620                 exponent - The exponent to raise *this* by. Must be positive.
1621                 modulus - The modulus.
1622
1623         Returns:
1624
1625                 *this* ^ *exponent* (mod *modulus*).
1626
1627         See Also:
1628
1629                 <pow>, <mod>
1630 */
1631 BigInteger.prototype.modPow = function(exponent, modulus) {
1632         var result = ONE;
1633         var base = this;
1634
1635         while (exponent.isPositive()) {
1636                 if (exponent.isOdd()) {
1637                         result = result.multiply(base).remainder(modulus);
1638                 }
1639
1640                 exponent = exponent.quotient(BigInteger.small[2]);
1641                 if (exponent.isPositive()) {
1642                         base = base.square().remainder(modulus);
1643                 }
1644         }
1645
1646         return result;
1647 };
1648
1649 /*
1650         Function: log
1651         Get the natural logarithm of a <BigInteger> as a native JavaScript number.
1652
1653         This is equivalent to
1654
1655         > Math.log(this.toJSValue())
1656
1657         but handles values outside of the native number range.
1658
1659         Returns:
1660
1661                 log( *this* )
1662
1663         See Also:
1664
1665                 <toJSValue>
1666 */
1667 BigInteger.prototype.log = function() {
1668         switch (this._s) {
1669         case 0:  return -Infinity;
1670         case -1: return NaN;
1671         default: // Fall through.
1672         }
1673
1674         var l = this._d.length;
1675
1676         if (l*BigInteger_base_log10 < 30) {
1677                 return Math.log(this.valueOf());
1678         }
1679
1680         var N = Math.ceil(30/BigInteger_base_log10);
1681         var firstNdigits = this._d.slice(l - N);
1682         return Math.log((new BigInteger(firstNdigits, 1, CONSTRUCT)).valueOf()) + (l - N) * Math.log(BigInteger_base);
1683 };
1684
1685 /*
1686         Function: valueOf
1687         Convert a <BigInteger> to a native JavaScript integer.
1688
1689         This is called automatically by JavaScipt to convert a <BigInteger> to a
1690         native value.
1691
1692         Returns:
1693
1694                 > parseInt(this.toString(), 10)
1695
1696         See Also:
1697
1698                 <toString>, <toJSValue>
1699 */
1700 BigInteger.prototype.valueOf = function() {
1701         return parseInt(this.toString(), 10);
1702 };
1703
1704 /*
1705         Function: toJSValue
1706         Convert a <BigInteger> to a native JavaScript integer.
1707
1708         This is the same as valueOf, but more explicitly named.
1709
1710         Returns:
1711
1712                 > parseInt(this.toString(), 10)
1713
1714         See Also:
1715
1716                 <toString>, <valueOf>
1717 */
1718 BigInteger.prototype.toJSValue = function() {
1719         return parseInt(this.toString(), 10);
1720 };
1721
1722 var MAX_EXP = BigInteger(0x7FFFFFFF);
1723 // Constant: MAX_EXP
1724 // The largest exponent allowed in <pow> and <exp10> (0x7FFFFFFF or 2147483647).
1725 BigInteger.MAX_EXP = MAX_EXP;
1726
1727 (function() {
1728         function makeUnary(fn) {
1729                 return function(a) {
1730                         return fn.call(BigInteger(a));
1731                 };
1732         }
1733
1734         function makeBinary(fn) {
1735                 return function(a, b) {
1736                         return fn.call(BigInteger(a), BigInteger(b));
1737                 };
1738         }
1739
1740         function makeTrinary(fn) {
1741                 return function(a, b, c) {
1742                         return fn.call(BigInteger(a), BigInteger(b), BigInteger(c));
1743                 };
1744         }
1745
1746         (function() {
1747                 var i, fn;
1748                 var unary = "toJSValue,isEven,isOdd,sign,isZero,isNegative,abs,isUnit,square,negate,isPositive,toString,next,prev,log".split(",");
1749                 var binary = "compare,remainder,divRem,subtract,add,quotient,divide,multiply,pow,compareAbs".split(",");
1750                 var trinary = ["modPow"];
1751
1752                 for (i = 0; i < unary.length; i++) {
1753                         fn = unary[i];
1754                         BigInteger[fn] = makeUnary(BigInteger.prototype[fn]);
1755                 }
1756
1757                 for (i = 0; i < binary.length; i++) {
1758                         fn = binary[i];
1759                         BigInteger[fn] = makeBinary(BigInteger.prototype[fn]);
1760                 }
1761
1762                 for (i = 0; i < trinary.length; i++) {
1763                         fn = trinary[i];
1764                         BigInteger[fn] = makeTrinary(BigInteger.prototype[fn]);
1765                 }
1766
1767                 BigInteger.exp10 = function(x, n) {
1768                         return BigInteger(x).exp10(n);
1769                 };
1770         })();
1771 })();
1772
1773 exports.BigInteger = BigInteger;
1774 })(typeof exports !== 'undefined' ? exports : this);