# Proof that no O(n) multiplication algorithm exists

For the multiplication of two $$n$$ digit numbers, the best known algorithm has complexity $$O(n \log n)$$. Has it been proven that this is the best possible, or that an algorithm $$O(n)$$ is not possible?

• This is a famous open problem – Ariel Jun 4 '20 at 10:53
• You should be careful to specify your computational model here. In the commonly used word RAM model, there does exist an $\mathrm{O}(n)$ time algorithm: see, e.g., this lecture series by Ryan O’Donnell for a full description, which also refers to Knuth TAOCP Seminumerical Algorithms §4.3.3.C (in particular, the penultimate paragraph of that section in the third edition). – wchargin Jun 5 '20 at 5:24

There is a conditional $$\Omega(n\log n)$$ lower bound due to Afshani, Freksen, Kamma, Green Larsen, Lower Bounds for Multiplication via Network Coding.

No nontrivial lower bound for the multiplcation is known (clearly, it is $$\Omega(n)$$) and David Harvey himself does not know if a complexity of $$O(n\log(n))$$ is the best possible: in his own words: "in this sense, our work is expected to be the end of the road for this problem, although we don't know yet how to prove this rigorously". See also the original paper al page 1: "If the Schönhage–Strassen conjecture is correct, then Theorem 1.1 is asymptotically optimal. Unfortunately, no super-linear lower bound for $$M(n)$$ is known."

• One very simple way multiplication could be faster is if current FFT algorithms aren't optimal. It is an open question if there is a FFT algorithm that runs in less than O(n log n). Such an algorithm could pretty easily speed up integer multiplication – Oscar Smith Jun 5 '20 at 3:30

You could do it in O(1), kinda...

1. Precompute a lookup tables of log and log-1 values.
2. Get absolute values
3. Look up the two numbers,
4. Add the log of the two numbers
5. Look up log-1
6. Change to negative if one of the original numbers was negative.

Boom! O(1)

If you work with 32bit signed ints then that would only take 8gb of of memory for the first table (312 x 4bytes) and 16gb for the second (312 x 8bytes). (It may be possible to compress them a bit for the small logs and log-1s)

Quite a bit of memory yes, but readily available on consumer grade laptops.

If you have lots of 32 signed ints it may be worth the large contact overhead?!

• Anything well defined can be done in O(1) if you fix a maximum input size. – gmatht Jun 5 '20 at 7:42
• Even if we change this from a theoretical question, on a modern machine a 32bit multiply is pretty cheap and cache misses across a 8GB array would be pretty expensive. – gmatht Jun 5 '20 at 7:57
• @gmatht True true. – DarcyThomas Jun 5 '20 at 8:03
• Step 1 costs $\Omega(b^n)$ since there are $b^n$ entries in this table for $n$-digit numbers in base $b$. And it only gives the correct result if the log values are sufficiently precise, which would increase the cost further (the larger $n$ is, the more precision you need in each table entry). This is not O(1), not even kinda: it's at least exponential. – Gilles 'SO- stop being evil' Jun 5 '20 at 11:17