Terrence Howard already figured this out.
Mathematicians still don't know the fastest way to multiply numbers
21–30 of 152 posts
Re: Mathematicians still don't know the fastest way to multiply numbers
#22I 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
Re: Mathematicians still don't know the fastest way to multiply numbers
#23Ok, 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…
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.
Re: Mathematicians still don't know the fastest way to multiply numbers
#24I 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.
Re: Mathematicians still don't know the fastest way to multiply numbers
#25Does the article just end after describing the problem for me only? I am left wanting for more.
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
Re: Mathematicians still don't know the fastest way to multiply numbers
#26I 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 Stras…
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!
Re: Mathematicians still don't know the fastest way to multiply numbers
#27Ok, 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…
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
Re: Mathematicians still don't know the fastest way to multiply numbers
#28Earlier 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.
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.
Re: Mathematicians still don't know the fastest way to multiply numbers
#29Ok, 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…
your algorithm for multiplication involves doing multiplication?
You might want to learn about recursion. It'll blow your mind.
Re: Mathematicians still don't know the fastest way to multiply numbers
#30Ok, 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…
You’re missing the O(1) space complexity.