Mathematicians still don't know the fastest way to multiply numbers(scientificamerican.com) |
Mathematicians still don't know the fastest way to multiply numbers(scientificamerican.com) |
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...
There is a nice picture of the "best" choice for different ranges of sizes of numbers to be multiplied at http://gmplib.org/devel/log.i7.1024.png
More context and explanation can be found at: http://gmplib.org/devel/
Then for each digit, you select between the other input multiplied by 0 (all zeros), +1 (identity), +2 (shift left by one bit), or -1 or -2 (flip all the bits of +1 or +2, plus a correction). Since a number has about half as many digits in base 4 as in base 2, you have about half as many digits to sum as if you'd done this in base 2.
Then you sum up all those results, but since carry propagation is expensive, you mostly use "compressors", e.g. you sum up three intermediates at a time, but you do it bit-by-bit, where three 1-bit numbers add up to a 2-bit number (from 0 to 3). This is called a Wallace Tree. The point is that you are generating carries, but you aren't propagating them, just adding them back into the set of things to be summed.
At the end of the tree step, you have just two numbers left, and you add them conventionally. That's the only step that needs full carry propagation.
If you are implementing a multiply-add, or multiplying several numbers and adding up all the results or similar, then you usually only need one full carry propagation stage.
The overall circuit has quadratic area but only a logarithmic depth in gates. IIRC whether to do Booth or not is a tradeoff: at least in some circumstances the rewrite steps make it slower but smaller. Hardware tool vendors have done a lot of work to tune these circuits very tightly, using e.g. specialized gates like AOI, heuristics for how to set up the tree, etc.
(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.
There are other weird formatting things in this article, which I blame on AI. I don't think the whole article was written by AI, but the copy-editing and formatting looks like an AI messed up things, such as those pointless round brackets or the inconsistency of multiplication (sometimes there is a × sign, sometimes there isn't), or this:
> have suspected that O(n²) was an inherent speed limit for multiplication. The celebrated Soviet math professor Andrey Kolmogorov posed the O(n^2)
The AI can't decide on notation.
12 × 34 = 0xC x 0x22 = 1100 x 100010
Only two 1's!
1100 add 5 zeroes + 1100 add one zero = 110011000 = 408
ta-daa!
https://tech.yahoo.com/science/articles/mathematicians-still...
In your case, doing prime factoring is where the cost would be, wouldn't it?
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.
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
Adds are not really considered negligible; the article is just sloppy. (Some shifts might be negligible in some models because a fixed shift requires no logic gates.) The cost of the adds in Karatsuba is significant both theoretically and in practice, and determines the cutoff where Karatsuba is useful. But the exponent in O(n^(log_2 3)) is dominated by the recursive multiplications; the adds only affect the leading constant hidden in the O().
When considering multiplication algorithms the parameter N is the number of digits of the two numbers. In that model adds do not complete in negligible time, and instead take O(N) time.
If that gets proven, would programming multiplication algorithms become faster? I'm curious
So for numbers we normally work with, no. Maybe with cryptographic operations though.
Factorize big numbers, sort an array, beat stockfish at chess, create a SOTA microkernel OS from English description. All O(1) with lookup table!
It's not how complexity works.
Yes, but it suffers from a large amount of space complexity, and probably would have high constant factors in practice.
(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.
In fact a computer executing it would be so large that speed of light would be the main constraint limiting execution speed, not theoretical algorithmic complexity that ignores data locality.
That's base 5 then. It needs to go from -2 to +1 if you want base 4
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.
But obviously multiplying two n-bit binary numbers is not done in O(1) time, so "only counting the number of multiplies" is not a meaningful model, and not the model adopted by the researchers quoted in the article.
The lookup table would not work for that case
1234567890
x 111111
------------
1234567890
12345678900
123456789000
1234567890000
12345678900000
+ 123456789000000
-----------------
137,174,072,825,790
So what I wrote debunks your assumptions and proves your argument wrong.
This is how conversations normally go.
There's also NTT / Fourier multiplication as an option, for big integers or polynomials or modular arithmetic.
In general any problem can be solved in 1 step with a lookup table, so here you go P=NP solved.
If additions were truly free, an even easier optimal algorithm would just be repeated addition involving zero multiplications.
Memoizing number-by-digit multiplication doesn't make multiplication O(1) because one must still do an N-digit addition (which is O(N)) for each digit.