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:
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.
This is a problem I have a lot in modern programming ecosystems: How do I tell the difference between a library written by a team of experts who have spent decades optimizing everything to do with the task and a library written by one guy that's an unnecessary straightforward wrapper over the obvious implementation?
Or increasingly, a library written by an LLM referencing a pile of such “one guy” projects of varying levels of suck (from actually good to good-got-it-is-full-of-suck).
What I have been seeing recently is having a great LLM rewrite the library leads to fewer bugs and also optimized for your use case. More expensive for sure than pulling something like epub.js but when the library has infinite open issues it can be a lot better.
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).
If you’re interested, I found https://arxiv.org/abs/2505.09814v1 to beat Strassen for medium-sized and larger covariance matrices. YMMV of course. Takes a little adjustment for XX^H but it’s not so bad.
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!
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?
Hardware multipliers often use a sort of base-4-ish lookup table trick as well, using the Booth-Wallace algorithm. Booth's idea is to rewrite one of the inputs in base (usually) "4", except that the digits go from -2 to +2 instead of 0 to 3. (That's five possible digits! This helps the rewriting stage not have to propagate carries. Carry propagation is very expensive.) You can use Booth in a base higher than 4, especially if you know one of the multiplicands before the other, but you run into tradeoffs pretty quickly.
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.
It's still a modified base 4, because the significance of the i'th digit is 4^i, not 5^i.
Edited to add: I'm also not sure whether real-life implementations have -0 as an option. Of course -0 could be normalized to +0, but it might be cheaper not to bother if the sign is applied after the digit selection.
It isn't balanced quinary, but rather redundant balanced quaternary (base 4). In balanced quinary (base 5), each digit has 5x the significance of the previous one, but in Booth's encoding algorithm it's 4x.
If digit i has significance b^i, then b (the base of the exponentiation) is the base (or radix) of the number system.
The page you linked explicitly mentions the binary version of Booth encoding as having base b=2 and three signed digits {-1, 0, 1}. The quaternary version similarly has b=4 and five signed digits {-2, -1, 0, 1, 2} ... and possibly sometimes -0 in practice, not sure.
Every combinational logic function can be implemented as a look up table, which can be implemented as a hardware ROM. It is common to consider speed-power-area tradeoffs to find good implementations.
> I am assuming it would be because multiplying would still be faster than reading from a lookup table?
Even if it isn’t, it still would be a lot cheaper. With 32-bit integers, the lookup table would have 2⁶⁴ 64-bit values. If my math six right, that is 128 exabytes of read-only memory. With 64-but integers, it truly would be impractical, at 2¹²⁸ 128-bit values.
You don't need to look up the entire multiplication in a single move. When we do multiplication outside of our own mental lookup tables, we have an algorithm for that. The one described in the article. You can size your lookup table however large you like.
Assuming the ink is free, you use some sort of scheme to take advantage of the full printable ascii character set, and you don't bother presenting key values (if necessary, you could print a key offset at the top-left of each page), just the table outputs, I'm getting a break-even point at each character being around 0.2 square nanometers.
if you want a little more in depth explanation of the whole multiplication thing Ican recommend TAOCP volume 2. it has a section called 'How fast can we multiply?' it should provide more insight. there is a paper from djb (Daniel J Bernstein),which I can also recommemd: https://cr.yp.to/lineartime/multapps-20080515.pdf
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 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?
Jesus, I took 4 years of Electrical Engineering and at no point did any professor make this brilliant analogy. It would have helped many students, including myself.
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.
Yeah, that shift-and-add algorithm is sometimes used on microcontrollers, either in software if there's no hardware multiplier, or in hardware if you want the bare minimum in acceleration at a tiny cost in area.
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().
> If we're disregarding shifts and adds as completing in negligible time
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.
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?
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.
Residue number systems are really neat! They're sometimes used in crypto implementations, but there you're doing modular multiplication and in most cases the modular reduction then becomes costly, so it's not a free lunch. (Except in RSA and a few other cases. RSA-CRT gets you a "free" ~4x performance boost except it's more brittle to mistakes and side-channel / fault attacks.)
There's also NTT / Fourier multiplication as an option, for big integers or polynomials or modular arithmetic.
I think you would probably just pick enough primes at the start to handle numbers up to the number of bits you need. If we stick with primes that fit in 32-bit unsigned integers, then using the largest k such primes covers numbers up this many bits or decimal digits:
If we use primes that fit in 8-bit unsigned integers, here's what we can handle with the largest k such primes. This table only goes to 54 because after that we run out of primes.
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.
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.
The article discusses how Python uses it for numbers above ~2100 bits for that reason. That’s way beyond your regular floating-point type in terms of precision.
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
Well, yes, which is why they don't measure it your way, as it doesn't lead to discovering anything interesting about computation to have a shortcut like that. Or if they do it's part of a larger analysis, called an oracle machine.
Maybe I'm not communicating the point clearly. In order to use a table to do the whole multiplication it has to be much larger than the largest number you would want to multiply with it. A lot of the analysis of algorithms, especially multiplication as discussed here, is about astronomically large numbers, so you don't want the existence of an even more astronomically large table as a prerequisite.
We are talking about mathematicians. We are not talking about computer engineers trying to implement a physical GPU that can multiply matrices as fast as possible. You don't have to physically build the astronomically look up table by hand. One can simply state that it exists. Proofs do not have to be clean to be a proof. You might not "want" something in a proof, but if it works then it works.
What you are stating is simply that any algorithm whose inputs are bounded can be solved in O(1) time with a lookup table. That's known and obvious, which makes it not interesting.
Moreover it only works with bounded inputs. If your input is unbounded (as is this case with multiplication over arbitrarily large numbers) then an infinitely big lookup table is just not possible because it's part of the algorithm and hence needs to be finite.
If infinitely-big lookup tables were allowed you could for example write an algorithm that solves the halting problem, just index into the lookup table for its solution. And actually you could do this for any problem! So any problem, even so called "non computable" ones, admit a solution that runs in time linear to their input. I hope you see that this is nonsensical and it's why lookup tables are considered part of the algorithm and hence need to be finite.
> You might not "want" something in a proof, but if it works then it works.
And at the same time you don't get to change the definition of algorithm to allow your "proof" to be valid, otherwise you're just talking about nonsense.
>And at the same time you don't get to change the definition of algorithm to allow your "proof" to be valid
It is other people who are trying to attack my statement who are trying to apply words like "algorithm" to it. You have such a fixed view of how things operate that you are failing to be able to take a step back and accept the existence of being able to solve any problem in a single step. You can claim that it is obvious, and trivial, and uninteresting, but that doesn't invalidate it. Sometimes thinking outside of the box is required and such strict adherence to what has come before can cloud your view of an "obvious" solution that was there the whole time.
> You can claim that it is obvious, and trivial, and uninteresting, but that doesn't invalidate it. Sometimes thinking outside of the box is required and such strict adherence to what has come before can cloud your view of an "obvious" solution that was there the whole time.
Then sure, go ahead. Define your own model of computation, one not based on turing machines and which somehow allows for infinitely big lookup tables, and then see what great insight it provides you.
I wonder discoveries you will be able to make in a system where you can say that the solution of a problem is just its solution.
Using e.g. a single zettabit-sized look-up table to give the 64-bit result of a multiplication of two 32-bit numbers suffers from a similar problem. But if we're talking about practical concerns there are already faster methods than random access in >100 exabytes of memory. And if we're talking theoretical concerns your answer still hasn't addressed the question of how to multiply numbers fast.
The model usually measures in terms of fixed-size operations, e.g. 2-input binary gates. There's some variation in how to count memory lookups, but even in models where accessing a large memory counts as only one step, any tables present in the code still have to be fixed-size (except in models like P/poly, but even then they can't be exponential size).
The article is explicit that addition is O(n), with n digits, which is cheaper than multiplication is believed to be. Naive multiplication is O(n*n) -- considerably less than your algorithm.
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.
> Please don't complain about tangential annoyances—e.g. article or website formats, name collisions, or back-button breakage. They're too common to be interesting.
Tons and tons of sites have annoying popups. As such, complaining about it is usually off topic; that is, the complaint has nothing to do with the substance of the specific article that was posted for discussion.
The best place for such a complaint is to send it back to the website publisher. Then at least they will know their audience doesn’t like it.
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.
If it ever had the slightest chance of being useful on Earth, it would not be called a "galactic algorithm". In this case that algorithm might be more than galactic: there isn't enough matter in the observable universe to build a conventional computer able to execute it.
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.
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.
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.
Erm, I'm not sure you clarified anything other than removing one pair of spurious round brackets that who knows why they're there in the source material.
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)
It is sadly emblematic of how much SciAm has cheapened itself over the past decade. They used to care about technical details. Now they serve up poorly formatted rehashes of news (largely) from 65 years ago.
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.
> 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.
By your reasoning, multiplying two numbers in binary involves no multiplication at all, because multiplying by 1 and multiplying by 0 are both trivial operations.
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 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.
The reason the adds don't count is not because they arbitrarily decided to ignore them.
Addition is O(n), multiplication is more than O(n), by the nature of the big-O notation, when you have to do a series of operation, you only have to count the ones with the highest complexity. So in the Karatsuba example where the formula involves both additions and (recursive) multiplications, the additions don't count only because the multiplications dominate.
Or, as a formula, O(n log n) + O(n) = O(n log n), and btw O(n/2*10) = O(n), in big-O, constant factors don't count
Not an expert, but I think the algorithm works for any base, not just 10. The python implementation uses base 2^30 for their multiplication. Base 10 is just a convenient illustration
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.
They don't count the additions or shifts because they're both linear time operations, and thus provably at least as fast as multiplication (both in an asymptotic and exact sense). In any case where multiplication is super-linear, this means that addition and shifting are are not the temporal bottleneck at any stage in the algorithm where you have a constant number of those operations surrounding at least one multiplicative recursive call (on numbers of similar magnitudes).
If additions were truly free, an even easier optimal algorithm would just be repeated addition involving zero multiplications.
The complexity of Karatsuba's algorithm, because it's a recursive one that gets "wider" at every level, is dominated by the width of that recursion. The top level always has a small number of operations, so we don't explicitly count them there, but the bottom has the truly huge number of operations that contribute to the algorithm's complexity, because each level of recursion dramatically increases the number of operations. Some number of those operations (most of them, in fact) will be single-digit additions.
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.
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...
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
This really demonstrates the utility of pulling in a library written by experts in the field the library handles.
This is a problem I have a lot in modern programming ecosystems: How do I tell the difference between a library written by a team of experts who have spent decades optimizing everything to do with the task and a library written by one guy that's an unnecessary straightforward wrapper over the obvious implementation?
Or increasingly, a library written by an LLM referencing a pile of such “one guy” projects of varying levels of suck (from actually good to good-got-it-is-full-of-suck).
What I have been seeing recently is having a great LLM rewrite the library leads to fewer bugs and also optimized for your use case. More expensive for sure than pulling something like epub.js but when the library has infinite open issues it can be a lot better.
You defer to the advice of experts you trust. Which somehow have become harder to come by in terms of signal to noise than 20-30 years ago.
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!
It's complicated. :-)
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/
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).
If you’re interested, I found https://arxiv.org/abs/2505.09814v1 to beat Strassen for medium-sized and larger covariance matrices. YMMV of course. Takes a little adjustment for XX^H but it’s not so bad.
Thanks!
[dead]
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!
> once the sub-matrices get small enough,
the next rabbit hole starts when you try to start lifting F_2 into Z for a given <n,n,n> tensor.
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?
In a sense, they do exactly that! But since there are only two single-digit numbers in binary, it makes for a pretty short table.
Hardware multipliers often use a sort of base-4-ish lookup table trick as well, using the Booth-Wallace algorithm. Booth's idea is to rewrite one of the inputs in base (usually) "4", except that the digits go from -2 to +2 instead of 0 to 3. (That's five possible digits! This helps the rewriting stage not have to propagate carries. Carry propagation is very expensive.) You can use Booth in a base higher than 4, especially if you know one of the multiplicands before the other, but you run into tradeoffs pretty quickly.
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.
Carry propagation is indeed quite slow. With so much math for AI, is it finally time to go back to analog? Superposition is instant.
If carry propagation is so expensive, why are the mathematicians, like Karatsuba, ignoring it? It seems like we need a better complexity measure.
> Booth's idea is to rewrite one of the inputs in base (usually) "4", except that the digits go from -2 to +2 instead of 0 to 3.
That's base 5 then. It needs to go from -2 to +1 if you want base 4
It's still a modified base 4, because the significance of the i'th digit is 4^i, not 5^i.
Edited to add: I'm also not sure whether real-life implementations have -0 as an option. Of course -0 could be normalized to +0, but it might be cheaper not to bother if the sign is applied after the digit selection.
No, balanced ternary, for example, uses {-1, 0, 1}. The system you're discussing is balanced quinary (base 5).
https://en.wikipedia.org/wiki/Signed-digit_representation
It isn't balanced quinary, but rather redundant balanced quaternary (base 4). In balanced quinary (base 5), each digit has 5x the significance of the previous one, but in Booth's encoding algorithm it's 4x.
If digit i has significance b^i, then b (the base of the exponentiation) is the base (or radix) of the number system.
The page you linked explicitly mentions the binary version of Booth encoding as having base b=2 and three signed digits {-1, 0, 1}. The quaternary version similarly has b=4 and five signed digits {-2, -1, 0, 1, 2} ... and possibly sometimes -0 in practice, not sure.
Every combinational logic function can be implemented as a look up table, which can be implemented as a hardware ROM. It is common to consider speed-power-area tradeoffs to find good implementations.
> I am assuming it would be because multiplying would still be faster than reading from a lookup table?
Even if it isn’t, it still would be a lot cheaper. With 32-bit integers, the lookup table would have 2⁶⁴ 64-bit values. If my math six right, that is 128 exabytes of read-only memory. With 64-but integers, it truly would be impractical, at 2¹²⁸ 128-bit values.
You don't need to look up the entire multiplication in a single move. When we do multiplication outside of our own mental lookup tables, we have an algorithm for that. The one described in the article. You can size your lookup table however large you like.
Printing it on paper and manually looking it up is probably cheaper with today’s ram-prices
Assuming the ink is free, you use some sort of scheme to take advantage of the full printable ascii character set, and you don't bother presenting key values (if necessary, you could print a key offset at the top-left of each page), just the table outputs, I'm getting a break-even point at each character being around 0.2 square nanometers.
The problem is that you also need multiplication to implement OCR.
Recursion is such a beautiful thing
Does the article just end after describing the problem for me only? I am left wanting for more.
It's an open question in mathematics/CS, that's all we know. If you want to know more, get to mathing :)
looks like ads swallowed the content and now I am hitting a paywall.
if you want a little more in depth explanation of the whole multiplication thing Ican recommend TAOCP volume 2. it has a section called 'How fast can we multiply?' it should provide more insight. there is a paper from djb (Daniel J Bernstein),which I can also recommemd: https://cr.yp.to/lineartime/multapps-20080515.pdf
This is one of my favorite section of TAOCP! Thank you for the link.
Scroll down, there is a huge ad but the article continues.
trying again, now there is a paywall anyways. I give up.
Ask Sol 5.6 for the answer
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.
Lower bounds are really hard.
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?
Can you explain some more? Thanks.
Jesus, I took 4 years of Electrical Engineering and at no point did any professor make this brilliant analogy. It would have helped many students, including myself.
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:
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.Yeah, that shift-and-add algorithm is sometimes used on microcontrollers, either in software if there's no hardware multiplier, or in hardware if you want the bare minimum in acceleration at a tiny cost in area.
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().
> If we're disregarding shifts and adds as completing in negligible time
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.
Russian Peasant Multiplication (https://www.embeddedrelated.com/showarticle/760.php)
Mirror in Yahoo News:
https://tech.yahoo.com/science/articles/mathematicians-still...
We're going to need a bigger abacus.
Archive link. Fuck paywalls. Surprised nobody posted yet. https://archive.ph/k3dnD
Not everyone is seeing a paywall. Not sure if it’s the adblocker or other factors.
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.
Residue number systems are really neat! They're sometimes used in crypto implementations, but there you're doing modular multiplication and in most cases the modular reduction then becomes costly, so it's not a free lunch. (Except in RSA and a few other cases. RSA-CRT gets you a "free" ~4x performance boost except it's more brittle to mistakes and side-channel / fault attacks.)
There's also NTT / Fourier multiplication as an option, for big integers or polynomials or modular arithmetic.
I think the problem comes when you do a multiplication and you need more primes for uniqueness.
I think you would probably just pick enough primes at the start to handle numbers up to the number of bits you need. If we stick with primes that fit in 32-bit unsigned integers, then using the largest k such primes covers numbers up this many bits or decimal digits:
Here it is if we use the k largest primes that fit in 16-bit unsigned integers: If we use primes that fit in 8-bit unsigned integers, here's what we can handle with the largest k such primes. This table only goes to 54 because after that we run out of primes.You mean like those guaranteed-always-compresses-by-at-least-one-bit algorithm patents gzip page made fun of?
In your case, doing prime factoring is where the cost would be, wouldn't it?
Yes, but the point is to look for different representations, not necessarily use this specific one.
The complexity is obviously nlogn - it's just hard to prove (this comment is only somewhat serious)
Maybe they should reduce sorting to multiplication lol
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!
Addition and conditional bit shifting (which is multiplication by powers of 2).
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.
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.
The article discusses how Python uses it for numbers above ~2100 bits for that reason. That’s way beyond your regular floating-point type in terms of precision.
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
The O(n log n) algorithm is galactic (only becomes more efficient when multiplying massive numbers)
So for numbers we normally work with, no. Maybe with cryptographic operations though.
Even crypto isn't that large: 2^4096 is kind of the norm here.
Some mathematical researchers are working in the million, billion, or even trillion-bit range.
Matrix multiplication is constantly getting improved but these methods aren’t improvements on practical implementation.
Paywall.
[dead]
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
I disagree. 1 step is a finite sequence of instructions.
The lookup table is part of the algorithm, and is not finite.
In general any problem can be solved in 1 step with a lookup table, so here you go P=NP solved.
It doesn't have to be part of the algorithm. It all depends on how you measure it.
Well, yes, which is why they don't measure it your way, as it doesn't lead to discovering anything interesting about computation to have a shortcut like that. Or if they do it's part of a larger analysis, called an oracle machine.
I am against statements like:
A: "X people don't know how to do Y"
B: "Why not do Z?"
A: "Z is too easy and boring so they actually added more restrictions to how you are allowed to do Y so that solution doesn't count"
Maybe I'm not communicating the point clearly. In order to use a table to do the whole multiplication it has to be much larger than the largest number you would want to multiply with it. A lot of the analysis of algorithms, especially multiplication as discussed here, is about astronomically large numbers, so you don't want the existence of an even more astronomically large table as a prerequisite.
We are talking about mathematicians. We are not talking about computer engineers trying to implement a physical GPU that can multiply matrices as fast as possible. You don't have to physically build the astronomically look up table by hand. One can simply state that it exists. Proofs do not have to be clean to be a proof. You might not "want" something in a proof, but if it works then it works.
What you are stating is simply that any algorithm whose inputs are bounded can be solved in O(1) time with a lookup table. That's known and obvious, which makes it not interesting.
Moreover it only works with bounded inputs. If your input is unbounded (as is this case with multiplication over arbitrarily large numbers) then an infinitely big lookup table is just not possible because it's part of the algorithm and hence needs to be finite.
If infinitely-big lookup tables were allowed you could for example write an algorithm that solves the halting problem, just index into the lookup table for its solution. And actually you could do this for any problem! So any problem, even so called "non computable" ones, admit a solution that runs in time linear to their input. I hope you see that this is nonsensical and it's why lookup tables are considered part of the algorithm and hence need to be finite.
> You might not "want" something in a proof, but if it works then it works.
And at the same time you don't get to change the definition of algorithm to allow your "proof" to be valid, otherwise you're just talking about nonsense.
>And at the same time you don't get to change the definition of algorithm to allow your "proof" to be valid
It is other people who are trying to attack my statement who are trying to apply words like "algorithm" to it. You have such a fixed view of how things operate that you are failing to be able to take a step back and accept the existence of being able to solve any problem in a single step. You can claim that it is obvious, and trivial, and uninteresting, but that doesn't invalidate it. Sometimes thinking outside of the box is required and such strict adherence to what has come before can cloud your view of an "obvious" solution that was there the whole time.
> You can claim that it is obvious, and trivial, and uninteresting, but that doesn't invalidate it. Sometimes thinking outside of the box is required and such strict adherence to what has come before can cloud your view of an "obvious" solution that was there the whole time.
Then sure, go ahead. Define your own model of computation, one not based on turing machines and which somehow allows for infinitely big lookup tables, and then see what great insight it provides you.
I wonder discoveries you will be able to make in a system where you can say that the solution of a problem is just its solution.
Cool. I will assert a magic 8 ball that gives the correct answer. Are we done?
Yup, and everyone measures it to be part of the algorithm, otherwise you start getting nonsensical results.
This would be the solution for any problem/algorithm, wouldn't it?
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.
>This would be the solution for any problem/algorithm, wouldn't it?
Yes, but it suffers from a large amount of space complexity, and probably would have high constant factors in practice.
Using e.g. a single zettabit-sized look-up table to give the 64-bit result of a multiplication of two 32-bit numbers suffers from a similar problem. But if we're talking about practical concerns there are already faster methods than random access in >100 exabytes of memory. And if we're talking theoretical concerns your answer still hasn't addressed the question of how to multiply numbers fast.
Exactly.
So what I wrote debunks your assumptions and proves your argument wrong.
This is how conversations normally go.
What you wrote agreed with me.
>All O(1) with lookup table!
The model usually measures in terms of fixed-size operations, e.g. 2-input binary gates. There's some variation in how to count memory lookups, but even in models where accessing a large memory counts as only one step, any tables present in the code still have to be fixed-size (except in models like P/poly, but even then they can't be exponential size).
because you're looking up a result not solving for it
You solve it by looking it up.
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.
The article is explicit that addition is O(n), with n digits, which is cheaper than multiplication is believed to be. Naive multiplication is O(n*n) -- considerably less than your algorithm.
My algorithm is O(n+n+..n) which is O(n), since there we also ignore addition fortunately :D
It would only be O(n) if the number of additions was constant. Here it varies with the size of the multiplier, giving us O(n*m).
Terrence Howard already figured this out.
wHy DOnT tHeY ASk aI
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.
From the HN guidelines:
> Please don't complain about tangential annoyances—e.g. article or website formats, name collisions, or back-button breakage. They're too common to be interesting.
Tons and tons of sites have annoying popups. As such, complaining about it is usually off topic; that is, the complaint has nothing to do with the substance of the specific article that was posted for discussion.
The best place for such a complaint is to send it back to the website publisher. Then at least they will know their audience doesn’t like it.
Dang that's my bad. Thank you for the gentile direction.
Direction that's not Jewish?
Lmao whoops, I meant gentle.
I get it, but I don't think we should remain silent within the community. Norms for websites are important to cultivate.
Shout-out to javascript disabled by default :)
And Safari Reader Mode!
[dead]
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.
If it ever had the slightest chance of being useful on Earth, it would not be called a "galactic algorithm". In this case that algorithm might be more than galactic: there isn't enough matter in the observable universe to build a conventional computer able to execute it.
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.
2 ^ (713 739 807 325 663 489 766 475 852 620 783 120 641) digits. Nope, an implementation of that algorithm will never be directly useful.
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.
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.
Erm, I'm not sure you clarified anything other than removing one pair of spurious round brackets that who knows why they're there in the source material.
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.
The AI is just like me, then.
> The AI can't decide on notation.
It is sadly emblematic of how much SciAm has cheapened itself over the past decade. They used to care about technical details. Now they serve up poorly formatted rehashes of news (largely) from 65 years ago.
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.
> 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.
By your reasoning, multiplying two numbers in binary involves no multiplication at all, because multiplying by 1 and multiplying by 0 are both trivial operations.
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 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.
Adding up those n1 numbers, each at least n2 digits long, takes O(n1 * n2) time.
The reason the adds don't count is not because they arbitrarily decided to ignore them.
Addition is O(n), multiplication is more than O(n), by the nature of the big-O notation, when you have to do a series of operation, you only have to count the ones with the highest complexity. So in the Karatsuba example where the formula involves both additions and (recursive) multiplications, the additions don't count only because the multiplications dominate.
Or, as a formula, O(n log n) + O(n) = O(n log n), and btw O(n/2*10) = O(n), in big-O, constant factors don't count
You're missing the fact that "multiplying a digit with a number" is not a single operation.
No, that's taken into account.
Not an expert, but I think the algorithm works for any base, not just 10. The python implementation uses base 2^30 for their multiplication. Base 10 is just a convenient illustration
The lookup table would not work for that case
You’re missing the O(1) space complexity.
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.
They don't count the additions or shifts because they're both linear time operations, and thus provably at least as fast as multiplication (both in an asymptotic and exact sense). In any case where multiplication is super-linear, this means that addition and shifting are are not the temporal bottleneck at any stage in the algorithm where you have a constant number of those operations surrounding at least one multiplicative recursive call (on numbers of similar magnitudes).
If additions were truly free, an even easier optimal algorithm would just be repeated addition involving zero multiplications.
The complexity of Karatsuba's algorithm, because it's a recursive one that gets "wider" at every level, is dominated by the width of that recursion. The top level always has a small number of operations, so we don't explicitly count them there, but the bottom has the truly huge number of operations that contribute to the algorithm's complexity, because each level of recursion dramatically increases the number of operations. Some number of those operations (most of them, in fact) will be single-digit additions.
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.
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.
your algorithm for multiplication involves doing multiplication?
You might want to learn about recursion. It'll blow your mind.
… which needs a terminating case, which cannot be not defined as the same recursion.
When talking informally, people often omit mentioning the base case when it's obvious or trivial.
Btw, your recursion doesn't necessarily need a terminating case.
See eg this definition of the list of Fibonacci numbers in Haskell:
Strictly-speaking, that's corecursion.
Of course. But it's close enough as a reply to "your algorithm for multiplication involves doing multiplication?"