TOOM-COOK MULTIPLICATION

'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 Θ(n^{log(5)/log(3)}), about Θ(n^1.465). In general, Toom-''k'' runs in Θ(''c''(''k'') ''n^e''), where ''e'' = log(2''k''-1) / log(''k''), ''n^e'' is the time spent on sub-multiplications, and ''c'' is the time spent on additions and multiplication by small constants.^[1] 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 Θ(''n''^{log(3)/log(2)}), which is about Θ(''n''^1.585). Ordinary long multiplication is equivalent to Toom-1, with complexity Θ(''n''²).
Although the exponent ''e'' can be set arbitrarily close to 1 by increasing ''k'', the function ''c'' unfortunately grows very rapidly.^{[1] [3]} The growth rate for mixed-level Toom-Cook schemes was still an open research problem in 2005.^[4] An implementation described by Donald Knuth achieves the time complexity Θ(''n'' 2^{√(2 log ''n'')} log ''n'').^[5]
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. [1] (thesis)

Contents

Example

Notes

References

External links

Example

A possible implementation of Toom-3, optimal with respect to the number of operations^[6] 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'') = 31''x''^2+415''x''+926
''b''(''x'') = 123''x''^2+456''x''+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'' ''x''⁴ + ''w3'' ''x''³ + ''w2'' ''x''² + ''w1'' ''x'' + ''w0'' =
''C'' = ''c''(1,000) =
3,813
65,181
327,597
749,691
730,614
----------------------
3,878,509,347,421,614

Notes

1. Knuth, p. 296
2. Knuth, p. 296
3. Crandall & Pomerance, p. 474
4. Crandall & Pomerance, p. 536
5. Knuth, p. 302
6. Bodrato, p.132

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