Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

scientificamerican.com

Post reply on HN
Print view View original

51–60 of 152 posts

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

#51

Post by inkysigma »

ccleve wrote: post #10

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 t…

The final time complexity for Karatsubas does account for the addition via the master theorem and gives you something less than n^2. It’s just in some sense the recursion is dominant so we add to the exponent. As a result, I think the article is just talking about counting multiplications since it’s in some sense the “expensive” operation in the both the recursive karatsuba and the regular grade school method.

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

#52

Post by chowells »

ccleve wrote: post #23
floxy wrote: post #17

Earlier quoted context omitted.

1234567890 x 111111 ------------ 1234567890 12345678900 123456789000 1234567890000 12345678900000 + 123456789000000 ----------------- 137,174,072,825,790 ...looks like O(n^2).

Once the longer number starts repeating digits, then it's not n^2 anymore. Multiplies get replaced with lookups. And we're only counting the multiplies. That's all they counted in the article. Not the adds, not the shifts.

The slowest multiplications are always when the two numbers are about the same size... That is to say, the case you're talking about doesn't happen.

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

#53

Post by WCSTombs »

zeroonetwothree wrote: post #37
avmich wrote: post #33

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?

True but addition becomes a lot less efficient in this representation :)

To make both addition and multiplication O(n), you can store numbers as their residues modulo a bunch of different primes and appeal to the Chinese Remainder Theorem. However, then size comparison becomes difficult.

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

#54

Post by SkiFire13 »

ccleve wrote: post #10

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 t…

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

This simplification relies on the fact that after making a multiplication the cost of merging it with the result of another is always less than the cost of performing the multiplication, so it doesn't change the overall complexity.

This is not true in your proposed algorithm: a lookup is O(1), but merging is O(N), so you cannot do the same simplification and have to count the complexity of performing adds as well.

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

#57

Post by monster_truck »

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.

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

#58

Post by hcs »

charcircuit wrote: post #39

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

An algorithm is a finite sequence of instructions, and so can't include an infinite table. More generally, https://en.wikipedia.org/wiki/Effective_method

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

#59

Post by wormslayer666 »

JoelJacobson wrote: post #43

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 b…

A bit tangential, but the folks behind the GNU Multiple Precision Library (GMPLib) have the problem of choosing algorithms more or less fleshed out. They've got some fairly approachable manual pages[1] for the various algorithms they use as operand sizes scale up, where Karatsuba is only the second of six options in terms of operational complexity.

[1] https://gmplib.org/manual/Multiplication-Algorithms

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

#60

Post by sureglymop »

JoelJacobson wrote: post #44
JoelJacobson wrote: post #43

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 b…

Here is the full pgsql-hackers mailing list thread where you can follow our work from initial idea to commit: https://www.postgresql.org/message-id/flat/9d8a4a42-c354-41f...

Love this, thank you for providing the context!
Post reply on HN