1

我在实现 Karatsuba 算法时遇到了一些麻烦。我的项目限制我使用以下库：iostream、iomanip、cctype、cstring。此外，我仅限于使用整数内置类型和数组/动态数组来处理数字（只会输入无符号整数）。我已经构建了一个类来使用动态数组处理任意大小的整数。我需要实现一个将大整数相乘的函数，如果可能的话，我想使用 Karatsuba。我遇到的麻烦是如何分解大整数并进行算法中要求的乘法运算。我认为这应该递归完成。我希望有人能给我一个如何做到这一点的例子。

例如：

我有两个数字存储在动态数组中。假设它们是：

X = 123456789123456789123456789 Y = 987654321987654321987654321987654321

考虑到 unsigned int 类型的存储限制，Karatsuba 需要如何处理这个问题？任何帮助将非常感激！

4

2 回答 2

3

如果您查看此处的伪代码，您可以对其稍作修改以与数组一起使用，如下所示：

procedure karatsuba(num1, num2)

    if (num1.Length < 2) or (num2.Length < 2) //Length < 2 means number < 10    
        return num1 * num2 //Might require another mult routine that multiplies the arrays by single digits

    /* calculates the size of the numbers */
    m = max(ceiling(num1.Length / 2), ceiling(num2.Length / 2))
    low1, low2 = lower half of num1, num2
    high1, high2 = higher half of num1, num2

    /* 3 calls made to numbers approximately half the size */
    z0 = karatsuba(low1,low2)
    z1 = karatsuba((low1+high1),(low2+high2))
    z2 = karatsuba(high1,high2)

    //Note: In general x * 10 ^ y in this case is simply a left-shift
    //      of the digits in the 'x' array y-places. i.e. 4 * 10 ^ 3
    //      results in the array x[4] = { 4, 0, 0, 0 }
    return (z2.shiftLeft(m*2)) + ((z1-z2-z0).shiftLeft(m)) + (z0)

如果您为数字数组定义了加法、减法和额外的一位数乘法例程，则该算法应该很容易实现（当然还有其他必需的例程，例如数字移位和数组拆分）。

因此，对于这些其他例程还有其他初步工作，但这就是 Karatsuba 例程的实施方式。

于 2013-11-07T17:21:56.803 回答
1

伪代码有错误，即，而不是

return (z2.shiftLeft(m)) + ((z1-z2-z0).shiftLeft(m/2)) + (z0)

它应该是

return (z2.shiftLeft(m*2)) + ((z1-z2-z0).shiftLeft(m)) + (z0)
于 2016-08-09T02:35:07.663 回答