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

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.

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.

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

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.

             1234567890 
           x     111111
           ------------
             1234567890
            12345678900
           123456789000
          1234567890000
         12345678900000
      + 123456789000000
      -----------------
    137,174,072,825,790 

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.

Terrence Howard already figured this out.

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

Mirror in Yahoo News:

https://tech.yahoo.com/science/articles/mathematicians-still...

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?

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

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

Paywall.

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.

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

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.