BigInt.js 17 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614
  1. // BigInt, a suite of routines for performing multiple-precision arithmetic in
  2. // JavaScript.
  3. //
  4. // Copyright 1998-2005 David Shapiro.
  5. //
  6. // You may use, re-use, abuse,
  7. // copy, and modify this code to your liking, but please keep this header.
  8. // Thanks!
  9. //
  10. // Dave Shapiro
  11. // dave@ohdave.com
  12. // IMPORTANT THING: Be sure to set maxDigits according to your precision
  13. // needs. Use the setMaxDigits() function to do this. See comments below.
  14. //
  15. // Tweaked by Ian Bunning
  16. // Alterations:
  17. // Fix bug in function biFromHex(s) to allow
  18. // parsing of strings of length != 0 (mod 4)
  19. // Changes made by Dave Shapiro as of 12/30/2004:
  20. //
  21. // The BigInt() constructor doesn't take a string anymore. If you want to
  22. // create a BigInt from a string, use biFromDecimal() for base-10
  23. // representations, biFromHex() for base-16 representations, or
  24. // biFromString() for base-2-to-36 representations.
  25. //
  26. // biFromArray() has been removed. Use biCopy() instead, passing a BigInt
  27. // instead of an array.
  28. //
  29. // The BigInt() constructor now only constructs a zeroed-out array.
  30. // Alternatively, if you pass <true>, it won't construct any array. See the
  31. // biCopy() method for an example of this.
  32. //
  33. // Be sure to set maxDigits depending on your precision needs. The default
  34. // zeroed-out array ZERO_ARRAY is constructed inside the setMaxDigits()
  35. // function. So use this function to set the variable. DON'T JUST SET THE
  36. // VALUE. USE THE FUNCTION.
  37. //
  38. // ZERO_ARRAY exists to hopefully speed up construction of BigInts(). By
  39. // precalculating the zero array, we can just use slice(0) to make copies of
  40. // it. Presumably this calls faster native code, as opposed to setting the
  41. // elements one at a time. I have not done any timing tests to verify this
  42. // claim.
  43. // Max number = 10^16 - 2 = 9999999999999998;
  44. // 2^53 = 9007199254740992;
  45. var biRadixBase = 2;
  46. var biRadixBits = 16;
  47. var bitsPerDigit = biRadixBits;
  48. var biRadix = 1 << 16;
  49. // = 2^16 = 65536
  50. var biHalfRadix = biRadix >>> 1;
  51. var biRadixSquared = biRadix * biRadix;
  52. var maxDigitVal = biRadix - 1;
  53. var maxInteger = 9999999999999998;
  54. // maxDigits:
  55. // Change this to accommodate your largest number size. Use setMaxDigits()
  56. // to change it!
  57. //
  58. // In general, if you're working with numbers of size N bits, you'll need 2*N
  59. // bits of storage. Each digit holds 16 bits. So, a 1024-bit key will need
  60. //
  61. // 1024 * 2 / 16 = 128 digits of storage.
  62. //
  63. var maxDigits;
  64. var ZERO_ARRAY;
  65. var bigZero, bigOne;
  66. function setMaxDigits(value) {
  67. maxDigits = value;
  68. ZERO_ARRAY = new Array(maxDigits);
  69. for (var iza = 0; iza < ZERO_ARRAY.length; iza++)
  70. ZERO_ARRAY[iza] = 0;
  71. bigZero = new BigInt();
  72. bigOne = new BigInt();
  73. bigOne.digits[0] = 1;
  74. }
  75. setMaxDigits(20);
  76. // The maximum number of digits in base 10 you can convert to an
  77. // integer without JavaScript throwing up on you.
  78. var dpl10 = 15;
  79. // lr10 = 10 ^ dpl10
  80. var lr10 = biFromNumber(1000000000000000);
  81. function BigInt(flag) {
  82. if (typeof flag == "boolean" && flag == true) {
  83. this.digits = null;
  84. } else {
  85. this.digits = ZERO_ARRAY.slice(0);
  86. }
  87. this.isNeg = false;
  88. }
  89. function biFromDecimal(s) {
  90. var isNeg = s.charAt(0) == '-';
  91. var i = isNeg ? 1 : 0;
  92. var result;
  93. // Skip leading zeros.
  94. while (i < s.length && s.charAt(i) == '0')
  95. ++i;
  96. if (i == s.length) {
  97. result = new BigInt();
  98. } else {
  99. var digitCount = s.length - i;
  100. var fgl = digitCount % dpl10;
  101. if (fgl == 0)
  102. fgl = dpl10;
  103. result = biFromNumber(Number(s.substr(i, fgl)));
  104. i += fgl;
  105. while (i < s.length) {
  106. result = biAdd(biMultiply(result, lr10), biFromNumber(Number(s.substr(i, dpl10))));
  107. i += dpl10;
  108. }
  109. result.isNeg = isNeg;
  110. }
  111. return result;
  112. }
  113. function biCopy(bi) {
  114. var result = new BigInt(true);
  115. result.digits = bi.digits.slice(0);
  116. result.isNeg = bi.isNeg;
  117. return result;
  118. }
  119. function biFromNumber(i) {
  120. var result = new BigInt();
  121. result.isNeg = i < 0;
  122. i = Math.abs(i);
  123. var j = 0;
  124. while (i > 0) {
  125. result.digits[j++] = i & maxDigitVal;
  126. i >>= biRadixBits;
  127. }
  128. return result;
  129. }
  130. function reverseStr(s) {
  131. var result = "";
  132. for (var i = s.length - 1; i > -1; --i) {
  133. result += s.charAt(i);
  134. }
  135. return result;
  136. }
  137. var hexatrigesimalToChar = new Array('0','1','2','3','4','5','6','7','8','9','a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z');
  138. function biToString(x, radix) // 2 <= radix <= 36
  139. {
  140. var b = new BigInt();
  141. b.digits[0] = radix;
  142. var qr = biDivideModulo(x, b);
  143. var result = hexatrigesimalToChar[qr[1].digits[0]];
  144. while (biCompare(qr[0], bigZero) == 1) {
  145. qr = biDivideModulo(qr[0], b);
  146. digit = qr[1].digits[0];
  147. result += hexatrigesimalToChar[qr[1].digits[0]];
  148. }
  149. return (x.isNeg ? "-" : "") + reverseStr(result);
  150. }
  151. function biToDecimal(x) {
  152. var b = new BigInt();
  153. b.digits[0] = 10;
  154. var qr = biDivideModulo(x, b);
  155. var result = String(qr[1].digits[0]);
  156. while (biCompare(qr[0], bigZero) == 1) {
  157. qr = biDivideModulo(qr[0], b);
  158. result += String(qr[1].digits[0]);
  159. }
  160. return (x.isNeg ? "-" : "") + reverseStr(result);
  161. }
  162. var hexToChar = new Array('0','1','2','3','4','5','6','7','8','9','a','b','c','d','e','f');
  163. function digitToHex(n) {
  164. var mask = 0xf;
  165. var result = "";
  166. for (i = 0; i < 4; ++i) {
  167. result += hexToChar[n & mask];
  168. n >>>= 4;
  169. }
  170. return reverseStr(result);
  171. }
  172. function biToHex(x) {
  173. var result = "";
  174. var n = biHighIndex(x);
  175. for (var i = biHighIndex(x); i > -1; --i) {
  176. result += digitToHex(x.digits[i]);
  177. }
  178. return result;
  179. }
  180. function charToHex(c) {
  181. var ZERO = 48;
  182. var NINE = ZERO + 9;
  183. var littleA = 97;
  184. var littleZ = littleA + 25;
  185. var bigA = 65;
  186. var bigZ = 65 + 25;
  187. var result;
  188. if (c >= ZERO && c <= NINE) {
  189. result = c - ZERO;
  190. } else if (c >= bigA && c <= bigZ) {
  191. result = 10 + c - bigA;
  192. } else if (c >= littleA && c <= littleZ) {
  193. result = 10 + c - littleA;
  194. } else {
  195. result = 0;
  196. }
  197. return result;
  198. }
  199. function hexToDigit(s) {
  200. var result = 0;
  201. var sl = Math.min(s.length, 4);
  202. for (var i = 0; i < sl; ++i) {
  203. result <<= 4;
  204. result |= charToHex(s.charCodeAt(i))
  205. }
  206. return result;
  207. }
  208. function biFromHex(s) {
  209. var result = new BigInt();
  210. var sl = s.length;
  211. for (var i = sl, j = 0; i > 0; i -= 4,
  212. ++j) {
  213. result.digits[j] = hexToDigit(s.substr(Math.max(i - 4, 0), Math.min(i, 4)));
  214. }
  215. return result;
  216. }
  217. function biFromString(s, radix) {
  218. var isNeg = s.charAt(0) == '-';
  219. var istop = isNeg ? 1 : 0;
  220. var result = new BigInt();
  221. var place = new BigInt();
  222. place.digits[0] = 1;
  223. // radix^0
  224. for (var i = s.length - 1; i >= istop; i--) {
  225. var c = s.charCodeAt(i);
  226. var digit = charToHex(c);
  227. var biDigit = biMultiplyDigit(place, digit);
  228. result = biAdd(result, biDigit);
  229. place = biMultiplyDigit(place, radix);
  230. }
  231. result.isNeg = isNeg;
  232. return result;
  233. }
  234. function biToBytes(x) // Returns a string containing raw bytes.
  235. {
  236. var result = "";
  237. for (var i = biHighIndex(x); i > -1; --i) {
  238. result += digitToBytes(x.digits[i]);
  239. }
  240. return result;
  241. }
  242. function digitToBytes(n) // Convert two-byte digit to string containing both bytes.
  243. {
  244. var c1 = String.fromCharCode(n & 0xff);
  245. n >>>= 8;
  246. var c2 = String.fromCharCode(n & 0xff);
  247. return c2 + c1;
  248. }
  249. function biDump(b) {
  250. return (b.isNeg ? "-" : "") + b.digits.join(" ");
  251. }
  252. function biAdd(x, y) {
  253. var result;
  254. if (x.isNeg != y.isNeg) {
  255. y.isNeg = !y.isNeg;
  256. result = biSubtract(x, y);
  257. y.isNeg = !y.isNeg;
  258. } else {
  259. result = new BigInt();
  260. var c = 0;
  261. var n;
  262. for (var i = 0; i < x.digits.length; ++i) {
  263. n = x.digits[i] + y.digits[i] + c;
  264. result.digits[i] = n & 0xffff;
  265. c = Number(n >= biRadix);
  266. }
  267. result.isNeg = x.isNeg;
  268. }
  269. return result;
  270. }
  271. function biSubtract(x, y) {
  272. var result;
  273. if (x.isNeg != y.isNeg) {
  274. y.isNeg = !y.isNeg;
  275. result = biAdd(x, y);
  276. y.isNeg = !y.isNeg;
  277. } else {
  278. result = new BigInt();
  279. var n, c;
  280. c = 0;
  281. for (var i = 0; i < x.digits.length; ++i) {
  282. n = x.digits[i] - y.digits[i] + c;
  283. result.digits[i] = n & 0xffff;
  284. // Stupid non-conforming modulus operation.
  285. if (result.digits[i] < 0)
  286. result.digits[i] += biRadix;
  287. c = 0 - Number(n < 0);
  288. }
  289. // Fix up the negative sign, if any.
  290. if (c == -1) {
  291. c = 0;
  292. for (var i = 0; i < x.digits.length; ++i) {
  293. n = 0 - result.digits[i] + c;
  294. result.digits[i] = n & 0xffff;
  295. // Stupid non-conforming modulus operation.
  296. if (result.digits[i] < 0)
  297. result.digits[i] += biRadix;
  298. c = 0 - Number(n < 0);
  299. }
  300. // Result is opposite sign of arguments.
  301. result.isNeg = !x.isNeg;
  302. } else {
  303. // Result is same sign.
  304. result.isNeg = x.isNeg;
  305. }
  306. }
  307. return result;
  308. }
  309. function biHighIndex(x) {
  310. var result = x.digits.length - 1;
  311. while (result > 0 && x.digits[result] == 0)
  312. --result;
  313. return result;
  314. }
  315. function biNumBits(x) {
  316. var n = biHighIndex(x);
  317. var d = x.digits[n];
  318. var m = (n + 1) * bitsPerDigit;
  319. var result;
  320. for (result = m; result > m - bitsPerDigit; --result) {
  321. if ((d & 0x8000) != 0)
  322. break;
  323. d <<= 1;
  324. }
  325. return result;
  326. }
  327. function biMultiply(x, y) {
  328. var result = new BigInt();
  329. var c;
  330. var n = biHighIndex(x);
  331. var t = biHighIndex(y);
  332. var u, uv, k;
  333. for (var i = 0; i <= t; ++i) {
  334. c = 0;
  335. k = i;
  336. for (j = 0; j <= n; ++j,
  337. ++k) {
  338. uv = result.digits[k] + x.digits[j] * y.digits[i] + c;
  339. result.digits[k] = uv & maxDigitVal;
  340. c = uv >>> biRadixBits;
  341. }
  342. result.digits[i + n + 1] = c;
  343. }
  344. // Someone give me a logical xor, please.
  345. result.isNeg = x.isNeg != y.isNeg;
  346. return result;
  347. }
  348. function biMultiplyDigit(x, y) {
  349. var n, c, uv;
  350. result = new BigInt();
  351. n = biHighIndex(x);
  352. c = 0;
  353. for (var j = 0; j <= n; ++j) {
  354. uv = result.digits[j] + x.digits[j] * y + c;
  355. result.digits[j] = uv & maxDigitVal;
  356. c = uv >>> biRadixBits;
  357. }
  358. result.digits[1 + n] = c;
  359. return result;
  360. }
  361. function arrayCopy(src, srcStart, dest, destStart, n) {
  362. var m = Math.min(srcStart + n, src.length);
  363. for (var i = srcStart, j = destStart; i < m; ++i,
  364. ++j) {
  365. dest[j] = src[i];
  366. }
  367. }
  368. var highBitMasks = new Array(0x0000,0x8000,0xC000,0xE000,0xF000,0xF800,0xFC00,0xFE00,0xFF00,0xFF80,0xFFC0,0xFFE0,0xFFF0,0xFFF8,0xFFFC,0xFFFE,0xFFFF);
  369. function biShiftLeft(x, n) {
  370. var digitCount = Math.floor(n / bitsPerDigit);
  371. var result = new BigInt();
  372. arrayCopy(x.digits, 0, result.digits, digitCount, result.digits.length - digitCount);
  373. var bits = n % bitsPerDigit;
  374. var rightBits = bitsPerDigit - bits;
  375. for (var i = result.digits.length - 1, i1 = i - 1; i > 0; --i,
  376. --i1) {
  377. result.digits[i] = ((result.digits[i] << bits) & maxDigitVal) | ((result.digits[i1] & highBitMasks[bits]) >>> (rightBits));
  378. }
  379. result.digits[0] = ((result.digits[i] << bits) & maxDigitVal);
  380. result.isNeg = x.isNeg;
  381. return result;
  382. }
  383. var lowBitMasks = new Array(0x0000,0x0001,0x0003,0x0007,0x000F,0x001F,0x003F,0x007F,0x00FF,0x01FF,0x03FF,0x07FF,0x0FFF,0x1FFF,0x3FFF,0x7FFF,0xFFFF);
  384. function biShiftRight(x, n) {
  385. var digitCount = Math.floor(n / bitsPerDigit);
  386. var result = new BigInt();
  387. arrayCopy(x.digits, digitCount, result.digits, 0, x.digits.length - digitCount);
  388. var bits = n % bitsPerDigit;
  389. var leftBits = bitsPerDigit - bits;
  390. for (var i = 0, i1 = i + 1; i < result.digits.length - 1; ++i,
  391. ++i1) {
  392. result.digits[i] = (result.digits[i] >>> bits) | ((result.digits[i1] & lowBitMasks[bits]) << leftBits);
  393. }
  394. result.digits[result.digits.length - 1] >>>= bits;
  395. result.isNeg = x.isNeg;
  396. return result;
  397. }
  398. function biMultiplyByRadixPower(x, n) {
  399. var result = new BigInt();
  400. arrayCopy(x.digits, 0, result.digits, n, result.digits.length - n);
  401. return result;
  402. }
  403. function biDivideByRadixPower(x, n) {
  404. var result = new BigInt();
  405. arrayCopy(x.digits, n, result.digits, 0, result.digits.length - n);
  406. return result;
  407. }
  408. function biModuloByRadixPower(x, n) {
  409. var result = new BigInt();
  410. arrayCopy(x.digits, 0, result.digits, 0, n);
  411. return result;
  412. }
  413. function biCompare(x, y) {
  414. if (x.isNeg != y.isNeg) {
  415. return 1 - 2 * Number(x.isNeg);
  416. }
  417. for (var i = x.digits.length - 1; i >= 0; --i) {
  418. if (x.digits[i] != y.digits[i]) {
  419. if (x.isNeg) {
  420. return 1 - 2 * Number(x.digits[i] > y.digits[i]);
  421. } else {
  422. return 1 - 2 * Number(x.digits[i] < y.digits[i]);
  423. }
  424. }
  425. }
  426. return 0;
  427. }
  428. function biDivideModulo(x, y) {
  429. var nb = biNumBits(x);
  430. var tb = biNumBits(y);
  431. var origYIsNeg = y.isNeg;
  432. var q, r;
  433. if (nb < tb) {
  434. // |x| < |y|
  435. if (x.isNeg) {
  436. q = biCopy(bigOne);
  437. q.isNeg = !y.isNeg;
  438. x.isNeg = false;
  439. y.isNeg = false;
  440. r = biSubtract(y, x);
  441. // Restore signs, 'cause they're references.
  442. x.isNeg = true;
  443. y.isNeg = origYIsNeg;
  444. } else {
  445. q = new BigInt();
  446. r = biCopy(x);
  447. }
  448. return new Array(q,r);
  449. }
  450. q = new BigInt();
  451. r = x;
  452. // Normalize Y.
  453. var t = Math.ceil(tb / bitsPerDigit) - 1;
  454. var lambda = 0;
  455. while (y.digits[t] < biHalfRadix) {
  456. y = biShiftLeft(y, 1);
  457. ++lambda;
  458. ++tb;
  459. t = Math.ceil(tb / bitsPerDigit) - 1;
  460. }
  461. // Shift r over to keep the quotient constant. We'll shift the
  462. // remainder back at the end.
  463. r = biShiftLeft(r, lambda);
  464. nb += lambda;
  465. // Update the bit count for x.
  466. var n = Math.ceil(nb / bitsPerDigit) - 1;
  467. var b = biMultiplyByRadixPower(y, n - t);
  468. while (biCompare(r, b) != -1) {
  469. ++q.digits[n - t];
  470. r = biSubtract(r, b);
  471. }
  472. for (var i = n; i > t; --i) {
  473. var ri = (i >= r.digits.length) ? 0 : r.digits[i];
  474. var ri1 = (i - 1 >= r.digits.length) ? 0 : r.digits[i - 1];
  475. var ri2 = (i - 2 >= r.digits.length) ? 0 : r.digits[i - 2];
  476. var yt = (t >= y.digits.length) ? 0 : y.digits[t];
  477. var yt1 = (t - 1 >= y.digits.length) ? 0 : y.digits[t - 1];
  478. if (ri == yt) {
  479. q.digits[i - t - 1] = maxDigitVal;
  480. } else {
  481. q.digits[i - t - 1] = Math.floor((ri * biRadix + ri1) / yt);
  482. }
  483. var c1 = q.digits[i - t - 1] * ((yt * biRadix) + yt1);
  484. var c2 = (ri * biRadixSquared) + ((ri1 * biRadix) + ri2);
  485. while (c1 > c2) {
  486. --q.digits[i - t - 1];
  487. c1 = q.digits[i - t - 1] * ((yt * biRadix) | yt1);
  488. c2 = (ri * biRadix * biRadix) + ((ri1 * biRadix) + ri2);
  489. }
  490. b = biMultiplyByRadixPower(y, i - t - 1);
  491. r = biSubtract(r, biMultiplyDigit(b, q.digits[i - t - 1]));
  492. if (r.isNeg) {
  493. r = biAdd(r, b);
  494. --q.digits[i - t - 1];
  495. }
  496. }
  497. r = biShiftRight(r, lambda);
  498. // Fiddle with the signs and stuff to make sure that 0 <= r < y.
  499. q.isNeg = x.isNeg != origYIsNeg;
  500. if (x.isNeg) {
  501. if (origYIsNeg) {
  502. q = biAdd(q, bigOne);
  503. } else {
  504. q = biSubtract(q, bigOne);
  505. }
  506. y = biShiftRight(y, lambda);
  507. r = biSubtract(y, r);
  508. }
  509. // Check for the unbelievably stupid degenerate case of r == -0.
  510. if (r.digits[0] == 0 && biHighIndex(r) == 0)
  511. r.isNeg = false;
  512. return new Array(q,r);
  513. }
  514. function biDivide(x, y) {
  515. return biDivideModulo(x, y)[0];
  516. }
  517. function biModulo(x, y) {
  518. return biDivideModulo(x, y)[1];
  519. }
  520. function biMultiplyMod(x, y, m) {
  521. return biModulo(biMultiply(x, y), m);
  522. }
  523. function biPow(x, y) {
  524. var result = bigOne;
  525. var a = x;
  526. while (true) {
  527. if ((y & 1) != 0)
  528. result = biMultiply(result, a);
  529. y >>= 1;
  530. if (y == 0)
  531. break;
  532. a = biMultiply(a, a);
  533. }
  534. return result;
  535. }
  536. function biPowMod(x, y, m) {
  537. var result = bigOne;
  538. var a = x;
  539. var k = y;
  540. while (true) {
  541. if ((k.digits[0] & 1) != 0)
  542. result = biMultiplyMod(result, a, m);
  543. k = biShiftRight(k, 1);
  544. if (k.digits[0] == 0 && biHighIndex(k) == 0)
  545. break;
  546. a = biMultiplyMod(a, a, m);
  547. }
  548. return result;
  549. }
  550. module.exports.biFromHex = biFromHex
  551. module.exports.bigInt = BigInt
  552. module.exports.biHighIndex = biHighIndex
  553. module.exports.biCopy = biCopy
  554. module.exports.biHighIndex = biHighIndex
  555. module.exports.biDivide = biDivide