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

11–20 of 152 posts

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

#11

Post by TimorousBestie »

jmalicki wrote: post #8

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

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

#12

Post by pfdietz »

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…

Adding up those n1 numbers, each at least n2 digits long, takes O(n1 * n2) time.

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

#14

Post by aaronbwebber »

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…

your algorithm for multiplication involves doing multiplication?

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

#16

Post by jordigh »

pgreenwood wrote: post #6

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.

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

#17

Post by floxy »

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…

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

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

#18

Post by mgaunard »

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…

You're missing the fact that "multiplying a digit with a number" is not a single operation.

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

#20

Post by ccleve »

mgaunard wrote: post #18
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…

You're missing the fact that "multiplying a digit with a number" is not a single operation.

No, that's taken into account.
Post reply on HN