]>
git.immae.eu Git - perso/Immae/Projets/Cryptomonnaies/BIP39.git/blob - src/js/entropy.js
2 * Detects entropy from a string.
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
16 window
.Entropy
= new (function() {
18 // matchers returns an array of the matched events for each type of entropy.
20 // matchers.binary("010") returns ["0", "1", "0"]
21 // matchers.binary("a10") returns ["1", "0"]
22 // matchers.hex("a10") returns ["a", "1", "0"]
24 binary: function(str
) {
25 return str
.match(/[0-1]/gi) || [];
27 base6: function(str
) {
28 return str
.match(/[0-5]/gi) || [];
31 return str
.match(/[1-6]/gi) || []; // ie dice numbers
33 base10: function(str
) {
34 return str
.match(/[0-9]/gi) || [];
37 return str
.match(/[0-9A-F]/gi) || [];
40 // Format is NumberSuit, eg
47 return str
.match(/([A2-9TJQK][CDHS])/gi) || [];
51 // Convert array of cards from ["ac", "4d", "ks"]
52 // to numbers between 0 and 51 [0, 16, 51]
53 function convertCardsToInts(cards
) {
55 var values
= "a23456789tjqk";
57 for (var i
=0; i
<cards
.length
; i
++) {
58 var card
= cards
[i
].toLowerCase();
61 var asInt
= 13 * suits
.indexOf(suit
) + values
.indexOf(value
);
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") {
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
];
86 base
.str
= "base 6 (dice)";
88 base
.parts
= newParts
;
89 base
.matcher
= matchers
.base6
;
91 // Detect empty entropy
92 if (base
.parts
.length
== 0) {
99 // Pull leading zeros off
100 var leadingZeros
= [];
101 while (base
.ints
[0] == "0") {
102 leadingZeros
.push("0");
105 // Convert leading zeros to binary equivalent
106 var numBinLeadingZeros
= Math
.floor(Math
.log2(base
.asInt
) * leadingZeros
.length
);
107 var binLeadingZeros
= "";
108 for (var i
=0; i
<numBinLeadingZeros
; i
++) {
109 binLeadingZeros
+= "0";
111 // Handle entropy of zero
112 if (base
.ints
.length
== 0) {
114 binaryStr: binLeadingZeros
,
115 cleanStr: leadingZeros
.join(""),
119 // If the first integer is small, it must be padded with zeros.
120 // Otherwise the chance of the first bit being 1 is 100%, which is
121 // obviously incorrect.
122 // This is not perfect for unusual bases, so is only done for bases
123 // of 2^n, eg octal or hexadecimal
124 if (base
.asInt
== 16) {
125 var firstInt
= base
.ints
[0];
126 var firstIntBits
= firstInt
.toString(2).length
;
127 var maxFirstIntBits
= (base
.asInt
-1).toString(2).length
;
128 var missingFirstIntBits
= maxFirstIntBits
- firstIntBits
;
129 for (var i
=0; i
<missingFirstIntBits
; i
++) {
130 binLeadingZeros
+= "0";
133 // Convert base.ints to BigInteger.
134 // Due to using unusual bases, eg cards of base52, this is not as simple as
135 // using BigInteger.parse()
136 var entropyInt
= BigInteger
.ZERO
;
137 for (var i
=base
.ints
.length
-1; i
>=0; i
--) {
138 var thisInt
= BigInteger
.parse(base
.ints
[i
]);
139 var power
= (base
.ints
.length
- 1) - i
;
140 var additionalEntropy
= BigInteger
.parse(base
.asInt
).pow(power
).multiply(thisInt
);
141 entropyInt
= entropyInt
.add(additionalEntropy
);
143 // Convert entropy to different formats
144 var entropyBin
= binLeadingZeros
+ entropyInt
.toString(2);
145 var entropyClean
= base
.parts
.join("");
146 if (base
.asInt
== 52) {
147 entropyClean
= base
.parts
.join(" ").toUpperCase();
148 entropyClean
= entropyClean
.replace(/C
/g
, "\u2663");
149 entropyClean
= entropyClean
.replace(/D
/g
, "\u2666");
150 entropyClean
= entropyClean
.replace(/H
/g
, "\u2665");
151 entropyClean
= entropyClean
.replace(/S
/g
, "\u2660");
154 binaryStr: entropyBin
,
155 cleanStr: entropyClean
,
161 function getBase(str
) {
162 // Need to get the lowest base for the supplied entropy.
163 // This prevents interpreting, say, dice rolls as hexadecimal.
164 var binaryMatches
= matchers
.binary(str
);
165 var hexMatches
= matchers
.hex(str
);
166 // Find the lowest base that can be used, whilst ignoring any irrelevant chars
167 if (binaryMatches
.length
== hexMatches
.length
&& hexMatches
.length
> 0) {
168 var ints
= binaryMatches
.map(function(i
) { return parseInt(i
, 2) });
171 parts: binaryMatches
,
172 matcher: matchers
.binary
,
177 var cardMatches
= matchers
.card(str
);
178 if (cardMatches
.length
>= hexMatches
.length
/ 2) {
179 var ints
= convertCardsToInts(cardMatches
);
183 matcher: matchers
.card
,
188 var diceMatches
= matchers
.dice(str
);
189 if (diceMatches
.length
== hexMatches
.length
&& hexMatches
.length
> 0) {
190 var ints
= diceMatches
.map(function(i
) { return parseInt(i
) });
194 matcher: matchers
.dice
,
199 var base6Matches
= matchers
.base6(str
);
200 if (base6Matches
.length
== hexMatches
.length
&& hexMatches
.length
> 0) {
201 var ints
= base6Matches
.map(function(i
) { return parseInt(i
) });
205 matcher: matchers
.base6
,
210 var base10Matches
= matchers
.base10(str
);
211 if (base10Matches
.length
== hexMatches
.length
&& hexMatches
.length
> 0) {
212 var ints
= base10Matches
.map(function(i
) { return parseInt(i
) });
215 parts: base10Matches
,
216 matcher: matchers
.base10
,
221 var ints
= hexMatches
.map(function(i
) { return parseInt(i
, 16) });
225 matcher: matchers
.hex
,
231 // Polyfill for Math.log2
232 // See https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Math/log2#Polyfill
233 Math
.log2
= Math
.log2
|| function(x
) {
234 // The polyfill isn't good enough because of the poor accuracy of
236 // log2(8) gave 2.9999999999999996 which when floored causes issues.
237 // So instead use the BigInteger library to get it right.
238 return BigInteger
.log(x
) / BigInteger
.log(2);
244 // BigInteger library included here because
245 // only the entropy library depends on it
246 // so if entropy detection is removed so is the dependency
250 JavaScript BigInteger library version 0.9.1
251 http://silentmatt.com/biginteger/
253 Copyright (c) 2009 Matthew Crumley <email@matthewcrumley.com>
254 Copyright (c) 2010,2011 by John Tobey <John.Tobey@gmail.com>
255 Licensed under the MIT license.
257 Support for arbitrary internal representation base was added by
272 An arbitrarily-large integer.
274 <BigInteger> objects should be considered immutable. None of the "built-in"
275 methods modify *this* or their arguments. All properties should be
278 All the methods of <BigInteger> instances can be called "statically". The
279 static versions are convenient if you don't already have a <BigInteger>
282 As an example, these calls are equivalent.
284 > BigInteger(4).multiply(5); // returns BigInteger(20);
285 > BigInteger.multiply(4, 5); // returns BigInteger(20);
288 > var a = BigInteger.toJSValue("0b101010"); // Not completely useless...
291 var CONSTRUCT
= {}; // Unique token to call "private" version of constructor
294 Constructor: BigInteger()
295 Convert a value to a <BigInteger>.
297 Although <BigInteger()> is the constructor for <BigInteger> objects, it is
298 best not to call it as a constructor. If *n* is a <BigInteger> object, it is
299 simply returned as-is. Otherwise, <BigInteger()> is equivalent to <parse>
300 without a radix argument.
302 > var n0 = BigInteger(); // Same as <BigInteger.ZERO>
303 > var n1 = BigInteger("123"); // Create a new <BigInteger> with value 123
304 > var n2 = BigInteger(123); // Create a new <BigInteger> with value 123
305 > var n3 = BigInteger(n2); // Return n2, unchanged
307 The constructor form only takes an array and a sign. *n* must be an
308 array of numbers in little-endian order, where each digit is between 0
309 and BigInteger.base. The second parameter sets the sign: -1 for
310 negative, +1 for positive, or 0 for zero. The array is *not copied and
311 may be modified*. If the array contains only zeros, the sign parameter
312 is ignored and is forced to zero.
314 > new BigInteger([5], -1): create a new BigInteger with value -5
318 n - Value to convert to a <BigInteger>.
322 A <BigInteger> value.
326 <parse>, <BigInteger>
328 function BigInteger(n
, s
, token
) {
329 if (token
!== CONSTRUCT
) {
330 if (n
instanceof BigInteger
) {
333 else if (typeof n
=== "undefined") {
336 return BigInteger
.parse(n
);
339 n
= n
|| []; // Provide the nullary constructor for subclasses.
340 while (n
.length
&& !n
[n
.length
- 1]) {
344 this._s
= n
.length
? (s
|| 1) : 0;
347 BigInteger
._construct = function(n
, s
) {
348 return new BigInteger(n
, s
, CONSTRUCT
);
351 // Base-10 speedup hacks in parse, toString, exp10 and log functions
352 // require base to be a power of 10. 10^7 is the largest such power
353 // that won't cause a precision loss when digits are multiplied.
354 var BigInteger_base
= 10000000;
355 var BigInteger_base_log10
= 7;
357 BigInteger
.base
= BigInteger_base
;
358 BigInteger
.base_log10
= BigInteger_base_log10
;
360 var ZERO
= new BigInteger([], 0, CONSTRUCT
);
363 BigInteger
.ZERO
= ZERO
;
365 var ONE
= new BigInteger([1], 1, CONSTRUCT
);
368 BigInteger
.ONE
= ONE
;
370 var M_ONE
= new BigInteger(ONE
._d
, -1, CONSTRUCT
);
373 BigInteger
.M_ONE
= M_ONE
;
376 // Shortcut for <ZERO>.
377 BigInteger
._0
= ZERO
;
380 // Shortcut for <ONE>.
385 Array of <BigIntegers> from 0 to 36.
387 These are used internally for parsing, but useful when you need a "small"
392 <ZERO>, <ONE>, <_0>, <_1>
397 /* Assuming BigInteger_base > 36 */
398 new BigInteger( [2], 1, CONSTRUCT
),
399 new BigInteger( [3], 1, CONSTRUCT
),
400 new BigInteger( [4], 1, CONSTRUCT
),
401 new BigInteger( [5], 1, CONSTRUCT
),
402 new BigInteger( [6], 1, CONSTRUCT
),
403 new BigInteger( [7], 1, CONSTRUCT
),
404 new BigInteger( [8], 1, CONSTRUCT
),
405 new BigInteger( [9], 1, CONSTRUCT
),
406 new BigInteger([10], 1, CONSTRUCT
),
407 new BigInteger([11], 1, CONSTRUCT
),
408 new BigInteger([12], 1, CONSTRUCT
),
409 new BigInteger([13], 1, CONSTRUCT
),
410 new BigInteger([14], 1, CONSTRUCT
),
411 new BigInteger([15], 1, CONSTRUCT
),
412 new BigInteger([16], 1, CONSTRUCT
),
413 new BigInteger([17], 1, CONSTRUCT
),
414 new BigInteger([18], 1, CONSTRUCT
),
415 new BigInteger([19], 1, CONSTRUCT
),
416 new BigInteger([20], 1, CONSTRUCT
),
417 new BigInteger([21], 1, CONSTRUCT
),
418 new BigInteger([22], 1, CONSTRUCT
),
419 new BigInteger([23], 1, CONSTRUCT
),
420 new BigInteger([24], 1, CONSTRUCT
),
421 new BigInteger([25], 1, CONSTRUCT
),
422 new BigInteger([26], 1, CONSTRUCT
),
423 new BigInteger([27], 1, CONSTRUCT
),
424 new BigInteger([28], 1, CONSTRUCT
),
425 new BigInteger([29], 1, CONSTRUCT
),
426 new BigInteger([30], 1, CONSTRUCT
),
427 new BigInteger([31], 1, CONSTRUCT
),
428 new BigInteger([32], 1, CONSTRUCT
),
429 new BigInteger([33], 1, CONSTRUCT
),
430 new BigInteger([34], 1, CONSTRUCT
),
431 new BigInteger([35], 1, CONSTRUCT
),
432 new BigInteger([36], 1, CONSTRUCT
)
435 // Used for parsing/radix conversion
436 BigInteger
.digits
= "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ".split("");
440 Convert a <BigInteger> to a string.
442 When *base* is greater than 10, letters are upper case.
446 base - Optional base to represent the number in (default is base 10).
447 Must be between 2 and 36 inclusive, or an Error will be thrown.
451 The string representation of the <BigInteger>.
453 BigInteger
.prototype.toString = function(base
) {
455 if (base
< 2 || base
> 36) {
456 throw new Error("illegal radix " + base
+ ".");
462 var str
= this._s
< 0 ? "-" : "";
463 str
+= this._d
[this._d
.length
- 1].toString();
464 for (var i
= this._d
.length
- 2; i
>= 0; i
--) {
465 var group
= this._d
[i
].toString();
466 while (group
.length
< BigInteger_base_log10
) group
= '0' + group
;
472 var numerals
= BigInteger
.digits
;
473 base
= BigInteger
.small
[base
];
481 var divmod
= n
.divRem(base
);
484 // TODO: This could be changed to unshift instead of reversing at the end.
485 // Benchmark both to compare speeds.
486 digits
.push(numerals
[digit
.valueOf()]);
488 return (sign
< 0 ? "-" : "") + digits
.reverse().join("");
492 // Verify strings for parsing
493 BigInteger
.radixRegex
= [
535 Parse a string into a <BigInteger>.
537 *base* is optional but, if provided, must be from 2 to 36 inclusive. If
538 *base* is not provided, it will be guessed based on the leading characters
541 - "0x" or "0X": *base* = 16
542 - "0c" or "0C": *base* = 8
543 - "0b" or "0B": *base* = 2
546 If no base is provided, or *base* is 10, the number can be in exponential
547 form. For example, these are all valid:
549 > BigInteger.parse("1e9"); // Same as "1000000000"
550 > BigInteger.parse("1.234*10^3"); // Same as 1234
551 > BigInteger.parse("56789 * 10 ** -2"); // Same as 567
553 If any characters fall outside the range defined by the radix, an exception
558 s - The string to parse.
559 base - Optional radix (default is to guess based on *s*).
563 a <BigInteger> instance.
565 BigInteger
.parse = function(s
, base
) {
566 // Expands a number in exponential form to decimal form.
567 // expandExponential("-13.441*10^5") === "1344100";
568 // expandExponential("1.12300e-1") === "0.112300";
569 // expandExponential(1000000000000000000000000000000) === "1000000000000000000000000000000";
570 function expandExponential(str
) {
571 str
= str
.replace(/\s*[*xX]\s*10\s*(\^|\*\*)\s*/, "e");
573 return str
.replace(/^([+\-])?(\d+)\.?(\d*)[eE]([+\-]?\d+)$/, function(x
, s
, n
, f
, c
) {
576 var i
= n
.length
+ c
;
577 x
= (l
? n : f
).length
;
578 c
= ((c
= Math
.abs(c
)) >= x
? c
- x
+ l : 0);
579 var z
= (new Array(c
+ 1)).join("0");
581 return (s
|| "") + (l
? r
= z
+ r : r
+= z
).substr(0, i
+= l
? z
.length : 0) + (i
< r
.length
? "." + r
.substr(i
) : "");
586 if (typeof base
=== "undefined" || +base
=== 10) {
587 s
= expandExponential(s
);
591 if (typeof base
=== "undefined") {
594 else if (base
== 16) {
597 else if (base
== 8) {
600 else if (base
== 2) {
606 var parts
= new RegExp('^([+\\-]?)(' + prefixRE
+ ')?([0-9a-z]*)(?:\\.\\d*)?$', 'i').exec(s
);
608 var sign
= parts
[1] || "+";
609 var baseSection
= parts
[2] || "";
610 var digits
= parts
[3] || "";
612 if (typeof base
=== "undefined") {
614 if (baseSection
=== "0x" || baseSection
=== "0X") { // Hex
617 else if (baseSection
=== "0c" || baseSection
=== "0C") { // Octal
620 else if (baseSection
=== "0b" || baseSection
=== "0B") { // Binary
627 else if (base
< 2 || base
> 36) {
628 throw new Error("Illegal radix " + base
+ ".");
633 // Check for digits outside the range
634 if (!(BigInteger
.radixRegex
[base
].test(digits
))) {
635 throw new Error("Bad digit for radix " + base
);
638 // Strip leading zeros, and convert to array
639 digits
= digits
.replace(/^0+/, "").split("");
640 if (digits
.length
=== 0) {
644 // Get the sign (we know it's not zero)
645 sign
= (sign
=== "-") ? -1 : 1;
650 while (digits
.length
>= BigInteger_base_log10
) {
651 d
.push(parseInt(digits
.splice(digits
.length
-BigInteger
.base_log10
, BigInteger
.base_log10
).join(''), 10));
653 d
.push(parseInt(digits
.join(''), 10));
654 return new BigInteger(d
, sign
, CONSTRUCT
);
659 base
= BigInteger
.small
[base
];
660 var small
= BigInteger
.small
;
661 for (var i
= 0; i
< digits
.length
; i
++) {
662 d
= d
.multiply(base
).add(small
[parseInt(digits
[i
], 36)]);
664 return new BigInteger(d
._d
, sign
, CONSTRUCT
);
667 throw new Error("Invalid BigInteger format: " + s
);
673 Add two <BigIntegers>.
677 n - The number to add to *this*. Will be converted to a <BigInteger>.
681 The numbers added together.
685 <subtract>, <multiply>, <quotient>, <next>
687 BigInteger
.prototype.add = function(n
) {
689 return BigInteger(n
);
696 if (this._s
!== n
._s
) {
698 return this.subtract(n
);
705 var sum
= new Array(Math
.max(al
, bl
) + 1);
706 var size
= Math
.min(al
, bl
);
710 for (var i
= 0; i
< size
; i
++) {
711 digit
= a
[i
] + b
[i
] + carry
;
712 sum
[i
] = digit
% BigInteger_base
;
713 carry
= (digit
/ BigInteger_base
) | 0;
719 for (i
= size
; carry
&& i
< al
; i
++) {
720 digit
= a
[i
] + carry
;
721 sum
[i
] = digit
% BigInteger_base
;
722 carry
= (digit
/ BigInteger_base
) | 0;
728 for ( ; i
< al
; i
++) {
732 return new BigInteger(sum
, this._s
, CONSTRUCT
);
737 Get the additive inverse of a <BigInteger>.
741 A <BigInteger> with the same magnatude, but with the opposite sign.
747 BigInteger
.prototype.negate = function() {
748 return new BigInteger(this._d
, (-this._s
) | 0, CONSTRUCT
);
753 Get the absolute value of a <BigInteger>.
757 A <BigInteger> with the same magnatude, but always positive (or zero).
763 BigInteger
.prototype.abs = function() {
764 return (this._s
< 0) ? this.negate() : this;
769 Subtract two <BigIntegers>.
773 n - The number to subtract from *this*. Will be converted to a <BigInteger>.
777 The *n* subtracted from *this*.
781 <add>, <multiply>, <quotient>, <prev>
783 BigInteger
.prototype.subtract = function(n
) {
785 return BigInteger(n
).negate();
792 if (this._s
!== n
._s
) {
798 // negative - negative => -|a| - -|b| => -|a| + |b| => |b| - |a|
800 m
= new BigInteger(n
._d
, 1, CONSTRUCT
);
801 n
= new BigInteger(this._d
, 1, CONSTRUCT
);
804 // Both are positive => a - b
805 var sign
= m
.compareAbs(n
);
821 var diff
= new Array(al
); // al >= bl since a > b
826 for (i
= 0; i
< bl
; i
++) {
827 digit
= a
[i
] - borrow
- b
[i
];
829 digit
+= BigInteger_base
;
837 for (i
= bl
; i
< al
; i
++) {
838 digit
= a
[i
] - borrow
;
840 digit
+= BigInteger_base
;
848 for ( ; i
< al
; i
++) {
852 return new BigInteger(diff
, sign
, CONSTRUCT
);
856 function addOne(n
, sign
) {
863 var digit
= (a
[i
] || 0) + 1;
864 sum
[i
] = digit
% BigInteger_base
;
865 if (digit
<= BigInteger_base
- 1) {
871 return new BigInteger(sum
, sign
, CONSTRUCT
);
874 function subtractOne(n
, sign
) {
881 var digit
= (a
[i
] || 0) - 1;
883 sum
[i
] = digit
+ BigInteger_base
;
892 return new BigInteger(sum
, sign
, CONSTRUCT
);
897 Get the next <BigInteger> (add one).
907 BigInteger
.prototype.next = function() {
912 return subtractOne(this, -1);
915 return addOne(this, 1);
921 Get the previous <BigInteger> (subtract one).
931 BigInteger
.prototype.prev = function() {
936 return addOne(this, -1);
939 return subtractOne(this, 1);
946 Compare the absolute value of two <BigIntegers>.
948 Calling <compareAbs> is faster than calling <abs> twice, then <compare>.
952 n - The number to compare to *this*. Will be converted to a <BigInteger>.
956 -1, 0, or +1 if *|this|* is less than, equal to, or greater than *|n|*.
962 BigInteger
.prototype.compareAbs = function(n
) {
967 if (!(n
instanceof BigInteger
)) {
969 return(isNaN(n
) ? n : -1);
975 return (n
._s
!== 0) ? -1 : 0;
981 var l
= this._d
.length
;
982 var nl
= n
._d
.length
;
992 for (var i
= l
-1; i
>= 0; i
--) {
994 return a
[i
] < b
[i
] ? -1 : 1;
1003 Compare two <BigIntegers>.
1007 n - The number to compare to *this*. Will be converted to a <BigInteger>.
1011 -1, 0, or +1 if *this* is less than, equal to, or greater than *n*.
1015 <compareAbs>, <isPositive>, <isNegative>, <isUnit>
1017 BigInteger
.prototype.compare = function(n
) {
1024 if (this._s
=== 0) {
1028 if (this._s
=== n
._s
) { // both positive or both negative
1029 var cmp
= this.compareAbs(n
);
1030 return cmp
* this._s
;
1039 Return true iff *this* is either 1 or -1.
1043 true if *this* compares equal to <BigInteger.ONE> or <BigInteger.M_ONE>.
1047 <isZero>, <isNegative>, <isPositive>, <compareAbs>, <compare>,
1048 <BigInteger.ONE>, <BigInteger.M_ONE>
1050 BigInteger
.prototype.isUnit = function() {
1051 return this === ONE
||
1053 (this._d
.length
=== 1 && this._d
[0] === 1);
1058 Multiply two <BigIntegers>.
1062 n - The number to multiply *this* by. Will be converted to a
1067 The numbers multiplied together.
1071 <add>, <subtract>, <quotient>, <square>
1073 BigInteger
.prototype.multiply = function(n
) {
1074 // TODO: Consider adding Karatsuba multiplication for large numbers
1075 if (this._s
=== 0) {
1083 if (this.isUnit()) {
1091 return this.negate();
1096 return this.square();
1099 var r
= (this._d
.length
>= n
._d
.length
);
1100 var a
= (r
? this : n
)._d
; // a will be longer than b
1101 var b
= (r
? n : this)._d
;
1106 var partial
= new Array(pl
);
1108 for (i
= 0; i
< pl
; i
++) {
1112 for (i
= 0; i
< bl
; i
++) {
1115 var jlimit
= al
+ i
;
1117 for (var j
= i
; j
< jlimit
; j
++) {
1118 digit
= partial
[j
] + bi
* a
[j
- i
] + carry
;
1119 carry
= (digit
/ BigInteger_base
) | 0;
1120 partial
[j
] = (digit
% BigInteger_base
) | 0;
1123 digit
= partial
[j
] + carry
;
1124 carry
= (digit
/ BigInteger_base
) | 0;
1125 partial
[j
] = digit
% BigInteger_base
;
1128 return new BigInteger(partial
, this._s
* n
._s
, CONSTRUCT
);
1131 // Multiply a BigInteger by a single-digit native number
1132 // Assumes that this and n are >= 0
1133 // This is not really intended to be used outside the library itself
1134 BigInteger
.prototype.multiplySingleDigit = function(n
) {
1135 if (n
=== 0 || this._s
=== 0) {
1143 if (this._d
.length
=== 1) {
1144 digit
= this._d
[0] * n
;
1145 if (digit
>= BigInteger_base
) {
1146 return new BigInteger([(digit
% BigInteger_base
)|0,
1147 (digit
/ BigInteger_base
)|0], 1, CONSTRUCT
);
1149 return new BigInteger([digit
], 1, CONSTRUCT
);
1153 return this.add(this);
1155 if (this.isUnit()) {
1156 return new BigInteger([n
], 1, CONSTRUCT
);
1163 var partial
= new Array(pl
);
1164 for (var i
= 0; i
< pl
; i
++) {
1169 for (var j
= 0; j
< al
; j
++) {
1170 digit
= n
* a
[j
] + carry
;
1171 carry
= (digit
/ BigInteger_base
) | 0;
1172 partial
[j
] = (digit
% BigInteger_base
) | 0;
1178 return new BigInteger(partial
, 1, CONSTRUCT
);
1183 Multiply a <BigInteger> by itself.
1185 This is slightly faster than regular multiplication, since it removes the
1186 duplicated multiplcations.
1190 > this.multiply(this)
1195 BigInteger
.prototype.square = function() {
1196 // Normally, squaring a 10-digit number would take 100 multiplications.
1197 // Of these 10 are unique diagonals, of the remaining 90 (100-10), 45 are repeated.
1198 // This procedure saves (N*(N-1))/2 multiplications, (e.g., 45 of 100 multiplies).
1199 // Based on code by Gary Darby, Intellitech Systems Inc., www.DelphiForFun.org
1201 if (this._s
=== 0) {
1204 if (this.isUnit()) {
1208 var digits
= this._d
;
1209 var length
= digits
.length
;
1210 var imult1
= new Array(length
+ length
+ 1);
1211 var product
, carry
, k
;
1214 // Calculate diagonal
1215 for (i
= 0; i
< length
; i
++) {
1217 product
= digits
[i
] * digits
[i
];
1218 carry
= (product
/ BigInteger_base
) | 0;
1219 imult1
[k
] = product
% BigInteger_base
;
1220 imult1
[k
+ 1] = carry
;
1223 // Calculate repeating part
1224 for (i
= 0; i
< length
; i
++) {
1227 for (var j
= i
+ 1; j
< length
; j
++, k
++) {
1228 product
= digits
[j
] * digits
[i
] * 2 + imult1
[k
] + carry
;
1229 carry
= (product
/ BigInteger_base
) | 0;
1230 imult1
[k
] = product
% BigInteger_base
;
1233 var digit
= carry
+ imult1
[k
];
1234 carry
= (digit
/ BigInteger_base
) | 0;
1235 imult1
[k
] = digit
% BigInteger_base
;
1236 imult1
[k
+ 1] += carry
;
1239 return new BigInteger(imult1
, 1, CONSTRUCT
);
1244 Divide two <BigIntegers> and truncate towards zero.
1246 <quotient> throws an exception if *n* is zero.
1250 n - The number to divide *this* by. Will be converted to a <BigInteger>.
1254 The *this* / *n*, truncated to an integer.
1258 <add>, <subtract>, <multiply>, <divRem>, <remainder>
1260 BigInteger
.prototype.quotient = function(n
) {
1261 return this.divRem(n
)[0];
1266 Deprecated synonym for <quotient>.
1268 BigInteger
.prototype.divide
= BigInteger
.prototype.quotient
;
1272 Calculate the remainder of two <BigIntegers>.
1274 <remainder> throws an exception if *n* is zero.
1278 n - The remainder after *this* is divided *this* by *n*. Will be
1279 converted to a <BigInteger>.
1287 <divRem>, <quotient>
1289 BigInteger
.prototype.remainder = function(n
) {
1290 return this.divRem(n
)[1];
1295 Calculate the integer quotient and remainder of two <BigIntegers>.
1297 <divRem> throws an exception if *n* is zero.
1301 n - The number to divide *this* by. Will be converted to a <BigInteger>.
1305 A two-element array containing the quotient and the remainder.
1309 is exactly equivalent to
1311 > [a.quotient(b), a.remainder(b)]
1313 except it is faster, because they are calculated at the same time.
1317 <quotient>, <remainder>
1319 BigInteger
.prototype.divRem = function(n
) {
1322 throw new Error("Divide by zero");
1324 if (this._s
=== 0) {
1325 return [ZERO
, ZERO
];
1327 if (n
._d
.length
=== 1) {
1328 return this.divRemSmall(n
._s
* n
._d
[0]);
1331 // Test for easy cases -- |n1| <= |n2|
1332 switch (this.compareAbs(n
)) {
1334 return [this._s
=== n
._s
? ONE : M_ONE
, ZERO
];
1335 case -1: // |n1| < |n2|
1336 return [ZERO
, this];
1339 var sign
= this._s
* n
._s
;
1341 var b_digits
= this._d
;
1342 var b_index
= b_digits
.length
;
1343 var digits
= n
._d
.length
;
1347 var part
= new BigInteger([], 0, CONSTRUCT
);
1350 part
._d
.unshift(b_digits
[--b_index
]);
1351 part
= new BigInteger(part
._d
, 1, CONSTRUCT
);
1353 if (part
.compareAbs(n
) < 0) {
1357 if (part
._s
=== 0) {
1361 var xlen
= part
._d
.length
, ylen
= a
._d
.length
;
1362 var highx
= part
._d
[xlen
-1]*BigInteger_base
+ part
._d
[xlen
-2];
1363 var highy
= a
._d
[ylen
-1]*BigInteger_base
+ a
._d
[ylen
-2];
1364 if (part
._d
.length
> a
._d
.length
) {
1365 // The length of part._d can either match a._d length,
1366 // or exceed it by one.
1367 highx
= (highx
+1)*BigInteger_base
;
1369 guess
= Math
.ceil(highx
/highy
);
1372 var check
= a
.multiplySingleDigit(guess
);
1373 if (check
.compareAbs(part
) <= 0) {
1383 var diff
= part
.subtract(check
);
1384 part
._d
= diff
._d
.slice();
1387 return [new BigInteger(quot
.reverse(), sign
, CONSTRUCT
),
1388 new BigInteger(part
._d
, this._s
, CONSTRUCT
)];
1391 // Throws an exception if n is outside of (-BigInteger.base, -1] or
1392 // [1, BigInteger.base). It's not necessary to call this, since the
1393 // other division functions will call it if they are able to.
1394 BigInteger
.prototype.divRemSmall = function(n
) {
1398 throw new Error("Divide by zero");
1401 var n_s
= n
< 0 ? -1 : 1;
1402 var sign
= this._s
* n_s
;
1405 if (n
< 1 || n
>= BigInteger_base
) {
1406 throw new Error("Argument out of range");
1409 if (this._s
=== 0) {
1410 return [ZERO
, ZERO
];
1413 if (n
=== 1 || n
=== -1) {
1414 return [(sign
=== 1) ? this.abs() : new BigInteger(this._d
, sign
, CONSTRUCT
), ZERO
];
1417 // 2 <= n < BigInteger_base
1419 // divide a single digit by a single digit
1420 if (this._d
.length
=== 1) {
1421 var q
= new BigInteger([(this._d
[0] / n
) | 0], 1, CONSTRUCT
);
1422 r
= new BigInteger([(this._d
[0] % n
) | 0], 1, CONSTRUCT
);
1432 var digits
= this._d
.slice();
1433 var quot
= new Array(digits
.length
);
1439 while (digits
.length
) {
1440 part
= part
* BigInteger_base
+ digits
[digits
.length
- 1];
1444 diff
= BigInteger_base
* diff
+ part
;
1451 guess
= (part
/ n
) | 0;
1454 var check
= n
* guess
;
1455 diff
= part
- check
;
1466 r
= new BigInteger([diff
], 1, CONSTRUCT
);
1470 return [new BigInteger(quot
.reverse(), sign
, CONSTRUCT
), r
];
1475 Return true iff *this* is divisible by two.
1477 Note that <BigInteger.ZERO> is even.
1481 true if *this* is even, false otherwise.
1487 BigInteger
.prototype.isEven = function() {
1488 var digits
= this._d
;
1489 return this._s
=== 0 || digits
.length
=== 0 || (digits
[0] % 2) === 0;
1494 Return true iff *this* is not divisible by two.
1498 true if *this* is odd, false otherwise.
1504 BigInteger
.prototype.isOdd = function() {
1505 return !this.isEven();
1510 Get the sign of a <BigInteger>.
1520 <isZero>, <isPositive>, <isNegative>, <compare>, <BigInteger.ZERO>
1522 BigInteger
.prototype.sign = function() {
1527 Function: isPositive
1528 Return true iff *this* > 0.
1532 true if *this*.compare(<BigInteger.ZERO>) == 1.
1536 <sign>, <isZero>, <isNegative>, <isUnit>, <compare>, <BigInteger.ZERO>
1538 BigInteger
.prototype.isPositive = function() {
1543 Function: isNegative
1544 Return true iff *this* < 0.
1548 true if *this*.compare(<BigInteger.ZERO>) == -1.
1552 <sign>, <isPositive>, <isZero>, <isUnit>, <compare>, <BigInteger.ZERO>
1554 BigInteger
.prototype.isNegative = function() {
1560 Return true iff *this* == 0.
1564 true if *this*.compare(<BigInteger.ZERO>) == 0.
1568 <sign>, <isPositive>, <isNegative>, <isUnit>, <BigInteger.ZERO>
1570 BigInteger
.prototype.isZero = function() {
1571 return this._s
=== 0;
1576 Multiply a <BigInteger> by a power of 10.
1578 This is equivalent to, but faster than
1581 > return this.multiply(BigInteger("1e" + n));
1584 > return this.quotient(BigInteger("1e" + -n));
1589 n - The power of 10 to multiply *this* by. *n* is converted to a
1590 javascipt number and must be no greater than <BigInteger.MAX_EXP>
1591 (0x7FFFFFFF), or an exception will be thrown.
1595 *this* * (10 ** *n*), truncated to an integer if necessary.
1601 BigInteger
.prototype.exp10 = function(n
) {
1606 if (Math
.abs(n
) > Number(MAX_EXP
)) {
1607 throw new Error("exponent too large in BigInteger.exp10");
1609 // Optimization for this == 0. This also keeps us from having to trim zeros in the positive n case
1610 if (this._s
=== 0) {
1614 var k
= new BigInteger(this._d
.slice(), this._s
, CONSTRUCT
);
1616 for (; n
>= BigInteger_base_log10
; n
-= BigInteger_base_log10
) {
1622 k
= k
.multiplySingleDigit(Math
.pow(10, n
));
1623 return (this._s
< 0 ? k
.negate() : k
);
1624 } else if (-n
>= this._d
.length
*BigInteger_base_log10
) {
1627 var k
= new BigInteger(this._d
.slice(), this._s
, CONSTRUCT
);
1629 for (n
= -n
; n
>= BigInteger_base_log10
; n
-= BigInteger_base_log10
) {
1632 return (n
== 0) ? k : k
.divRemSmall(Math
.pow(10, n
))[0];
1638 Raise a <BigInteger> to a power.
1640 In this implementation, 0**0 is 1.
1644 n - The exponent to raise *this* by. *n* must be no greater than
1645 <BigInteger.MAX_EXP> (0x7FFFFFFF), or an exception will be thrown.
1649 *this* raised to the *nth* power.
1655 BigInteger
.prototype.pow = function(n
) {
1656 if (this.isUnit()) {
1661 return BigInteger(n
).isOdd() ? this : this.negate();
1669 else if (n
._s
< 0) {
1670 if (this._s
=== 0) {
1671 throw new Error("Divide by zero");
1677 if (this._s
=== 0) {
1684 if (n
.compareAbs(MAX_EXP
) > 0) {
1685 throw new Error("exponent too large in BigInteger.pow");
1689 var two
= BigInteger
.small
[2];
1691 while (n
.isPositive()) {
1693 aux
= aux
.multiply(x
);
1699 n
= n
.quotient(two
);
1707 Raise a <BigInteger> to a power (mod m).
1709 Because it is reduced by a modulus, <modPow> is not limited by
1710 <BigInteger.MAX_EXP> like <pow>.
1714 exponent - The exponent to raise *this* by. Must be positive.
1715 modulus - The modulus.
1719 *this* ^ *exponent* (mod *modulus*).
1725 BigInteger
.prototype.modPow = function(exponent
, modulus
) {
1729 while (exponent
.isPositive()) {
1730 if (exponent
.isOdd()) {
1731 result
= result
.multiply(base
).remainder(modulus
);
1734 exponent
= exponent
.quotient(BigInteger
.small
[2]);
1735 if (exponent
.isPositive()) {
1736 base
= base
.square().remainder(modulus
);
1745 Get the natural logarithm of a <BigInteger> as a native JavaScript number.
1747 This is equivalent to
1749 > Math.log(this.toJSValue())
1751 but handles values outside of the native number range.
1761 BigInteger
.prototype.log = function() {
1763 case 0: return -Infinity
;
1764 case -1: return NaN
;
1765 default: // Fall through.
1768 var l
= this._d
.length
;
1770 if (l
*BigInteger_base_log10
< 30) {
1771 return Math
.log(this.valueOf());
1774 var N
= Math
.ceil(30/BigInteger_base_log10
);
1775 var firstNdigits
= this._d
.slice(l
- N
);
1776 return Math
.log((new BigInteger(firstNdigits
, 1, CONSTRUCT
)).valueOf()) + (l
- N
) * Math
.log(BigInteger_base
);
1781 Convert a <BigInteger> to a native JavaScript integer.
1783 This is called automatically by JavaScipt to convert a <BigInteger> to a
1788 > parseInt(this.toString(), 10)
1792 <toString>, <toJSValue>
1794 BigInteger
.prototype.valueOf = function() {
1795 return parseInt(this.toString(), 10);
1800 Convert a <BigInteger> to a native JavaScript integer.
1802 This is the same as valueOf, but more explicitly named.
1806 > parseInt(this.toString(), 10)
1810 <toString>, <valueOf>
1812 BigInteger
.prototype.toJSValue = function() {
1813 return parseInt(this.toString(), 10);
1816 var MAX_EXP
= BigInteger(0x7FFFFFFF);
1817 // Constant: MAX_EXP
1818 // The largest exponent allowed in <pow> and <exp10> (0x7FFFFFFF or 2147483647).
1819 BigInteger
.MAX_EXP
= MAX_EXP
;
1822 function makeUnary(fn
) {
1823 return function(a
) {
1824 return fn
.call(BigInteger(a
));
1828 function makeBinary(fn
) {
1829 return function(a
, b
) {
1830 return fn
.call(BigInteger(a
), BigInteger(b
));
1834 function makeTrinary(fn
) {
1835 return function(a
, b
, c
) {
1836 return fn
.call(BigInteger(a
), BigInteger(b
), BigInteger(c
));
1842 var unary
= "toJSValue,isEven,isOdd,sign,isZero,isNegative,abs,isUnit,square,negate,isPositive,toString,next,prev,log".split(",");
1843 var binary
= "compare,remainder,divRem,subtract,add,quotient,divide,multiply,pow,compareAbs".split(",");
1844 var trinary
= ["modPow"];
1846 for (i
= 0; i
< unary
.length
; i
++) {
1848 BigInteger
[fn
] = makeUnary(BigInteger
.prototype[fn
]);
1851 for (i
= 0; i
< binary
.length
; i
++) {
1853 BigInteger
[fn
] = makeBinary(BigInteger
.prototype[fn
]);
1856 for (i
= 0; i
< trinary
.length
; i
++) {
1858 BigInteger
[fn
] = makeTrinary(BigInteger
.prototype[fn
]);
1861 BigInteger
.exp10 = function(x
, n
) {
1862 return BigInteger(x
).exp10(n
);
1867 exports
.BigInteger
= BigInteger
;
1868 })(typeof exports
!== 'undefined' ? exports : this);