# 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? Commented Oct 19, 2013 at 20:03
• For the practical question, I recommend using GMP. If you're curious what they use, look at the documentation or the source code. Commented Oct 20, 2013 at 8:04
• 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. Commented May 20, 2020 at 12:53
• To focus, how large is n? 100 digits and 10 million digits are different. Commented Aug 17, 2022 at 18:01
• If you don't care about the space complexity and accept an upper bound on $n$, store a precomputed array. Address computation and value lookup can be done in time $O(n)$.
– user16034
Commented Aug 17, 2022 at 18:05

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. Commented Apr 28, 2019 at 19:32
• Karatsuba is really easy mathematically, just one simple formula. Also nice to distribute to multiple processors and to vectorise. Commented Feb 19, 2020 at 10:53
• @hardmath do you want to move that to an answer to get upvotes :-) Commented Jul 22, 2020 at 19:05
• @Ciro: There's a Question about the practical effects of this at MatterModeling.SE (a beta site I was unaware of) and one of the Answers is quite a good explanation of how large the numbers have to be to get an improvement. Commented Jul 22, 2020 at 19:26
• @hardmath OMG, that site is so obscure, should at most be a tag on chemistry or physics. In any case, I still recommend dumping the link to the paper and quick summary. Doesn't matter if useless in practice, paper itself says authors didn't care about being useful in practice. This is Computer Science SE, doesn't have to be useful :-) Commented Jul 22, 2020 at 19:32

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) Commented Oct 20, 2013 at 17:15
• @StevenStadnicki oh cool, I need to look at that then; do you happen to know the complexity? Commented Oct 20, 2013 at 23:54

n log(n) by Harvey and van der Hoeven (2021)

This was mentioned in two comments previously (1, 2), but it deserves its own answer.

Published as: "Integer multiplication in time O(n logn)"

This achieves the long conjectured (e.g. by Schonhage and Strassen in 1971) but not yet proven optimum of n log(n).

It would be good to include a summary of the method here, but I have not tried to understand it as I have better things to do with my life like learning about the busy beaver problem.

Discussions of practical usage considering non asymptotic considerations:

Some relevant quotes from the paper itself:

All of the algorithms presented in this paper can be made completely explicit, and all implied big-O constants are in principle effectively computable. On the other hand, we make no attempt to minimise these constants or to otherwise exhibit a practical multiplication algorithm. Our aim is to establish the theoretical O(n log n) bound as directly as possible.

and:

4.4. Further remarks. Our presentation of the Gaussian resampling technique has been optimised in favour of giving the simplest possible proof of the main M(n) = O(n log n) bound. In this section we outline several ways in which these results may be improved and generalised, with an eye towards practical applications

and further down:

After making this modification, it would be interesting to investigate whether this method is competitive for practical computations of complex DFTs of length s when s is a large prime. One would choose a smooth transform length t somewhat larger than s, say 1.25s < t < 1.5s, and use the algorithm to reduce the desired DFT of length s to a DFT of length t; the latter could be handled via existing software libraries implementing the Cooley–Tukey algorithm. For large enough s, perhaps around $$2^{20}$$ or $$2^{30}$$, we expect that the invocations of S and J would be quite cheap compared to the FFT of length t

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 full 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 realistically be done today for n = 256, but there isn’t that much demand.

Otherwise, for small n (let's say you have a computer with 64 bit arithmetic, and your numbers are less than 5 x 64 bits) the speed will change dramatically at certain sizes. For small sizes, you could perform Karatsuba by hand. And look how the number of operations changes very carefully. For example from 16x16 to 17x17 words there could be a massive change.

One source claims Karatsuba is fasted up to 10^96 (320 bits, 5 64-bit words). But I could see Toom-Cook being faster, calculating products of 3 128-bit quantities, and calculating the 128 bit products using Karatsuba. So for the fastest for small n, I'd expect many individual cases. Plus this would be very implementation dependent.

• (FWIW, the tag is mathematical-programming, not digital-circuits.)(And I think 319+1 bit may have been 10*32 bits.) Commented Aug 19, 2022 at 4:37
• Do you actually look at tags? Did you see "space complexity can be relaxed here", so O (n^2) space and hardware seems quite reasonable. Commented Oct 21, 2023 at 17:45
• (I do actually look at tags, e.g. to try to figure out whether space complexity refers to a formula for the number of memory cells in addition to input+output, λ² for a circuit, (μm)² or something else.) Commented Oct 21, 2023 at 20:07