Javascript中的Karatsuba算法

Karatsuba Algorithm in Javascript

本文关键字：算法 Karatsuba 中的 Javascript      更新时间：2023-09-26

我用Javascript实现了Karatsuba的算法。

const multiply = (a, b) => {
    let sizeA = numOfDigits(a);
    let sizeB = numOfDigits(b);
    if(sizeA < sizeB) {
        a = '0'.repeat(sizeB-sizeA).concat(a);
    }
    else if(sizeB < sizeA) {
        b = '0'.repeat(sizeA - sizeB).concat(b);
    }
    if (numOfDigits(a) === 1 && numOfDigits(b) === 1) {
        return a * b;
    } else {
        let n = numOfDigits(a);
        n = ( n % 2 === 0 ) ? n : n + 1;
        let n_2 =  parseInt(Math.ceil(n /2));
        let splitA = reduceInHalf(a);
        let splitB = reduceInHalf(b);
        let p = splitA[0];
        let q = splitA[1];
        let r = splitB[0];
        let s = splitB[1];
        let u = multiply(p, r);
        let v = multiply((q - p).toString(), (s - r).toString());
        let w = multiply(q, s);
        let product = u * Math.pow(10,n) + (u + w - v) * Math.pow(10, n_2) + w;
        return product;
    }
}

当我传递非常大的数字时，它会失败，比如2个64位的数字。我遇到了最大调用栈的问题。我还遇到了另一个返回错误结果的实现。

对于2个32位数的数字也可以正常工作。只要我输入2个64位的数字，它就会进入一个不终止的递归。这能实现吗?

看起来你依赖于JavaScript数字功能的各个部分(例如q - p，和所有的u * Math.pow(10,n) + (u + w - v) * Math.pow(10, n_2) + w);但是JavaScript数字是双精度浮点值。它们不能精确地表示超过16位的整数。(参见"可存储在双精度体中的最大整数")

如果你想用非常大的整数做数学，你需要找到一个大整数库，或者自己管理它(使用字符串或数组或诸如此类的东西)。

相关文章：