c++ - Karatsuba C++ 实现

Question

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

例如:

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

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