# What is the fastest algorithm for multiplication of two n-digit numbers?

I want to know which algorithm is fastest for multiplication of two n-digit numbers? Space complexity can be relaxed here!

• Are you interested in the theoretical question or in the practical question? – Yuval Filmus Oct 19 '13 at 20:03
• Both, but more inclined towards practical one! – Andy Oct 20 '13 at 6:49
• For the practical question, I recommend using GMP. If you're curious what they use, look at the documentation or the source code. – Yuval Filmus Oct 20 '13 at 8:04
• Nobody knows. We haven't found it yet. – JeffE Oct 21 '13 at 2:55
• It depends. If you are satisfied with an algorithm that can multiply only a very specific class of numbers, look at this algorithm that can multiply two $n$-bit numbers in $O(kn)$, where $k$ related to the Collatz problem. – DaBler May 20 at 12:53

As of now Fürer's algorithm by Martin Fürer has a time complexity of $n \log(n)2^{Θ(log*(n))}$ which uses Fourier transforms over complex numbers. His algorithm is actually based on Schönhage and Strassen's algorithm which has a time complexity of $Θ(n\log(n)\log(\log(n)))$

Other algorithms which are faster than Grade School Multiplication algorithm are Karatsuba multiplication which has a time complexity of $O(n^{\log_{2}3})$ ≈ $O(n^{1.585})$ and Toom 3 algorithm which has a time complexity of $Θ(n^{1.465})$

Note that these are the fast algorithms. Finding fastest algorithm for multiplication is an open problem in Computer Science.

References :

• Note the recent paper by D. Harvey and J. van der Hoeven (March 2019) describing an algorithm with $O(n\ln n)$ complexity. – hardmath Apr 28 '19 at 19:32
• Karatsuba is really easy mathematically, just one simple formula. Also nice to distribute to multiple processors and to vectorise. – gnasher729 Feb 19 at 10:53

Note that the FFT algorithms listed by avi add a large constant, making them impractical for numbers less than thousands+ bits.

In addition to that list, there are some other interesting algorithms, and open questions:

• Linear time multiplication on a RAM model (with precomputation)
• Multiplication by a Constant is Sublinear (PDF) - this means a sublinear number of additions which gets for a total of $\mathcal{O}\left(\frac {n^2} {\log n} \right)$ bit complexity. This is essentially equivalent to long multiplication (where you shift/add based on the number of $1$s in the lower number), which is $\mathcal{O}\left({n^2} \right)$, but with an $\mathcal{O}\left(\log n\right)$ speedup.
• Residue number system and other representations of numbers; multiplication is almost linear time. The downside is, the multiplication is modular and {overflow detection, parity, magnitude comparison} are all as hard or almost as hard as converting the number back to binary or similar representation and doing the traditional comparison; this conversion is at least as bad as traditional multiplication (at the moment, AFAIK).
• Other Representations:
• [Logarithmic representation]: multiplication is addition of the logarithmic representation. Example: $$16 \times 32 = 2^{\log_2 16 + \log_2 32} = 2^{4+5} = 2^{9}$$
• Downside is conversion to and from logarithmic representation can be as hard as multiplication or harder, the representation can also be fractional/irrational/approximate etc. Other operations (addition?) are likely more difficult.
• Canonical representation: represent the numbers as the exponents of the prime factorization. Multiplication is addition of the exponents. Example: $$36 \times 48 = 3^2\cdot 5^1\times 2^{2}\cdot 3^1\cdot 4^1 = {2^2}\cdot {3^2} \cdot 4^1 \cdot 5^1$$
• Downside is, requires factors, or factorization, a much harder problem than multiplication. Other operations such as addition are likely very difficult.
• I believe a residue/Chinese Remainder Theorem-based approach with the right moduli can lead to speedups over traditional multiplication even with the conversion back; at some point this was in chapter 4 of TAOCP, at least as a footnote. (It still doesn't get near the FFT-based methods, but it's an interesting historical note) – Steven Stadnicki Oct 20 '13 at 17:15
• @StevenStadnicki oh cool, I need to look at that then; do you happen to know the complexity? – Realz Slaw Oct 20 '13 at 23:54

If space and amount of hardware is no concern, then you can do what most CPUs do: For two n-bit numbers, use n^2 AND gates to produce n^2 zeroes and ones, then use n^2 half adders to reduce the number of values by 1/3, do that again until you can get the final result with one set of full adders.

Time = O(log n), hardware cost = O(n^2). Could realistybe done today for n= 256, but there isn’t that much demand.