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

101–110 of 152 posts

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

#101

Post by hansvm »

techpression wrote: post #97
Someone wrote: post #85

Earlier quoted context omitted.

> 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

Assuming the ink is free, you use some sort of scheme to take advantage of the full printable ascii character set, and you don't bother presenting key values (if necessary, you could print a key offset at the top-left of each page), just the table outputs, I'm getting a break-even point at each character being around 0.2 square nanometers.

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

#102

Post by sroussey »

less_less wrote: post #70
sparky_z wrote: post #65

Earlier quoted context omitted.

In a sense, they do exactly that! But since there are only two single-digit numbers in binary, it makes for a pretty short table.

Hardware multipliers often use a sort of base-4-ish lookup table trick as well, using the Booth-Wallace algorithm. Booth's idea is to rewrite one of the inputs in base (usually) "4", except that the digits go from -2 to +2 instead of 0 to 3. (That's five possible digits! This helps the rewriting stage not have to propagate carries. Carry propagation is very expensive.) You can use Booth in a base higher than 4, espec…

Carry propagation is indeed quite slow. With so much math for AI, is it finally time to go back to analog? Superposition is instant.

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

#103

Post by Sharlin »

hankbond wrote: post #99
snowwrestler wrote: post #96

Earlier quoted context omitted.

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.

Direction that's not Jewish?

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

#104

Post by tug2024 »

jmalicki wrote: post #26
TimorousBestie wrote: post #11

Earlier quoted context omitted.

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!

[dead]

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

#105

Post by jason_s »

ErroneousBosh wrote: post #62

I don't know what age range "grade school" is, but I remember being taught that method when I was about 7 or 8, although it didn't really "land" properly until I read the short story "The Feeling of Power" by Isaac Asimov. What I'm surprised to see left out here (unless I missed it in the page's horrible formatting) is a mention of the way that computers multiply two integers. They use a technique I saw described in…

Russian Peasant Multiplication (https://www.embeddedrelated.com/showarticle/760.php)

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

#106

Post by morpheos137 »

Karatsuba in my understanding only becomes advantageous for very large numbers relative to human scale. Mathematically it is interesting but in engineering terms the overhead usually is not worth it for practical applications. There is a fundamental trade off between factor size and product precision. If you can accept lower precision then floating point works well for large in human scale numbers.

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

#107

Post by charcircuit »

bmacho wrote: post #72
charcircuit wrote: post #69

Earlier quoted context omitted.

>This would be the solution for any problem/algorithm, wouldn't it? Yes, but it suffers from a large amount of space complexity, and probably would have high constant factors in practice.

Exactly. So what I wrote debunks your assumptions and proves your argument wrong. This is how conversations normally go.

What you wrote agreed with me.

>All O(1) with lookup table!

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

#108

Post by jason_s »

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…

I get it, but I don't think we should remain silent within the community. Norms for websites are important to cultivate.

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

#109

Post by jason_s »

TimTheTinker wrote: post #24
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

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.

Even crypto isn't that large: 2^4096 is kind of the norm here.

Some mathematical researchers are working in the million, billion, or even trillion-bit range.

Post reply on HN