API tools faq
paste
Advertisement
Guest User

Untitled

a guest
May 22nd, 2019
80
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 38.34 KB | None | 0 0
raw download clone embed print report
  1. const bigInt = function (undefined) {
  2. "use strict";
  3. var BASE = 1e7,
  4. LOG_BASE = 7,
  5. MAX_INT = 9007199254740992,
  6. MAX_INT_ARR = smallToArray(MAX_INT),
  7. LOG_MAX_INT = Math.log(MAX_INT);
  8.  
  9. function Integer(v, radix) {
  10. if (typeof v === "undefined") return Integer[0];
  11. if (typeof radix !== "undefined") return +radix === 10 ? parseValue(v) : parseBase(v, radix);
  12. return parseValue(v)
  13. }
  14.  
  15. function BigInteger(value, sign) {
  16. this.value = value;
  17. this.sign = sign;
  18. this.isSmall = false
  19. }
  20. BigInteger.prototype = Object.create(Integer.prototype);
  21.  
  22. function SmallInteger(value) {
  23. this.value = value;
  24. this.sign = value < 0;
  25. this.isSmall = true
  26. }
  27. SmallInteger.prototype = Object.create(Integer.prototype);
  28.  
  29. function isPrecise(n) {
  30. return -MAX_INT < n && n < MAX_INT
  31. }
  32.  
  33. function smallToArray(n) {
  34. if (n < 1e7) return [n];
  35. if (n < 1e14) return [n % 1e7, Math.floor(n / 1e7)];
  36. return [n % 1e7, Math.floor(n / 1e7) % 1e7, Math.floor(n / 1e14)]
  37. }
  38.  
  39. function arrayToSmall(arr) {
  40. trim(arr);
  41. var length = arr.length;
  42. if (length < 4 && compareAbs(arr, MAX_INT_ARR) < 0) {
  43. switch (length) {
  44. case 0:
  45. return 0;
  46. case 1:
  47. return arr[0];
  48. case 2:
  49. return arr[0] + arr[1] * BASE;
  50. default:
  51. return arr[0] + (arr[1] + arr[2] * BASE) * BASE
  52. }
  53. }
  54. return arr
  55. }
  56.  
  57. function trim(v) {
  58. var i = v.length;
  59. while (v[--i] === 0);
  60. v.length = i + 1
  61. }
  62.  
  63. function createArray(length) {
  64. var x = new Array(length);
  65. var i = -1;
  66. while (++i < length) {
  67. x[i] = 0
  68. }
  69. return x
  70. }
  71.  
  72. function truncate(n) {
  73. if (n > 0) return Math.floor(n);
  74. return Math.ceil(n)
  75. }
  76.  
  77. function add(a, b) {
  78. var l_a = a.length,
  79. l_b = b.length,
  80. r = new Array(l_a),
  81. carry = 0,
  82. base = BASE,
  83. sum, i;
  84. for (i = 0; i < l_b; i++) {
  85. sum = a[i] + b[i] + carry;
  86. carry = sum >= base ? 1 : 0;
  87. r[i] = sum - carry * base
  88. }
  89. while (i < l_a) {
  90. sum = a[i] + carry;
  91. carry = sum === base ? 1 : 0;
  92. r[i++] = sum - carry * base
  93. }
  94. if (carry > 0) r.push(carry);
  95. return r
  96. }
  97.  
  98. function addAny(a, b) {
  99. if (a.length >= b.length) return add(a, b);
  100. return add(b, a)
  101. }
  102.  
  103. function addSmall(a, carry) {
  104. var l = a.length,
  105. r = new Array(l),
  106. base = BASE,
  107. sum, i;
  108. for (i = 0; i < l; i++) {
  109. sum = a[i] - base + carry;
  110. carry = Math.floor(sum / base);
  111. r[i] = sum - carry * base;
  112. carry += 1
  113. }
  114. while (carry > 0) {
  115. r[i++] = carry % base;
  116. carry = Math.floor(carry / base)
  117. }
  118. return r
  119. }
  120. BigInteger.prototype.add = function (v) {
  121. var n = parseValue(v);
  122. if (this.sign !== n.sign) {
  123. return this.subtract(n.negate())
  124. }
  125. var a = this.value,
  126. b = n.value;
  127. if (n.isSmall) {
  128. return new BigInteger(addSmall(a, Math.abs(b)), this.sign)
  129. }
  130. return new BigInteger(addAny(a, b), this.sign)
  131. };
  132. BigInteger.prototype.plus = BigInteger.prototype.add;
  133. SmallInteger.prototype.add = function (v) {
  134. var n = parseValue(v);
  135. var a = this.value;
  136. if (a < 0 !== n.sign) {
  137. return this.subtract(n.negate())
  138. }
  139. var b = n.value;
  140. if (n.isSmall) {
  141. if (isPrecise(a + b)) return new SmallInteger(a + b);
  142. b = smallToArray(Math.abs(b))
  143. }
  144. return new BigInteger(addSmall(b, Math.abs(a)), a < 0)
  145. };
  146. SmallInteger.prototype.plus = SmallInteger.prototype.add;
  147.  
  148. function subtract(a, b) {
  149. var a_l = a.length,
  150. b_l = b.length,
  151. r = new Array(a_l),
  152. borrow = 0,
  153. base = BASE,
  154. i, difference;
  155. for (i = 0; i < b_l; i++) {
  156. difference = a[i] - borrow - b[i];
  157. if (difference < 0) {
  158. difference += base;
  159. borrow = 1
  160. } else borrow = 0;
  161. r[i] = difference
  162. }
  163. for (i = b_l; i < a_l; i++) {
  164. difference = a[i] - borrow;
  165. if (difference < 0) difference += base;
  166. else {
  167. r[i++] = difference;
  168. break
  169. }
  170. r[i] = difference
  171. }
  172. for (; i < a_l; i++) {
  173. r[i] = a[i]
  174. }
  175. trim(r);
  176. return r
  177. }
  178.  
  179. function subtractAny(a, b, sign) {
  180. var value;
  181. if (compareAbs(a, b) >= 0) {
  182. value = subtract(a, b)
  183. } else {
  184. value = subtract(b, a);
  185. sign = !sign
  186. }
  187. value = arrayToSmall(value);
  188. if (typeof value === "number") {
  189. if (sign) value = -value;
  190. return new SmallInteger(value)
  191. }
  192. return new BigInteger(value, sign)
  193. }
  194.  
  195. function subtractSmall(a, b, sign) {
  196. var l = a.length,
  197. r = new Array(l),
  198. carry = -b,
  199. base = BASE,
  200. i, difference;
  201. for (i = 0; i < l; i++) {
  202. difference = a[i] + carry;
  203. carry = Math.floor(difference / base);
  204. difference %= base;
  205. r[i] = difference < 0 ? difference + base : difference
  206. }
  207. r = arrayToSmall(r);
  208. if (typeof r === "number") {
  209. if (sign) r = -r;
  210. return new SmallInteger(r)
  211. }
  212. return new BigInteger(r, sign)
  213. }
  214. BigInteger.prototype.subtract = function (v) {
  215. var n = parseValue(v);
  216. if (this.sign !== n.sign) {
  217. return this.add(n.negate())
  218. }
  219. var a = this.value,
  220. b = n.value;
  221. if (n.isSmall) return subtractSmall(a, Math.abs(b), this.sign);
  222. return subtractAny(a, b, this.sign)
  223. };
  224. BigInteger.prototype.minus = BigInteger.prototype.subtract;
  225. SmallInteger.prototype.subtract = function (v) {
  226. var n = parseValue(v);
  227. var a = this.value;
  228. if (a < 0 !== n.sign) {
  229. return this.add(n.negate())
  230. }
  231. var b = n.value;
  232. if (n.isSmall) {
  233. return new SmallInteger(a - b)
  234. }
  235. return subtractSmall(b, Math.abs(a), a >= 0)
  236. };
  237. SmallInteger.prototype.minus = SmallInteger.prototype.subtract;
  238. BigInteger.prototype.negate = function () {
  239. return new BigInteger(this.value, !this.sign)
  240. };
  241. SmallInteger.prototype.negate = function () {
  242. var sign = this.sign;
  243. var small = new SmallInteger(-this.value);
  244. small.sign = !sign;
  245. return small
  246. };
  247. BigInteger.prototype.abs = function () {
  248. return new BigInteger(this.value, false)
  249. };
  250. SmallInteger.prototype.abs = function () {
  251. return new SmallInteger(Math.abs(this.value))
  252. };
  253.  
  254. function multiplyLong(a, b) {
  255. var a_l = a.length,
  256. b_l = b.length,
  257. l = a_l + b_l,
  258. r = createArray(l),
  259. base = BASE,
  260. product, carry, i, a_i, b_j;
  261. for (i = 0; i < a_l; ++i) {
  262. a_i = a[i];
  263. for (var j = 0; j < b_l; ++j) {
  264. b_j = b[j];
  265. product = a_i * b_j + r[i + j];
  266. carry = Math.floor(product / base);
  267. r[i + j] = product - carry * base;
  268. r[i + j + 1] += carry
  269. }
  270. }
  271. trim(r);
  272. return r
  273. }
  274.  
  275. function multiplySmall(a, b) {
  276. var l = a.length,
  277. r = new Array(l),
  278. base = BASE,
  279. carry = 0,
  280. product, i;
  281. for (i = 0; i < l; i++) {
  282. product = a[i] * b + carry;
  283. carry = Math.floor(product / base);
  284. r[i] = product - carry * base
  285. }
  286. while (carry > 0) {
  287. r[i++] = carry % base;
  288. carry = Math.floor(carry / base)
  289. }
  290. return r
  291. }
  292.  
  293. function shiftLeft(x, n) {
  294. var r = [];
  295. while (n-- > 0) r.push(0);
  296. return r.concat(x)
  297. }
  298.  
  299. function multiplyKaratsuba(x, y) {
  300. var n = Math.max(x.length, y.length);
  301. if (n <= 30) return multiplyLong(x, y);
  302. n = Math.ceil(n / 2);
  303. var b = x.slice(n),
  304. a = x.slice(0, n),
  305. d = y.slice(n),
  306. c = y.slice(0, n);
  307. var ac = multiplyKaratsuba(a, c),
  308. bd = multiplyKaratsuba(b, d),
  309. abcd = multiplyKaratsuba(addAny(a, b), addAny(c, d));
  310. var product = addAny(addAny(ac, shiftLeft(subtract(subtract(abcd, ac), bd), n)), shiftLeft(bd, 2 * n));
  311. trim(product);
  312. return product
  313. }
  314.  
  315. function useKaratsuba(l1, l2) {
  316. return -.012 * l1 - .012 * l2 + 15e-6 * l1 * l2 > 0
  317. }
  318. BigInteger.prototype.multiply = function (v) {
  319. var n = parseValue(v),
  320. a = this.value,
  321. b = n.value,
  322. sign = this.sign !== n.sign,
  323. abs;
  324. if (n.isSmall) {
  325. if (b === 0) return Integer[0];
  326. if (b === 1) return this;
  327. if (b === -1) return this.negate();
  328. abs = Math.abs(b);
  329. if (abs < BASE) {
  330. return new BigInteger(multiplySmall(a, abs), sign)
  331. }
  332. b = smallToArray(abs)
  333. }
  334. if (useKaratsuba(a.length, b.length)) return new BigInteger(multiplyKaratsuba(a, b), sign);
  335. return new BigInteger(multiplyLong(a, b), sign)
  336. };
  337. BigInteger.prototype.times = BigInteger.prototype.multiply;
  338.  
  339. function multiplySmallAndArray(a, b, sign) {
  340. if (a < BASE) {
  341. return new BigInteger(multiplySmall(b, a), sign)
  342. }
  343. return new BigInteger(multiplyLong(b, smallToArray(a)), sign)
  344. }
  345. SmallInteger.prototype._multiplyBySmall = function (a) {
  346. if (isPrecise(a.value * this.value)) {
  347. return new SmallInteger(a.value * this.value)
  348. }
  349. return multiplySmallAndArray(Math.abs(a.value), smallToArray(Math.abs(this.value)), this.sign !== a.sign)
  350. };
  351. BigInteger.prototype._multiplyBySmall = function (a) {
  352. if (a.value === 0) return Integer[0];
  353. if (a.value === 1) return this;
  354. if (a.value === -1) return this.negate();
  355. return multiplySmallAndArray(Math.abs(a.value), this.value, this.sign !== a.sign)
  356. };
  357. SmallInteger.prototype.multiply = function (v) {
  358. return parseValue(v)._multiplyBySmall(this)
  359. };
  360. SmallInteger.prototype.times = SmallInteger.prototype.multiply;
  361.  
  362. function square(a) {
  363. var l = a.length,
  364. r = createArray(l + l),
  365. base = BASE,
  366. product, carry, i, a_i, a_j;
  367. for (i = 0; i < l; i++) {
  368. a_i = a[i];
  369. carry = 0 - a_i * a_i;
  370. for (var j = i; j < l; j++) {
  371. a_j = a[j];
  372. product = 2 * (a_i * a_j) + r[i + j] + carry;
  373. carry = Math.floor(product / base);
  374. r[i + j] = product - carry * base
  375. }
  376. r[i + l] = carry
  377. }
  378. trim(r);
  379. return r
  380. }
  381. BigInteger.prototype.square = function () {
  382. return new BigInteger(square(this.value), false)
  383. };
  384. SmallInteger.prototype.square = function () {
  385. var value = this.value * this.value;
  386. if (isPrecise(value)) return new SmallInteger(value);
  387. return new BigInteger(square(smallToArray(Math.abs(this.value))), false)
  388. };
  389.  
  390. function divMod1(a, b) {
  391. var a_l = a.length,
  392. b_l = b.length,
  393. base = BASE,
  394. result = createArray(b.length),
  395. divisorMostSignificantDigit = b[b_l - 1],
  396. lambda = Math.ceil(base / (2 * divisorMostSignificantDigit)),
  397. remainder = multiplySmall(a, lambda),
  398. divisor = multiplySmall(b, lambda),
  399. quotientDigit, shift, carry, borrow, i, l, q;
  400. if (remainder.length <= a_l) remainder.push(0);
  401. divisor.push(0);
  402. divisorMostSignificantDigit = divisor[b_l - 1];
  403. for (shift = a_l - b_l; shift >= 0; shift--) {
  404. quotientDigit = base - 1;
  405. if (remainder[shift + b_l] !== divisorMostSignificantDigit) {
  406. quotientDigit = Math.floor((remainder[shift + b_l] * base + remainder[shift + b_l - 1]) / divisorMostSignificantDigit)
  407. }
  408. carry = 0;
  409. borrow = 0;
  410. l = divisor.length;
  411. for (i = 0; i < l; i++) {
  412. carry += quotientDigit * divisor[i];
  413. q = Math.floor(carry / base);
  414. borrow += remainder[shift + i] - (carry - q * base);
  415. carry = q;
  416. if (borrow < 0) {
  417. remainder[shift + i] = borrow + base;
  418. borrow = -1
  419. } else {
  420. remainder[shift + i] = borrow;
  421. borrow = 0
  422. }
  423. }
  424. while (borrow !== 0) {
  425. quotientDigit -= 1;
  426. carry = 0;
  427. for (i = 0; i < l; i++) {
  428. carry += remainder[shift + i] - base + divisor[i];
  429. if (carry < 0) {
  430. remainder[shift + i] = carry + base;
  431. carry = 0
  432. } else {
  433. remainder[shift + i] = carry;
  434. carry = 1
  435. }
  436. }
  437. borrow += carry
  438. }
  439. result[shift] = quotientDigit
  440. }
  441. remainder = divModSmall(remainder, lambda)[0];
  442. return [arrayToSmall(result), arrayToSmall(remainder)]
  443. }
  444.  
  445. function divMod2(a, b) {
  446. var a_l = a.length,
  447. b_l = b.length,
  448. result = [],
  449. part = [],
  450. base = BASE,
  451. guess, xlen, highx, highy, check;
  452. while (a_l) {
  453. part.unshift(a[--a_l]);
  454. trim(part);
  455. if (compareAbs(part, b) < 0) {
  456. result.push(0);
  457. continue
  458. }
  459. xlen = part.length;
  460. highx = part[xlen - 1] * base + part[xlen - 2];
  461. highy = b[b_l - 1] * base + b[b_l - 2];
  462. if (xlen > b_l) {
  463. highx = (highx + 1) * base
  464. }
  465. guess = Math.ceil(highx / highy);
  466. do {
  467. check = multiplySmall(b, guess);
  468. if (compareAbs(check, part) <= 0) break;
  469. guess--
  470. } while (guess);
  471. result.push(guess);
  472. part = subtract(part, check)
  473. }
  474. result.reverse();
  475. return [arrayToSmall(result), arrayToSmall(part)]
  476. }
  477.  
  478. function divModSmall(value, lambda) {
  479. var length = value.length,
  480. quotient = createArray(length),
  481. base = BASE,
  482. i, q, remainder, divisor;
  483. remainder = 0;
  484. for (i = length - 1; i >= 0; --i) {
  485. divisor = remainder * base + value[i];
  486. q = truncate(divisor / lambda);
  487. remainder = divisor - q * lambda;
  488. quotient[i] = q | 0
  489. }
  490. return [quotient, remainder | 0]
  491. }
  492.  
  493. function divModAny(self, v) {
  494. var value, n = parseValue(v);
  495. var a = self.value,
  496. b = n.value;
  497. var quotient;
  498. if (b === 0) throw new Error("Cannot divide by zero");
  499. if (self.isSmall) {
  500. if (n.isSmall) {
  501. return [new SmallInteger(truncate(a / b)), new SmallInteger(a % b)]
  502. }
  503. return [Integer[0], self]
  504. }
  505. if (n.isSmall) {
  506. if (b === 1) return [self, Integer[0]];
  507. if (b == -1) return [self.negate(), Integer[0]];
  508. var abs = Math.abs(b);
  509. if (abs < BASE) {
  510. value = divModSmall(a, abs);
  511. quotient = arrayToSmall(value[0]);
  512. var remainder = value[1];
  513. if (self.sign) remainder = -remainder;
  514. if (typeof quotient === "number") {
  515. if (self.sign !== n.sign) quotient = -quotient;
  516. return [new SmallInteger(quotient), new SmallInteger(remainder)]
  517. }
  518. return [new BigInteger(quotient, self.sign !== n.sign), new SmallInteger(remainder)]
  519. }
  520. b = smallToArray(abs)
  521. }
  522. var comparison = compareAbs(a, b);
  523. if (comparison === -1) return [Integer[0], self];
  524. if (comparison === 0) return [Integer[self.sign === n.sign ? 1 : -1], Integer[0]];
  525. if (a.length + b.length <= 200) value = divMod1(a, b);
  526. else value = divMod2(a, b);
  527. quotient = value[0];
  528. var qSign = self.sign !== n.sign,
  529. mod = value[1],
  530. mSign = self.sign;
  531. if (typeof quotient === "number") {
  532. if (qSign) quotient = -quotient;
  533. quotient = new SmallInteger(quotient)
  534. } else quotient = new BigInteger(quotient, qSign);
  535. if (typeof mod === "number") {
  536. if (mSign) mod = -mod;
  537. mod = new SmallInteger(mod)
  538. } else mod = new BigInteger(mod, mSign);
  539. return [quotient, mod]
  540. }
  541. BigInteger.prototype.divmod = function (v) {
  542. var result = divModAny(this, v);
  543. return {
  544. quotient: result[0],
  545. remainder: result[1]
  546. }
  547. };
  548. SmallInteger.prototype.divmod = BigInteger.prototype.divmod;
  549. BigInteger.prototype.divide = function (v) {
  550. return divModAny(this, v)[0]
  551. };
  552. SmallInteger.prototype.over = SmallInteger.prototype.divide = BigInteger.prototype.over = BigInteger.prototype.divide;
  553. BigInteger.prototype.mod = function (v) {
  554. return divModAny(this, v)[1]
  555. };
  556. SmallInteger.prototype.remainder = SmallInteger.prototype.mod = BigInteger.prototype.remainder = BigInteger.prototype.mod;
  557. BigInteger.prototype.pow = function (v) {
  558. var n = parseValue(v),
  559. a = this.value,
  560. b = n.value,
  561. value, x, y;
  562. if (b === 0) return Integer[1];
  563. if (a === 0) return Integer[0];
  564. if (a === 1) return Integer[1];
  565. if (a === -1) return n.isEven() ? Integer[1] : Integer[-1];
  566. if (n.sign) {
  567. return Integer[0]
  568. }
  569. if (!n.isSmall) throw new Error("The exponent " + n.toString() + " is too large.");
  570. if (this.isSmall) {
  571. if (isPrecise(value = Math.pow(a, b))) return new SmallInteger(truncate(value))
  572. }
  573. x = this;
  574. y = Integer[1];
  575. while (true) {
  576. if (b & 1 === 1) {
  577. y = y.times(x);
  578. --b
  579. }
  580. if (b === 0) break;
  581. b /= 2;
  582. x = x.square()
  583. }
  584. return y
  585. };
  586. SmallInteger.prototype.pow = BigInteger.prototype.pow;
  587. BigInteger.prototype.modPow = function (exp, mod) {
  588. exp = parseValue(exp);
  589. mod = parseValue(mod);
  590. if (mod.isZero()) throw new Error("Cannot take modPow with modulus 0");
  591. var r = Integer[1],
  592. base = this.mod(mod);
  593. while (exp.isPositive()) {
  594. if (base.isZero()) return Integer[0];
  595. if (exp.isOdd()) r = r.multiply(base).mod(mod);
  596. exp = exp.divide(2);
  597. base = base.square().mod(mod)
  598. }
  599. return r
  600. };
  601. SmallInteger.prototype.modPow = BigInteger.prototype.modPow;
  602.  
  603. function compareAbs(a, b) {
  604. if (a.length !== b.length) {
  605. return a.length > b.length ? 1 : -1
  606. }
  607. for (var i = a.length - 1; i >= 0; i--) {
  608. if (a[i] !== b[i]) return a[i] > b[i] ? 1 : -1
  609. }
  610. return 0
  611. }
  612. BigInteger.prototype.compareAbs = function (v) {
  613. var n = parseValue(v),
  614. a = this.value,
  615. b = n.value;
  616. if (n.isSmall) return 1;
  617. return compareAbs(a, b)
  618. };
  619. SmallInteger.prototype.compareAbs = function (v) {
  620. var n = parseValue(v),
  621. a = Math.abs(this.value),
  622. b = n.value;
  623. if (n.isSmall) {
  624. b = Math.abs(b);
  625. return a === b ? 0 : a > b ? 1 : -1
  626. }
  627. return -1
  628. };
  629. BigInteger.prototype.compare = function (v) {
  630. if (v === Infinity) {
  631. return -1
  632. }
  633. if (v === -Infinity) {
  634. return 1
  635. }
  636. var n = parseValue(v),
  637. a = this.value,
  638. b = n.value;
  639. if (this.sign !== n.sign) {
  640. return n.sign ? 1 : -1
  641. }
  642. if (n.isSmall) {
  643. return this.sign ? -1 : 1
  644. }
  645. return compareAbs(a, b) * (this.sign ? -1 : 1)
  646. };
  647. BigInteger.prototype.compareTo = BigInteger.prototype.compare;
  648. SmallInteger.prototype.compare = function (v) {
  649. if (v === Infinity) {
  650. return -1
  651. }
  652. if (v === -Infinity) {
  653. return 1
  654. }
  655. var n = parseValue(v),
  656. a = this.value,
  657. b = n.value;
  658. if (n.isSmall) {
  659. return a == b ? 0 : a > b ? 1 : -1
  660. }
  661. if (a < 0 !== n.sign) {
  662. return a < 0 ? -1 : 1
  663. }
  664. return a < 0 ? 1 : -1
  665. };
  666. SmallInteger.prototype.compareTo = SmallInteger.prototype.compare;
  667. BigInteger.prototype.equals = function (v) {
  668. return this.compare(v) === 0
  669. };
  670. SmallInteger.prototype.eq = SmallInteger.prototype.equals = BigInteger.prototype.eq = BigInteger.prototype.equals;
  671. BigInteger.prototype.notEquals = function (v) {
  672. return this.compare(v) !== 0
  673. };
  674. SmallInteger.prototype.neq = SmallInteger.prototype.notEquals = BigInteger.prototype.neq = BigInteger.prototype.notEquals;
  675. BigInteger.prototype.greater = function (v) {
  676. return this.compare(v) > 0
  677. };
  678. SmallInteger.prototype.gt = SmallInteger.prototype.greater = BigInteger.prototype.gt = BigInteger.prototype.greater;
  679. BigInteger.prototype.lesser = function (v) {
  680. return this.compare(v) < 0
  681. };
  682. SmallInteger.prototype.lt = SmallInteger.prototype.lesser = BigInteger.prototype.lt = BigInteger.prototype.lesser;
  683. BigInteger.prototype.greaterOrEquals = function (v) {
  684. return this.compare(v) >= 0
  685. };
  686. SmallInteger.prototype.geq = SmallInteger.prototype.greaterOrEquals = BigInteger.prototype.geq = BigInteger.prototype.greaterOrEquals;
  687. BigInteger.prototype.lesserOrEquals = function (v) {
  688. return this.compare(v) <= 0
  689. };
  690. SmallInteger.prototype.leq = SmallInteger.prototype.lesserOrEquals = BigInteger.prototype.leq = BigInteger.prototype.lesserOrEquals;
  691. BigInteger.prototype.isEven = function () {
  692. return (this.value[0] & 1) === 0
  693. };
  694. SmallInteger.prototype.isEven = function () {
  695. return (this.value & 1) === 0
  696. };
  697. BigInteger.prototype.isOdd = function () {
  698. return (this.value[0] & 1) === 1
  699. };
  700. SmallInteger.prototype.isOdd = function () {
  701. return (this.value & 1) === 1
  702. };
  703. BigInteger.prototype.isPositive = function () {
  704. return !this.sign
  705. };
  706. SmallInteger.prototype.isPositive = function () {
  707. return this.value > 0
  708. };
  709. BigInteger.prototype.isNegative = function () {
  710. return this.sign
  711. };
  712. SmallInteger.prototype.isNegative = function () {
  713. return this.value < 0
  714. };
  715. BigInteger.prototype.isUnit = function () {
  716. return false
  717. };
  718. SmallInteger.prototype.isUnit = function () {
  719. return Math.abs(this.value) === 1
  720. };
  721. BigInteger.prototype.isZero = function () {
  722. return false
  723. };
  724. SmallInteger.prototype.isZero = function () {
  725. return this.value === 0
  726. };
  727. BigInteger.prototype.isDivisibleBy = function (v) {
  728. var n = parseValue(v);
  729. var value = n.value;
  730. if (value === 0) return false;
  731. if (value === 1) return true;
  732. if (value === 2) return this.isEven();
  733. return this.mod(n).equals(Integer[0])
  734. };
  735. SmallInteger.prototype.isDivisibleBy = BigInteger.prototype.isDivisibleBy;
  736.  
  737. function isBasicPrime(v) {
  738. var n = v.abs();
  739. if (n.isUnit()) return false;
  740. if (n.equals(2) || n.equals(3) || n.equals(5)) return true;
  741. if (n.isEven() || n.isDivisibleBy(3) || n.isDivisibleBy(5)) return false;
  742. if (n.lesser(49)) return true
  743. }
  744.  
  745. function millerRabinTest(n, a) {
  746. var nPrev = n.prev(),
  747. b = nPrev,
  748. r = 0,
  749. d, t, i, x;
  750. while (b.isEven()) b = b.divide(2), r++;
  751. next: for (i = 0; i < a.length; i++) {
  752. if (n.lesser(a[i])) continue;
  753. x = bigInt(a[i]).modPow(b, n);
  754. if (x.equals(Integer[1]) || x.equals(nPrev)) continue;
  755. for (d = r - 1; d != 0; d--) {
  756. x = x.square().mod(n);
  757. if (x.equals(nPrev)) continue next
  758. }
  759. return false
  760. }
  761. return true
  762. }
  763. BigInteger.prototype.isPrime = function (strict) {
  764. var isPrime = isBasicPrime(this);
  765. if (isPrime !== undefined) return isPrime;
  766. var n = this.abs();
  767. var bits = n.bitLength();
  768. if (bits <= 64) return millerRabinTest(n, [2, 325, 9375, 28178, 450775, 9780504, 1795265022]);
  769. var logN = Math.log(2) * bits;
  770. var t = Math.ceil(strict === true ? 2 * Math.pow(logN, 2) : logN);
  771. for (var a = [], i = 0; i < t; i++) {
  772. a.push(bigInt(i + 2))
  773. }
  774. return millerRabinTest(n, a)
  775. };
  776. SmallInteger.prototype.isPrime = BigInteger.prototype.isPrime;
  777. BigInteger.prototype.isProbablePrime = function (iterations) {
  778. var isPrime = isBasicPrime(this);
  779. if (isPrime !== undefined) return isPrime;
  780. var n = this.abs();
  781. var t = iterations === undefined ? 5 : iterations;
  782. for (var a = [], i = 0; i < t; i++) {
  783. a.push(bigInt.randBetween(2, n.minus(2)))
  784. }
  785. return millerRabinTest(n, a)
  786. };
  787. SmallInteger.prototype.isProbablePrime = BigInteger.prototype.isProbablePrime;
  788. BigInteger.prototype.modInv = function (n) {
  789. var t = bigInt.zero,
  790. newT = bigInt.one,
  791. r = parseValue(n),
  792. newR = this.abs(),
  793. q, lastT, lastR;
  794. while (!newR.equals(bigInt.zero)) {
  795. q = r.divide(newR);
  796. lastT = t;
  797. lastR = r;
  798. t = newT;
  799. r = newR;
  800. newT = lastT.subtract(q.multiply(newT));
  801. newR = lastR.subtract(q.multiply(newR))
  802. }
  803. if (!r.equals(1)) throw new Error(this.toString() + " and " + n.toString() + " are not co-prime");
  804. if (t.compare(0) === -1) {
  805. t = t.add(n)
  806. }
  807. if (this.isNegative()) {
  808. return t.negate()
  809. }
  810. return t
  811. };
  812. SmallInteger.prototype.modInv = BigInteger.prototype.modInv;
  813. BigInteger.prototype.next = function () {
  814. var value = this.value;
  815. if (this.sign) {
  816. return subtractSmall(value, 1, this.sign)
  817. }
  818. return new BigInteger(addSmall(value, 1), this.sign)
  819. };
  820. SmallInteger.prototype.next = function () {
  821. var value = this.value;
  822. if (value + 1 < MAX_INT) return new SmallInteger(value + 1);
  823. return new BigInteger(MAX_INT_ARR, false)
  824. };
  825. BigInteger.prototype.prev = function () {
  826. var value = this.value;
  827. if (this.sign) {
  828. return new BigInteger(addSmall(value, 1), true)
  829. }
  830. return subtractSmall(value, 1, this.sign)
  831. };
  832. SmallInteger.prototype.prev = function () {
  833. var value = this.value;
  834. if (value - 1 > -MAX_INT) return new SmallInteger(value - 1);
  835. return new BigInteger(MAX_INT_ARR, true)
  836. };
  837. var powersOfTwo = [1];
  838. while (2 * powersOfTwo[powersOfTwo.length - 1] <= BASE) powersOfTwo.push(2 * powersOfTwo[powersOfTwo.length - 1]);
  839. var powers2Length = powersOfTwo.length,
  840. highestPower2 = powersOfTwo[powers2Length - 1];
  841.  
  842. function shift_isSmall(n) {
  843. return (typeof n === "number" || typeof n === "string") && +Math.abs(n) <= BASE || n instanceof BigInteger && n.value.length <= 1
  844. }
  845. BigInteger.prototype.shiftLeft = function (n) {
  846. if (!shift_isSmall(n)) {
  847. throw new Error(String(n) + " is too large for shifting.")
  848. }
  849. n = +n;
  850. if (n < 0) return this.shiftRight(-n);
  851. var result = this;
  852. if (result.isZero()) return result;
  853. while (n >= powers2Length) {
  854. result = result.multiply(highestPower2);
  855. n -= powers2Length - 1
  856. }
  857. return result.multiply(powersOfTwo[n])
  858. };
  859. SmallInteger.prototype.shiftLeft = BigInteger.prototype.shiftLeft;
  860. BigInteger.prototype.shiftRight = function (n) {
  861. var remQuo;
  862. if (!shift_isSmall(n)) {
  863. throw new Error(String(n) + " is too large for shifting.")
  864. }
  865. n = +n;
  866. if (n < 0) return this.shiftLeft(-n);
  867. var result = this;
  868. while (n >= powers2Length) {
  869. if (result.isZero() || result.isNegative() && result.isUnit()) return result;
  870. remQuo = divModAny(result, highestPower2);
  871. result = remQuo[1].isNegative() ? remQuo[0].prev() : remQuo[0];
  872. n -= powers2Length - 1
  873. }
  874. remQuo = divModAny(result, powersOfTwo[n]);
  875. return remQuo[1].isNegative() ? remQuo[0].prev() : remQuo[0]
  876. };
  877. SmallInteger.prototype.shiftRight = BigInteger.prototype.shiftRight;
  878.  
  879. function bitwise(x, y, fn) {
  880. y = parseValue(y);
  881. var xSign = x.isNegative(),
  882. ySign = y.isNegative();
  883. var xRem = xSign ? x.not() : x,
  884. yRem = ySign ? y.not() : y;
  885. var xDigit = 0,
  886. yDigit = 0;
  887. var xDivMod = null,
  888. yDivMod = null;
  889. var result = [];
  890. while (!xRem.isZero() || !yRem.isZero()) {
  891. xDivMod = divModAny(xRem, highestPower2);
  892. xDigit = xDivMod[1].toJSNumber();
  893. if (xSign) {
  894. xDigit = highestPower2 - 1 - xDigit
  895. }
  896. yDivMod = divModAny(yRem, highestPower2);
  897. yDigit = yDivMod[1].toJSNumber();
  898. if (ySign) {
  899. yDigit = highestPower2 - 1 - yDigit
  900. }
  901. xRem = xDivMod[0];
  902. yRem = yDivMod[0];
  903. result.push(fn(xDigit, yDigit))
  904. }
  905. var sum = fn(xSign ? 1 : 0, ySign ? 1 : 0) !== 0 ? bigInt(-1) : bigInt(0);
  906. for (var i = result.length - 1; i >= 0; i -= 1) {
  907. sum = sum.multiply(highestPower2).add(bigInt(result[i]))
  908. }
  909. return sum
  910. }
  911. BigInteger.prototype.not = function () {
  912. return this.negate().prev()
  913. };
  914. SmallInteger.prototype.not = BigInteger.prototype.not;
  915. BigInteger.prototype.and = function (n) {
  916. return bitwise(this, n, function (a, b) {
  917. return a & b
  918. })
  919. };
  920. SmallInteger.prototype.and = BigInteger.prototype.and;
  921. BigInteger.prototype.or = function (n) {
  922. return bitwise(this, n, function (a, b) {
  923. return a | b
  924. })
  925. };
  926. SmallInteger.prototype.or = BigInteger.prototype.or;
  927. BigInteger.prototype.xor = function (n) {
  928. return bitwise(this, n, function (a, b) {
  929. return a ^ b
  930. })
  931. };
  932. SmallInteger.prototype.xor = BigInteger.prototype.xor;
  933. var LOBMASK_I = 1 << 30,
  934. LOBMASK_BI = (BASE & -BASE) * (BASE & -BASE) | LOBMASK_I;
  935.  
  936. function roughLOB(n) {
  937. var v = n.value,
  938. x = typeof v === "number" ? v | LOBMASK_I : v[0] + v[1] * BASE | LOBMASK_BI;
  939. return x & -x
  940. }
  941.  
  942. function integerLogarithm(value, base) {
  943. if (base.compareTo(value) <= 0) {
  944. var tmp = integerLogarithm(value, base.square(base));
  945. var p = tmp.p;
  946. var e = tmp.e;
  947. var t = p.multiply(base);
  948. return t.compareTo(value) <= 0 ? {
  949. p: t,
  950. e: e * 2 + 1
  951. } : {
  952. p: p,
  953. e: e * 2
  954. }
  955. }
  956. return {
  957. p: bigInt(1),
  958. e: 0
  959. }
  960. }
  961. BigInteger.prototype.bitLength = function () {
  962. var n = this;
  963. if (n.compareTo(bigInt(0)) < 0) {
  964. n = n.negate().subtract(bigInt(1))
  965. }
  966. if (n.compareTo(bigInt(0)) === 0) {
  967. return bigInt(0)
  968. }
  969. return bigInt(integerLogarithm(n, bigInt(2)).e).add(bigInt(1))
  970. };
  971. SmallInteger.prototype.bitLength = BigInteger.prototype.bitLength;
  972.  
  973. function max(a, b) {
  974. a = parseValue(a);
  975. b = parseValue(b);
  976. return a.greater(b) ? a : b
  977. }
  978.  
  979. function min(a, b) {
  980. a = parseValue(a);
  981. b = parseValue(b);
  982. return a.lesser(b) ? a : b
  983. }
  984.  
  985. function gcd(a, b) {
  986. a = parseValue(a).abs();
  987. b = parseValue(b).abs();
  988. if (a.equals(b)) return a;
  989. if (a.isZero()) return b;
  990. if (b.isZero()) return a;
  991. var c = Integer[1],
  992. d, t;
  993. while (a.isEven() && b.isEven()) {
  994. d = Math.min(roughLOB(a), roughLOB(b));
  995. a = a.divide(d);
  996. b = b.divide(d);
  997. c = c.multiply(d)
  998. }
  999. while (a.isEven()) {
  1000. a = a.divide(roughLOB(a))
  1001. }
  1002. do {
  1003. while (b.isEven()) {
  1004. b = b.divide(roughLOB(b))
  1005. }
  1006. if (a.greater(b)) {
  1007. t = b;
  1008. b = a;
  1009. a = t
  1010. }
  1011. b = b.subtract(a)
  1012. } while (!b.isZero());
  1013. return c.isUnit() ? a : a.multiply(c)
  1014. }
  1015.  
  1016. function lcm(a, b) {
  1017. a = parseValue(a).abs();
  1018. b = parseValue(b).abs();
  1019. return a.divide(gcd(a, b)).multiply(b)
  1020. }
  1021.  
  1022. function randBetween(a, b) {
  1023. a = parseValue(a);
  1024. b = parseValue(b);
  1025. var low = min(a, b),
  1026. high = max(a, b);
  1027. var range = high.subtract(low).add(1);
  1028. if (range.isSmall) return low.add(Math.floor(Math.random() * range));
  1029. var length = range.value.length - 1;
  1030. var result = [],
  1031. restricted = true;
  1032. for (var i = length; i >= 0; i--) {
  1033. var top = restricted ? range.value[i] : BASE;
  1034. var digit = truncate(Math.random() * top);
  1035. result.unshift(digit);
  1036. if (digit < top) restricted = false
  1037. }
  1038. result = arrayToSmall(result);
  1039. return low.add(typeof result === "number" ? new SmallInteger(result) : new BigInteger(result, false))
  1040. }
  1041. var parseBase = function (text, base) {
  1042. var length = text.length;
  1043. var i;
  1044. var absBase = Math.abs(base);
  1045. for (var i = 0; i < length; i++) {
  1046. var c = text[i].toLowerCase();
  1047. if (c === "-") continue;
  1048. if (/[a-z0-9]/.test(c)) {
  1049. if (/[0-9]/.test(c) && +c >= absBase) {
  1050. if (c === "1" && absBase === 1) continue;
  1051. throw new Error(c + " is not a valid digit in base " + base + ".")
  1052. } else if (c.charCodeAt(0) - 87 >= absBase) {
  1053. throw new Error(c + " is not a valid digit in base " + base + ".")
  1054. }
  1055. }
  1056. }
  1057. if (2 <= base && base <= 36) {
  1058. if (length <= LOG_MAX_INT / Math.log(base)) {
  1059. var result = parseInt(text, base);
  1060. if (isNaN(result)) {
  1061. throw new Error(c + " is not a valid digit in base " + base + ".")
  1062. }
  1063. return new SmallInteger(parseInt(text, base))
  1064. }
  1065. }
  1066. base = parseValue(base);
  1067. var digits = [];
  1068. var isNegative = text[0] === "-";
  1069. for (i = isNegative ? 1 : 0; i < text.length; i++) {
  1070. var c = text[i].toLowerCase(),
  1071. charCode = c.charCodeAt(0);
  1072. if (48 <= charCode && charCode <= 57) digits.push(parseValue(c));
  1073. else if (97 <= charCode && charCode <= 122) digits.push(parseValue(c.charCodeAt(0) - 87));
  1074. else if (c === "<") {
  1075. var start = i;
  1076. do {
  1077. i++
  1078. } while (text[i] !== ">");
  1079. digits.push(parseValue(text.slice(start + 1, i)))
  1080. } else throw new Error(c + " is not a valid character")
  1081. }
  1082. return parseBaseFromArray(digits, base, isNegative)
  1083. };
  1084.  
  1085. function parseBaseFromArray(digits, base, isNegative) {
  1086. var val = Integer[0],
  1087. pow = Integer[1],
  1088. i;
  1089. for (i = digits.length - 1; i >= 0; i--) {
  1090. val = val.add(digits[i].times(pow));
  1091. pow = pow.times(base)
  1092. }
  1093. return isNegative ? val.negate() : val
  1094. }
  1095.  
  1096. function stringify(digit) {
  1097. if (digit <= 35) {
  1098. return "0123456789abcdefghijklmnopqrstuvwxyz".charAt(digit)
  1099. }
  1100. return "<" + digit + ">"
  1101. }
  1102.  
  1103. function toBase(n, base) {
  1104. base = bigInt(base);
  1105. if (base.isZero()) {
  1106. if (n.isZero()) return {
  1107. value: [0],
  1108. isNegative: false
  1109. };
  1110. throw new Error("Cannot convert nonzero numbers to base 0.")
  1111. }
  1112. if (base.equals(-1)) {
  1113. if (n.isZero()) return {
  1114. value: [0],
  1115. isNegative: false
  1116. };
  1117. if (n.isNegative()) return {
  1118. value: [].concat.apply([], Array.apply(null, Array(-n)).map(Array.prototype.valueOf, [1, 0])),
  1119. isNegative: false
  1120. };
  1121. var arr = Array.apply(null, Array(+n - 1)).map(Array.prototype.valueOf, [0, 1]);
  1122. arr.unshift([1]);
  1123. return {
  1124. value: [].concat.apply([], arr),
  1125. isNegative: false
  1126. }
  1127. }
  1128. var neg = false;
  1129. if (n.isNegative() && base.isPositive()) {
  1130. neg = true;
  1131. n = n.abs()
  1132. }
  1133. if (base.equals(1)) {
  1134. if (n.isZero()) return {
  1135. value: [0],
  1136. isNegative: false
  1137. };
  1138. return {
  1139. value: Array.apply(null, Array(+n)).map(Number.prototype.valueOf, 1),
  1140. isNegative: neg
  1141. }
  1142. }
  1143. var out = [];
  1144. var left = n,
  1145. divmod;
  1146. while (left.isNegative() || left.compareAbs(base) >= 0) {
  1147. divmod = left.divmod(base);
  1148. left = divmod.quotient;
  1149. var digit = divmod.remainder;
  1150. if (digit.isNegative()) {
  1151. digit = base.minus(digit).abs();
  1152. left = left.next()
  1153. }
  1154. out.push(digit.toJSNumber())
  1155. }
  1156. out.push(left.toJSNumber());
  1157. return {
  1158. value: out.reverse(),
  1159. isNegative: neg
  1160. }
  1161. }
  1162.  
  1163. function toBaseString(n, base) {
  1164. var arr = toBase(n, base);
  1165. return (arr.isNegative ? "-" : "") + arr.value.map(stringify).join("")
  1166. }
  1167. BigInteger.prototype.toArray = function (radix) {
  1168. return toBase(this, radix)
  1169. };
  1170. SmallInteger.prototype.toArray = function (radix) {
  1171. return toBase(this, radix)
  1172. };
  1173. BigInteger.prototype.toString = function (radix) {
  1174. if (radix === undefined) radix = 10;
  1175. if (radix !== 10) return toBaseString(this, radix);
  1176. var v = this.value,
  1177. l = v.length,
  1178. str = String(v[--l]),
  1179. zeros = "0000000",
  1180. digit;
  1181. while (--l >= 0) {
  1182. digit = String(v[l]);
  1183. str += zeros.slice(digit.length) + digit
  1184. }
  1185. var sign = this.sign ? "-" : "";
  1186. return sign + str
  1187. };
  1188. SmallInteger.prototype.toString = function (radix) {
  1189. if (radix === undefined) radix = 10;
  1190. if (radix != 10) return toBaseString(this, radix);
  1191. return String(this.value)
  1192. };
  1193. BigInteger.prototype.toJSON = SmallInteger.prototype.toJSON = function () {
  1194. return this.toString()
  1195. };
  1196. BigInteger.prototype.valueOf = function () {
  1197. return parseInt(this.toString(), 10)
  1198. };
  1199. BigInteger.prototype.toJSNumber = BigInteger.prototype.valueOf;
  1200. SmallInteger.prototype.valueOf = function () {
  1201. return this.value
  1202. };
  1203. SmallInteger.prototype.toJSNumber = SmallInteger.prototype.valueOf;
  1204.  
  1205. function parseStringValue(v) {
  1206. if (isPrecise(+v)) {
  1207. var x = +v;
  1208. if (x === truncate(x)) return new SmallInteger(x);
  1209. throw new Error("Invalid integer: " + v)
  1210. }
  1211. var sign = v[0] === "-";
  1212. if (sign) v = v.slice(1);
  1213. var split = v.split(/e/i);
  1214. if (split.length > 2) throw new Error("Invalid integer: " + split.join("e"));
  1215. if (split.length === 2) {
  1216. var exp = split[1];
  1217. if (exp[0] === "+") exp = exp.slice(1);
  1218. exp = +exp;
  1219. if (exp !== truncate(exp) || !isPrecise(exp)) throw new Error("Invalid integer: " + exp + " is not a valid exponent.");
  1220. var text = split[0];
  1221. var decimalPlace = text.indexOf(".");
  1222. if (decimalPlace >= 0) {
  1223. exp -= text.length - decimalPlace - 1;
  1224. text = text.slice(0, decimalPlace) + text.slice(decimalPlace + 1)
  1225. }
  1226. if (exp < 0) throw new Error("Cannot include negative exponent part for integers");
  1227. text += new Array(exp + 1).join("0");
  1228. v = text
  1229. }
  1230. var isValid = /^([0-9][0-9]*)$/.test(v);
  1231. if (!isValid) throw new Error("Invalid integer: " + v);
  1232. var r = [],
  1233. max = v.length,
  1234. l = LOG_BASE,
  1235. min = max - l;
  1236. while (max > 0) {
  1237. r.push(+v.slice(min, max));
  1238. min -= l;
  1239. if (min < 0) min = 0;
  1240. max -= l
  1241. }
  1242. trim(r);
  1243. return new BigInteger(r, sign)
  1244. }
  1245.  
  1246. function parseNumberValue(v) {
  1247. if (isPrecise(v)) {
  1248. if (v !== truncate(v)) throw new Error(v + " is not an integer.");
  1249. return new SmallInteger(v)
  1250. }
  1251. return parseStringValue(v.toString())
  1252. }
  1253.  
  1254. function parseValue(v) {
  1255. if (typeof v === "number") {
  1256. return parseNumberValue(v)
  1257. }
  1258. if (typeof v === "string") {
  1259. return parseStringValue(v)
  1260. }
  1261. return v
  1262. }
  1263. for (var i = 0; i < 1e3; i++) {
  1264. Integer[i] = new SmallInteger(i);
  1265. if (i > 0) Integer[-i] = new SmallInteger(-i)
  1266. }
  1267. Integer.one = Integer[1];
  1268. Integer.zero = Integer[0];
  1269. Integer.minusOne = Integer[-1];
  1270. Integer.max = max;
  1271. Integer.min = min;
  1272. Integer.gcd = gcd;
  1273. Integer.lcm = lcm;
  1274. Integer.isInstance = function (x) {
  1275. return x instanceof BigInteger || x instanceof SmallInteger
  1276. };
  1277. Integer.randBetween = randBetween;
  1278. Integer.fromArray = function (digits, base, isNegative) {
  1279. return parseBaseFromArray(digits.map(parseValue), parseValue(base || 10), isNegative)
  1280. };
  1281. return Integer
  1282. }();
  1283. if (typeof module !== "undefined" && module.hasOwnProperty("exports")) {
  1284. module.exports = bigInt
  1285. }
  1286. if (typeof define === "function" && define.amd) {
  1287. define("big-integer", [], function () {
  1288. return bigInt
  1289. })
  1290. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!