Karatsuba C++实现

Question

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

例如：

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

X= 123456789123456789123456789 Y= 987654321987654321987654321987654321

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

Answer 1

如果您查看伪代码here，您可以对其进行一些修改，以使用如下所示的数组：

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例程的实现方式。

Answer 2

伪代码中存在错误，即

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

它应该是

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