Mathematicians discover the perfect way to multiply (2019) | Hacker News Reader

Mathematicians discover the perfect way to multiply (2019)

quantamagazine.org

113 pointsgalaxyLogic33 comments

It's from 2019 and discussed several times before.

https://hn.algolia.com/?query=Mathematicians%20Discover%20th... shows about 175 comments, cumulative, with https://news.ycombinator.com/item?id=23919869 having 94.

Yeah, it looks like this article is getting written now due to the result being formally published.

Year added above. Thanks!

Related past threads:

Mathematicians Discover the Perfect Way to Multiply - https://news.ycombinator.com/item?id=28579007 - Sept 2021 (2 comments)

Mathematicians discover a perfect way to multiply (2019) - https://news.ycombinator.com/item?id=23919869 - July 2020 (94 comments)

Mathematicians Discover the Perfect Way to Multiply - https://news.ycombinator.com/item?id=19672835 - April 2019 (68 comments)

Mathematicians Discover the Perfect Way to Multiply - https://news.ycombinator.com/item?id=19644374 - April 2019 (12 comments)

Integer multiplication in time O(n log n) [pdf] - https://news.ycombinator.com/item?id=19474280 - March 2019 (67 comments)

Didn’t see details of the actual method other than it is based on fast Fourier transforms. Would be cool to see a breakdown like they did for the carrying and Karatsuba methods or better yet some code.

Paper is here:

https://hal.archives-ouvertes.fr/hal-02070778v2/document

(I just googled the authors' names).

They should have just written the code, patented it, and taken a gaggle of VCs to the cleaners.

It has almost no practical use. It's a galactic algorithm. See https://mattermodeling.stackexchange.com/q/1355/243

Could you pack a bunch of different numbers in one big one, in such a way that multiplying them was equivalent to doing a layer in a machine learning model?

Since 10x10 goes in the hundreds bucket, along with 100x1 as long as nothing overflows.

Technically, it's not known if it's a galactic algorithm. The author of the paper has said that he thinks it might be competitive with Fürer with some minor tweaks.

The algorithm isn't (likely) to be faster for problems that people actually have. It scales better, so it's faster than older algorithms for large enough numbers, but the numbers would have to be absurdly large, beyond what anybody is likely to need anytime soon, if ever, for the algorithm to be useful.

Classic HN comment. Fundamentally misunderstands complexity theory, and considers the objective function of scientific progress to be the obtainment of VC cash.

Well, you could buy a bunch of scientific progress by transferring some money from the rich to the smart.

Until the merely clever discover that among the rich number many who are not anywhere near smart. Then everybody gets cagey and butthurt after the clever get rich. Science plods along, budgets mostly unchanged.

I interpreted it as a tongue in cheek "we've discovered [thing] give us money" the some VC funds seem more than happy to throw money at

Also, fundamentally misunderstands the patent system...

I've expanded out the Karatsuba method to prove it to myself that it works for any (10a+b)(10c+d). I can highly recommend.

You're not alone. (10a+b)(10c+d) = 100ac+10(ad+bc)+bd = 100ac+10(ac+ad+bc+bd-ac-bd)+bd = 100ac+10[(a+b)(c+d)-ac-bd]+bd. Quite pleasing, aesthetically.

Having heard as a kid that "cells multiply by division" left me permanently confused.

There is something very deep about that

i was scarred by i = i + 1. How can 2 equal 3?

Title is inaccurate. The authors discovered (in 2019) an n log n algorithm for multiplication, but didn't prove n log n was optimal.

This point is discussed in the article. And since the FFT is n log n, any faster algorithm would have to be completely different.

The article points out why n log n is optimal from information theory lower bounds.

I get the Quanta is pretty popular around here and runs some good articles, but their headlines are so clickbaity.

> Four thousand years ago, the Babylonians invented multiplication

Invented… or discovered?

Well, mathematics wasn't discovered, so regardless of what the right word is, it isn't "discovered".

That is really a philosophical question.

This is the kind of thing that you can really overthink. I would just say it is whatever people call it.

Most people would intuitively say "invent" rather than "discover" so that's what it is. Words are defined by their usage. If that results in a strange and unsatisfying definition then so be it.

I disagree, mathematics is 100% discovered. It's not like we humans are inventing it ourselves.

Wolfram seems (to me) to say that he can show that math is some strange combination of invented (or rather, sensed) and discovered.

https://writings.stephenwolfram.com/2022/03/the-physicalizat...

Think of algorithmic theorem provers. They search the space of possible logical conclusions and in that manner find proofs. Thus they discover proofs, they discover mathematics.

But really I don't know what the difference between discovering and inventing is? You discover that something works, call it an invention. What else is invention than discovery?

Is there some sort of equivalent for division?

Division can (up to a multiplicative constant, which by definition does not matter for O(...)) be reduced to multiplication:

> https://en.wikipedia.org/w/index.php?title=Division_algorith...

Reply on news.ycombinator.com