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