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