Toom-Cook 乘法
当数据规模稍大时，Toom-Cook 乘法是比 Karatsuba 乘法更快的算法，当然 相对于Karatsuba 算法，这个算法更难一些。我曾想自己实现一个Toom-3 和Toom-4算法，但限于时间和精力，一直没有来得及动手。相信本版许多人也对Toom-Cook算法感兴趣，先贴出一些资料，欢迎大家补充和讨论。以下内容转自 http://everything2.com/index.pl?node=Toom-Cook+multiplication&lastnode_id=346167&searchy.x=38&searchy.y=7Description
The Toom-Cook algorithm for multiplication of large numbers on computer is a divide and conquer approach that combines features of many other methods. Like Karatsuba multiplication, it operates by dividing the input numbers into limbs of smaller size, and expresses the larger product in terms of calculations made on the smaller pieces. Recursion can be applied to do the calculations on these smaller pieces, again using Toom-Cook, until the individual pieces are small enough to succumb to a more straightforward approach such as the same "long multiplication" performed on pencil and paper.
The method takes the names of its two discoverers. In 1963, Andrei Toom produced a construction that proved that the time complexity of multiplication had an upper bound that was considerably lower than the O(n2) of conventional long multiplication. The proof included an implicit description of the method, which Stephen Cook included, slightly modified, in his 1966 PhD thesis. One feature of the Toom-Cook method is it does not define a single solution; instead, it defines an entire family of methods for efficient multiplication. Implementors have considerable freedom to select a particular Toom-Cook method that makes most sense on a particular computer architecture, such as by making use of powers of 2 which suit the computer's binary notation.
The method has considerable commonality with multiplication using the fast Fourier Transform, in that it works on the same principles of polynomial multiplication. The input numbers are split into limbs of a given size, and each is written as a polynomial, using the limb size as radix. Instead of multiplying the polynomials directly, they are evaluated at a set of points, and the values multiplied together at those points. The product polynomial is then determined, based on the products at those points. Finally, substitution of the radix returns the final answer. The degrees of freedom available to choose an appropriate algorithm are the number of limbs the input is divided into, and the points at which the polynomials are evaluated.
An example
Let us take an example, multiplying 123,456,789 by 987,654,321. We can apply a "Toom-3" algorithm, splitting each number into 3 limbs of length 3 digits, and can choose a set of points, for example, {-2, -1, 0, 1, 2}. The calculations so far look like this:
A(x) = 123x2 + 456x + 789
B(x) = 987x2 + 654x + 321
x= -2A=369B= 2961AB=1092609
x= -1A=456B=654AB= 298224
x=0A=789B=321AB= 253269
x=1A= 1368B= 1962AB=2684016
x=2A= 2193B= 5577AB= 12230361
We could have used Toom-Cook again to perform the multiplications AB, but this will do for illustrative purposes. There are efficient ways to calculate the values of A and B, such as the method of finite differences, which can be used to calculate the successive values of A and B using only addition. It now remains to find the polynomial P(x)=A(x)B(x) based on the values at the five points. There is a general solution to this problem, but we can do much better. The solution we are looking for is of the form
P(x) = p4x4 + p3x3 + p2x2 + p1x + p0
and we can substitute the values of x at the points to get a set of simultaneous equations that are linear in the unknowns pi:
16p4 - 8p3 + 4p2 - 2p1 + p0 =1092609
p4 -p3 +p2 -p1 + p0 = 298224
p0 = 253269
p4 +p3 +p2 +p1 + p0 =2684016
16p4 + 8p3 + 4p2 + 2p1 + p0 = 12230361
That's a few linear equations to solve, with a little algebra. Fortunately many of the terms are easy to separate and we get the solution:
p4 =121401
p3 =530514
p2 = 1116450
p1 =662382
p0 =253269
which we can finally turn back to a number by substituting x=1000 in the product polynomial P(x). The easiest way to do this is to just write each coefficient with the right place value.
121,401
530,514
1,116,450
662,382
253,269
=======================
121,932,631,112,635,269
That may have seemed like hard work, but the difficult steps (evaluating the values and solving the equations) turn out to be quite easy for a computer to do, requiring simple operations such as addition, subtraction, shifts, and multiplication and division by small constants. The important part is to note that the body of the problem was reduced to five multiplies, each on numbers about one-third the size of the original inputs.
Variations
The simplest variations on the Toom algorithm rely on judicious choices of the set of points to evaluate all the polynomials at. A good choice will mean that the initial evaluations and the solution of the equations are easy (for the computer!). Some authors make a formal presentation of the method, in terms of matrix manipulations and the linear algebra solution of the equations. However, a good choice of points always supports a more efficient solution at this step.
There are always two of the coefficients which can be computed directly. The numerical coefficient of the product polynomial can be got by multiplying the trailing terms in the inputs (which corresponds to the substitution x=0), and the leading coefficient is likewise the product of the original leading terms (which corresponds to the asymptotic behavior of the function as x approaches infinity). Since these terms required one multiplication each, many authors compute those first and eliminate them from the other equations immediately.
The method generalizes immediately to splits of the number into more pieces. In general, a "Toom-K" algorithm will split the inputs into k limbs of equal width, evaluate the polynomials at (2k-1) points, and solve for the (2k-1) coefficients in the product polynomial. Knuth shows this in action with the choices of points {0, 1, ... 2k-2} or {-(k-1), -(k-2), ... k-2, k-1} in The Art of Computer Programming. The multiplication part then becomes (2k-1) calculations, at 1/k of the original size. A "Toom-2" algorithm can be shown to be equivalent to Karatsuba multiplication.
The gmp library for multiple precision arithmetic uses a Toom-3 algorithm for numbers of tens of thousands of digits, and only switches to a Fourier transform method when the numbers reach hundreds of thousands of digits. It uses the points x=0, 0.5, 1, 2 and the point at infinity to perform simple evaluations and solution of the equations.
Efficiency
The time complexity of a Toom-k algorithm is relatively easy to calculate. Since the algorithm recursively replaces a multiplication by (2k-1) smaller ones, k times smaller than the previous iteration, the theoretical complexity is O(n(log(2k-1))/(log k)). This would suggest a larger k value gives a more efficient algorithm, but for larger k, the evaluation and interpolation steps can become quite hairy. (However, some authors have attempted values of k as large as 16).
Time complexity of some Toom-k sizes
k | Notes | Complexity for n digits big-Oh notation
============================================================
2 | Karatsuba | O(n1.585)
3 | Most common | O(n1.465)
4 | Feasible | O(n1.404)
...| |
16 | Difficult!| O(n1.239)
============================================================
The table illustrates increased sizes experience diminishing returns, and while the method can approach the O(n log n) of fast Fourier Transform methods with larger values of k, the computation efforts outside of the multiplications can rapidly become significant. Nevertheless, the big-Oh notation hides a constant, and empirical results indicate that a lovingly crafted Toom algorithm will beat an FFT method for all but the most enormous calculations. 另一篇文章，Toom-Cook multiplication —— 维客(wiki)
Toom-Cook multiplication
来自 维客
Jump to: navigation, search
Toom-Cook, sometimes known as Toom-3, is a multiplication algorithm, a method of multiplying two large integers.
Given two large integers, a and b, Toom-Cook splits up a and b into k smaller parts each of length l, and performs operations on the parts. As k grows, one may combine many of the multiplication sub-operations, thus reducing the overall complexity of the algorithm. The multiplication sub-operations can then be computed recursively using Toom-Cook multiplication again, and so on. Although the terms "Toom-3" and "Toom-Cook" are sometimes used interchangeably, Toom-3 is only a single instance of the Toom-Cook algorithm, where k = 3.
Toom-3 reduces 9 multiplications to 5, and runs in Θ(nlog(5)/log(3)), about Θ(n1.465). In general, Toom-k runs in Θ(c(k) ne), where e = log(2k-1) / log(k), ne is the time spent on sub-multiplications, and c is the time spent on additions and multiplication by small constants.<ref>Knuth, p. 296</ref> The Karatsuba algorithm is a special case of Toom-Cook, where the number is split into two smaller ones. It reduces 4 multiplications to 3 and so operates at Θ(nlog(3)/log(2)), which is about Θ(n1.585). Ordinary long multiplication is equivalent to Toom-1, with complexity Θ(n2).
Although the exponent e can be set arbitrarily close to 1 by increasing k, the function c unfortunately grows very rapidly.<ref>Knuth, p. 296</ref> <ref>Crandall & Pomerance, p. 474</ref> The growth rate for mixed-level Toom-Cook schemes was still an open research problem in 2005.<ref>Crandall & Pomerance, p. 536</ref> An implementation described by Donald Knuth achieves the time complexity Θ(n 2√(2 log n) log n).<ref>Knuth, p. 302</ref>
Due to its overhead, Toom-Cook is slower than long multiplication with small numbers, and it is therefore typically used for intermediate-size multiplications, before the asymptotically faster Schönhage-Strassen algorithm (with complexity Θ(n log n log log n)) becomes practical.
Andrei Toom first described this algorithm in 1963, while Stephen Cook improved the algorithm and published it in his PhD thesis in 1966. (thesis)
目录
[隐藏]
1 Example
2 Notes
3 References
4 External links
[编辑]Example
A possible implementation of Toom-3, optimal with respect to the number of operations<ref>Bodrato, p.132</ref> is illustrated below. The same idea can be generalized to any Toom-N algorithm, but an efficient sequence of operation is not easy to find.
Assume we wish to multiply A=31,415,926 and B=123,456,789. Each integer is divided into three equal length numbers, l digits wide.
With l=3 we can represent the two operands by two polynomials:
a(x) =31x^2+415x+926
b(x) = 123x^2+456x+789
where A=a(1,000) and B=b(1,000).
To compute c(x) = a(x) * b(x), we evaluate the two polynomials a and b in five points, and multiply the results, for our example we perform the following:
w4=c(1/0)=a(1/0)*b(1/0)= 31 * 123 = 3813
w3=c(-2) =a(-2) *b(-2) =(4*31-2*415+926)*(4*123-2*456+789)= 220*369 =81180
w2=c(-1) =a(-1) *b(-1) =(31-415+926)*(123-456+789)= 542*456 = 247152
w1=c(1)=a(1)*b(1)=(31+415+926)*(123+456+789)=1372*1368=1876896
w0=c(0)=a(0)*b(0)= 926 * 789 = 730614
Then solve the interpolation problem
w3 <-(w3 - w1)/3 = -598572
w1 <-(w1 - w2)/2 =814872
w2 <- w2 - w0 = -483462
w3 <-(w2 - w3)/2 + 2*w4= 65181
w2 <- w2 + w1 - w4 =327597
w1 <- w1 - w3 =749691
The result can be recomposed with:
c(x) = w4 x4 + w3 x3 + w2 x2 + w1 x + w0 =
C = c(1,000) =
3,813
65,181
327,597
749,691
730,614
----------------------
3,878,509,347,421,614
[编辑]Notes
<references/>
[编辑]References
D. Knuth. The Art of Computer Programming, Volume 2. Third Edition, Addison-Wesley, 1997.
R. Crandall & C. Pomerance. Prime Numbers - A Computational Perspective. Second Edition, Springer, 2005.
M. Bodrato. Toward Optimal Toom-Cook Multiplication.... In WAIFI'07, Springer, 2007.
[编辑]External links
Toom-Cook 3-Way Multiplication from GMP Documentations
取自"http://www.wiki.cn/wiki/Toom-Cook_multiplication"
最后贴上我收集到的关于Toom-Cook算法的资料。 这个算法就是把大数当作多项式
然后求出结果多项式的值
再根据多项式求结果的值
中文资料在TAOCP V2中文版上有 从 V7.x 起，HugeCalc 已实现了Toom3算法，
而且对于平方，还实现了切分成4段、5段的算法，
所以即便不采用任何高级算法（FFT/FNT算法），速度依然可以很快！ 好吧，从google绕回来了。
有没有从因子位数长度m确定取多大n的经验公式，即 Toom-Cook-n？
说是总效率是C* $(m/n)^(log(2k-1)/log(k))$，但好象单步复杂度C服从$n^2$。
接着该怎么分析？ Toom-4是应该是最好的算法了，只要选择0,无穷大，1,-1,2,2,1/2即可实现，再往上处理的数据位太少了，比Toom-4不经济（Toom-3可达到$2^29$,Toom-4可以达到$2^28$,Toom-6只能达到$2^20$) http://gmplib.org/manual/Toom-3_002dWay-Multiplication.html 好像GMP实现到了Toom6
具体在其源代码的mpn/generic下 刚去读GMP源代码了
在乘法顶层函数里有着超复杂的分类调用
大概是有
toom22, toom32, toom42, toom33, toom43, toom53, toom63, toom44, toom6h, toom8h几种算法 大数乘法最低复杂度的极限人类能达到多少？可否降至O(nLog(n))以下，甚至更低？
除了FFT以外，是否可以找到比FFT更好的计算方法？ 乘法就是卷积。
我前段时间发现，FFT和Toom-Cook是等价的。