Mathematicians Discover the Perfect Way to Multiply

https://www.quantamagazine.org/mathematicians-discover-the-perfect-way-to-multiply-20190411/

by pseudolus • 7 years ago

31 12 7 years ago

quantamagazine.org

pseudolus• 7 years ago

Here's a link to the actual paper:

https://hal.archives-ouvertes.fr/hal-02070778/document (PDF)

amichail• 7 years ago

The second author is the creator of TeXmacs btw.

hannob• 7 years ago

The title is a bit misleading, though they do explain it in the text.

It seems they cannot show right now that this is the perfect way to multiply. It's faster than any previously existing way and they hope to be able to proove in the future that there is no faster way.

I found this interesting because coming from cryptography I know that it's very hard to have any lower bounds for algorithm speed. Which is why we can't have provably secure cryptography (yet?).

lower• 7 years ago

Previous discussion:

https://news.ycombinator.com/item?id=19474280

spuz• 7 years ago

Previous discussion: https://news.ycombinator.com/item?id=19474280

rollthehard6• 7 years ago

Q - how do you multiply something like 25x63 example in your head? Personally, I'd break that down also, by doing -

5 x 63 = 315 x 5 = 1575

reminds me a little of the Feynman story about his duel with the abacus master. https://news.ycombinator.com/item?id=5849665

docdeek• 7 years ago

For that example I would be thinking 60 x 25 = 1500 (4 x 25=100, so that's the simple part for me) and then 3 x 25 = 75, and add the two products.

soVeryTired• 7 years ago

In general I find mental arithmetic like this easiest if you start from the most significant digits. So you just need to keep track of a running sum and which multiplications you still need to add.

Here's the calculation as I would do it in my head, more or less:

25 * 63 = (20 + 5) * (60 * 3)

= (20 * 60) + (5 * 60) + (3 * 20) + (5 * 3)

= 1200 + (5 * 60) + (3 * 20) + (5 * 3)

= 1500 + (3 * 20) + (5 * 3)

= 1560 + (5 * 3)

= 1575

flashgordon• 7 years ago

If division can be involved, why not:

= ((25 * 4) * 63) /4

= 100 * 63 /4

= 6300 / 4

= (6400 - 100) / 4

= 1600 - 25

= 1575

JustSomeNobody• 7 years ago

25 X 63

25 X 6 X 10 = 1500

25 X 3 = 75

1500 + 75

1575

This is easier for me to do in my head than juggle as many steps as the "perfect way"

rawwar• 7 years ago

Aren't algorithms for multiplying integers in O(n log n) using DFT known for a long time (eg. Cooley-Tukey)?

eesmith• 7 years ago

According to the article, Schönhage and Strassen introduced the use of fast Fourier transform to integer multiplication in 1971, giving n × log n × log(log n). "The technique has been the basis for every fast multiplication algorithm since."

"Over the past decade, mathematicians have found successively faster multiplication algorithms, each of which has inched closer to n × log n, without quite reaching it. Then last month, Harvey and van der Hoeven got there."

Mathematicians Discover the Perfect Way to Multiply

Related Stories