]>
git.immae.eu Git - perso/Immae/Projets/Cryptomonnaies/BIP39.git/blob - src/js/biginteger.js
2 JavaScript BigInteger library version 0.9.1
3 http://silentmatt.com/biginteger/
5 Copyright (c) 2009 Matthew Crumley <email@matthewcrumley.com>
6 Copyright (c) 2010,2011 by John Tobey <John.Tobey@gmail.com>
7 Licensed under the MIT license.
9 Support for arbitrary internal representation base was added by
24 An arbitrarily-large integer.
26 <BigInteger> objects should be considered immutable. None of the "built-in"
27 methods modify *this* or their arguments. All properties should be
30 All the methods of <BigInteger> instances can be called "statically". The
31 static versions are convenient if you don't already have a <BigInteger>
34 As an example, these calls are equivalent.
36 > BigInteger(4).multiply(5); // returns BigInteger(20);
37 > BigInteger.multiply(4, 5); // returns BigInteger(20);
40 > var a = BigInteger.toJSValue("0b101010"); // Not completely useless...
43 var CONSTRUCT
= {}; // Unique token to call "private" version of constructor
46 Constructor: BigInteger()
47 Convert a value to a <BigInteger>.
49 Although <BigInteger()> is the constructor for <BigInteger> objects, it is
50 best not to call it as a constructor. If *n* is a <BigInteger> object, it is
51 simply returned as-is. Otherwise, <BigInteger()> is equivalent to <parse>
52 without a radix argument.
54 > var n0 = BigInteger(); // Same as <BigInteger.ZERO>
55 > var n1 = BigInteger("123"); // Create a new <BigInteger> with value 123
56 > var n2 = BigInteger(123); // Create a new <BigInteger> with value 123
57 > var n3 = BigInteger(n2); // Return n2, unchanged
59 The constructor form only takes an array and a sign. *n* must be an
60 array of numbers in little-endian order, where each digit is between 0
61 and BigInteger.base. The second parameter sets the sign: -1 for
62 negative, +1 for positive, or 0 for zero. The array is *not copied and
63 may be modified*. If the array contains only zeros, the sign parameter
64 is ignored and is forced to zero.
66 > new BigInteger([5], -1): create a new BigInteger with value -5
70 n - Value to convert to a <BigInteger>.
80 function BigInteger(n
, s
, token
) {
81 if (token
!== CONSTRUCT
) {
82 if (n
instanceof BigInteger
) {
85 else if (typeof n
=== "undefined") {
88 return BigInteger
.parse(n
);
91 n
= n
|| []; // Provide the nullary constructor for subclasses.
92 while (n
.length
&& !n
[n
.length
- 1]) {
96 this._s
= n
.length
? (s
|| 1) : 0;
99 BigInteger
._construct = function(n
, s
) {
100 return new BigInteger(n
, s
, CONSTRUCT
);
103 // Base-10 speedup hacks in parse, toString, exp10 and log functions
104 // require base to be a power of 10. 10^7 is the largest such power
105 // that won't cause a precision loss when digits are multiplied.
106 var BigInteger_base
= 10000000;
107 var BigInteger_base_log10
= 7;
109 BigInteger
.base
= BigInteger_base
;
110 BigInteger
.base_log10
= BigInteger_base_log10
;
112 var ZERO
= new BigInteger([], 0, CONSTRUCT
);
115 BigInteger
.ZERO
= ZERO
;
117 var ONE
= new BigInteger([1], 1, CONSTRUCT
);
120 BigInteger
.ONE
= ONE
;
122 var M_ONE
= new BigInteger(ONE
._d
, -1, CONSTRUCT
);
125 BigInteger
.M_ONE
= M_ONE
;
128 // Shortcut for <ZERO>.
129 BigInteger
._0
= ZERO
;
132 // Shortcut for <ONE>.
137 Array of <BigIntegers> from 0 to 36.
139 These are used internally for parsing, but useful when you need a "small"
144 <ZERO>, <ONE>, <_0>, <_1>
149 /* Assuming BigInteger_base > 36 */
150 new BigInteger( [2], 1, CONSTRUCT
),
151 new BigInteger( [3], 1, CONSTRUCT
),
152 new BigInteger( [4], 1, CONSTRUCT
),
153 new BigInteger( [5], 1, CONSTRUCT
),
154 new BigInteger( [6], 1, CONSTRUCT
),
155 new BigInteger( [7], 1, CONSTRUCT
),
156 new BigInteger( [8], 1, CONSTRUCT
),
157 new BigInteger( [9], 1, CONSTRUCT
),
158 new BigInteger([10], 1, CONSTRUCT
),
159 new BigInteger([11], 1, CONSTRUCT
),
160 new BigInteger([12], 1, CONSTRUCT
),
161 new BigInteger([13], 1, CONSTRUCT
),
162 new BigInteger([14], 1, CONSTRUCT
),
163 new BigInteger([15], 1, CONSTRUCT
),
164 new BigInteger([16], 1, CONSTRUCT
),
165 new BigInteger([17], 1, CONSTRUCT
),
166 new BigInteger([18], 1, CONSTRUCT
),
167 new BigInteger([19], 1, CONSTRUCT
),
168 new BigInteger([20], 1, CONSTRUCT
),
169 new BigInteger([21], 1, CONSTRUCT
),
170 new BigInteger([22], 1, CONSTRUCT
),
171 new BigInteger([23], 1, CONSTRUCT
),
172 new BigInteger([24], 1, CONSTRUCT
),
173 new BigInteger([25], 1, CONSTRUCT
),
174 new BigInteger([26], 1, CONSTRUCT
),
175 new BigInteger([27], 1, CONSTRUCT
),
176 new BigInteger([28], 1, CONSTRUCT
),
177 new BigInteger([29], 1, CONSTRUCT
),
178 new BigInteger([30], 1, CONSTRUCT
),
179 new BigInteger([31], 1, CONSTRUCT
),
180 new BigInteger([32], 1, CONSTRUCT
),
181 new BigInteger([33], 1, CONSTRUCT
),
182 new BigInteger([34], 1, CONSTRUCT
),
183 new BigInteger([35], 1, CONSTRUCT
),
184 new BigInteger([36], 1, CONSTRUCT
)
187 // Used for parsing/radix conversion
188 BigInteger
.digits
= "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ".split("");
192 Convert a <BigInteger> to a string.
194 When *base* is greater than 10, letters are upper case.
198 base - Optional base to represent the number in (default is base 10).
199 Must be between 2 and 36 inclusive, or an Error will be thrown.
203 The string representation of the <BigInteger>.
205 BigInteger
.prototype.toString = function(base
) {
207 if (base
< 2 || base
> 36) {
208 throw new Error("illegal radix " + base
+ ".");
214 var str
= this._s
< 0 ? "-" : "";
215 str
+= this._d
[this._d
.length
- 1].toString();
216 for (var i
= this._d
.length
- 2; i
>= 0; i
--) {
217 var group
= this._d
[i
].toString();
218 while (group
.length
< BigInteger_base_log10
) group
= '0' + group
;
224 var numerals
= BigInteger
.digits
;
225 base
= BigInteger
.small
[base
];
233 var divmod
= n
.divRem(base
);
236 // TODO: This could be changed to unshift instead of reversing at the end.
237 // Benchmark both to compare speeds.
238 digits
.push(numerals
[digit
.valueOf()]);
240 return (sign
< 0 ? "-" : "") + digits
.reverse().join("");
244 // Verify strings for parsing
245 BigInteger
.radixRegex
= [
287 Parse a string into a <BigInteger>.
289 *base* is optional but, if provided, must be from 2 to 36 inclusive. If
290 *base* is not provided, it will be guessed based on the leading characters
293 - "0x" or "0X": *base* = 16
294 - "0c" or "0C": *base* = 8
295 - "0b" or "0B": *base* = 2
298 If no base is provided, or *base* is 10, the number can be in exponential
299 form. For example, these are all valid:
301 > BigInteger.parse("1e9"); // Same as "1000000000"
302 > BigInteger.parse("1.234*10^3"); // Same as 1234
303 > BigInteger.parse("56789 * 10 ** -2"); // Same as 567
305 If any characters fall outside the range defined by the radix, an exception
310 s - The string to parse.
311 base - Optional radix (default is to guess based on *s*).
315 a <BigInteger> instance.
317 BigInteger
.parse = function(s
, base
) {
318 // Expands a number in exponential form to decimal form.
319 // expandExponential("-13.441*10^5") === "1344100";
320 // expandExponential("1.12300e-1") === "0.112300";
321 // expandExponential(1000000000000000000000000000000) === "1000000000000000000000000000000";
322 function expandExponential(str
) {
323 str
= str
.replace(/\s*[*xX]\s*10\s*(\^|\*\*)\s*/, "e");
325 return str
.replace(/^([+\-])?(\d+)\.?(\d*)[eE]([+\-]?\d+)$/, function(x
, s
, n
, f
, c
) {
328 var i
= n
.length
+ c
;
329 x
= (l
? n : f
).length
;
330 c
= ((c
= Math
.abs(c
)) >= x
? c
- x
+ l : 0);
331 var z
= (new Array(c
+ 1)).join("0");
333 return (s
|| "") + (l
? r
= z
+ r : r
+= z
).substr(0, i
+= l
? z
.length : 0) + (i
< r
.length
? "." + r
.substr(i
) : "");
338 if (typeof base
=== "undefined" || +base
=== 10) {
339 s
= expandExponential(s
);
343 if (typeof base
=== "undefined") {
346 else if (base
== 16) {
349 else if (base
== 8) {
352 else if (base
== 2) {
358 var parts
= new RegExp('^([+\\-]?)(' + prefixRE
+ ')?([0-9a-z]*)(?:\\.\\d*)?$', 'i').exec(s
);
360 var sign
= parts
[1] || "+";
361 var baseSection
= parts
[2] || "";
362 var digits
= parts
[3] || "";
364 if (typeof base
=== "undefined") {
366 if (baseSection
=== "0x" || baseSection
=== "0X") { // Hex
369 else if (baseSection
=== "0c" || baseSection
=== "0C") { // Octal
372 else if (baseSection
=== "0b" || baseSection
=== "0B") { // Binary
379 else if (base
< 2 || base
> 36) {
380 throw new Error("Illegal radix " + base
+ ".");
385 // Check for digits outside the range
386 if (!(BigInteger
.radixRegex
[base
].test(digits
))) {
387 throw new Error("Bad digit for radix " + base
);
390 // Strip leading zeros, and convert to array
391 digits
= digits
.replace(/^0+/, "").split("");
392 if (digits
.length
=== 0) {
396 // Get the sign (we know it's not zero)
397 sign
= (sign
=== "-") ? -1 : 1;
402 while (digits
.length
>= BigInteger_base_log10
) {
403 d
.push(parseInt(digits
.splice(digits
.length
-BigInteger
.base_log10
, BigInteger
.base_log10
).join(''), 10));
405 d
.push(parseInt(digits
.join(''), 10));
406 return new BigInteger(d
, sign
, CONSTRUCT
);
411 base
= BigInteger
.small
[base
];
412 var small
= BigInteger
.small
;
413 for (var i
= 0; i
< digits
.length
; i
++) {
414 d
= d
.multiply(base
).add(small
[parseInt(digits
[i
], 36)]);
416 return new BigInteger(d
._d
, sign
, CONSTRUCT
);
419 throw new Error("Invalid BigInteger format: " + s
);
425 Add two <BigIntegers>.
429 n - The number to add to *this*. Will be converted to a <BigInteger>.
433 The numbers added together.
437 <subtract>, <multiply>, <quotient>, <next>
439 BigInteger
.prototype.add = function(n
) {
441 return BigInteger(n
);
448 if (this._s
!== n
._s
) {
450 return this.subtract(n
);
457 var sum
= new Array(Math
.max(al
, bl
) + 1);
458 var size
= Math
.min(al
, bl
);
462 for (var i
= 0; i
< size
; i
++) {
463 digit
= a
[i
] + b
[i
] + carry
;
464 sum
[i
] = digit
% BigInteger_base
;
465 carry
= (digit
/ BigInteger_base
) | 0;
471 for (i
= size
; carry
&& i
< al
; i
++) {
472 digit
= a
[i
] + carry
;
473 sum
[i
] = digit
% BigInteger_base
;
474 carry
= (digit
/ BigInteger_base
) | 0;
480 for ( ; i
< al
; i
++) {
484 return new BigInteger(sum
, this._s
, CONSTRUCT
);
489 Get the additive inverse of a <BigInteger>.
493 A <BigInteger> with the same magnatude, but with the opposite sign.
499 BigInteger
.prototype.negate = function() {
500 return new BigInteger(this._d
, (-this._s
) | 0, CONSTRUCT
);
505 Get the absolute value of a <BigInteger>.
509 A <BigInteger> with the same magnatude, but always positive (or zero).
515 BigInteger
.prototype.abs = function() {
516 return (this._s
< 0) ? this.negate() : this;
521 Subtract two <BigIntegers>.
525 n - The number to subtract from *this*. Will be converted to a <BigInteger>.
529 The *n* subtracted from *this*.
533 <add>, <multiply>, <quotient>, <prev>
535 BigInteger
.prototype.subtract = function(n
) {
537 return BigInteger(n
).negate();
544 if (this._s
!== n
._s
) {
550 // negative - negative => -|a| - -|b| => -|a| + |b| => |b| - |a|
552 m
= new BigInteger(n
._d
, 1, CONSTRUCT
);
553 n
= new BigInteger(this._d
, 1, CONSTRUCT
);
556 // Both are positive => a - b
557 var sign
= m
.compareAbs(n
);
573 var diff
= new Array(al
); // al >= bl since a > b
578 for (i
= 0; i
< bl
; i
++) {
579 digit
= a
[i
] - borrow
- b
[i
];
581 digit
+= BigInteger_base
;
589 for (i
= bl
; i
< al
; i
++) {
590 digit
= a
[i
] - borrow
;
592 digit
+= BigInteger_base
;
600 for ( ; i
< al
; i
++) {
604 return new BigInteger(diff
, sign
, CONSTRUCT
);
608 function addOne(n
, sign
) {
615 var digit
= (a
[i
] || 0) + 1;
616 sum
[i
] = digit
% BigInteger_base
;
617 if (digit
<= BigInteger_base
- 1) {
623 return new BigInteger(sum
, sign
, CONSTRUCT
);
626 function subtractOne(n
, sign
) {
633 var digit
= (a
[i
] || 0) - 1;
635 sum
[i
] = digit
+ BigInteger_base
;
644 return new BigInteger(sum
, sign
, CONSTRUCT
);
649 Get the next <BigInteger> (add one).
659 BigInteger
.prototype.next = function() {
664 return subtractOne(this, -1);
667 return addOne(this, 1);
673 Get the previous <BigInteger> (subtract one).
683 BigInteger
.prototype.prev = function() {
688 return addOne(this, -1);
691 return subtractOne(this, 1);
698 Compare the absolute value of two <BigIntegers>.
700 Calling <compareAbs> is faster than calling <abs> twice, then <compare>.
704 n - The number to compare to *this*. Will be converted to a <BigInteger>.
708 -1, 0, or +1 if *|this|* is less than, equal to, or greater than *|n|*.
714 BigInteger
.prototype.compareAbs = function(n
) {
719 if (!(n
instanceof BigInteger
)) {
721 return(isNaN(n
) ? n : -1);
727 return (n
._s
!== 0) ? -1 : 0;
733 var l
= this._d
.length
;
734 var nl
= n
._d
.length
;
744 for (var i
= l
-1; i
>= 0; i
--) {
746 return a
[i
] < b
[i
] ? -1 : 1;
755 Compare two <BigIntegers>.
759 n - The number to compare to *this*. Will be converted to a <BigInteger>.
763 -1, 0, or +1 if *this* is less than, equal to, or greater than *n*.
767 <compareAbs>, <isPositive>, <isNegative>, <isUnit>
769 BigInteger
.prototype.compare = function(n
) {
780 if (this._s
=== n
._s
) { // both positive or both negative
781 var cmp
= this.compareAbs(n
);
782 return cmp
* this._s
;
791 Return true iff *this* is either 1 or -1.
795 true if *this* compares equal to <BigInteger.ONE> or <BigInteger.M_ONE>.
799 <isZero>, <isNegative>, <isPositive>, <compareAbs>, <compare>,
800 <BigInteger.ONE>, <BigInteger.M_ONE>
802 BigInteger
.prototype.isUnit = function() {
803 return this === ONE
||
805 (this._d
.length
=== 1 && this._d
[0] === 1);
810 Multiply two <BigIntegers>.
814 n - The number to multiply *this* by. Will be converted to a
819 The numbers multiplied together.
823 <add>, <subtract>, <quotient>, <square>
825 BigInteger
.prototype.multiply = function(n
) {
826 // TODO: Consider adding Karatsuba multiplication for large numbers
843 return this.negate();
848 return this.square();
851 var r
= (this._d
.length
>= n
._d
.length
);
852 var a
= (r
? this : n
)._d
; // a will be longer than b
853 var b
= (r
? n : this)._d
;
858 var partial
= new Array(pl
);
860 for (i
= 0; i
< pl
; i
++) {
864 for (i
= 0; i
< bl
; i
++) {
869 for (var j
= i
; j
< jlimit
; j
++) {
870 digit
= partial
[j
] + bi
* a
[j
- i
] + carry
;
871 carry
= (digit
/ BigInteger_base
) | 0;
872 partial
[j
] = (digit
% BigInteger_base
) | 0;
875 digit
= partial
[j
] + carry
;
876 carry
= (digit
/ BigInteger_base
) | 0;
877 partial
[j
] = digit
% BigInteger_base
;
880 return new BigInteger(partial
, this._s
* n
._s
, CONSTRUCT
);
883 // Multiply a BigInteger by a single-digit native number
884 // Assumes that this and n are >= 0
885 // This is not really intended to be used outside the library itself
886 BigInteger
.prototype.multiplySingleDigit = function(n
) {
887 if (n
=== 0 || this._s
=== 0) {
895 if (this._d
.length
=== 1) {
896 digit
= this._d
[0] * n
;
897 if (digit
>= BigInteger_base
) {
898 return new BigInteger([(digit
% BigInteger_base
)|0,
899 (digit
/ BigInteger_base
)|0], 1, CONSTRUCT
);
901 return new BigInteger([digit
], 1, CONSTRUCT
);
905 return this.add(this);
908 return new BigInteger([n
], 1, CONSTRUCT
);
915 var partial
= new Array(pl
);
916 for (var i
= 0; i
< pl
; i
++) {
921 for (var j
= 0; j
< al
; j
++) {
922 digit
= n
* a
[j
] + carry
;
923 carry
= (digit
/ BigInteger_base
) | 0;
924 partial
[j
] = (digit
% BigInteger_base
) | 0;
930 return new BigInteger(partial
, 1, CONSTRUCT
);
935 Multiply a <BigInteger> by itself.
937 This is slightly faster than regular multiplication, since it removes the
938 duplicated multiplcations.
942 > this.multiply(this)
947 BigInteger
.prototype.square = function() {
948 // Normally, squaring a 10-digit number would take 100 multiplications.
949 // Of these 10 are unique diagonals, of the remaining 90 (100-10), 45 are repeated.
950 // This procedure saves (N*(N-1))/2 multiplications, (e.g., 45 of 100 multiplies).
951 // Based on code by Gary Darby, Intellitech Systems Inc., www.DelphiForFun.org
960 var digits
= this._d
;
961 var length
= digits
.length
;
962 var imult1
= new Array(length
+ length
+ 1);
963 var product
, carry
, k
;
966 // Calculate diagonal
967 for (i
= 0; i
< length
; i
++) {
969 product
= digits
[i
] * digits
[i
];
970 carry
= (product
/ BigInteger_base
) | 0;
971 imult1
[k
] = product
% BigInteger_base
;
972 imult1
[k
+ 1] = carry
;
975 // Calculate repeating part
976 for (i
= 0; i
< length
; i
++) {
979 for (var j
= i
+ 1; j
< length
; j
++, k
++) {
980 product
= digits
[j
] * digits
[i
] * 2 + imult1
[k
] + carry
;
981 carry
= (product
/ BigInteger_base
) | 0;
982 imult1
[k
] = product
% BigInteger_base
;
985 var digit
= carry
+ imult1
[k
];
986 carry
= (digit
/ BigInteger_base
) | 0;
987 imult1
[k
] = digit
% BigInteger_base
;
988 imult1
[k
+ 1] += carry
;
991 return new BigInteger(imult1
, 1, CONSTRUCT
);
996 Divide two <BigIntegers> and truncate towards zero.
998 <quotient> throws an exception if *n* is zero.
1002 n - The number to divide *this* by. Will be converted to a <BigInteger>.
1006 The *this* / *n*, truncated to an integer.
1010 <add>, <subtract>, <multiply>, <divRem>, <remainder>
1012 BigInteger
.prototype.quotient = function(n
) {
1013 return this.divRem(n
)[0];
1018 Deprecated synonym for <quotient>.
1020 BigInteger
.prototype.divide
= BigInteger
.prototype.quotient
;
1024 Calculate the remainder of two <BigIntegers>.
1026 <remainder> throws an exception if *n* is zero.
1030 n - The remainder after *this* is divided *this* by *n*. Will be
1031 converted to a <BigInteger>.
1039 <divRem>, <quotient>
1041 BigInteger
.prototype.remainder = function(n
) {
1042 return this.divRem(n
)[1];
1047 Calculate the integer quotient and remainder of two <BigIntegers>.
1049 <divRem> throws an exception if *n* is zero.
1053 n - The number to divide *this* by. Will be converted to a <BigInteger>.
1057 A two-element array containing the quotient and the remainder.
1061 is exactly equivalent to
1063 > [a.quotient(b), a.remainder(b)]
1065 except it is faster, because they are calculated at the same time.
1069 <quotient>, <remainder>
1071 BigInteger
.prototype.divRem = function(n
) {
1074 throw new Error("Divide by zero");
1076 if (this._s
=== 0) {
1077 return [ZERO
, ZERO
];
1079 if (n
._d
.length
=== 1) {
1080 return this.divRemSmall(n
._s
* n
._d
[0]);
1083 // Test for easy cases -- |n1| <= |n2|
1084 switch (this.compareAbs(n
)) {
1086 return [this._s
=== n
._s
? ONE : M_ONE
, ZERO
];
1087 case -1: // |n1| < |n2|
1088 return [ZERO
, this];
1091 var sign
= this._s
* n
._s
;
1093 var b_digits
= this._d
;
1094 var b_index
= b_digits
.length
;
1095 var digits
= n
._d
.length
;
1099 var part
= new BigInteger([], 0, CONSTRUCT
);
1102 part
._d
.unshift(b_digits
[--b_index
]);
1103 part
= new BigInteger(part
._d
, 1, CONSTRUCT
);
1105 if (part
.compareAbs(n
) < 0) {
1109 if (part
._s
=== 0) {
1113 var xlen
= part
._d
.length
, ylen
= a
._d
.length
;
1114 var highx
= part
._d
[xlen
-1]*BigInteger_base
+ part
._d
[xlen
-2];
1115 var highy
= a
._d
[ylen
-1]*BigInteger_base
+ a
._d
[ylen
-2];
1116 if (part
._d
.length
> a
._d
.length
) {
1117 // The length of part._d can either match a._d length,
1118 // or exceed it by one.
1119 highx
= (highx
+1)*BigInteger_base
;
1121 guess
= Math
.ceil(highx
/highy
);
1124 var check
= a
.multiplySingleDigit(guess
);
1125 if (check
.compareAbs(part
) <= 0) {
1135 var diff
= part
.subtract(check
);
1136 part
._d
= diff
._d
.slice();
1139 return [new BigInteger(quot
.reverse(), sign
, CONSTRUCT
),
1140 new BigInteger(part
._d
, this._s
, CONSTRUCT
)];
1143 // Throws an exception if n is outside of (-BigInteger.base, -1] or
1144 // [1, BigInteger.base). It's not necessary to call this, since the
1145 // other division functions will call it if they are able to.
1146 BigInteger
.prototype.divRemSmall = function(n
) {
1150 throw new Error("Divide by zero");
1153 var n_s
= n
< 0 ? -1 : 1;
1154 var sign
= this._s
* n_s
;
1157 if (n
< 1 || n
>= BigInteger_base
) {
1158 throw new Error("Argument out of range");
1161 if (this._s
=== 0) {
1162 return [ZERO
, ZERO
];
1165 if (n
=== 1 || n
=== -1) {
1166 return [(sign
=== 1) ? this.abs() : new BigInteger(this._d
, sign
, CONSTRUCT
), ZERO
];
1169 // 2 <= n < BigInteger_base
1171 // divide a single digit by a single digit
1172 if (this._d
.length
=== 1) {
1173 var q
= new BigInteger([(this._d
[0] / n
) | 0], 1, CONSTRUCT
);
1174 r
= new BigInteger([(this._d
[0] % n
) | 0], 1, CONSTRUCT
);
1184 var digits
= this._d
.slice();
1185 var quot
= new Array(digits
.length
);
1191 while (digits
.length
) {
1192 part
= part
* BigInteger_base
+ digits
[digits
.length
- 1];
1196 diff
= BigInteger_base
* diff
+ part
;
1203 guess
= (part
/ n
) | 0;
1206 var check
= n
* guess
;
1207 diff
= part
- check
;
1218 r
= new BigInteger([diff
], 1, CONSTRUCT
);
1222 return [new BigInteger(quot
.reverse(), sign
, CONSTRUCT
), r
];
1227 Return true iff *this* is divisible by two.
1229 Note that <BigInteger.ZERO> is even.
1233 true if *this* is even, false otherwise.
1239 BigInteger
.prototype.isEven = function() {
1240 var digits
= this._d
;
1241 return this._s
=== 0 || digits
.length
=== 0 || (digits
[0] % 2) === 0;
1246 Return true iff *this* is not divisible by two.
1250 true if *this* is odd, false otherwise.
1256 BigInteger
.prototype.isOdd = function() {
1257 return !this.isEven();
1262 Get the sign of a <BigInteger>.
1272 <isZero>, <isPositive>, <isNegative>, <compare>, <BigInteger.ZERO>
1274 BigInteger
.prototype.sign = function() {
1279 Function: isPositive
1280 Return true iff *this* > 0.
1284 true if *this*.compare(<BigInteger.ZERO>) == 1.
1288 <sign>, <isZero>, <isNegative>, <isUnit>, <compare>, <BigInteger.ZERO>
1290 BigInteger
.prototype.isPositive = function() {
1295 Function: isNegative
1296 Return true iff *this* < 0.
1300 true if *this*.compare(<BigInteger.ZERO>) == -1.
1304 <sign>, <isPositive>, <isZero>, <isUnit>, <compare>, <BigInteger.ZERO>
1306 BigInteger
.prototype.isNegative = function() {
1312 Return true iff *this* == 0.
1316 true if *this*.compare(<BigInteger.ZERO>) == 0.
1320 <sign>, <isPositive>, <isNegative>, <isUnit>, <BigInteger.ZERO>
1322 BigInteger
.prototype.isZero = function() {
1323 return this._s
=== 0;
1328 Multiply a <BigInteger> by a power of 10.
1330 This is equivalent to, but faster than
1333 > return this.multiply(BigInteger("1e" + n));
1336 > return this.quotient(BigInteger("1e" + -n));
1341 n - The power of 10 to multiply *this* by. *n* is converted to a
1342 javascipt number and must be no greater than <BigInteger.MAX_EXP>
1343 (0x7FFFFFFF), or an exception will be thrown.
1347 *this* * (10 ** *n*), truncated to an integer if necessary.
1353 BigInteger
.prototype.exp10 = function(n
) {
1358 if (Math
.abs(n
) > Number(MAX_EXP
)) {
1359 throw new Error("exponent too large in BigInteger.exp10");
1361 // Optimization for this == 0. This also keeps us from having to trim zeros in the positive n case
1362 if (this._s
=== 0) {
1366 var k
= new BigInteger(this._d
.slice(), this._s
, CONSTRUCT
);
1368 for (; n
>= BigInteger_base_log10
; n
-= BigInteger_base_log10
) {
1374 k
= k
.multiplySingleDigit(Math
.pow(10, n
));
1375 return (this._s
< 0 ? k
.negate() : k
);
1376 } else if (-n
>= this._d
.length
*BigInteger_base_log10
) {
1379 var k
= new BigInteger(this._d
.slice(), this._s
, CONSTRUCT
);
1381 for (n
= -n
; n
>= BigInteger_base_log10
; n
-= BigInteger_base_log10
) {
1384 return (n
== 0) ? k : k
.divRemSmall(Math
.pow(10, n
))[0];
1390 Raise a <BigInteger> to a power.
1392 In this implementation, 0**0 is 1.
1396 n - The exponent to raise *this* by. *n* must be no greater than
1397 <BigInteger.MAX_EXP> (0x7FFFFFFF), or an exception will be thrown.
1401 *this* raised to the *nth* power.
1407 BigInteger
.prototype.pow = function(n
) {
1408 if (this.isUnit()) {
1413 return BigInteger(n
).isOdd() ? this : this.negate();
1421 else if (n
._s
< 0) {
1422 if (this._s
=== 0) {
1423 throw new Error("Divide by zero");
1429 if (this._s
=== 0) {
1436 if (n
.compareAbs(MAX_EXP
) > 0) {
1437 throw new Error("exponent too large in BigInteger.pow");
1441 var two
= BigInteger
.small
[2];
1443 while (n
.isPositive()) {
1445 aux
= aux
.multiply(x
);
1451 n
= n
.quotient(two
);
1459 Raise a <BigInteger> to a power (mod m).
1461 Because it is reduced by a modulus, <modPow> is not limited by
1462 <BigInteger.MAX_EXP> like <pow>.
1466 exponent - The exponent to raise *this* by. Must be positive.
1467 modulus - The modulus.
1471 *this* ^ *exponent* (mod *modulus*).
1477 BigInteger
.prototype.modPow = function(exponent
, modulus
) {
1481 while (exponent
.isPositive()) {
1482 if (exponent
.isOdd()) {
1483 result
= result
.multiply(base
).remainder(modulus
);
1486 exponent
= exponent
.quotient(BigInteger
.small
[2]);
1487 if (exponent
.isPositive()) {
1488 base
= base
.square().remainder(modulus
);
1497 Get the natural logarithm of a <BigInteger> as a native JavaScript number.
1499 This is equivalent to
1501 > Math.log(this.toJSValue())
1503 but handles values outside of the native number range.
1513 BigInteger
.prototype.log = function() {
1515 case 0: return -Infinity
;
1516 case -1: return NaN
;
1517 default: // Fall through.
1520 var l
= this._d
.length
;
1522 if (l
*BigInteger_base_log10
< 30) {
1523 return Math
.log(this.valueOf());
1526 var N
= Math
.ceil(30/BigInteger_base_log10
);
1527 var firstNdigits
= this._d
.slice(l
- N
);
1528 return Math
.log((new BigInteger(firstNdigits
, 1, CONSTRUCT
)).valueOf()) + (l
- N
) * Math
.log(BigInteger_base
);
1533 Convert a <BigInteger> to a native JavaScript integer.
1535 This is called automatically by JavaScipt to convert a <BigInteger> to a
1540 > parseInt(this.toString(), 10)
1544 <toString>, <toJSValue>
1546 BigInteger
.prototype.valueOf = function() {
1547 return parseInt(this.toString(), 10);
1552 Convert a <BigInteger> to a native JavaScript integer.
1554 This is the same as valueOf, but more explicitly named.
1558 > parseInt(this.toString(), 10)
1562 <toString>, <valueOf>
1564 BigInteger
.prototype.toJSValue = function() {
1565 return parseInt(this.toString(), 10);
1568 var MAX_EXP
= BigInteger(0x7FFFFFFF);
1569 // Constant: MAX_EXP
1570 // The largest exponent allowed in <pow> and <exp10> (0x7FFFFFFF or 2147483647).
1571 BigInteger
.MAX_EXP
= MAX_EXP
;
1574 function makeUnary(fn
) {
1575 return function(a
) {
1576 return fn
.call(BigInteger(a
));
1580 function makeBinary(fn
) {
1581 return function(a
, b
) {
1582 return fn
.call(BigInteger(a
), BigInteger(b
));
1586 function makeTrinary(fn
) {
1587 return function(a
, b
, c
) {
1588 return fn
.call(BigInteger(a
), BigInteger(b
), BigInteger(c
));
1594 var unary
= "toJSValue,isEven,isOdd,sign,isZero,isNegative,abs,isUnit,square,negate,isPositive,toString,next,prev,log".split(",");
1595 var binary
= "compare,remainder,divRem,subtract,add,quotient,divide,multiply,pow,compareAbs".split(",");
1596 var trinary
= ["modPow"];
1598 for (i
= 0; i
< unary
.length
; i
++) {
1600 BigInteger
[fn
] = makeUnary(BigInteger
.prototype[fn
]);
1603 for (i
= 0; i
< binary
.length
; i
++) {
1605 BigInteger
[fn
] = makeBinary(BigInteger
.prototype[fn
]);
1608 for (i
= 0; i
< trinary
.length
; i
++) {
1610 BigInteger
[fn
] = makeTrinary(BigInteger
.prototype[fn
]);
1613 BigInteger
.exp10 = function(x
, n
) {
1614 return BigInteger(x
).exp10(n
);
1619 exports
.BigInteger
= BigInteger
;
1620 })(typeof exports
!== 'undefined' ? exports : this);