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