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

91–100 of 152 posts

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

#91

Post by GuB-42 »

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…

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

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

#92

Post by cvoss »

6510 wrote: post #61

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

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

#93

Post by entrope »

jordigh wrote: post #16
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 mul…

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

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

#94

Post by entrope »

moi2388 wrote: post #89

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.

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

#95

Post by moi2388 »

entrope wrote: post #94
moi2388 wrote: post #89

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

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

#96

Post by snowwrestler »

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.

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.

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

#97

Post by techpression »

Someone wrote: post #85
nobrains wrote: post #64

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?

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

Printing it on paper and manually looking it up is probably cheaper with today’s ram-prices

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

#98

Post by AlotOfReading »

moi2388 wrote: post #95
entrope wrote: post #94

Earlier quoted context omitted.

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

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

#99

Post by hankbond »

snowwrestler wrote: post #96
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.

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…

Dang that's my bad. Thank you for the gentile direction.
Post reply on HN