Search code examples
javascriptalgorithmbigintkaratsuba

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?


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?

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));


Solution

  • Invoking Math.pow is very suspicious. According to documentation, it

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

    You don't want any approximations in Karatzuba.