Multiplication algorithm

A multiplication algorithm is an algorithm (or method) to multiply two numbers. Depending on the size of the numbers, different algorithms are more efficient than others. Numerous algorithms are known and there has been much research into the topic.

The oldest and simplest method, known since antiquity as long multiplication or grade-school multiplication, consists of multiplying every digit in the first number by every digit in the second and adding the results. This has a time complexity of ${\displaystyle O(n^{2})}$, where n is the number of digits. When done by hand, this may also be reframed as grid method multiplication or lattice multiplication. In software, this may be called "shift and add" due to bitshifts and addition being the only two operations needed.

In 1960, Anatoly Karatsuba discovered Karatsuba multiplication, unleashing a flood of research into fast multiplication algorithms. This method uses three multiplications rather than four to multiply two two-digit numbers. (A variant of this can also be used to multiply complex numbers quickly.) Done recursively, this has a time complexity of ${\displaystyle O(n^{\log _{2}3})}$. Splitting numbers into more than two parts results in Toom-Cook multiplication; for example, using three parts results in the Toom-3 algorithm. Using many parts can set the exponent arbitrarily close to 1, but the constant factor also grows, making it impractical.

In 1968, the Schönhage-Strassen algorithm, which makes use of a Fourier transform over a modulus, was discovered. It has a time complexity of ${\displaystyle O(n\log n\log \log n)}$. In 2007, Martin Fürer proposed an algorithm with complexity ${\displaystyle O(n\log n2^{\Theta (\log ^{*}n)})}$. In 2014, Harvey, Joris van der Hoeven, and Lecerf proposed one with complexity ${\displaystyle O(n\log n2^{3\log ^{*}n})}$, thus making the implicit constant explicit; this was improved to ${\displaystyle O(n\log n2^{2\log ^{*}n})}$ in 2018. Lastly, in 2019, Harvey and van der Hoeven came up with an algorithm with complexity ${\displaystyle O(n\log n)}$. This matches a guess by Schönhage and Strassen that this would be the optimal bound, although this remains a conjecture today.

Integer multiplication algorithms can also be used to multiply polynomials by means of the method of Kronecker substitution.