HN Explorer

36 comments

[ 3.1 ms ] story [ 61.4 ms ] thread
memco
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.
datavirtue
They should have just written the code, patented it, and taken a gaggle of VCs to the cleaners.
Qem
It has almost no practical use. It's a galactic algorithm. See https://mattermodeling.stackexchange.com/q/1355/243
eternityforest
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.

adgjlsfhk1
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.
doobop
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.
DC-3
Classic HN comment. Fundamentally misunderstands complexity theory, and considers the objective function of scientific progress to be the obtainment of VC cash.
mhh__
Well, you could buy a bunch of scientific progress by transferring some money from the rich to the smart.
robbedpeter
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.
olliej
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
klyrs
Also, fundamentally misunderstands the patent system...
[deleted]
(comment deleted)
dalke
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.

Sniffnoy
Yeah, it looks like this article is getting written now due to the result being formally published.
dang
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)

scarmig
Title is inaccurate. The authors discovered (in 2019) an n log n algorithm for multiplication, but didn't prove n log n was optimal.
not2b
This point is discussed in the article. And since the FFT is n log n, any faster algorithm would have to be completely different.
ChrisLomont
The article points out why n log n is optimal from information theory lower bounds.
Koshkin
Having heard as a kid that "cells multiply by division" left me permanently confused.
[deleted]
(comment deleted)
yread
i was scarred by i = i + 1. How can 2 equal 3?
btdmaster
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.
dhosek
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.
jw1224
> Four thousand years ago, the Babylonians invented multiplication

Invented… or discovered?

lal
Well, mathematics wasn't discovered, so regardless of what the right word is, it isn't "discovered".
quickthrower2
That is really a philosophical question.
Asraelite
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.

galaxyLogic
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?

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