4 ms·
Mathematicians discover the perfect way to multiply (2019)
- memco 5y agoDidn’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.
- titzer 5y agoPaper is here: https://hal.archives-ouvertes.fr/hal-02070778v2/document https://hal.archives-ouvertes.fr/hal-02070778v2/document (I just googled the authors' names).
- datavirtue 5y agoThey should have just written the code, patented it, and taken a gaggle of VCs to the cleaners.
- Qem 5y agoIt has almost no practical use. It's a galactic algorithm. See https://mattermodeling.stackexchange.com/q/1355/243 https://mattermodeling.stackexchange.com/q/1355/243
- eternityforest 5y agoCould 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 5y agoTechnically, 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 5y agoThe 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 5y agoClassic HN comment. Fundamentally misunderstands complexity theory, and considers the objective function of scientific progress to be the obtainment of VC cash.
- mhh__ 5y agoWell, you could buy a bunch of scientific progress by transferring some money from the rich to the smart.
- robbedpeter 5y agoUntil 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 5y agoI 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 5y agoAlso, fundamentally misunderstands the patent system...
- deleted 5y ago[deleted]
- dalke 5y agoIt's from 2019 and discussed several times before. https://hn.algolia.com/?query=Mathematicians%20Discover%20the%20Perfect%20Way%20to%20Multiply&type=story&dateRange=all&sort=byDate&storyText=false&prefix&page=0 https://hn.algolia.com/?query=Mathematicians%20Discover%20th... shows about 175 comments, cumulative, with https://news.ycombinator.com/item?id=23919869 https://news.ycombinator.com/item?id=23919869 having 94.
- Sniffnoy 5y agoYeah, it looks like this article is getting written now due to the result being formally published.
- dang 5y agoYear added above. Thanks! Related past threads: Mathematicians Discover the Perfect Way to Multiply - https://news.ycombinator.com/item?id=28579007 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 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 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 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 https://news.ycombinator.com/item?id=19474280 - March 2019 (67 comments)
- scarmig 5y agoTitle is inaccurate. The authors discovered (in 2019) an n log n algorithm for multiplication, but didn't prove n log n was optimal.
- not2b 5y agoThis point is discussed in the article. And since the FFT is n log n, any faster algorithm would have to be completely different.
- ChrisLomont 5y agoThe article points out why n log n is optimal from information theory lower bounds.
- Koshkin 5y agoHaving heard as a kid that "cells multiply by division" left me permanently confused.
- deleted 5y ago[deleted]
- galaxyLogic 5y agoThere is something very deep about that
- yread 5y agoi was scarred by i = i + 1. How can 2 equal 3?
- btdmaster 5y agoI'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 5y agoYou'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 5y ago> Four thousand years ago, the Babylonians invented multiplication Invented… or discovered?
- lal 5y agoWell, mathematics wasn't discovered, so regardless of what the right word is, it isn't "discovered".
- quickthrower2 5y agoThat is really a philosophical question.
- Asraelite 5y agoThis 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.
- loxias 5y agoI disagree, mathematics is 100% discovered. It's not like we humans are inventing it ourselves.
- anamax 5y agoWolfram 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-physicalization-of-metamathematics-and-its-implications-for-the-foundations-of-mathematics/ https://writings.stephenwolfram.com/2022/03/the-physicalizat...
- throwaway_1928 5y ago
- 5y ago
- bee_rider 5y agoI get the Quanta is pretty popular around here and runs some good articles, but their headlines are so clickbaity.
- justbaker 5y agoIs there some sort of equivalent for division?
- q-big 5y agoDivision 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_algorithm&oldid=1074526636#Large-integer_methods https://en.wikipedia.org/w/index.php?title=Division_algorith...