Karatsuba算法的实现，该方法只计算小数字正确，但大答案不正确，问题是什么？

Question

Karatsuba算法的实现，该方法只计算小数正确，但大答案不正确，有什么问题？

var x = "1685287499328328297814655639278583667919355849391453456921116729";
var y = "7114192848577754587969744626558571536728983167954552999895348492";

function karatsuba(x, y) {
    if (x.length < 2 && y.length < 2) {
        return BigInt(parseInt(x) * parseInt(y));
    }
    var m = Math.min(x.length, y.length);
    var m2 = m / 2;
    var a = BigInt(x.substring(0, m2));
    var b = BigInt(x.substring(m2));
    var c = BigInt(y.substring(0, m2));
    var d = BigInt(y.substring(m2));
    var ac = a * c;
    var bd = b * d;
    var sum = (a + b) * (c + d) - ac - bd;

    return BigInt(Math.pow(10, m)) * ac + BigInt(Math.pow(10, m2)) * sum + bd;
}

console.log(karatsuba(x, y));

Answer 1

调用 Math.pow 非常可疑。根据documentation，它

Returns an implementation-dependent approximation to the result of raising x to the power y.

您不想在 Karatzuba 中使用任何近似值。

Answer 2

除了：

您在拆分数字时使用 m2，但在缩放 before/in 组合/“（多项式）评估”时（也）使用 m。

你需要使用 2*m2.

Answer 3

return BigInt(parseInt(x) * parseInt(y));

在构造 BigInt 之前将大的东西相乘是不对的。

Karatsuba算法的实现，该方法只计算小数字正确，但大答案不正确，问题是什么？

the implementation of the Karatsuba algorithm, the method only counts the small numbers true, but the big answer is not correct, what's the problem?

javascript

algorithm

bigint

karatsuba