The O(n log n) Mirage: Why We Still Don't Know the Fastest Way to Multiply Practical Numbers

The Quest for the Ultimate Multiplication Algorithm

When we think of basic arithmetic, we tend to view it as a solved problem. After all, multiplication is one of the first mathematical concepts taught to children, and it is executed billions of times per second by the silicon inside our smartphones, laptops, and cloud servers. Yet, in the realm of computer science, multiplication remains an active, fiercely contested battleground.

For decades, mathematicians and computer scientists have been hunting for the absolute speed limit of integer multiplication. In 2019, researchers David Harvey and Joris van der Hoeven published a groundbreaking paper proving that two $n$-bit integers can be multiplied in $O(n \log n)$ time. This was hailed as a monumental theoretical achievement, solving a conjecture first proposed by Schönhage and Strassen in 1971.

But here is the catch: despite this mathematical breakthrough, no computer on Earth actually uses this algorithm. If you inspect the source code of modern arbitrary-precision arithmetic libraries like GMP (GNU Multiple Precision Arithmetic Library), or the underlying engines of Python, Rust, and Go, you will not find a single line of the Harvey-Hoeven algorithm. Why? Because the fastest theoretical way to multiply numbers is practically useless. This discrepancy exposes a profound truth about modern software development: the clean, asymptotic world of Big-O notation often collides violently with the messy, physical realities of computer architecture.

From Grade School to Karatsuba: Breaking the Quadratic Barrier

To understand why the latest breakthrough is a "galactic algorithm" (an algorithm that is theoretically superior but practically unusable), we must first look at how we got here.

If you multiply two $n$-digit numbers using the traditional grade-school method, you multiply each digit of the first number by every digit of the second number. This requires $n^2$ single-digit multiplications. In computational complexity terms, this is an $O(n^2)$ algorithm. If you double the size of the numbers, the work quadruples. For small numbers, this is perfectly fine. But for cryptography, scientific computing, and high-precision physics, where numbers can be millions of digits long, $O(n^2)$ quickly becomes a performance bottleneck.

In 1960, Anatoly Karatsuba revolutionized the field by discovering the first sub-quadratic multiplication algorithm. By cleverly rearranging algebraic terms, Karatsuba showed that you could multiply two $n$-digit numbers by performing only three half-sized multiplications instead of four. This reduced the time complexity to:

$$O(n^{\log_2 3}) \approx O(n^{1.58})$$

Karatsuba's algorithm is a masterclass in divide-and-conquer strategy. It is highly practical and is still used today in production software when dealing with numbers that are several hundred to several thousand bits long.

The Galactic Leap: Fast Fourier Transforms

As numbers grow even larger, Karatsuba's algorithm eventually loses its edge. To handle truly massive integers, computer scientists turned to signal processing. By treating the digits of a number as coefficients of a polynomial, we can use the Fast Fourier Transform (FFT) to perform multiplication in the frequency domain.

In 1971, Arnold Schönhage and Volker Strassen introduced their landmark FFT-based multiplication algorithm, which achieved a complexity of:

$$O(n \log n \log \log n)$$

For nearly half a century, this was the gold standard for multiplying giant numbers. It is the engine that powers the Great Internet Mersenne Prime Search (GIMPS) and complex cryptographic key generation. However, Schönhage and Strassen conjectured that the absolute mathematical limit should be even cleaner: $O(n \log n)$.

In 2019, Harvey and van der Hoeven finally delivered the proof. By mapping the problem to a 12-dimensional space and using multi-dimensional FFTs, they bypassed the structural limitations of previous designs and achieved the elusive $O(n \log n)$ bound. Mathematically, the quest was over. Practically, a new set of problems had just begun.

The Problem with Galactic Algorithms

Why is the $O(n \log n)$ algorithm ignored by software engineers? The answer lies in the "hidden constant" of Big-O notation.

Big-O notation describes asymptotic behavior—how an algorithm's runtime scales as the input size $n$ approaches infinity. It intentionally ignores constant factors and lower-order terms. An algorithm with a complexity of $1,000,000 \cdot n$ is still technically $O(n)$, while an algorithm with a complexity of $0.1 \cdot n^2$ is $O(n^2)$. If you are multiplying small numbers, the $O(n^2)$ algorithm will be vastly faster because of the massive constant multiplier in the $O(n)$ alternative.

For the Harvey-Hoeven algorithm, the overhead of setting up the multi-dimensional FFT spaces, managing recursion, and coordinating memory is astronomically high. The researchers themselves admitted that their algorithm only becomes faster than existing methods for numbers that are unimaginably large.

How large? The crossover point where the $O(n \log n)$ algorithm beats Schönhage-Strassen is estimated to occur when multiplying numbers that have more than $2^{1729^{12}}$ bits. To put this in perspective, the total number of atoms in the observable universe is estimated to be around $10^{80}$. The number of bits required to make the "fastest" multiplication algorithm actually fast is so large that it could not physically be represented within our universe. It is, in the truest sense of the word, a galactic algorithm.

The Hardware Reality: Cache, Pipelines, and Bit-Whacking

For software engineers writing high-performance code, optimization is not just about reducing algebraic operations; it is about respecting the physical design of modern CPUs.

1. Cache Hierarchies: Modern CPUs are fast, but memory access is slow. An algorithm that has excellent spatial and temporal locality (keeping data in L1/L2 cache) will consistently outperform an algorithm with a lower theoretical complexity that constantly misses the cache. FFT-based multiplication algorithms require massive, non-sequential memory lookups, which can lead to severe cache thrashing on standard hardware.

2. SIMD and Vectorization: Modern processors feature Single Instruction, Multiple Data (SIMD) architectures (such as AVX-512 or ARM Neon). Simple algorithms like Karatsuba or Toom-Cook can be easily vectorized, allowing the CPU to perform multiple arithmetic operations in parallel on a single clock cycle. The hyper-complex, multi-dimensional structures of galactic algorithms do not map easily to CPU registers.

3. Instruction Pipelining: Simple loops with predictable branch behavior allow the CPU's branch predictor and execution pipelines to run at maximum efficiency. High-overhead recursive algorithms disrupt this pipeline, leading to costly CPU stalls.

Conclusion: The Infinite Search for the Pragmatic Optimum

The story of multiplication algorithms is a humbling reminder of the divide between mathematics and engineering. While mathematicians have proven that $O(n \log n)$ is the theoretical speed limit for multiplication, the practical crown remains divided.

For the software you write today, the "fastest" way to multiply numbers depends entirely on scale:

• For small numbers (under 64 bits): Direct hardware-level CPU instructions ($O(1)$ clock cycles).
• For medium numbers (100 to 10,000 bits): Karatsuba's algorithm.
• For large numbers (10,000 to 1,000,000 bits): Toom-Cook multi-way division.
• For massive numbers (over 1,000,000 bits): The Schönhage-Strassen FFT method.

As hardware architectures evolve, perhaps with the rise of optical or quantum computing, the physical constraints of memory and cache may shift. But for now, the fastest way to multiply numbers remains a beautifully unsolved, practical mystery.