https://zgspws.com/js/BigInt.js

1
2
3var biRadixBase = 2;
4var biRadixBits = 16;
5var bitsPerDigit = biRadixBits;
6var biRadix = 1 << 16; // = 2^16 = 65536
7var biHalfRadix = biRadix >>> 1;
8var biRadixSquared = biRadix * biRadix;
9var maxDigitVal = biRadix - 1;
10var maxInteger = 9999999999999998; 
11
12// maxDigits:
13// Change this to accommodate your largest number size. Use setMaxDigits()
14// to change it!
15//
16// In general, if you're working with numbers of size N bits, you'll need 2*N
17// bits of storage. Each digit holds 16 bits. So, a 1024-bit key will need
18//
19// 1024 * 2 / 16 = 128 digits of storage.
20//
21
22var maxDigits;
23var ZERO_ARRAY;
24var bigZero, bigOne;
25
26function setMaxDigits(value)
27{
28	maxDigits = value;
29	ZERO_ARRAY = new Array(maxDigits);
30	for (var iza = 0; iza < ZERO_ARRAY.length; iza++) ZERO_ARRAY[iza] = 0;
31	bigZero = new BigInt();
32	bigOne = new BigInt();
33	bigOne.digits[0] = 1;
34}
35
36setMaxDigits(20);
37
38// The maximum number of digits in base 10 you can convert to an
39// integer without JavaScript throwing up on you.
40var dpl10 = 15;
41// lr10 = 10 ^ dpl10
42var lr10 = biFromNumber(1000000000000000);
43
44function BigInt(flag)
45{
46	if (typeof flag == "boolean" && flag == true) {
47		this.digits = null;
48	}
49	else {
50		this.digits = ZERO_ARRAY.slice(0);
51	}
52	this.isNeg = false;
53}
54
55function biFromDecimal(s)
56{
57	var isNeg = s.charAt(0) == '-';
58	var i = isNeg ? 1 : 0;
59	var result;
60	// Skip leading zeros.
61	while (i < s.length && s.charAt(i) == '0') ++i;
62	if (i == s.length) {
63		result = new BigInt();
64	}
65	else {
66		var digitCount = s.length - i;
67		var fgl = digitCount % dpl10;
68		if (fgl == 0) fgl = dpl10;
69		result = biFromNumber(Number(s.substr(i, fgl)));
70		i += fgl;
71		while (i < s.length) {
72			result = biAdd(biMultiply(result, lr10),
73			               biFromNumber(Number(s.substr(i, dpl10))));
74			i += dpl10;
75		}
76		result.isNeg = isNeg;
77	}
78	return result;
79}
80
81function biCopy(bi)
82{
83	var result = new BigInt(true);
84	result.digits = bi.digits.slice(0);
85	result.isNeg = bi.isNeg;
86	return result;
87}
88
89function biFromNumber(i)
90{
91	var result = new BigInt();
92	result.isNeg = i < 0;
93	i = Math.abs(i);
94	var j = 0;
95	while (i > 0) {
96		result.digits[j++] = i & maxDigitVal;
97		i = Math.floor(i / biRadix);
98	}
99	return result;
100}
101
102function reverseStr(s)
103{
104	var result = "";
105	for (var i = s.length - 1; i > -1; --i) {
106		result += s.charAt(i);
107	}
108	return result;
109}
110
111var hexatrigesimalToChar = new Array(
112 '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
113 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j',
114 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't',
115 'u', 'v', 'w', 'x', 'y', 'z'
116);
117
118function biToString(x, radix)
119	// 2 <= radix <= 36
120{
121	var b = new BigInt();
122	b.digits[0] = radix;
123	var qr = biDivideModulo(x, b);
124	var result = hexatrigesimalToChar[qr[1].digits[0]];
125	while (biCompare(qr[0], bigZero) == 1) {
126		qr = biDivideModulo(qr[0], b);
127		digit = qr[1].digits[0];
128		result += hexatrigesimalToChar[qr[1].digits[0]];
129	}
130	return (x.isNeg ? "-" : "") + reverseStr(result);
131}
132
133function biToDecimal(x)
134{
135	var b = new BigInt();
136	b.digits[0] = 10;
137	var qr = biDivideModulo(x, b);
138	var result = String(qr[1].digits[0]);
139	while (biCompare(qr[0], bigZero) == 1) {
140		qr = biDivideModulo(qr[0], b);
141		result += String(qr[1].digits[0]);
142	}
143	return (x.isNeg ? "-" : "") + reverseStr(result);
144}
145
146var hexToChar = new Array('0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
147                          'a', 'b', 'c', 'd', 'e', 'f');
148
149function digitToHex(n)
150{
151	var mask = 0xf;
152	var result = "";
153	for (i = 0; i < 4; ++i) {
154		result += hexToChar[n & mask];
155		n >>>= 4;
156	}
157	return reverseStr(result);
158}
159
160function biToHex(x)
161{
162	var result = "";
163	var n = biHighIndex(x);
164	for (var i = biHighIndex(x); i > -1; --i) {
165		result += digitToHex(x.digits[i]);
166	}
167	return result;
168}
169
170function charToHex(c)
171{
172	var ZERO = 48;
173	var NINE = ZERO + 9;
174	var littleA = 97;
175	var littleZ = littleA + 25;
176	var bigA = 65;
177	var bigZ = 65 + 25;
178	var result;
179
180	if (c >= ZERO && c <= NINE) {
181		result = c - ZERO;
182	} else if (c >= bigA && c <= bigZ) {
183		result = 10 + c - bigA;
184	} else if (c >= littleA && c <= littleZ) {
185		result = 10 + c - littleA;
186	} else {
187		result = 0;
188	}
189	return result;
190}
191
192function hexToDigit(s)
193{
194	var result = 0;
195	var sl = Math.min(s.length, 4);
196	for (var i = 0; i < sl; ++i) {
197		result <<= 4;
198		result |= charToHex(s.charCodeAt(i))
199	}
200	return result;
201}
202
203function biFromHex(s)
204{
205	var result = new BigInt();
206	var sl = s.length;
207	for (var i = sl, j = 0; i > 0; i -= 4, ++j) {

208		result.digits[j] = hexToDigit(s.substr(Math.max(i - 4, 0), Math.min(i, 4)));
209	}
210	return result;
211}
212
213function biFromString(s, radix)
214{
215	var isNeg = s.charAt(0) == '-';
216	var istop = isNeg ? 1 : 0;
217	var result = new BigInt();
218	var place = new BigInt();
219	place.digits[0] = 1; // radix^0
220	for (var i = s.length - 1; i >= istop; i--) {
221		var c = s.charCodeAt(i);
222		var digit = charToHex(c);
223		var biDigit = biMultiplyDigit(place, digit);
224		result = biAdd(result, biDigit);
225		place = biMultiplyDigit(place, radix);
226	}
227	result.isNeg = isNeg;
228	return result;
229}
230
231function biDump(b)
232{
233	return (b.isNeg ? "-" : "") + b.digits.join(" ");
234}
235
236function biAdd(x, y)
237{
238	var result;
239
240	if (x.isNeg != y.isNeg) {
241		y.isNeg = !y.isNeg;
242		result = biSubtract(x, y);
243		y.isNeg = !y.isNeg;
244	}
245	else {
246		result = new BigInt();
247		var c = 0;
248		var n;
249		for (var i = 0; i < x.digits.length; ++i) {
250			n = x.digits[i] + y.digits[i] + c;
251			result.digits[i] = n % biRadix;
252			c = Number(n >= biRadix);
253		}
254		result.isNeg = x.isNeg;
255	}
256	return result;
257}
258
259function biSubtract(x, y)
260{
261	var result;
262	if (x.isNeg != y.isNeg) {
263		y.isNeg = !y.isNeg;
264		result = biAdd(x, y);
265		y.isNeg = !y.isNeg;
266	} else {
267		result = new BigInt();
268		var n, c;
269		c = 0;
270		for (var i = 0; i < x.digits.length; ++i) {
271			n = x.digits[i] - y.digits[i] + c;
272			result.digits[i] = n % biRadix;
273			// Stupid non-conforming modulus operation.
274			if (result.digits[i] < 0) result.digits[i] += biRadix;
275			c = 0 - Number(n < 0);
276		}
277		// Fix up the negative sign, if any.
278		if (c == -1) {
279			c = 0;
280			for (var i = 0; i < x.digits.length; ++i) {
281				n = 0 - result.digits[i] + c;
282				result.digits[i] = n % biRadix;
283				// Stupid non-conforming modulus operation.
284				if (result.digits[i] < 0) result.digits[i] += biRadix;
285				c = 0 - Number(n < 0);
286			}
287			// Result is opposite sign of arguments.
288			result.isNeg = !x.isNeg;
289		} else {
290			// Result is same sign.
291			result.isNeg = x.isNeg;
292		}
293	}
294	return result;
295}
296
297function biHighIndex(x)
298{
299	var result = x.digits.length - 1;
300	while (result > 0 && x.digits[result] == 0) --result;
301	return result;
302}
303
304function biNumBits(x)
305{
306	var n = biHighIndex(x);
307	var d = x.digits[n];
308	var m = (n + 1) * bitsPerDigit;
309	var result;
310	for (result = m; result > m - bitsPerDigit; --result) {
311		if ((d & 0x8000) != 0) break;
312		d <<= 1;
313	}
314	return result;
315}
316
317function biMultiply(x, y)
318{
319	var result = new BigInt();
320	var c;
321	var n = biHighIndex(x);
322	var t = biHighIndex(y);
323	var u, uv, k;
324
325	for (var i = 0; i <= t; ++i) {
326		c = 0;
327		k = i;
328		for (j = 0; j <= n; ++j, ++k) {
329			uv = result.digits[k] + x.digits[j] * y.digits[i] + c;
330			result.digits[k] = uv & maxDigitVal;
331			c = uv >>> biRadixBits;
332			//c = Math.floor(uv / biRadix);
333		}
334		result.digits[i + n + 1] = c;
335	}
336	// Someone give me a logical xor, please.
337	result.isNeg = x.isNeg != y.isNeg;
338	return result;
339}
340
341function biMultiplyDigit(x, y)
342{
343	var n, c, uv;
344
345	result = new BigInt();
346	n = biHighIndex(x);
347	c = 0;
348	for (var j = 0; j <= n; ++j) {
349		uv = result.digits[j] + x.digits[j] * y + c;
350		result.digits[j] = uv & maxDigitVal;
351		c = uv >>> biRadixBits;
352		//c = Math.floor(uv / biRadix);
353	}
354	result.digits[1 + n] = c;
355	return result;
356}
357
358function arrayCopy(src, srcStart, dest, destStart, n)
359{
360	var m = Math.min(srcStart + n, src.length);
361	for (var i = srcStart, j = destStart; i < m; ++i, ++j) {
362		dest[j] = src[i];

363	}
364}
365
366var highBitMasks = new Array(0x0000, 0x8000, 0xC000, 0xE000, 0xF000, 0xF800,
367                             0xFC00, 0xFE00, 0xFF00, 0xFF80, 0xFFC0, 0xFFE0,
368                             0xFFF0, 0xFFF8, 0xFFFC, 0xFFFE, 0xFFFF);
369
370function biShiftLeft(x, n)
371{
372	var digitCount = Math.floor(n / bitsPerDigit);
373	var result = new BigInt();
374	arrayCopy(x.digits, 0, result.digits, digitCount,
375	          result.digits.length - digitCount);
376	var bits = n % bitsPerDigit;
377	var rightBits = bitsPerDigit - bits;
378	for (var i = result.digits.length - 1, i1 = i - 1; i > 0; --i, --i1) {
379		result.digits[i] = ((result.digits[i] << bits) & maxDigitVal) |
380		                   ((result.digits[i1] & highBitMasks[bits]) >>>
381		                    (rightBits));
382	}
383	result.digits[0] = ((result.digits[i] << bits) & maxDigitVal);
384	result.isNeg = x.isNeg;
385	return result;
386}
387
388var lowBitMasks = new Array(0x0000, 0x0001, 0x0003, 0x0007, 0x000F, 0x001F,
389                            0x003F, 0x007F, 0x00FF, 0x01FF, 0x03FF, 0x07FF,
390                            0x0FFF, 0x1FFF, 0x3FFF, 0x7FFF, 0xFFFF);
391
392function biShiftRight(x, n)
393{
394	var digitCount = Math.floor(n / bitsPerDigit);
395	var result = new BigInt();
396	arrayCopy(x.digits, digitCount, result.digits, 0,
397	          x.digits.length - digitCount);
398	var bits = n % bitsPerDigit;
399	var leftBits = bitsPerDigit - bits;
400	for (var i = 0, i1 = i + 1; i < result.digits.length - 1; ++i, ++i1) {
401		result.digits[i] = (result.digits[i] >>> bits) |
402		                   ((result.digits[i1] & lowBitMasks[bits]) << leftBits);
403	}
404	result.digits[result.digits.length - 1] >>>= bits;
405	result.isNeg = x.isNeg;
406	return result;
407}
408
409function biMultiplyByRadixPower(x, n)
410{
411	var result = new BigInt();
412	arrayCopy(x.digits, 0, result.digits, n, result.digits.length - n);
413	return result;
414}
415
416function biDivideByRadixPower(x, n)
417{
418	var result = new BigInt();
419	arrayCopy(x.digits, n, result.digits, 0, result.digits.length - n);
420	return result;
421}
422
423function biModuloByRadixPower(x, n)
424{
425	var result = new BigInt();
426	arrayCopy(x.digits, 0, result.digits, 0, n);
427	return result;
428}
429
430function biCompare(x, y)
431{
432	if (x.isNeg != y.isNeg) {
433		return 1 - 2 * Number(x.isNeg);
434	}
435	for (var i = x.digits.length - 1; i >= 0; --i) {
436		if (x.digits[i] != y.digits[i]) {
437			if (x.isNeg) {
438				return 1 - 2 * Number(x.digits[i] > y.digits[i]);
439			} else {
440				return 1 - 2 * Number(x.digits[i] < y.digits[i]);
441			}
442		}
443	}
444	return 0;
445}
446
447function biDivideModulo(x, y)
448{
449	var nb = biNumBits(x);
450	var tb = biNumBits(y);
451	var origYIsNeg = y.isNeg;
452	var q, r;
453	if (nb < tb) {
454		// |x| < |y|
455		if (x.isNeg) {
456			q = biCopy(bigOne);
457			q.isNeg = !y.isNeg;
458			x.isNeg = false;
459			y.isNeg = false;
460			r = biSubtract(y, x);
461			// Restore signs, 'cause they're references.
462			x.isNeg = true;
463			y.isNeg = origYIsNeg;
464		} else {
465			q = new BigInt();
466			r = biCopy(x);
467		}
468		return new Array(q, r);
469	}
470
471	q = new BigInt();
472	r = x;
473
474	// Normalize Y.
475	var t = Math.ceil(tb / bitsPerDigit) - 1;
476	var lambda = 0;
477	while (y.digits[t] < biHalfRadix) {
478		y = biShiftLeft(y, 1);
479		++lambda;
480		++tb;
481		t = Math.ceil(tb / bitsPerDigit) - 1;
482	}
483	// Shift r over to keep the quotient constant. We'll shift the
484	// remainder back at the end.
485	r = biShiftLeft(r, lambda);
486	nb += lambda; // Update the bit count for x.
487	var n = Math.ceil(nb / bitsPerDigit) - 1;
488
489	var b = biMultiplyByRadixPower(y, n - t);
490	while (biCompare(r, b) != -1) {
491		++q.digits[n - t];
492		r = biSubtract(r, b);
493	}
494	for (var i = n; i > t; --i) {
495    var ri = (i >= r.digits.length) ? 0 : r.digits[i];
496    var ri1 = (i - 1 >= r.digits.length) ? 0 : r.digits[i - 1];
497    var ri2 = (i - 2 >= r.digits.length) ? 0 : r.digits[i - 2];
498    var yt = (t >= y.digits.length) ? 0 : y.digits[t];
499    var yt1 = (t - 1 >= y.digits.length) ? 0 : y.digits[t - 1];
500		if (ri == yt) {
501			q.digits[i - t - 1] = maxDigitVal;
502		} else {
503			q.digits[i - t - 1] = Math.floor((ri * biRadix + ri1) / yt);
504		}
505
506		var c1 = q.digits[i - t - 1] * ((yt * biRadix) + yt1);

507		var c2 = (ri * biRadixSquared) + ((ri1 * biRadix) + ri2);
508		while (c1 > c2) {
509			--q.digits[i - t - 1];
510			c1 = q.digits[i - t - 1] * ((yt * biRadix) | yt1);
511			c2 = (ri * biRadix * biRadix) + ((ri1 * biRadix) + ri2);
512		}
513
514		b = biMultiplyByRadixPower(y, i - t - 1);
515		r = biSubtract(r, biMultiplyDigit(b, q.digits[i - t - 1]));
516		if (r.isNeg) {
517			r = biAdd(r, b);
518			--q.digits[i - t - 1];
519		}
520	}
521	r = biShiftRight(r, lambda);
522	// Fiddle with the signs and stuff to make sure that 0 <= r < y.
523	q.isNeg = x.isNeg != origYIsNeg;
524	if (x.isNeg) {
525		if (origYIsNeg) {
526			q = biAdd(q, bigOne);
527		} else {
528			q = biSubtract(q, bigOne);
529		}
530		y = biShiftRight(y, lambda);
531		r = biSubtract(y, r);
532	}
533	// Check for the unbelievably stupid degenerate case of r == -0.
534	if (r.digits[0] == 0 && biHighIndex(r) == 0) r.isNeg = false;
535
536	return new Array(q, r);
537}
538
539function biDivide(x, y)
540{
541	return biDivideModulo(x, y)[0];
542}
543
544function biModulo(x, y)
545{
546	return biDivideModulo(x, y)[1];
547}
548
549function biMultiplyMod(x, y, m)
550{
551	return biModulo(biMultiply(x, y), m);
552}
553
554function biPow(x, y)
555{
556	var result = bigOne;
557	var a = x;
558	while (true) {
559		if ((y & 1) != 0) result = biMultiply(result, a);
560		y >>= 1;
561		if (y == 0) break;
562		a = biMultiply(a, a);
563	}
564	return result;
565}
566
567function biPowMod(x, y, m)
568{
569	var result = bigOne;
570	var a = x;
571	var k = y;
572	while (true) {
573		if ((k.digits[0] & 1) != 0) result = biMultiplyMod(result, a, m);
574		k = biShiftRight(k, 1);
575		if (k.digits[0] == 0 && biHighIndex(k) == 0) break;
576		a = biMultiplyMod(a, a, m);
577	}
578	return result;
579}
580