Toom Cook algorithm

The Toom Cook algorithm is an efficient algorithm for multiplying two whole numbers , which works on the principle of divide and conquer . It was first described by Andrei Toom , later improved by Cook and published in his doctoral thesis.

It exists in two variants. The variant with a fixed division has a runtime complexity of , where is a fixed constant that only depends on the division, but not on the input length . The variant with variable division has runtime complexity . ${\displaystyle O\left(n^{1+\varepsilon }\right)}$ ${\displaystyle \varepsilon }$ ${\displaystyle n}$ ${\displaystyle O\left(n\cdot \log(n)\cdot 2^{\sqrt {2\log(n)}}\right)}$

The algorithm is the generalization of the Karatsuba algorithm and is significantly faster than the naive algorithm based on the school method (or the Russian pawn multiplication in the binary system ), which has runtime complexity . For sufficiently large numbers, however, it is also slower than the Schönhage-Strassen algorithm , whose runtime is complex and which, from the point of view of complexity theory, is the fastest, practically applied algorithm for multiplying whole numbers. ${\displaystyle \Theta (n^{2})}$ ${\displaystyle O{\Big (}n\cdot \log(n)\cdot \log {\big (}\log(n){\big )}{\Big )}}$

Web links

• PhD thesis by Stephen Cook