FRESH

Hacker News

Home

Mathematicians still don't know the fastest way to multiply numbers

230 points by beardyw

by JoelJacobson

3 subcomments

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...

by ErroneousBosh

4 subcomments

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,   90496 odd, add 90496 to the total
  --------------------------------------
                     144935
```
If we're disregarding shifts and adds as completing in negligible time, well, this whole thing is just done with shifts and adds, and you can predict how many of them by identifying the leftmost bit set in the multiplier.

by jmalicki

1 subcomments

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).

by projectileboy

1 subcomments

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!

by nobrains

3 subcomments

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?

by bombela

4 subcomments

Does the article just end after describing the problem for me only? I am left wanting for more.

by qingcharles

1 subcomments

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.

by jdhwosnhw

2 subcomments

I was under the impression that because the grade school technique we learn is really just convolution over the digits, the fastest algorithms achieve o(n logn) via fourier transforms. Is that not the case?

by 6510

1 subcomments

If you do it in binary you only need addition.
12 × 34 = 0xC x 0x22 = 1100 x 100010
Only two 1's!
1100 add 5 zeroes + 1100 add one zero = 110011000 = 408
ta-daa!

by jdw64

2 subcomments

I already know about fast multiplication algorithms, but it seems there's still no proof that a faster algorithm absolutely cannot exist. In other words, we don't know where the limit is yet.
If that gets proven, would programming multiplication algorithms become faster? I'm curious

by ChocMontePy

0 subcomment

Mirror in Yahoo News:
https://tech.yahoo.com/science/articles/mathematicians-still...

0 subcomment

by alienbaby

0 subcomment

We're going to need a bigger abacus.

by tobadzistsini

1 subcomments

Archive link. Fuck paywalls. Surprised nobody posted yet. https://archive.ph/k3dnD

by avmich

2 subcomments

We can likely use different number representations for faster results. E.g. numbers in the form of coefficients to prime factors can be multipled at O(n) time, right?

by Davidzheng

1 subcomments

The complexity is obviously nlogn - it's just hard to prove (this comment is only somewhat serious)

by stfnon

0 subcomment

back in 2008 I had actually a ton of success using Strassen turboplicattion kernels with some extra custom CUDA lora (its more for Cholay) than anything else but it worked. Obviously I was forbidden to use it due to interest of shana.

by morpheos137

1 subcomments

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.

by NetMageSCW

0 subcomment

Paywall.

by thx1138jgs

0 subcomment

[dead]

by moi2388

1 subcomments

For large numbers, operations like addition don’t matter? Only multiplication? And now we want to find the fewest amount of multiplications?
Okay. No problem.
(ad + bc) = d + d .. + d + c + c .. + c
There we go, zero multiplications.

by MarcelOlsz

0 subcomment

Terrence Howard already figured this out.

by QuantumNoodle

0 subcomment

wHy DOnT tHeY ASk aI

by charcircuit

4 subcomments

How is it measured? A lookup table takes 1 step to find the answer of a multiplication.

by hankbond

3 subcomments

Shout out to a cookie ToS modal on top of an email newsletter modal on top of the article. What a great way to make me immediately click back and leave the site.

by Kyuren

2 subcomments

If the 2019 algorithm is only useful for "galactic numbers" that's really neat because it will help a lot in the future as it seems like computation is only increasing in scale.

by monster_truck

0 subcomment

On some level I feel like we aren't even really trying. This stuff is so damn dry, though.
(warning, I refuse to like math and address it on my own terms, proceed further at your own peril)
Started looking into exact integer matrix multiplication, wanted to use it for some differential bullshit to find whatever they call the magic numbers that simplify a lot of complicated work into virtually no work for suspension/drivetrain/grip simulations at scale
To my surprise rocm didn't even usefully accelerate it! I said there is no fuckin way a 7900XTX is only good for 0.5 TOPS when working with 64 bit integers. I knew RNS/CRT/GEMM was a thing which led me to this https://github.com/RIKEN-RCCS/GEMMul8. Nothing pisses me off more than CUDA having something ROCm doesn't. So I told the models to try and fill the moat in with concrete. Think I got up to almost 3 TOPS before I stopped, and there are some pretty absurd wins for int32/other shapes.
Here's the slop https://github.com/doublemover/RNS8, I haven't cleaned it up or anything.
Life has gotten in the way so I had to set it down, and fighting the air conditioning when its "95 feels like 107" and the sky is filled with smoke is... not cool. I will finish it after summer. The HotAisle guy is a legend and hooked it up with some credits so I will be able to do the same for CDNA3, it at least compiles and runs but it has not been optimized/tested much yet.
Started with ChatGPT 5.5 but it sucked. I'm not paying $200/mo to play reset bingo while they figure out their bugs, especially without 20x. They lit my last $50 on fire in like 20 minutes with no remediation past "keep paying and you'll get more resets". Don't sleep on Deepseek, V4 Pro was responsible for the biggest leaps and it cost all of $15. It's genuinely great. The only way I'd go back to a closed model is if it was completely free. It will be fun to see how much better models are in a few months.

by pgreenwood

1 subcomments

I don't think the article did a great job with their two digit illustration. They simply state:
(ad + bc) = ((a + b) × (c + d)) – ac – bd.
First note this equation is more clearly be written as:
ad + bc = (a + b)(c + d) – ac – bd.
To see why this is so first expand (a + b)(c + d).
(a + b)(c + d) = ac + ad + bc + bd
now
(a + b)(c + d) − ac − bd = ac + ad + bc + bd − ac − bd
Hence
ad + bc = (a + b)(c + d) – ac – bd.

by ccleve

10 subcomments

Ok, maybe I don't understand the problem, but it seems obvious that it should never be greater than O(min(n1, n2) * 10), where n1 and n2 are the lengths in digits of each argument, and assuming we are multiplying decimal numbers.
Take the first digit of the longer number. Multiply it by the shorter number and store the result. Take the second digit of the longer number. If it matches the first digit, do a lookup of the last result and use that, else multiply and store. Repeat.
There will be a maximum of 10 * (length of the shorter number) multiplies, because there are only 10 unique digits. After that every operation is a lookup.
You could even do a tiny optimization by skipping the multiplication for the zero digit.
Worst case, the two numbers are the same length, in which case it's O(n/2 * 10), which is a heck of a lot better than O(n log n).
What am I missing here?
EDIT to respond to the comments: in the article, they are only counting the number of multiplies in the O() value. They are not including the adds.