c++ - 给出不精确答案的递归Karatsuba算法

Question

我一直在尝试在C++中为两个相同长度的大数实现Karatsuba乘法算法。我的代码对于较小的数字(例如3456 * 1492)正常工作，但是对于较大的数字(例如具有64位数字的数字)却失败了。通常它的前几位数字正确无误，但此后会出错。我正在使用Boost多精度库来处理大整数。

我的代码如下:

cpp_int karatsuba(cpp_int n1, cpp_int n2) {
    if (n1 < 10 || n2 < 10) {
        return n1 * n2;
    }

    int len = countDigits(n1);

    cpp_int a = n1 / cpp_int(pow(10, len/2));
    cpp_int b = n1 % cpp_int(pow(10, len/2));
    cpp_int c = n2 / cpp_int(pow(10, len/2));
    cpp_int d = n2 % cpp_int(pow(10, len/2));

    cpp_int sub1 = karatsuba(a, c);
    cpp_int sub2 = karatsuba(b, d);
    cpp_int sub3 = karatsuba(a+b, c+d) - sub1 - sub2;

    return sub1 * cpp_int(pow(10, len)) + sub3 * cpp_int(pow(10, len/2)) + sub2;
}

我已经将我的代码与几种在线实现进行了比较，但是我没有发现任何会影响答案的重大差异。 cpp_int类型的精度是否存在问题，或者我的代码存在问题？

非常感谢你的帮助!

Answer 1

我怀疑一个问题是pow返回的浮点表示形式已被错误地转换为cpp_int。

使用pow的多精度版本可能会有所帮助。

此外，len / 2会四舍五入，因此在计算pow(10，len)时应改为pow(10，(len / 2)* 2)。