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

71–80 of 152 posts

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

#71

Post by SkiFire13 »

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…

> 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

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

#72

Post by bmacho »

charcircuit wrote: post #69
bmacho wrote: post #50

Earlier quoted context omitted.

This would be the solution for any problem/algorithm, wouldn't it? Factorize big numbers, sort an array, beat stockfish at chess, create a SOTA microkernel OS from English description. All O(1) with lookup table! It's not how complexity works.

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

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

#73

Post by less_less »

WCSTombs wrote: post #53
zeroonetwothree wrote: post #37

Earlier quoted context omitted.

True but addition becomes a lot less efficient in this representation :)

To make both addition and multiplication O(n), you can store numbers as their residues modulo a bunch of different primes and appeal to the Chinese Remainder Theorem. However, then size comparison becomes difficult.

Residue number systems are really neat! They're sometimes used in crypto implementations, but there you're doing modular multiplication and in most cases the modular reduction then becomes costly, so it's not a free lunch. (Except in RSA and a few other cases. RSA-CRT gets you a "free" ~4x performance boost except it's more brittle to mistakes and side-channel / fault attacks.)

There's also NTT / Fourier multiplication as an option, for big integers or polynomials or modular arithmetic.

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

#74

Post by [deleted] »

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…

[deleted]

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

#75

Post by SkiFire13 »

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…

> If we're disregarding shifts and adds as completing in negligible time

When considering multiplication algorithms the parameter N is the number of digits of the two numbers. In that model adds do not complete in negligible time, and instead take O(N) time.

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

#76

Post by less_less »

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…

Yeah, that shift-and-add algorithm is sometimes used on microcontrollers, either in software if there's no hardware multiplier, or in hardware if you want the bare minimum in acceleration at a tiny cost in area.

Adds are not really considered negligible; the article is just sloppy. (Some shifts might be negligible in some models because a fixed shift requires no logic gates.) The cost of the adds in Karatsuba is significant both theoretically and in practice, and determines the cutoff where Karatsuba is useful. But the exponent in O(n^(log_2 3)) is dominated by the recursive multiplications; the adds only affect the leading constant hidden in the O().

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

#77

Post by SkiFire13 »

charcircuit wrote: post #68
hcs wrote: post #58

Earlier quoted context omitted.

An algorithm is a finite sequence of instructions, and so can't include an infinite table. More generally, https://en.wikipedia.org/wiki/Effective_method

I disagree. 1 step is a finite sequence of instructions.

The lookup table is part of the algorithm, and is not finite.

In general any problem can be solved in 1 step with a lookup table, so here you go P=NP solved.

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

#78

Post by less_less »

charcircuit wrote: post #39

How is it measured? A lookup table takes 1 step to find the answer of a multiplication.

The model usually measures in terms of fixed-size operations, e.g. 2-input binary gates. There's some variation in how to count memory lookups, but even in models where accessing a large memory counts as only one step, any tables present in the code still have to be fixed-size (except in models like P/poly, but even then they can't be exponential size).

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

#79

Post by kurlberg »

JoelJacobson wrote: post #43

Back in 2024, I was trying to optimize PostgreSQL's NUMERIC data type, which is base-10000, using Karatsuba. The problem of finding the optimal threshold of when to switch to Karatsuba turned out to be really hard, since it depends on the size of both factors combined. After some hundreds of hours, I gave up, and started thinking about if there could be a simpler solution. I came to think about another idea I'd had b…

It's complicated. :-)

There is a nice picture of the "best" choice for different ranges of sizes of numbers to be multiplied at http://gmplib.org/devel/log.i7.1024.png

More context and explanation can be found at: http://gmplib.org/devel/

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

#80

Post by less_less »

SkiFire13 wrote: post #71
less_less wrote: post #70

Earlier quoted context omitted.

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…

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

Post reply on HN