The Unsolved Mystery: Why Mathematicians Still Don't Know the Fastest Way to Multiply
Mathematicians still don't know the fastest way to multiply numbers
For millennia, we believed the grade-school method was the fastest way to multiply. Then, a young student named Anatoly Karatsuba shattered that assumption in 1960, proving that trading expensive multiplications for cheap additions could drastically speed up calculations. This discovery revolutionized computing, powering everything from Python to modern encryption. Yet, despite decades of progress, including a 2019 breakthrough by David Harvey and Joris van der Hoeven, the absolute theoretical limit for multiplying numbers remains a fascinating, unsolved mystery.
"The triumph comes with a crucial caveat, though. Just as Karatsuba’s algorithm only outperforms the grade-school approach when numbers get reasonably large, the Harvey-van der Hoeven algorithm doesn’t pull ahead until the numbers become truly galactic."
HN discussion
- The O(n log n) multiplication algorithm is 'galactic,' meaning it only outperforms standard methods for massive numbers and remains impractical for typical cryptographic or everyday operations.
- Critics argue the article's analysis is flawed for counting only multiplications while ignoring additions and shifts, which are linear-time operations that cannot be considered free in asymptotic complexity.
- Practitioners note that Strassen's matrix multiplication kernel becomes competitive with standard kernels only at large dimensions (e.g., n > 2500) and benefits significantly from exploiting specific matrix structures like symmetry.
- The fundamental limit of multiplication speed remains an open question in mathematics, with no proof yet establishing that an algorithm faster than O(n log n) is impossible.