1

我一直在尝试在 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或者我的代码中是否存在问题？

非常感谢你的帮助！

4

1 回答 1

2

我怀疑一个问题是 pow 正在返回一个浮点表示，该表示被不准确地转换为 cpp_int。

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

此外，len/2 向下取整，因此在计算 pow(10,len) 时，应该改为 pow(10,(len/2)*2)。

于 2020-05-25T21:46:12.623 回答