362 lines
10 KiB
JavaScript
362 lines
10 KiB
JavaScript
import { at } from "./utilities.js";
|
|
|
|
const L = 4;
|
|
const MAX = 9999;
|
|
const LIM = 10000;
|
|
|
|
const kBuffer = Symbol("buffer");
|
|
|
|
export class BigInteger {
|
|
/**
|
|
* @private
|
|
*/
|
|
static zero = BigInteger.from("0");
|
|
/**
|
|
* @private
|
|
*/
|
|
static one = BigInteger.from("1");
|
|
/**
|
|
* @private
|
|
*/
|
|
static two = BigInteger.from("2");
|
|
|
|
/**
|
|
* @param { number[] } buffer
|
|
* @param {boolean} [negative]
|
|
*/
|
|
constructor(buffer, negative = false) {
|
|
this[kBuffer] = buffer;
|
|
this.negative = negative;
|
|
}
|
|
|
|
/**
|
|
* @param { string } str
|
|
*/
|
|
static from(str) {
|
|
const negative = str[0] === "-";
|
|
if (negative) str = str.substring(1);
|
|
/**@type { number[] } */
|
|
const buffer = [];
|
|
let i = str.length;
|
|
let j = i - L;
|
|
while (j > 0) {
|
|
buffer.push(Number.parseInt(str.substring(j, i)));
|
|
j -= L;
|
|
i -= L;
|
|
}
|
|
buffer.push(Number.parseInt(str.substring(0, i)));
|
|
return new BigInteger(buffer, negative);
|
|
}
|
|
|
|
/**
|
|
* @param { BigInteger } a
|
|
* @param { BigInteger } b
|
|
*/
|
|
static ucmp(a, b) {
|
|
const l = a[kBuffer].length;
|
|
if (l !== b[kBuffer].length) return l > b[kBuffer].length ? 1 : -1;
|
|
for (let i = l - 1; i >= 0; i--) {
|
|
if (a[kBuffer][i] !== b[kBuffer][i]) return a[kBuffer][i] > b[kBuffer][i] ? 1 : -1;
|
|
}
|
|
return 0;
|
|
}
|
|
|
|
/**
|
|
* @param { BigInteger } num
|
|
*/
|
|
static isZero(num) {
|
|
return num[kBuffer].length === 1 && num[kBuffer][0] === 0;
|
|
}
|
|
|
|
/**
|
|
* @param { boolean } [negative]
|
|
* @returns { BigInteger }
|
|
*/
|
|
copy(negative = this.negative) {
|
|
return new BigInteger(Array.from(this[kBuffer]), negative);
|
|
}
|
|
|
|
/**
|
|
* @returns { BigInteger }
|
|
*/
|
|
shallowCopy() {
|
|
return new BigInteger(this[kBuffer], this.negative);
|
|
}
|
|
|
|
/**
|
|
* @param { BigInteger } num
|
|
* @param { boolean } [negative]
|
|
* @returns { this }
|
|
*/
|
|
assign(num, negative = num.negative) {
|
|
this[kBuffer] = Array.from(num[kBuffer]);
|
|
this.negative = negative;
|
|
return this;
|
|
}
|
|
|
|
/**
|
|
* @returns { this }
|
|
*/
|
|
toggleSign() {
|
|
this.negative = !this.negative;
|
|
return this;
|
|
}
|
|
|
|
/**
|
|
* @param { boolean } negative
|
|
* @returns { this }
|
|
*/
|
|
setSign(negative) {
|
|
this.negative = negative;
|
|
return this;
|
|
}
|
|
|
|
toString() {
|
|
const buff = this[kBuffer];
|
|
let accum = this.negative ? "-" : "";
|
|
accum += buff[buff.length - 1].toString();
|
|
for (let i = buff.length - 2; i >= 0; i--) accum += buff[i].toString().padStart(4, "0");
|
|
return accum;
|
|
}
|
|
|
|
/**
|
|
* @param { BigInteger } num
|
|
* @param { boolean } [negative]
|
|
* @returns { this }
|
|
*/
|
|
add(num, negative = num.negative) {
|
|
if (this.negative !== negative) return this.negative ? this.sub(num, true) : this.sub(num, false);
|
|
const buffA = this[kBuffer];
|
|
const buffB = num[kBuffer];
|
|
let carry = 0;
|
|
for (let i = 0; i < buffB.length; i++) {
|
|
while (buffA.length <= i) buffA.push(0);
|
|
buffA[i] += buffB[i] + carry;
|
|
carry = Number(buffA[i] > MAX);
|
|
if (carry) buffA[i] %= LIM;
|
|
}
|
|
if (carry) {
|
|
let i = buffB.length;
|
|
while (buffA.length <= i) buffA.push(0);
|
|
while (buffA[i] === MAX) {
|
|
buffA[i++] = 0;
|
|
while (buffA.length <= i) buffA.push(0);
|
|
}
|
|
buffA[i] += carry;
|
|
}
|
|
return this;
|
|
}
|
|
|
|
// /**
|
|
// * @param { BigInteger } num
|
|
// * @param { boolean } [negative]
|
|
// * @returns { this }
|
|
// */
|
|
// add(num, negative = num.negative) {
|
|
// if (this.negative !== negative) return this.sub(num, this.negative);
|
|
// return this.uadd(num);
|
|
// }
|
|
|
|
// /**
|
|
// * @param { BigInteger } num
|
|
// * @returns { this }
|
|
// */
|
|
// uadd(num) {
|
|
// const buffA = this[kBuffer];
|
|
// const buffB = num[kBuffer];
|
|
// let carry = 0;
|
|
// let i = 0;
|
|
// while (buffA.length < buffB.length) buffA.push(0);
|
|
// for (; i < buffB.length; i++) {
|
|
// buffA[i] += buffB[i] + carry;
|
|
// carry = Number(buffA[i] > MAX);
|
|
// if (carry) buffA[i] %= LIM;
|
|
// }
|
|
// if (carry === 1) {
|
|
// while (at(buffA, i, 0) === MAX) buffA[i++] = 0;
|
|
// buffA[i] += carry;
|
|
// }
|
|
// return this;
|
|
// }
|
|
|
|
/**
|
|
* @param { BigInteger } num
|
|
* @param { boolean } [negative]
|
|
* @returns { this }
|
|
*/
|
|
sub(num, negative = num.negative) {
|
|
if (this.negative !== negative) return this.negative ? this.add(num, true) : this.add(num, false);
|
|
if (BigInteger.ucmp(num, this) == 1) {
|
|
const self = this.shallowCopy();
|
|
return this.assign(num, negative).sub(self).toggleSign();
|
|
}
|
|
const buffA = this[kBuffer];
|
|
const buffB = num[kBuffer];
|
|
let carry = 0;
|
|
for (let i = 0; i < buffB.length; i++) {
|
|
buffA[i] -= buffB[i] + carry;
|
|
carry = Number(buffA[i] < 0);
|
|
if (carry) buffA[i] += LIM;
|
|
}
|
|
if (carry) {
|
|
let i = buffB.length;
|
|
while (buffA[i] === 0) buffA[i++] = MAX;
|
|
buffA[i] -= carry;
|
|
}
|
|
while (buffA.length > 1 && buffA[buffA.length - 1] == 0) buffA.pop();
|
|
return this;
|
|
}
|
|
|
|
// /**
|
|
// * @param { BigInteger } num
|
|
// * @param { boolean } [negative]
|
|
// * @returns { this }
|
|
// */
|
|
// sub(num, negative = num.negative) {
|
|
// if (this.negative !== negative) return this.add(num, this.negative);
|
|
// return this.usub(num);
|
|
// }
|
|
|
|
// /**
|
|
// * @param { BigInteger } num
|
|
// * @returns { this }
|
|
// */
|
|
// usub(num) {
|
|
// if (BigInteger.ucmp(num, this) == 1) {
|
|
// const self = this.shallowCopy();
|
|
// return this.assign(num, !this.negative).usub(self)
|
|
// }
|
|
// const buffA = this[kBuffer];
|
|
// const buffB = num[kBuffer];
|
|
// let carry = 0;
|
|
// let i = 0;
|
|
// for (; i < buffB.length; i++) {
|
|
// buffA[i] -= buffB[i] + carry;
|
|
// carry = Number(buffA[i] < 0);
|
|
// if (carry) buffA[i] += LIM;
|
|
// }
|
|
// if (carry == 1) {
|
|
// while (buffA[i] === 0) buffA[i++] = MAX;
|
|
// buffA[i] -= carry;
|
|
// }
|
|
// for (let i = buffA.length - 1; i > 0 && buffA[i] === 0; i--) buffA.pop();
|
|
// return this;
|
|
// }
|
|
|
|
/**
|
|
* @param { BigInteger } num
|
|
* @returns { this }
|
|
*/
|
|
mul(num) {
|
|
/**@type { number[] } */
|
|
const buff = [];
|
|
for (let i = 0; i < this[kBuffer].length; i++) {
|
|
const a = this[kBuffer][i];
|
|
for (let j = 0; j < num[kBuffer].length; j++) {
|
|
const b = num[kBuffer][j];
|
|
let k = i + j;
|
|
while (buff.length <= k) buff.push(0);
|
|
buff[k] += a * b;
|
|
while (buff[k] > MAX) {
|
|
const carry = Math.trunc(buff[k] / LIM)
|
|
buff[k++] %= LIM;
|
|
while (buff.length <= k) buff.push(0);
|
|
buff[k] += carry;
|
|
}
|
|
}
|
|
}
|
|
|
|
this[kBuffer] = buff;
|
|
this.negative = this.negative !== num.negative;
|
|
return this;
|
|
}
|
|
|
|
// /**
|
|
// * @param { BigInteger } num
|
|
// * @returns { this }
|
|
// */
|
|
// mul(num) {
|
|
// return this.umul(num).setSign(this.negative !== num.negative);
|
|
// }
|
|
|
|
// /**
|
|
// * @param { BigInteger } num
|
|
// * @returns { this }
|
|
// */
|
|
// umul(num) {
|
|
// /**@type { number[] } */
|
|
// const buff = [];
|
|
// for (let i = 0; i < this[kBuffer].length; i++) {
|
|
// const a = this[kBuffer][i];
|
|
// for (let j = 0; j < num[kBuffer].length; j++) {
|
|
// const b = num[kBuffer][j];
|
|
// let k = i + j;
|
|
// while (buff.length <= k) buff.push(0);
|
|
// buff[k] += a * b;
|
|
// while (buff[k] > MAX) {
|
|
// const carry = Math.trunc(buff[k] / LIM)
|
|
// buff[k++] %= LIM;
|
|
// while (buff.length <= k) buff.push(0);
|
|
// buff[k] += carry;
|
|
// }
|
|
// }
|
|
// }
|
|
// this[kBuffer] = buff;
|
|
// return this;
|
|
// }
|
|
|
|
/**
|
|
* @param { BigInteger } num
|
|
* @returns { this }
|
|
*/
|
|
div(num) {
|
|
const buffB = num[kBuffer];
|
|
const l = buffB.length - 1;
|
|
let quick = true;
|
|
for (let i = 0; i < l && quick; i++) quick = (buffB[i] == 0);
|
|
if (quick) {
|
|
const D = buffB[l];
|
|
const N = this[kBuffer].slice(l);
|
|
let carry = 0;
|
|
for (let i = N.length - 1; i >= 0; i--) {
|
|
N[i] += (carry * LIM);
|
|
carry = N[i] % D;
|
|
N[i] = Math.trunc(N[i] / D);
|
|
}
|
|
if (N.length < 1) N.push(0);
|
|
while (N.length > 1 && N[N.length - 1] == 0) N.pop();
|
|
this[kBuffer] = N;
|
|
this.negative = this.negative !== num.negative;
|
|
return this;
|
|
}
|
|
|
|
const A = num.copy();
|
|
for (let i = 0; i < l; i++) A[kBuffer][i] = 0;
|
|
const Q = this.copy().div(A);
|
|
const R = num.copy().add(BigInteger.one, num.negative);
|
|
const TMP = BigInteger.zero.copy();
|
|
while (BigInteger.ucmp(R, num) != -1) {
|
|
TMP.assign(Q).mul(num);
|
|
R.assign(this).sub(TMP);
|
|
TMP.assign(R).div(A).add(Q);
|
|
Q.add(TMP).div(BigInteger.two);
|
|
}
|
|
TMP.assign(Q).mul(num);
|
|
R.assign(this).sub(TMP);
|
|
if (this.negative !== R.negative && !BigInteger.isZero(R)) {
|
|
Q.sub(BigInteger.one, Q.negative);
|
|
R.add(num);
|
|
}
|
|
this[kBuffer] = Q[kBuffer];
|
|
this.negative = Q.negative;
|
|
return this;
|
|
}
|
|
|
|
/**
|
|
* @param { BigInteger } num
|
|
* @returns { this }
|
|
*/
|
|
udiv(num) {
|
|
throw new Error("Not Implemented");
|
|
}
|
|
} |