大整数乘法中的分治思想（TOOM-COOK的一种使用方法）

算法分析与设计学习中，接触到一道大整数乘法问题，分享出来，原题目如下：

算法分析在用分治法求两个n位大整数u和v的乘积时，将u和v都分割为长度为n/3的3段。证明可以用5次n/3位整数的乘法求得uv的值。按此思想设计大整数乘积的分治方法，并分析算法的计算复杂性。

先参考一道较为简单的题目：设有两个n位二进制数X，Y，求它们的乘积XY。
分析：按照一般算法，根据小学数学乘法规律，两个数中每位数都需要相应做乘法，则需要的时间复杂度是O(n^2)。

此时，我们考虑将X，Y分为高位、低位，即
X = | A| B | ， Y = | C| D|
A，B，C，D均为n/2位，求XY的问题可以转换为：

	X * Y = （A * 2^（n/2） +B ）  *（C * 2^（n/2） +D ）= AC * 2^n + (AD + BC) * 2^（n/2）+BD			 

则，可以看出利用分治法后，进行了4次n/2位的乘法运算。但是并没有涉及算法性能优化，时间复杂度依然是O(n^2)。

这个算法进行性能提升可以使用如下方法：
先计算

U = （A + B)(C + D), V = AC, W = BD则 Z = XY = V * 2^n +(U - V- W ) * 2^（n/2） + W

上面过程中，由于只使用了U、V、W涉及的3次乘法，比没有优化的少了一种，时间复杂度就降低到了

具体 过程可以参考 Karatsuba算法

Karatsuba算法伪代码实现如下

procedure karatsuba(num1, num2)if (num1 < 10) or (num2 < 10)return num1*num2/* calculates the size of the numbers */m = max(size_base10(num1), size_base10(num2))m2 = m/2/* split the digit sequences about the middle */high1, low1 = split_at(num1, m2)high2, low2 = split_at(num2, m2)/* 3 calls made to numbers approximately half the size */z0 = karatsuba(low1,low2)z1 = karatsuba((low1+high1),(low2+high2))z2 = karatsuba(high1,high2)return (z2*10^(2*m2))+((z1-z2-z0)*10^(m2))+(z0)

具体例子可以参照这个图片

那参照上述步骤，在解决最开始提到的5次n/3位整数乘法中也可以设法将两个大整数U、V分割为

U = |A| B| C
V =|D| E| F

然后利用（A +B +C )(D +E +F)的方法，在分别细分合并其中几项，来简化复杂度，以求达到5次乘法的要求。

PS，这个方法是一开始我的想法，实现后发现只能简化到6次乘法实现，所以最后寻找别的算法。

最后发现有TOOM-COOK方法来做这个工作，而题目涉及的分为3等份的过程就是TOOM-COOK中当n = 3 的特例，也称为TOOM3。

那先来看看TOOM-COOK的一般实现，即不规定分为多少份，设分为m份。

设有两个大整数U，V，利用分治思维将U、V分为如下部分

U  = |U-（m-1）|……|U2 |U1 |U0
V   =|V-（m-1）|……|V2 |V1 |V0

设X = 10^(n/m)

则可以将u和v及其乘积w=uv表示为

将U,V和W都看作关于变量X的多项式，可以得到

此时我们可以取2m-1个不同的数x1，x2，…，x2m-1代入上多项式，可得W(xi) 与 W0，W1，W2……W(2m-2)的关系，转换为矩阵为

那设B为红框部分的矩阵可以推得

此时，取x1、 x2、 x3、 x4…. 为不同的数，再结合以下两个式子，

可以得出W0 、W1、 W2、 W3、 W4与U0、 U1、U2 ，V0、 V1、 V2 的关系
最后移位相加得到最终结果，移位相加可以参考如下的图，因为设的是10进制的数，所以每次移位就是10^(n/m)

那其实说到这里，相信有人已经明白了TOOM-COOK算法的整体核心思想，整体实现流程可以简单概括为

那回归到本题，在具体的3等分n位大整数U、V问题中，可以详细描述为以下细节
首先，分治划分U、V

U = |U2 |U1 |U0
V =|V2 |V1 |V0

同样的，设X = 10^(n/3),那U、V及其乘积W = UV可以表示为

分别取X为5个不同的数，即

X1 = 0，X2 = 1，X3 = -1， X4 = 2，X5 =-2

代入多项式中

第一个结论，是W(Xi)与U0，U1，U2，U3，V0，V1，V2的关系，暂且将5种X取值下的W(Xi)标记为a,b,c,d,e

第二个结论，是W(Xi)即a,b,c,d,e与W = UV中各项参数W0，W1，W2，W3，W4的，其中可以看到矩阵B(TOOM-COOK一般方法中提到）

至此，建立了W0，W1，W2，W3，W4与U1、U2 ，V0、 V1、 V2 的关系，经过运算后，可以求出两个式子
①

②
再带入W=UV=W0+W1X+W2X2 +W3X3+W4X4 中，可以求出W
到了这一步，相信大家都已经对这道题有了更深的理解，下面我们来看一道具体的应用。

123456*987654

按照程序实现流程，划分UV后，分别求得a,b,c,d,e以及W0，W1，W2，W3，W4如下

UV=W0+W1X+W2X2+W3X3+W4X4即W0， W1 ， W2， W3， W4移位相加可得W结果

对比运算，可知结果无误

最后再说一下时间复杂度，a,b,c,d,e所涉及的一共5次乘法，加减不计，所以得到的递归方程如下：

求解得复杂度为

TOOM-COOK实现思路和算法可以参考大数乘法问题

/*** Java8中的 Toom-Cook multiplication 3路乘法*/
private static BigInteger multiplyToomCook3(BigInteger a, BigInteger b) {int alen = a.mag.length;int blen = b.mag.length;int largest = Math.max(alen, blen);// k is the size (in ints) of the lower-order slices.int k = (largest+2)/3;   // Equal to ceil(largest/3)// r is the size (in ints) of the highest-order slice.int r = largest - 2*k;// Obtain slices of the numbers. a2 and b2 are the most significant// bits of the numbers a and b, and a0 and b0 the least significant.BigInteger a0, a1, a2, b0, b1, b2;a2 = a.getToomSlice(k, r, 0, largest);a1 = a.getToomSlice(k, r, 1, largest);a0 = a.getToomSlice(k, r, 2, largest);b2 = b.getToomSlice(k, r, 0, largest);b1 = b.getToomSlice(k, r, 1, largest);b0 = b.getToomSlice(k, r, 2, largest);BigInteger v0, v1, v2, vm1, vinf, t1, t2, tm1, da1, db1;v0 = a0.multiply(b0);da1 = a2.add(a0);db1 = b2.add(b0);vm1 = da1.subtract(a1).multiply(db1.subtract(b1));da1 = da1.add(a1);db1 = db1.add(b1);v1 = da1.multiply(db1);v2 = da1.add(a2).shiftLeft(1).subtract(a0).multiply(db1.add(b2).shiftLeft(1).subtract(b0));vinf = a2.multiply(b2);// The algorithm requires two divisions by 2 and one by 3.// All divisions are known to be exact, that is, they do not produce// remainders, and all results are positive.  The divisions by 2 are// implemented as right shifts which are relatively efficient, leaving// only an exact division by 3, which is done by a specialized// linear-time algorithm.t2 = v2.subtract(vm1).exactDivideBy3();tm1 = v1.subtract(vm1).shiftRight(1);t1 = v1.subtract(v0);t2 = t2.subtract(t1).shiftRight(1);t1 = t1.subtract(tm1).subtract(vinf);t2 = t2.subtract(vinf.shiftLeft(1));tm1 = tm1.subtract(t2);// Number of bits to shift left.int ss = k*32;BigInteger result = vinf.shiftLeft(ss).add(t2).shiftLeft(ss).add(t1).shiftLeft(ss).add(tm1).shiftLeft(ss).add(v0);if (a.signum != b.signum) {return result.negate();} else {return result;}
}

参考资料
大数乘法问题
Karatsuba
两个n位大整数相乘算法
算法分析设计习题2-5
TOOM-COOK算法
TOOM-COOK
TOOM-3