]> git.immae.eu Git - perso/Immae/Projets/Cryptomonnaies/BIP39.git/blame - src/js/biginteger.js
Merge pull request #287 from sui77/master
[perso/Immae/Projets/Cryptomonnaies/BIP39.git] / src / js / biginteger.js
CommitLineData
b6dbc2a1
IC
1/*
2 JavaScript BigInteger library version 0.9.1
3 http://silentmatt.com/biginteger/
4
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.
8
9 Support for arbitrary internal representation base was added by
10 Vitaly Magerya.
11*/
12
13/*
14 File: biginteger.js
15
16 Exports:
17
18 <BigInteger>
19*/
20(function(exports) {
21"use strict";
22/*
23 Class: BigInteger
24 An arbitrarily-large integer.
25
26 <BigInteger> objects should be considered immutable. None of the "built-in"
27 methods modify *this* or their arguments. All properties should be
28 considered private.
29
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>
32 object.
33
34 As an example, these calls are equivalent.
35
36 > BigInteger(4).multiply(5); // returns BigInteger(20);
37 > BigInteger.multiply(4, 5); // returns BigInteger(20);
38
39 > var a = 42;
40 > var a = BigInteger.toJSValue("0b101010"); // Not completely useless...
41*/
42
43var CONSTRUCT = {}; // Unique token to call "private" version of constructor
44
45/*
46 Constructor: BigInteger()
47 Convert a value to a <BigInteger>.
48
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.
53
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
58
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.
65
66 > new BigInteger([5], -1): create a new BigInteger with value -5
67
68 Parameters:
69
70 n - Value to convert to a <BigInteger>.
71
72 Returns:
73
74 A <BigInteger> value.
75
76 See Also:
77
78 <parse>, <BigInteger>
79*/
80function BigInteger(n, s, token) {
81 if (token !== CONSTRUCT) {
82 if (n instanceof BigInteger) {
83 return n;
84 }
85 else if (typeof n === "undefined") {
86 return ZERO;
87 }
88 return BigInteger.parse(n);
89 }
90
91 n = n || []; // Provide the nullary constructor for subclasses.
92 while (n.length && !n[n.length - 1]) {
93 --n.length;
94 }
95 this._d = n;
96 this._s = n.length ? (s || 1) : 0;
97}
98
99BigInteger._construct = function(n, s) {
100 return new BigInteger(n, s, CONSTRUCT);
101};
102
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.
106var BigInteger_base = 10000000;
107var BigInteger_base_log10 = 7;
108
109BigInteger.base = BigInteger_base;
110BigInteger.base_log10 = BigInteger_base_log10;
111
112var ZERO = new BigInteger([], 0, CONSTRUCT);
113// Constant: ZERO
114// <BigInteger> 0.
115BigInteger.ZERO = ZERO;
116
117var ONE = new BigInteger([1], 1, CONSTRUCT);
118// Constant: ONE
119// <BigInteger> 1.
120BigInteger.ONE = ONE;
121
122var M_ONE = new BigInteger(ONE._d, -1, CONSTRUCT);
123// Constant: M_ONE
124// <BigInteger> -1.
125BigInteger.M_ONE = M_ONE;
126
127// Constant: _0
128// Shortcut for <ZERO>.
129BigInteger._0 = ZERO;
130
131// Constant: _1
132// Shortcut for <ONE>.
133BigInteger._1 = ONE;
134
135/*
136 Constant: small
137 Array of <BigIntegers> from 0 to 36.
138
139 These are used internally for parsing, but useful when you need a "small"
140 <BigInteger>.
141
142 See Also:
143
144 <ZERO>, <ONE>, <_0>, <_1>
145*/
146BigInteger.small = [
147 ZERO,
148 ONE,
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)
185];
186
187// Used for parsing/radix conversion
188BigInteger.digits = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ".split("");
189
190/*
191 Method: toString
192 Convert a <BigInteger> to a string.
193
194 When *base* is greater than 10, letters are upper case.
195
196 Parameters:
197
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.
200
201 Returns:
202
203 The string representation of the <BigInteger>.
204*/
205BigInteger.prototype.toString = function(base) {
206 base = +base || 10;
207 if (base < 2 || base > 36) {
208 throw new Error("illegal radix " + base + ".");
209 }
210 if (this._s === 0) {
211 return "0";
212 }
213 if (base === 10) {
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;
219 str += group;
220 }
221 return str;
222 }
223 else {
224 var numerals = BigInteger.digits;
225 base = BigInteger.small[base];
226 var sign = this._s;
227
228 var n = this.abs();
229 var digits = [];
230 var digit;
231
232 while (n._s !== 0) {
233 var divmod = n.divRem(base);
234 n = divmod[0];
235 digit = divmod[1];
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()]);
239 }
240 return (sign < 0 ? "-" : "") + digits.reverse().join("");
241 }
242};
243
244// Verify strings for parsing
245BigInteger.radixRegex = [
246 /^$/,
247 /^$/,
248 /^[01]*$/,
249 /^[012]*$/,
250 /^[0-3]*$/,
251 /^[0-4]*$/,
252 /^[0-5]*$/,
253 /^[0-6]*$/,
254 /^[0-7]*$/,
255 /^[0-8]*$/,
256 /^[0-9]*$/,
257 /^[0-9aA]*$/,
258 /^[0-9abAB]*$/,
259 /^[0-9abcABC]*$/,
260 /^[0-9a-dA-D]*$/,
261 /^[0-9a-eA-E]*$/,
262 /^[0-9a-fA-F]*$/,
263 /^[0-9a-gA-G]*$/,
264 /^[0-9a-hA-H]*$/,
265 /^[0-9a-iA-I]*$/,
266 /^[0-9a-jA-J]*$/,
267 /^[0-9a-kA-K]*$/,
268 /^[0-9a-lA-L]*$/,
269 /^[0-9a-mA-M]*$/,
270 /^[0-9a-nA-N]*$/,
271 /^[0-9a-oA-O]*$/,
272 /^[0-9a-pA-P]*$/,
273 /^[0-9a-qA-Q]*$/,
274 /^[0-9a-rA-R]*$/,
275 /^[0-9a-sA-S]*$/,
276 /^[0-9a-tA-T]*$/,
277 /^[0-9a-uA-U]*$/,
278 /^[0-9a-vA-V]*$/,
279 /^[0-9a-wA-W]*$/,
280 /^[0-9a-xA-X]*$/,
281 /^[0-9a-yA-Y]*$/,
282 /^[0-9a-zA-Z]*$/
283];
284
285/*
286 Function: parse
287 Parse a string into a <BigInteger>.
288
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
291 of *s* as follows:
292
293 - "0x" or "0X": *base* = 16
294 - "0c" or "0C": *base* = 8
295 - "0b" or "0B": *base* = 2
296 - else: *base* = 10
297
298 If no base is provided, or *base* is 10, the number can be in exponential
299 form. For example, these are all valid:
300
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
304
305 If any characters fall outside the range defined by the radix, an exception
306 will be thrown.
307
308 Parameters:
309
310 s - The string to parse.
311 base - Optional radix (default is to guess based on *s*).
312
313 Returns:
314
315 a <BigInteger> instance.
316*/
317BigInteger.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");
324
325 return str.replace(/^([+\-])?(\d+)\.?(\d*)[eE]([+\-]?\d+)$/, function(x, s, n, f, c) {
326 c = +c;
327 var l = c < 0;
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");
332 var r = n + f;
333 return (s || "") + (l ? r = z + r : r += z).substr(0, i += l ? z.length : 0) + (i < r.length ? "." + r.substr(i) : "");
334 });
335 }
336
337 s = s.toString();
338 if (typeof base === "undefined" || +base === 10) {
339 s = expandExponential(s);
340 }
341
342 var prefixRE;
343 if (typeof base === "undefined") {
344 prefixRE = '0[xcb]';
345 }
346 else if (base == 16) {
347 prefixRE = '0x';
348 }
349 else if (base == 8) {
350 prefixRE = '0c';
351 }
352 else if (base == 2) {
353 prefixRE = '0b';
354 }
355 else {
356 prefixRE = '';
357 }
358 var parts = new RegExp('^([+\\-]?)(' + prefixRE + ')?([0-9a-z]*)(?:\\.\\d*)?$', 'i').exec(s);
359 if (parts) {
360 var sign = parts[1] || "+";
361 var baseSection = parts[2] || "";
362 var digits = parts[3] || "";
363
364 if (typeof base === "undefined") {
365 // Guess base
366 if (baseSection === "0x" || baseSection === "0X") { // Hex
367 base = 16;
368 }
369 else if (baseSection === "0c" || baseSection === "0C") { // Octal
370 base = 8;
371 }
372 else if (baseSection === "0b" || baseSection === "0B") { // Binary
373 base = 2;
374 }
375 else {
376 base = 10;
377 }
378 }
379 else if (base < 2 || base > 36) {
380 throw new Error("Illegal radix " + base + ".");
381 }
382
383 base = +base;
384
385 // Check for digits outside the range
386 if (!(BigInteger.radixRegex[base].test(digits))) {
387 throw new Error("Bad digit for radix " + base);
388 }
389
390 // Strip leading zeros, and convert to array
391 digits = digits.replace(/^0+/, "").split("");
392 if (digits.length === 0) {
393 return ZERO;
394 }
395
396 // Get the sign (we know it's not zero)
397 sign = (sign === "-") ? -1 : 1;
398
399 // Optimize 10
400 if (base == 10) {
401 var d = [];
402 while (digits.length >= BigInteger_base_log10) {
403 d.push(parseInt(digits.splice(digits.length-BigInteger.base_log10, BigInteger.base_log10).join(''), 10));
404 }
405 d.push(parseInt(digits.join(''), 10));
406 return new BigInteger(d, sign, CONSTRUCT);
407 }
408
409 // Do the conversion
410 var d = ZERO;
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)]);
415 }
416 return new BigInteger(d._d, sign, CONSTRUCT);
417 }
418 else {
419 throw new Error("Invalid BigInteger format: " + s);
420 }
421};
422
423/*
424 Function: add
425 Add two <BigIntegers>.
426
427 Parameters:
428
429 n - The number to add to *this*. Will be converted to a <BigInteger>.
430
431 Returns:
432
433 The numbers added together.
434
435 See Also:
436
437 <subtract>, <multiply>, <quotient>, <next>
438*/
439BigInteger.prototype.add = function(n) {
440 if (this._s === 0) {
441 return BigInteger(n);
442 }
443
444 n = BigInteger(n);
445 if (n._s === 0) {
446 return this;
447 }
448 if (this._s !== n._s) {
449 n = n.negate();
450 return this.subtract(n);
451 }
452
453 var a = this._d;
454 var b = n._d;
455 var al = a.length;
456 var bl = b.length;
457 var sum = new Array(Math.max(al, bl) + 1);
458 var size = Math.min(al, bl);
459 var carry = 0;
460 var digit;
461
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;
466 }
467 if (bl > al) {
468 a = b;
469 al = bl;
470 }
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;
475 }
476 if (carry) {
477 sum[i] = carry;
478 }
479
480 for ( ; i < al; i++) {
481 sum[i] = a[i];
482 }
483
484 return new BigInteger(sum, this._s, CONSTRUCT);
485};
486
487/*
488 Function: negate
489 Get the additive inverse of a <BigInteger>.
490
491 Returns:
492
493 A <BigInteger> with the same magnatude, but with the opposite sign.
494
495 See Also:
496
497 <abs>
498*/
499BigInteger.prototype.negate = function() {
500 return new BigInteger(this._d, (-this._s) | 0, CONSTRUCT);
501};
502
503/*
504 Function: abs
505 Get the absolute value of a <BigInteger>.
506
507 Returns:
508
509 A <BigInteger> with the same magnatude, but always positive (or zero).
510
511 See Also:
512
513 <negate>
514*/
515BigInteger.prototype.abs = function() {
516 return (this._s < 0) ? this.negate() : this;
517};
518
519/*
520 Function: subtract
521 Subtract two <BigIntegers>.
522
523 Parameters:
524
525 n - The number to subtract from *this*. Will be converted to a <BigInteger>.
526
527 Returns:
528
529 The *n* subtracted from *this*.
530
531 See Also:
532
533 <add>, <multiply>, <quotient>, <prev>
534*/
535BigInteger.prototype.subtract = function(n) {
536 if (this._s === 0) {
537 return BigInteger(n).negate();
538 }
539
540 n = BigInteger(n);
541 if (n._s === 0) {
542 return this;
543 }
544 if (this._s !== n._s) {
545 n = n.negate();
546 return this.add(n);
547 }
548
549 var m = this;
550 // negative - negative => -|a| - -|b| => -|a| + |b| => |b| - |a|
551 if (this._s < 0) {
552 m = new BigInteger(n._d, 1, CONSTRUCT);
553 n = new BigInteger(this._d, 1, CONSTRUCT);
554 }
555
556 // Both are positive => a - b
557 var sign = m.compareAbs(n);
558 if (sign === 0) {
559 return ZERO;
560 }
561 else if (sign < 0) {
562 // swap m and n
563 var t = n;
564 n = m;
565 m = t;
566 }
567
568 // a > b
569 var a = m._d;
570 var b = n._d;
571 var al = a.length;
572 var bl = b.length;
573 var diff = new Array(al); // al >= bl since a > b
574 var borrow = 0;
575 var i;
576 var digit;
577
578 for (i = 0; i < bl; i++) {
579 digit = a[i] - borrow - b[i];
580 if (digit < 0) {
581 digit += BigInteger_base;
582 borrow = 1;
583 }
584 else {
585 borrow = 0;
586 }
587 diff[i] = digit;
588 }
589 for (i = bl; i < al; i++) {
590 digit = a[i] - borrow;
591 if (digit < 0) {
592 digit += BigInteger_base;
593 }
594 else {
595 diff[i++] = digit;
596 break;
597 }
598 diff[i] = digit;
599 }
600 for ( ; i < al; i++) {
601 diff[i] = a[i];
602 }
603
604 return new BigInteger(diff, sign, CONSTRUCT);
605};
606
607(function() {
608 function addOne(n, sign) {
609 var a = n._d;
610 var sum = a.slice();
611 var carry = true;
612 var i = 0;
613
614 while (true) {
615 var digit = (a[i] || 0) + 1;
616 sum[i] = digit % BigInteger_base;
617 if (digit <= BigInteger_base - 1) {
618 break;
619 }
620 ++i;
621 }
622
623 return new BigInteger(sum, sign, CONSTRUCT);
624 }
625
626 function subtractOne(n, sign) {
627 var a = n._d;
628 var sum = a.slice();
629 var borrow = true;
630 var i = 0;
631
632 while (true) {
633 var digit = (a[i] || 0) - 1;
634 if (digit < 0) {
635 sum[i] = digit + BigInteger_base;
636 }
637 else {
638 sum[i] = digit;
639 break;
640 }
641 ++i;
642 }
643
644 return new BigInteger(sum, sign, CONSTRUCT);
645 }
646
647 /*
648 Function: next
649 Get the next <BigInteger> (add one).
650
651 Returns:
652
653 *this* + 1.
654
655 See Also:
656
657 <add>, <prev>
658 */
659 BigInteger.prototype.next = function() {
660 switch (this._s) {
661 case 0:
662 return ONE;
663 case -1:
664 return subtractOne(this, -1);
665 // case 1:
666 default:
667 return addOne(this, 1);
668 }
669 };
670
671 /*
672 Function: prev
673 Get the previous <BigInteger> (subtract one).
674
675 Returns:
676
677 *this* - 1.
678
679 See Also:
680
681 <next>, <subtract>
682 */
683 BigInteger.prototype.prev = function() {
684 switch (this._s) {
685 case 0:
686 return M_ONE;
687 case -1:
688 return addOne(this, -1);
689 // case 1:
690 default:
691 return subtractOne(this, 1);
692 }
693 };
694})();
695
696/*
697 Function: compareAbs
698 Compare the absolute value of two <BigIntegers>.
699
700 Calling <compareAbs> is faster than calling <abs> twice, then <compare>.
701
702 Parameters:
703
704 n - The number to compare to *this*. Will be converted to a <BigInteger>.
705
706 Returns:
707
708 -1, 0, or +1 if *|this|* is less than, equal to, or greater than *|n|*.
709
710 See Also:
711
712 <compare>, <abs>
713*/
714BigInteger.prototype.compareAbs = function(n) {
715 if (this === n) {
716 return 0;
717 }
718
719 if (!(n instanceof BigInteger)) {
720 if (!isFinite(n)) {
721 return(isNaN(n) ? n : -1);
722 }
723 n = BigInteger(n);
724 }
725
726 if (this._s === 0) {
727 return (n._s !== 0) ? -1 : 0;
728 }
729 if (n._s === 0) {
730 return 1;
731 }
732
733 var l = this._d.length;
734 var nl = n._d.length;
735 if (l < nl) {
736 return -1;
737 }
738 else if (l > nl) {
739 return 1;
740 }
741
742 var a = this._d;
743 var b = n._d;
744 for (var i = l-1; i >= 0; i--) {
745 if (a[i] !== b[i]) {
746 return a[i] < b[i] ? -1 : 1;
747 }
748 }
749
750 return 0;
751};
752
753/*
754 Function: compare
755 Compare two <BigIntegers>.
756
757 Parameters:
758
759 n - The number to compare to *this*. Will be converted to a <BigInteger>.
760
761 Returns:
762
763 -1, 0, or +1 if *this* is less than, equal to, or greater than *n*.
764
765 See Also:
766
767 <compareAbs>, <isPositive>, <isNegative>, <isUnit>
768*/
769BigInteger.prototype.compare = function(n) {
770 if (this === n) {
771 return 0;
772 }
773
774 n = BigInteger(n);
775
776 if (this._s === 0) {
777 return -n._s;
778 }
779
780 if (this._s === n._s) { // both positive or both negative
781 var cmp = this.compareAbs(n);
782 return cmp * this._s;
783 }
784 else {
785 return this._s;
786 }
787};
788
789/*
790 Function: isUnit
791 Return true iff *this* is either 1 or -1.
792
793 Returns:
794
795 true if *this* compares equal to <BigInteger.ONE> or <BigInteger.M_ONE>.
796
797 See Also:
798
799 <isZero>, <isNegative>, <isPositive>, <compareAbs>, <compare>,
800 <BigInteger.ONE>, <BigInteger.M_ONE>
801*/
802BigInteger.prototype.isUnit = function() {
803 return this === ONE ||
804 this === M_ONE ||
805 (this._d.length === 1 && this._d[0] === 1);
806};
807
808/*
809 Function: multiply
810 Multiply two <BigIntegers>.
811
812 Parameters:
813
814 n - The number to multiply *this* by. Will be converted to a
815 <BigInteger>.
816
817 Returns:
818
819 The numbers multiplied together.
820
821 See Also:
822
823 <add>, <subtract>, <quotient>, <square>
824*/
825BigInteger.prototype.multiply = function(n) {
826 // TODO: Consider adding Karatsuba multiplication for large numbers
827 if (this._s === 0) {
828 return ZERO;
829 }
830
831 n = BigInteger(n);
832 if (n._s === 0) {
833 return ZERO;
834 }
835 if (this.isUnit()) {
836 if (this._s < 0) {
837 return n.negate();
838 }
839 return n;
840 }
841 if (n.isUnit()) {
842 if (n._s < 0) {
843 return this.negate();
844 }
845 return this;
846 }
847 if (this === n) {
848 return this.square();
849 }
850
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;
854 var al = a.length;
855 var bl = b.length;
856
857 var pl = al + bl;
858 var partial = new Array(pl);
859 var i;
860 for (i = 0; i < pl; i++) {
861 partial[i] = 0;
862 }
863
864 for (i = 0; i < bl; i++) {
865 var carry = 0;
866 var bi = b[i];
867 var jlimit = al + i;
868 var digit;
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;
873 }
874 if (carry) {
875 digit = partial[j] + carry;
876 carry = (digit / BigInteger_base) | 0;
877 partial[j] = digit % BigInteger_base;
878 }
879 }
880 return new BigInteger(partial, this._s * n._s, CONSTRUCT);
881};
882
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
886BigInteger.prototype.multiplySingleDigit = function(n) {
887 if (n === 0 || this._s === 0) {
888 return ZERO;
889 }
890 if (n === 1) {
891 return this;
892 }
893
894 var digit;
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);
900 }
901 return new BigInteger([digit], 1, CONSTRUCT);
902 }
903
904 if (n === 2) {
905 return this.add(this);
906 }
907 if (this.isUnit()) {
908 return new BigInteger([n], 1, CONSTRUCT);
909 }
910
911 var a = this._d;
912 var al = a.length;
913
914 var pl = al + 1;
915 var partial = new Array(pl);
916 for (var i = 0; i < pl; i++) {
917 partial[i] = 0;
918 }
919
920 var carry = 0;
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;
925 }
926 if (carry) {
927 partial[j] = carry;
928 }
929
930 return new BigInteger(partial, 1, CONSTRUCT);
931};
932
933/*
934 Function: square
935 Multiply a <BigInteger> by itself.
936
937 This is slightly faster than regular multiplication, since it removes the
938 duplicated multiplcations.
939
940 Returns:
941
942 > this.multiply(this)
943
944 See Also:
945 <multiply>
946*/
947BigInteger.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
952
953 if (this._s === 0) {
954 return ZERO;
955 }
956 if (this.isUnit()) {
957 return ONE;
958 }
959
960 var digits = this._d;
961 var length = digits.length;
962 var imult1 = new Array(length + length + 1);
963 var product, carry, k;
964 var i;
965
966 // Calculate diagonal
967 for (i = 0; i < length; i++) {
968 k = i * 2;
969 product = digits[i] * digits[i];
970 carry = (product / BigInteger_base) | 0;
971 imult1[k] = product % BigInteger_base;
972 imult1[k + 1] = carry;
973 }
974
975 // Calculate repeating part
976 for (i = 0; i < length; i++) {
977 carry = 0;
978 k = i * 2 + 1;
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;
983 }
984 k = length + i;
985 var digit = carry + imult1[k];
986 carry = (digit / BigInteger_base) | 0;
987 imult1[k] = digit % BigInteger_base;
988 imult1[k + 1] += carry;
989 }
990
991 return new BigInteger(imult1, 1, CONSTRUCT);
992};
993
994/*
995 Function: quotient
996 Divide two <BigIntegers> and truncate towards zero.
997
998 <quotient> throws an exception if *n* is zero.
999
1000 Parameters:
1001
1002 n - The number to divide *this* by. Will be converted to a <BigInteger>.
1003
1004 Returns:
1005
1006 The *this* / *n*, truncated to an integer.
1007
1008 See Also:
1009
1010 <add>, <subtract>, <multiply>, <divRem>, <remainder>
1011*/
1012BigInteger.prototype.quotient = function(n) {
1013 return this.divRem(n)[0];
1014};
1015
1016/*
1017 Function: divide
1018 Deprecated synonym for <quotient>.
1019*/
1020BigInteger.prototype.divide = BigInteger.prototype.quotient;
1021
1022/*
1023 Function: remainder
1024 Calculate the remainder of two <BigIntegers>.
1025
1026 <remainder> throws an exception if *n* is zero.
1027
1028 Parameters:
1029
1030 n - The remainder after *this* is divided *this* by *n*. Will be
1031 converted to a <BigInteger>.
1032
1033 Returns:
1034
1035 *this* % *n*.
1036
1037 See Also:
1038
1039 <divRem>, <quotient>
1040*/
1041BigInteger.prototype.remainder = function(n) {
1042 return this.divRem(n)[1];
1043};
1044
1045/*
1046 Function: divRem
1047 Calculate the integer quotient and remainder of two <BigIntegers>.
1048
1049 <divRem> throws an exception if *n* is zero.
1050
1051 Parameters:
1052
1053 n - The number to divide *this* by. Will be converted to a <BigInteger>.
1054
1055 Returns:
1056
1057 A two-element array containing the quotient and the remainder.
1058
1059 > a.divRem(b)
1060
1061 is exactly equivalent to
1062
1063 > [a.quotient(b), a.remainder(b)]
1064
1065 except it is faster, because they are calculated at the same time.
1066
1067 See Also:
1068
1069 <quotient>, <remainder>
1070*/
1071BigInteger.prototype.divRem = function(n) {
1072 n = BigInteger(n);
1073 if (n._s === 0) {
1074 throw new Error("Divide by zero");
1075 }
1076 if (this._s === 0) {
1077 return [ZERO, ZERO];
1078 }
1079 if (n._d.length === 1) {
1080 return this.divRemSmall(n._s * n._d[0]);
1081 }
1082
1083 // Test for easy cases -- |n1| <= |n2|
1084 switch (this.compareAbs(n)) {
1085 case 0: // n1 == n2
1086 return [this._s === n._s ? ONE : M_ONE, ZERO];
1087 case -1: // |n1| < |n2|
1088 return [ZERO, this];
1089 }
1090
1091 var sign = this._s * n._s;
1092 var a = n.abs();
1093 var b_digits = this._d;
1094 var b_index = b_digits.length;
1095 var digits = n._d.length;
1096 var quot = [];
1097 var guess;
1098
1099 var part = new BigInteger([], 0, CONSTRUCT);
1100
1101 while (b_index) {
1102 part._d.unshift(b_digits[--b_index]);
1103 part = new BigInteger(part._d, 1, CONSTRUCT);
1104
1105 if (part.compareAbs(n) < 0) {
1106 quot.push(0);
1107 continue;
1108 }
1109 if (part._s === 0) {
1110 guess = 0;
1111 }
1112 else {
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;
1120 }
1121 guess = Math.ceil(highx/highy);
1122 }
1123 do {
1124 var check = a.multiplySingleDigit(guess);
1125 if (check.compareAbs(part) <= 0) {
1126 break;
1127 }
1128 guess--;
1129 } while (guess);
1130
1131 quot.push(guess);
1132 if (!guess) {
1133 continue;
1134 }
1135 var diff = part.subtract(check);
1136 part._d = diff._d.slice();
1137 }
1138
1139 return [new BigInteger(quot.reverse(), sign, CONSTRUCT),
1140 new BigInteger(part._d, this._s, CONSTRUCT)];
1141};
1142
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.
1146BigInteger.prototype.divRemSmall = function(n) {
1147 var r;
1148 n = +n;
1149 if (n === 0) {
1150 throw new Error("Divide by zero");
1151 }
1152
1153 var n_s = n < 0 ? -1 : 1;
1154 var sign = this._s * n_s;
1155 n = Math.abs(n);
1156
1157 if (n < 1 || n >= BigInteger_base) {
1158 throw new Error("Argument out of range");
1159 }
1160
1161 if (this._s === 0) {
1162 return [ZERO, ZERO];
1163 }
1164
1165 if (n === 1 || n === -1) {
1166 return [(sign === 1) ? this.abs() : new BigInteger(this._d, sign, CONSTRUCT), ZERO];
1167 }
1168
1169 // 2 <= n < BigInteger_base
1170
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);
1175 if (sign < 0) {
1176 q = q.negate();
1177 }
1178 if (this._s < 0) {
1179 r = r.negate();
1180 }
1181 return [q, r];
1182 }
1183
1184 var digits = this._d.slice();
1185 var quot = new Array(digits.length);
1186 var part = 0;
1187 var diff = 0;
1188 var i = 0;
1189 var guess;
1190
1191 while (digits.length) {
1192 part = part * BigInteger_base + digits[digits.length - 1];
1193 if (part < n) {
1194 quot[i++] = 0;
1195 digits.pop();
1196 diff = BigInteger_base * diff + part;
1197 continue;
1198 }
1199 if (part === 0) {
1200 guess = 0;
1201 }
1202 else {
1203 guess = (part / n) | 0;
1204 }
1205
1206 var check = n * guess;
1207 diff = part - check;
1208 quot[i++] = guess;
1209 if (!guess) {
1210 digits.pop();
1211 continue;
1212 }
1213
1214 digits.pop();
1215 part = diff;
1216 }
1217
1218 r = new BigInteger([diff], 1, CONSTRUCT);
1219 if (this._s < 0) {
1220 r = r.negate();
1221 }
1222 return [new BigInteger(quot.reverse(), sign, CONSTRUCT), r];
1223};
1224
1225/*
1226 Function: isEven
1227 Return true iff *this* is divisible by two.
1228
1229 Note that <BigInteger.ZERO> is even.
1230
1231 Returns:
1232
1233 true if *this* is even, false otherwise.
1234
1235 See Also:
1236
1237 <isOdd>
1238*/
1239BigInteger.prototype.isEven = function() {
1240 var digits = this._d;
1241 return this._s === 0 || digits.length === 0 || (digits[0] % 2) === 0;
1242};
1243
1244/*
1245 Function: isOdd
1246 Return true iff *this* is not divisible by two.
1247
1248 Returns:
1249
1250 true if *this* is odd, false otherwise.
1251
1252 See Also:
1253
1254 <isEven>
1255*/
1256BigInteger.prototype.isOdd = function() {
1257 return !this.isEven();
1258};
1259
1260/*
1261 Function: sign
1262 Get the sign of a <BigInteger>.
1263
1264 Returns:
1265
1266 * -1 if *this* < 0
1267 * 0 if *this* == 0
1268 * +1 if *this* > 0
1269
1270 See Also:
1271
1272 <isZero>, <isPositive>, <isNegative>, <compare>, <BigInteger.ZERO>
1273*/
1274BigInteger.prototype.sign = function() {
1275 return this._s;
1276};
1277
1278/*
1279 Function: isPositive
1280 Return true iff *this* > 0.
1281
1282 Returns:
1283
1284 true if *this*.compare(<BigInteger.ZERO>) == 1.
1285
1286 See Also:
1287
1288 <sign>, <isZero>, <isNegative>, <isUnit>, <compare>, <BigInteger.ZERO>
1289*/
1290BigInteger.prototype.isPositive = function() {
1291 return this._s > 0;
1292};
1293
1294/*
1295 Function: isNegative
1296 Return true iff *this* < 0.
1297
1298 Returns:
1299
1300 true if *this*.compare(<BigInteger.ZERO>) == -1.
1301
1302 See Also:
1303
1304 <sign>, <isPositive>, <isZero>, <isUnit>, <compare>, <BigInteger.ZERO>
1305*/
1306BigInteger.prototype.isNegative = function() {
1307 return this._s < 0;
1308};
1309
1310/*
1311 Function: isZero
1312 Return true iff *this* == 0.
1313
1314 Returns:
1315
1316 true if *this*.compare(<BigInteger.ZERO>) == 0.
1317
1318 See Also:
1319
1320 <sign>, <isPositive>, <isNegative>, <isUnit>, <BigInteger.ZERO>
1321*/
1322BigInteger.prototype.isZero = function() {
1323 return this._s === 0;
1324};
1325
1326/*
1327 Function: exp10
1328 Multiply a <BigInteger> by a power of 10.
1329
1330 This is equivalent to, but faster than
1331
1332 > if (n >= 0) {
1333 > return this.multiply(BigInteger("1e" + n));
1334 > }
1335 > else { // n <= 0
1336 > return this.quotient(BigInteger("1e" + -n));
1337 > }
1338
1339 Parameters:
1340
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.
1344
1345 Returns:
1346
1347 *this* * (10 ** *n*), truncated to an integer if necessary.
1348
1349 See Also:
1350
1351 <pow>, <multiply>
1352*/
1353BigInteger.prototype.exp10 = function(n) {
1354 n = +n;
1355 if (n === 0) {
1356 return this;
1357 }
1358 if (Math.abs(n) > Number(MAX_EXP)) {
1359 throw new Error("exponent too large in BigInteger.exp10");
1360 }
1361 // Optimization for this == 0. This also keeps us from having to trim zeros in the positive n case
1362 if (this._s === 0) {
1363 return ZERO;
1364 }
1365 if (n > 0) {
1366 var k = new BigInteger(this._d.slice(), this._s, CONSTRUCT);
1367
1368 for (; n >= BigInteger_base_log10; n -= BigInteger_base_log10) {
1369 k._d.unshift(0);
1370 }
1371 if (n == 0)
1372 return k;
1373 k._s = 1;
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) {
1377 return ZERO;
1378 } else {
1379 var k = new BigInteger(this._d.slice(), this._s, CONSTRUCT);
1380
1381 for (n = -n; n >= BigInteger_base_log10; n -= BigInteger_base_log10) {
1382 k._d.shift();
1383 }
1384 return (n == 0) ? k : k.divRemSmall(Math.pow(10, n))[0];
1385 }
1386};
1387
1388/*
1389 Function: pow
1390 Raise a <BigInteger> to a power.
1391
1392 In this implementation, 0**0 is 1.
1393
1394 Parameters:
1395
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.
1398
1399 Returns:
1400
1401 *this* raised to the *nth* power.
1402
1403 See Also:
1404
1405 <modPow>
1406*/
1407BigInteger.prototype.pow = function(n) {
1408 if (this.isUnit()) {
1409 if (this._s > 0) {
1410 return this;
1411 }
1412 else {
1413 return BigInteger(n).isOdd() ? this : this.negate();
1414 }
1415 }
1416
1417 n = BigInteger(n);
1418 if (n._s === 0) {
1419 return ONE;
1420 }
1421 else if (n._s < 0) {
1422 if (this._s === 0) {
1423 throw new Error("Divide by zero");
1424 }
1425 else {
1426 return ZERO;
1427 }
1428 }
1429 if (this._s === 0) {
1430 return ZERO;
1431 }
1432 if (n.isUnit()) {
1433 return this;
1434 }
1435
1436 if (n.compareAbs(MAX_EXP) > 0) {
1437 throw new Error("exponent too large in BigInteger.pow");
1438 }
1439 var x = this;
1440 var aux = ONE;
1441 var two = BigInteger.small[2];
1442
1443 while (n.isPositive()) {
1444 if (n.isOdd()) {
1445 aux = aux.multiply(x);
1446 if (n.isUnit()) {
1447 return aux;
1448 }
1449 }
1450 x = x.square();
1451 n = n.quotient(two);
1452 }
1453
1454 return aux;
1455};
1456
1457/*
1458 Function: modPow
1459 Raise a <BigInteger> to a power (mod m).
1460
1461 Because it is reduced by a modulus, <modPow> is not limited by
1462 <BigInteger.MAX_EXP> like <pow>.
1463
1464 Parameters:
1465
1466 exponent - The exponent to raise *this* by. Must be positive.
1467 modulus - The modulus.
1468
1469 Returns:
1470
1471 *this* ^ *exponent* (mod *modulus*).
1472
1473 See Also:
1474
1475 <pow>, <mod>
1476*/
1477BigInteger.prototype.modPow = function(exponent, modulus) {
1478 var result = ONE;
1479 var base = this;
1480
1481 while (exponent.isPositive()) {
1482 if (exponent.isOdd()) {
1483 result = result.multiply(base).remainder(modulus);
1484 }
1485
1486 exponent = exponent.quotient(BigInteger.small[2]);
1487 if (exponent.isPositive()) {
1488 base = base.square().remainder(modulus);
1489 }
1490 }
1491
1492 return result;
1493};
1494
1495/*
1496 Function: log
1497 Get the natural logarithm of a <BigInteger> as a native JavaScript number.
1498
1499 This is equivalent to
1500
1501 > Math.log(this.toJSValue())
1502
1503 but handles values outside of the native number range.
1504
1505 Returns:
1506
1507 log( *this* )
1508
1509 See Also:
1510
1511 <toJSValue>
1512*/
1513BigInteger.prototype.log = function() {
1514 switch (this._s) {
1515 case 0: return -Infinity;
1516 case -1: return NaN;
1517 default: // Fall through.
1518 }
1519
1520 var l = this._d.length;
1521
1522 if (l*BigInteger_base_log10 < 30) {
1523 return Math.log(this.valueOf());
1524 }
1525
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);
1529};
1530
1531/*
1532 Function: valueOf
1533 Convert a <BigInteger> to a native JavaScript integer.
1534
1535 This is called automatically by JavaScipt to convert a <BigInteger> to a
1536 native value.
1537
1538 Returns:
1539
1540 > parseInt(this.toString(), 10)
1541
1542 See Also:
1543
1544 <toString>, <toJSValue>
1545*/
1546BigInteger.prototype.valueOf = function() {
1547 return parseInt(this.toString(), 10);
1548};
1549
1550/*
1551 Function: toJSValue
1552 Convert a <BigInteger> to a native JavaScript integer.
1553
1554 This is the same as valueOf, but more explicitly named.
1555
1556 Returns:
1557
1558 > parseInt(this.toString(), 10)
1559
1560 See Also:
1561
1562 <toString>, <valueOf>
1563*/
1564BigInteger.prototype.toJSValue = function() {
1565 return parseInt(this.toString(), 10);
1566};
1567
1568var MAX_EXP = BigInteger(0x7FFFFFFF);
1569// Constant: MAX_EXP
1570// The largest exponent allowed in <pow> and <exp10> (0x7FFFFFFF or 2147483647).
1571BigInteger.MAX_EXP = MAX_EXP;
1572
1573(function() {
1574 function makeUnary(fn) {
1575 return function(a) {
1576 return fn.call(BigInteger(a));
1577 };
1578 }
1579
1580 function makeBinary(fn) {
1581 return function(a, b) {
1582 return fn.call(BigInteger(a), BigInteger(b));
1583 };
1584 }
1585
1586 function makeTrinary(fn) {
1587 return function(a, b, c) {
1588 return fn.call(BigInteger(a), BigInteger(b), BigInteger(c));
1589 };
1590 }
1591
1592 (function() {
1593 var i, fn;
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"];
1597
1598 for (i = 0; i < unary.length; i++) {
1599 fn = unary[i];
1600 BigInteger[fn] = makeUnary(BigInteger.prototype[fn]);
1601 }
1602
1603 for (i = 0; i < binary.length; i++) {
1604 fn = binary[i];
1605 BigInteger[fn] = makeBinary(BigInteger.prototype[fn]);
1606 }
1607
1608 for (i = 0; i < trinary.length; i++) {
1609 fn = trinary[i];
1610 BigInteger[fn] = makeTrinary(BigInteger.prototype[fn]);
1611 }
1612
1613 BigInteger.exp10 = function(x, n) {
1614 return BigInteger(x).exp10(n);
1615 };
1616 })();
1617})();
1618
1619exports.BigInteger = BigInteger;
1620})(typeof exports !== 'undefined' ? exports : this);