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

111–120 of 152 posts

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

#111

Post by charcircuit »

hcs wrote: post #84
charcircuit wrote: post #81

Earlier quoted context omitted.

It doesn't have to be part of the algorithm. It all depends on how you measure it.

Well, yes, which is why they don't measure it your way, as it doesn't lead to discovering anything interesting about computation to have a shortcut like that. Or if they do it's part of a larger analysis, called an oracle machine.

I am against statements like:

A: "X people don't know how to do Y"

B: "Why not do Z?"

A: "Z is too easy and boring so they actually added more restrictions to how you are allowed to do Y so that solution doesn't count"

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

#112

Post by hcs »

charcircuit wrote: post #111
hcs wrote: post #84

Earlier quoted context omitted.

Well, yes, which is why they don't measure it your way, as it doesn't lead to discovering anything interesting about computation to have a shortcut like that. Or if they do it's part of a larger analysis, called an oracle machine.

I am against statements like: A: "X people don't know how to do Y" B: "Why not do Z?" A: "Z is too easy and boring so they actually added more restrictions to how you are allowed to do Y so that solution doesn't count"

Maybe I'm not communicating the point clearly. In order to use a table to do the whole multiplication it has to be much larger than the largest number you would want to multiply with it. A lot of the analysis of algorithms, especially multiplication as discussed here, is about astronomically large numbers, so you don't want the existence of an even more astronomically large table as a prerequisite.

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

#113

Post by numeri »

less_less wrote: post #80
SkiFire13 wrote: post #71

Earlier quoted context omitted.

> 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 base 5 then. It needs to go from -2 to +1 if you want base 4

It's still a modified base 4, because the significance of the i'th digit is 4^i, not 5^i. Edited to add: I'm also not sure whether real-life implementations have -0 as an option. Of course -0 could be normalized to +0, but it might be cheaper not to bother if the sign is applied after the digit selection.

No, balanced ternary, for example, uses {-1, 0, 1}. The system you're discussing is balanced quinary (base 5).

https://en.wikipedia.org/wiki/Signed-digit_representation

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

#114

Post by Bratmon »

inigyou wrote: post #86
wormslayer666 wrote: post #59

Earlier quoted context omitted.

A bit tangential, but the folks behind the GNU Multiple Precision Library (GMPLib) have the problem of choosing algorithms more or less fleshed out. They've got some fairly approachable manual pages[1] for the various algorithms they use as operand sizes scale up, where Karatsuba is only the second of six options in terms of operational complexity. [1] https://gmplib.org/manual/Multiplication-Algorithms

This really demonstrates the utility of pulling in a library written by experts in the field the library handles.

This is a problem I have a lot in modern programming ecosystems: How do I tell the difference between a library written by a team of experts who have spent decades optimizing everything to do with the task and a library written by one guy that's an unnecessary straightforward wrapper over the obvious implementation?

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

#115

Post by [deleted] »

Bratmon wrote: post #114
inigyou wrote: post #86

Earlier quoted context omitted.

This really demonstrates the utility of pulling in a library written by experts in the field the library handles.

This is a problem I have a lot in modern programming ecosystems: How do I tell the difference between a library written by a team of experts who have spent decades optimizing everything to do with the task and a library written by one guy that's an unnecessary straightforward wrapper over the obvious implementation?

[deleted]

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

#116

Post by dspillett »

Bratmon wrote: post #114
inigyou wrote: post #86

Earlier quoted context omitted.

This really demonstrates the utility of pulling in a library written by experts in the field the library handles.

This is a problem I have a lot in modern programming ecosystems: How do I tell the difference between a library written by a team of experts who have spent decades optimizing everything to do with the task and a library written by one guy that's an unnecessary straightforward wrapper over the obvious implementation?

Or increasingly, a library written by an LLM referencing a pile of such “one guy” projects of varying levels of suck (from actually good to good-got-it-is-full-of-suck).

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

#117

Post by layer8 »

Bratmon wrote: post #114
inigyou wrote: post #86

Earlier quoted context omitted.

This really demonstrates the utility of pulling in a library written by experts in the field the library handles.

This is a problem I have a lot in modern programming ecosystems: How do I tell the difference between a library written by a team of experts who have spent decades optimizing everything to do with the task and a library written by one guy that's an unnecessary straightforward wrapper over the obvious implementation?

You defer to the advice of experts you trust. Which somehow have become harder to come by in terms of signal to noise than 20-30 years ago.

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

#118

Post by layer8 »

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

The problem is that you also need multiplication to implement OCR.

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

#120

Post by layer8 »

morpheos137 wrote: post #106

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.

The article discusses how Python uses it for numbers above ~2100 bits for that reason. That’s way beyond your regular floating-point type in terms of precision.
Post reply on HN