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