给出不精确答案的递归 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).

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

Recursive Karatsuba Algorithm giving Imprecise Answers

c++

algorithm

math

boost

karatsuba