Я пытаюсь реализовать свой собственный класс LargeInteger в javascript (и позже перенесет на Java и Swift в случае успеха).Тем не менее, время работы не является удовлетворительным.Я хотел бы посмотреть, что я мог бы сделать, чтобы улучшить реализацию.
Я реализовал умножение Канатусбы и использовал метод Ньютона для деления.Тем не менее, они по-прежнему занимают много времени, особенно с длинными номерами
class LargeInteger {
//positive, digits
//constructor
constructor(s) {
if (s == "") {
return new LargeInteger("0");
}
//trim leading zeros
var i = 0;
while (s[i] == "0") {
i++;
}
s = s.substring(i);
if (s == "") {
s = "0";
}
this.positive = !(s[0] == "-");
this.digits = [];
if (this.positive) {
for (var i = 0; i < s.length; i++) {
this.digits.push(parseInt(s[i]));
}
} else {
for (var i = 1; i < s.length; i++) {
this.digits.push(parseInt(s[i]));
}
}
}
static init(digits, positive) {
if (positive) {
return new LargeInteger(digits.join(""));
} else {
return new LargeInteger("-" + digits.join(""));
}
}
get length() {
return this.digits.length;
}
isZero() {
return ((this.length == 1) && (this.digit(0) == 0))
}
isOne() {
return ((this.length == 1) && (this.digit(0) == 1))
}
//getter - nth digit
digit(n) {
return this.digits[n];
}
//print
print() {
if (this.positive) {
return this.digits.join("");
} else {
return "-" + this.digits.join("");
}
}
//negation
negate() {
return LargeInteger.init(this.digits, !this.positive);
}
//addition
add(q) {
if ((this.positive) && (!q.positive)) {
return this.subtract(q.negate());
} else if ((!this.positive) && (q.positive)) {
return q.subtract(this.negate());
}
var m = this.length;
var n = q.length;
if (m >= n) {
var larger = this;
var smaller = q;
} else {
var larger = q;
var smaller = this;
m = q.length;
n = this.length;
}
//longer (length m), shorter (length n)
var sumDigits = [];
var carry = 0;
var reverseDigitCount = 0;
for (reverseDigitCount = 0; reverseDigitCount < n; reverseDigitCount++) {
var sumDigit = larger.digit(m - reverseDigitCount - 1) + smaller.digit(n - reverseDigitCount - 1) + carry;
if (sumDigit >= 10) {
carry = 1;
sumDigit -= 10;
} else {
carry = 0;
}
if (reverseDigitCount == 0) {
sumDigits[0] = sumDigit;
} else {
sumDigits.unshift(sumDigit);
}
}
for (reverseDigitCount = reverseDigitCount; reverseDigitCount < m; reverseDigitCount++) {
if (larger.digit(m - reverseDigitCount - 1) + carry >= 10) {
sumDigits.unshift(larger.digit(m - reverseDigitCount - 1) + carry - 10);
carry = 1;
} else {
sumDigits.unshift(larger.digit(m - reverseDigitCount - 1) + carry);
carry = 0;
}
}
if (reverseDigitCount == m) {
if (carry == 1) {
sumDigits.unshift(1);
}
reverseDigitCount++;
}
var sum = new LargeInteger(sumDigits.join(""));
if ((this.positive) && (q.positive)) {
return sum;
} else {
return sum.negate();
}
}
//comparison
compare(q) {
if ((this.positive) && (!q.positive)) {
return 1;
}
if ((!this.positive) && (q.positive)) {
return -1;
}
if (this.length > q.length) {
if ((this.positive) && (q.positive)) {
return 1;
} else {
return -1;
}
}
if (q.length > this.length) {
if ((this.positive) && (q.positive)) {
return -1;
} else {
return 1;
}
}
for (var i = 0; i < this.length; i++) {
if (this.digit(i) > q.digit(i)) {
if ((this.positive) && (q.positive)) {
return 1;
} else {
return -1;
}
} else if (this.digit(i) < q.digit(i)) {
if ((this.positive) && (q.positive)) {
return -1;
} else {
return 1;
}
}
}
return 0;
}
//subtraction
subtract(q) {
if (this.compare(q) == 0) {
return new LargeInteger("0");
}
if (!q.positive) {
return this.add(q.negate());
}
if (this.compare(q) == -1) {
return q.subtract(this).negate();
}
//this larger than q
var m = this.length;
var n = q.length;
var diffDigits = [];
var carry = 0;
var reverseDigitCount = 0;
for (reverseDigitCount = 0; reverseDigitCount < n; reverseDigitCount++) {
var diffDigit = this.digit(m - reverseDigitCount - 1) - q.digit(n - reverseDigitCount - 1) + carry;
if (diffDigit < 0) {
carry = -1;
diffDigit += 10;
} else {
carry = 0;
}
if (reverseDigitCount == 0) {
diffDigits[0] = diffDigit;
} else {
diffDigits.unshift(diffDigit);
}
}
for (reverseDigitCount = reverseDigitCount; reverseDigitCount < m; reverseDigitCount++) {
if (this.digit(m - reverseDigitCount - 1) + carry < 0) {
diffDigits.unshift(this.digit(m - reverseDigitCount - 1) + carry + 10);
carry = -1;
} else {
diffDigits.unshift(this.digit(m - reverseDigitCount - 1) + carry);
carry = 0;
}
}
var difference = new LargeInteger(diffDigits.join(""));
return difference;
}
//multiplication
multiply(q) {
if ((this.isZero()) || (q.isZero())) {
return new LargeInteger("0");
}
if ((this.positive) && (!q.positive)) {
return this.multiply(q.negate()).negate();
} else if ((!this.positive) && (q.positive)) {
return this.negate().multiply(q).negate();
} else if ((!this.positive) && (!q.positive)) {
return this.negate().multiply(q.negate());
}
if ((this.length <= 1) || (q.length <= 1)) {
if (this.length == 1) {
var singleDigit = this;
var theOtherNumber = q;
} else {
var singleDigit = q;
var theOtherNumber = this;
}
var carry = 0;
var productString = "";
for (var i = 0; i < theOtherNumber.length; i++) {
var productTemp = singleDigit.digit(0) * theOtherNumber.digit(theOtherNumber.length - i - 1) + carry;
if (productTemp >= 10) {
productString = (productTemp % 10).toString() + productString;
carry = Math.floor(productTemp / 10);
} else {
productString = productTemp.toString() + productString;
carry = 0;
}
}
if (carry > 0) {
productString = carry.toString() + productString;
}
return new LargeInteger(productString);
}
var m = this.length;
var n = q.length;
var k = (m >= n) ? Math.round(m/2) : Math.round(n/2); //must use the larger
if (this.length >= k + 1) {
var high1 = LargeInteger.init(this.digits.slice(0, m - k), true);
var low1 = LargeInteger.init(this.digits.slice(m - k), true);
} else {
var high1 = new LargeInteger("0");
var low1 = this;
}
if (q.length >= k + 1) {
var high2 = LargeInteger.init(q.digits.slice(0, n - k), true);
var low2 = LargeInteger.init(q.digits.slice(n - k), true);
} else {
var high2 = new LargeInteger("0");
var low2 = q;
}
var x = low1.multiply(low2);
var w = low2.add(high2);
var y = low1.add(high1).multiply(w);
var z = high1.multiply(high2);
var prod1S = z.digits.slice(0);
if (!z.isZero()) {
for (var i = 0; i < 2 * k; i++) {
prod1S.push(0);
}
}
var prod1 = LargeInteger.init(prod1S, true);
var prod2Temp = y.subtract(z).subtract(x);
var prod2S = prod2Temp.digits.slice(0);
if (!prod2Temp.isZero()) {
for (var i = 0; i < k; i++) {
prod2S.push(0);
}
}
var prod2 = LargeInteger.init(prod2S, prod2Temp.positive);
var product = prod1.add(prod2).add(x);
return product;
}
//division by q
divide(q) {
if (this.isZero()) {
return new Array(new LargeInteger("0"), new LargeInteger("0"));
}
if (q.isOne()) {
return new Array(this, new LargeInteger("0"));
}
if (!q.positive) {
var tempResult = this.divide(q.negate());
return new Array(tempResult[0].negate(), tempResult[1]);
}
if (!this.positive) {
var tempResult = this.negate().divide(q);
if (tempResult[1].positive()) {
return new Array(tempResult[0].negate().subtract(new LargeInteger("1")), q.subtract(tempResult[1]));
} else {
return new Array(tempResult[0].negate(), new LargeInteger("0"));
}
}
var m = this.length;
var n = q.length;
if (m < n) {
return new Array(new LargeInteger("0"), this);
}
if (m == n) {
var quotient = new LargeInteger("0");
var compareResult = quotient.multiply(q).compare(this);
for (var i = 1; i <= 9; i++) {
quotient = new LargeInteger(i.toString());
if (quotient.multiply(q).compare(this) != compareResult) {
compareResult = quotient.multiply(q).compare(this);
break;
}
}
if (compareResult != 0) {
quotient = quotient.subtract(new LargeInteger("1"));
}
return new Array(quotient, this.subtract(q.multiply(quotient)));
}
if (m > n) {
//pown = 10^n
//a = floor(10^n/q)
var pownString = "1";
for (var i = 0; i < n; i++) {
pownString += "0";
}
var pown = new LargeInteger(pownString);
var a = new LargeInteger("1");
var compareResult = a.multiply(q).compare(pown);
for (var i = 2; i <= 10; i++) {
a = new LargeInteger(i.toString());
if (a.multiply(q).compare(pown) != compareResult) {
break;
}
}
a = a.subtract(new LargeInteger("1"));
//set y0
var powString = "1";
for (var i = 0; i < m - n; i++) {
powString += "0";
}
var pow = new LargeInteger(powString);
var leastIterate = 1;
if (pown.multiply(new LargeInteger("2")).subtract(q.multiply(new LargeInteger("2")).multiply(a)).compare(q) <= 0) {
var y = [pow.multiply(a)];
} else {
var y = [pow.multiply(a.add(new LargeInteger("1")))];
leastIterate = 2;
}
//y0 prepared
//start iterating
var i = 0;
for (i = 0; i < leastIterate; i++) { //prepared up to y1 or y2
var comp1 = y[i].multiply(y[i]).digits.join(""); //string
var comp2 = new LargeInteger(comp1.substring(0, comp1.length - m + n));
var comp3 = comp2.multiply(q).digits.join(""); //string
var comp = new LargeInteger(comp3.substring(0, comp3.length - n));
y.push(y[i].multiply(new LargeInteger("2")).subtract(comp));
}
while (y[i].compare(y[i-1]) == 1) {
comp1 = y[i].multiply(y[i]).digits.join(""); //string
comp2 = new LargeInteger(comp1.substring(0, comp1.length - m + n));
comp3 = comp2.multiply(q).digits.join(""); //string
comp = new LargeInteger(comp3.substring(0, comp3.length - n));
y.push(y[i].multiply(new LargeInteger("2")).subtract(comp));
i++;
}
var l = y[i];
var powmString = "1";
for (var j = 0; j < m; j++) {
powmString += "0";
}
var powm = new LargeInteger(powmString);
var compareResult = l.multiply(q).compare(powm);
while ((compareResult > 0) && (l.positive)) {
l = l.subtract(new LargeInteger("1"));
compareResult = l.multiply(q).compare(powm);
}
var k = l;
var tString = this.multiply(k).digits.join("");
var t = new LargeInteger(tString.substring(0, tString.length - m));
var tPlusOne = t.add(new LargeInteger("1"));
var compareResult1 = t.multiply(q).compare(this);
var compareResult2 = tPlusOne.multiply(q).compare(this);
if ((compareResult1 <= 0) && (compareResult2 <= 0)) {
var quotient = tPlusOne;
} else if (compareResult1 <= 0) {
var quotient = t;
} else {
var quotient = tPlusOne;
}
var remainder = this.subtract(q.multiply(quotient));
return new Array(quotient, remainder);
}
}
}
Используя мою реализацию, умножение, показанное с временем работы:.
4576238690438690843906845907890348902838908609890843905823904829038429308409 * 355353636389024839058320985423098569024386902385492 = 1626183059631537746502579433539886005813041574495363398753857749993877814539400045882476069301296744527463216854780249875202228
1009 *65,8499999990454 мс
Однако при использовании некоторых других библиотек умножение может быть выполнено в течение 1 мс.