Editing Toom–Cook multiplication (section)

{{Short description|Algorithm for multiplying large numbers}}
'''Toom–Cook''', sometimes known as '''Toom-3''', named after [[Andrei Toom]], who introduced the new algorithm with its low complexity, and [[Stephen Cook]], who cleaned the description of it, is a [[multiplication algorithm]] for 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 [[computational 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 incorrectly used interchangeably, Toom-3 is only a single instance of the Toom–Cook algorithm, where ''k'' = 3.

Toom-3 reduces nine multiplications to five, and runs in Θ(''n''<sup>log(5)/log(3)</sup>) ≈ Θ(''n''<sup>1.46</sup>). In general, Toom-''k'' runs in {{nowrap|Θ(''c''(''k'') ''n<sup>e</sup>'')}}, where {{nowrap|1=''e'' = log(2''k'' − 1) / log(''k'')}}, ''n<sup>e</sup>'' is the time spent on sub-multiplications, and ''c'' is the time spent on additions and multiplication by small constants.<ref name="Knuth, p. 296">Knuth, p. 296</ref> The [[Karatsuba algorithm]] is equivalent to Toom-2, where the number is split into two smaller ones. It reduces four multiplications to three and so operates at Θ(''n''<sup>log(3)/log(2)</sup>) ≈ Θ(''n''<sup>1.58</sup>).

Although the exponent ''e'' can be set arbitrarily close to 1 by increasing ''k'', the constant term in the function grows very rapidly.<ref name="Knuth, p. 296"/><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 {{math|Θ(''n'' 2<sup>{{sqrt|2 log ''n''}}</sup> 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 {{nowrap|Θ(''n'' log ''n'' log log ''n'')}}) becomes practical.

Toom first described this algorithm in 1963, and Cook published an improved (asymptotically equivalent) algorithm in his PhD thesis in 1966.<ref>[http://cr.yp.to/bib/1966/cook.html Positive Results], chapter III of Stephen A. Cook: ''On the Minimum Computation Time of Functions''.</ref>