src/js/entropy.js

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