[HN Gopher] Mathematicians discover the perfect way to multiply ...
___________________________________________________________________
Mathematicians discover the perfect way to multiply (2019)
Author : galaxyLogic
Score : 46 points
Date : 2022-03-08 21:12 UTC (1 hours ago)
(HTM) web link (www.quantamagazine.org)
(TXT) w3m dump (www.quantamagazine.org)
| scarmig wrote:
| 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 wrote:
| This point is discussed in the article. And since the FFT is n
| log n, any faster algorithm would have to be completely
| different.
| Koshkin wrote:
| Having heard as a kid that "cells multiply by division" left me
| permanently confused.
| memco wrote:
| 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 wrote:
| They should have just written the code, patented it, and taken
| a gaggle of VCs to the cleaners.
| Qem wrote:
| It has almost no practical use. It's a galactic algorithm.
| See https://mattermodeling.stackexchange.com/q/1355/243
| doobop wrote:
| 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.
| titzer wrote:
| Paper is here:
|
| https://hal.archives-ouvertes.fr/hal-02070778v2/document
|
| (I just googled the authors' names).
| [deleted]
| jw1224 wrote:
| > Four thousand years ago, the Babylonians invented
| multiplication
|
| Invented... or discovered?
| btdmaster wrote:
| 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.
| dalke wrote:
| 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.
| dang wrote:
| 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)
| Sniffnoy wrote:
| Yeah, it looks like this article is getting written now due to
| the result being formally published.
___________________________________________________________________
(page generated 2022-03-08 23:00 UTC)