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.
- JoelJacobson
Back in 2024, I was trying to optimize PostgreSQL's NUMERIC data type, which is base-10000, using Karatsuba. The problem of finding the optimal threshold of when to switch to Karatsuba turned out to be really hard, since it depends on the size of both factors combined. After some hundreds of hours, I gave up, and started thinking about if there could be a simpler solution. I came to think about another idea I'd had before but abandoned, about 64-bit modernizing the digit base from 10k to 100M, but that would be a challenge due to existing data on disk. Desperate of finding a solution, I wondered if it could be fast enough to do on-the-fly conversion back and forth between base-10k and base-100M, and then realized that, yes, of course, it will be fast already for quite small N (testing shows already between 3-6 base digits). The trick basically reduced the N in O(N^2) into half, i.e. O((N/2)^2), with some O(2*N) cost for the conversion back and forth.
I had a lot of fun hacking on this idea together with the maintainer of the NUMERIC data type, and after two months the patch finally was ready and got committed:
https://git.postgresql.org/gitweb/?p=postgresql.git;a=commit...
- ErroneousBosh
I don't know what age range "grade school" is, but I remember being taught that method when I was about 7 or 8, although it didn't really "land" properly until I read the short story "The Feeling of Power" by Isaac Asimov.
What I'm surprised to see left out here (unless I missed it in the page's horrible formatting) is a mention of the way that computers multiply two integers. They use a technique I saw described in a book when I was about 11 as the "Russian Farmer Method" (or something like that, it was in English and I might have misremembered it).
In that you shift the multiplier right and multiplicand left, halving one and doubling the other. If the multiplier is odd, add the multiplicand to the total.
It's really doing the same thing as "long multiplication" like you're taught in primary school but in binary so when you add a 0 to the right for the higher order digits you're doubling, not multiplying by ten. If you write code to do it you'd shift the multiplier first then consider whether or not to add by testing the Carry flag, or "Link bit" if like the author of the book I read you're demonstrating it on a PDP8 ;-)
But let's have a worked example, picking two numbers at random 205 * 707, use the smaller as the multiplier:
205, 707 odd, add 707 to total
102, 1414 even, disregard
51, 2828 odd, add 2828 to the total
25, 5656 odd, add 5656 to the total
12, 11312 even, disregard
6, 22624 even, disregard
3, 45248 odd, add 45248 to the total
1, […]
- jmalicki
I have actually had a ton of success using Strassen matrix multiplication kernels with extra structure in custom CUDA kernels (e.g. a covariance matrix is symmetric positive definite, or can be represented with Cholesky, and that comes up in a ton of useful computation). It's been a couple of years, but IIRC I would find it would start to win over the standard kernels at ~n>2500 or something (and in addition to Strassen was also exploiting the explicit structural constraints of the matrix, so not a completely fair comparison).
- projectileboy
For anyone interested in digging, check out Karatsuba's algorithm (https://en.wikipedia.org/wiki/Karatsuba_algorithm), Strassen matrix multiplication (https://en.wikipedia.org/wiki/Strassen_algorithm), and Toom-Cook multiplication (https://en.wikipedia.org/wiki/Toom–Cook_multiplication).
Of course, there are also implementation considerations. For example you can speed up Strassen by recursively breaking down the matrix into sub-matrices in parallel, but only down to a point - once the sub-matrices get small enough, it becomes faster to simply do a straight Strassen computation. And it depends on your hardware. For something seemingly so simple, you can go pretty far down a rabbit hole!
- nobrains
Why do we make computers multiply single digit numbers, instead of taking the result from a lookup table, like humans do? To answer my own question, I am assuming it would be because multiplying would still be faster than reading from a lookup table? Any ideas?
- bombela
Does the article just end after describing the problem for me only? I am left wanting for more.
- qingcharles
Amazed I hadn't heard of this before. Would be interesting to see if they can prove that they have discovered the fastest at O(n × log n) or whether there is more still to come.
- morpheos137
Karatsuba in my understanding only becomes advantageous for very large numbers relative to human scale. Mathematically it is interesting but in engineering terms the overhead usually is not worth it for practical applications. There is a fundamental trade off between factor size and product precision. If you can accept lower precision then floating point works well for large in human scale numbers.