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

31–40 of 152 posts

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

#32

Post by groundzeros2015 »

jdw64 wrote: post #22

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

Matrix multiplication is constantly getting improved but these methods aren’t improvements on practical implementation.

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

#34

Post by necovek »

avmich wrote: post #33

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?

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?

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

#35

Post by derwiki »

Terr_ wrote: post #19
hankbond wrote: post #13

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.

Shout-out to javascript disabled by default :)

And Safari Reader Mode!

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

#37

Post by zeroonetwothree »

avmich wrote: post #33

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 :)

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

#38

Post by svat »

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…

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.

Post reply on HN