How is it measured? A lookup table takes 1 step to find the answer of a multiplication.
because you're looking up a result not solving for it
You solve it by looking it up.
Mathematicians still don't know the fastest way to multiply numbers
41–50 of 152 posts
Re: Mathematicians still don't know the fastest way to multiply numbers
#42Does the article just end after describing the problem for me only? I am left wanting for more.
Scroll down, there is a huge ad but the article continues.
Re: Mathematicians still don't know the fastest way to multiply numbers
#43Back 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...
Re: Mathematicians still don't know the fastest way to multiply numbers
#44Back 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...
Re: Mathematicians still don't know the fastest way to multiply numbers
#45Earlier 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 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.
Re: Mathematicians still don't know the fastest way to multiply numbers
#46[deleted]
Re: Mathematicians still don't know the fastest way to multiply numbers
#47I 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 mul…
The AI is just like me, then.
Re: Mathematicians still don't know the fastest way to multiply numbers
#48Paywall.
Re: Mathematicians still don't know the fastest way to multiply numbers
#49back 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.
Re: Mathematicians still don't know the fastest way to multiply numbers
#50How is it measured? A lookup table takes 1 step to find the answer of a multiplication.
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.