Karatsuba乘法算法的JavaScript实现

function karatsuba(x, y) {
    // 将输入转换为字符串以获取长度
    const xStr = x.toString();
    const yStr = y.toString();
    const n = Math.max(xStr.length, yStr.length);
    const m = Math.floor(n / 2);

    // 如果数字长度小于或等于1，直接相乘
    if (n === 1) return x * y;

    // 补零使两个数字长度相同
    const high1 = parseInt(xStr.substring(0, xStr.length - m), 10);
    const low1 = parseInt(xStr.substring(xStr.length - m), 10);
    const high2 = parseInt(yStr.substring(0, yStr.length - m), 10);
    const low2 = parseInt(yStr.substring(yStr.length - m), 10);

    // 递归计算三个乘积
    const z0 = karatsuba(low1, low2);
    const z1 = karatsuba((low1 + high1), (low2 + high2));
    const z2 = karatsuba(high1, high2);

    // 组合结果
    return (z2 * Math.pow(10, 2 * m)) + ((z1 - z2 - z0) * Math.pow(10, m)) + z0;
}

// 示例
console.log(karatsuba(1234, 5678)); // 输出: 7006652