我有一些麻烦，实现Karatsuba的算法。我的项目我限制了以下库：iostream的，了iomanip，cctype，CString的。此外，我仅限使用整数内置类型和阵列/动态数组来处理数字（唯一的无符号整数将被输入）。我已经建立了一个类来处理使用动态数组的任意大小的整数。我需要实现一个函数，乘大整数，我想使用Karatsuba的如果可能的话。我遇到的麻烦是如何拆分大的整数，做呼吁算法中的乘法。我想这应该是递归完成。我希望有人可以给我如何做到这一点的一个例子。

I'm having some trouble implementing the Karatsuba algorithm. My project limits me to the following libraries: iostream, iomanip, cctype, cstring. Also, I'm limited to only using the integer built-in type and arrays/dynamic arrays to handle numbers (only unsigned integers will be input). I've built a class to handle integers of arbitrary size using dynamic arrays. I need to implement a function that multiplies big integers, and I'd like to use Karatsuba if possible. The trouble I'm running into is how to break apart large integers and do the multiplications called for in the algorithm. I assume this should be done recursively. I was hoping someone could give me an example of how to do this.

例如：

我有存储在动态数组两个数字。比方说，他们是：

I have two numbers stored in dynamic arrays. Let's say they are:

X = 123456789123456789123456789 Y = 987654321987654321987654321987654321

X = 123456789123456789123456789 Y = 987654321987654321987654321987654321

如何Karatsuba的需要处理这个问题，给出的无符号整数类型的存储限制？任何帮助将是非常美联社preciated！

How would Karatsuba need to handle this, given the storage limitations on the unsigned int type? Any help would be much appreciated!

推荐答案

如果你看一下伪code的此处（页面底部附近），你可以修改它有点与这样一个数组的使用方法：

If you look at the Pseudo-code here (near the bottom of the page), you can modify it a little to use with an array like so:

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)) + ((z1-z2-z0).shiftLeft(m/2)) + (z0)

只要你有一个加法，减法和定义你的电话号码数组，该算法应该很容易实现pretty的（当然还有其他必需的程序，例如数字移动和阵列分裂）额外的个位数的乘法程序。

Provided you have an addition, subtraction and extra single-digit multiplication routine defined for your number arrays this algorithm should be implemented pretty easily (of course along with the other required routines such as digit shifting and array splitting).

因此​​，对于那些其他例程其它preliminary工作，但是这是怎么Karatsuba的例行程序将被执行。

So, there is other preliminary work for those other routines, but that is how the Karatsuba routine would be implemented.