Mathematicians Discover the Perfect Way to Multiply | Hacker News Reader

Mathematicians Discover the Perfect Way to Multiply

quantamagazine.org

31 pointspseudolus12 comments

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

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

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

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.

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

If division can be involved, why not:

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

= 100 * 63 /4

= 6300 / 4

= (6400 - 100) / 4

= 1600 - 25

= 1575

Here's a link to the actual paper:

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

The second author is the creator of TeXmacs btw.

Previous discussion:

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

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

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

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"

Reply on news.ycombinator.com