Join PrimeGrid
Returning Participants
Community
Leader Boards
Results
Other
drummerslowrise

Message boards :
General discussion :
Maths whiz solves 48yearold multiplication problem
Author 
Message 

From University of New South Wales: “Maths whiz solves 48yearold multiplication problem”
A UNSW Sydney mathematician has cracked a maths problem that has stood for almost half a century which will enable computers to multiply huge numbers together much more quickly.
... “More technically, we have proved a 1971 conjecture of Schönhage and Strassen about the complexity of integer multiplication,” Professor Harvey says.
____________
 

dukebgVolunteer tester
Send message
Joined: 21 Nov 17 Posts: 242 ID: 950482 Credit: 23,670,125 RAC: 0

As expected, the "news article" is pretty much useless, comparing to the "school" long multiplication while it wasn't the efficient thing to compare to since 1962.
Fortunately, clicking through the "source" links does get to the actual paper
https://hal.archivesouvertes.fr/hal02070778/document
And the actual paper does go into modern FFTbased algorithms.
Unfortunately, a lot of it is way over my head, though I did skim through it. I'm not sure how implementable (or theoretical) the new algorithm is.  

dukebgVolunteer tester
Send message
Joined: 21 Nov 17 Posts: 242 ID: 950482 Credit: 23,670,125 RAC: 0

Ah, an answer to my question is in the paper too.
All of the algorithms presented in this paper can be made completely explicit,
and all implied bigO constants are in principle effectively computable. On the other
hand, we make no attempt to minimise these constants or to otherwise exhibit a
practical multiplication algorithm. Our aim is to establish the theoretical O(n log n)
bound as directly as possible.  

Yves GallotVolunteer developer Project scientist Send message
Joined: 19 Aug 12 Posts: 712 ID: 164101 Credit: 305,166,630 RAC: 0

As expected, the "news article" is pretty much useless, comparing to the "school" long multiplication while it wasn't the efficient thing to compare to since 1962.
Fortunately, clicking through the "source" links does get to the actual paper
https://hal.archivesouvertes.fr/hal02070778/document
And the actual paper does go into modern FFTbased algorithms.
Unfortunately, a lot of it is way over my head, though I did skim through it. I'm not sure how implementable (or theoretical) the new algorithm is.
"FFTbased algorithms" can be replaced by a simple recursive algorithm.
See https://cr.yp.to/arith/tangentfft20070809.pdf, § 2.
P(x) mod x^2n  r^2 can easily be computed from P(x) mod x^n  r and P(x) mod x^n + r and vice versa.
The FFT is the same algorithm but it is not well written.
The polynomial form is practicable even if the number (or the degree of the polynomial) is small.
Gauss used it, that's why he is viewed as the discoverer of the FFT.
I don't understand why people are still using the FFT approach because it overshadows a simple algebraic method.
If you apply recursively the polynomial reduction you see that the complexity is O(n log n) operations.
But we have to compute the square root of 1 => 1, sqrt(1), .... and then a field in which these roots exist. It can't be the real numbers but we can use the complex numbers or some finite fields. In both cases we have to use a number of digits to evaluate the roots.
The complexity of this number of digits is O(log log n) with SchönhageStrassen method and with this paper it is O(1).
In practice, log log n is very small and is a sort of constant in our algorithms. A priori this paper should not improve practical algorithms.
But this is a huge theoretical step that will certainly be simplified and could generate some concrete algorithms.  


Wired Article: https://www.wired.com/story/mathematiciansdiscovertheperfectwaytomultiply/
EDIT:
And while the new algorithm is important theoretically, in practice it won’t change much, since it’s only marginally better than the algorithms already being used. “The best we can hope for is we’re three times faster,” van der Hoeven said. “It won’t be spectacular.”
I dunno  speeding up GFN 3x sounds pretty spectacular to me![/i]  

Dave Send message
Joined: 13 Feb 12 Posts: 3062 ID: 130544 Credit: 2,116,944,724 RAC: 1,481,201

Wired Article: https://www.wired.com/story/mathematiciansdiscovertheperfectwaytomultiply/
EDIT:
And while the new algorithm is important theoretically, in practice it won’t change much, since it’s only marginally better than the algorithms already being used. “The best we can hope for is we’re three times faster,” van der Hoeven said. “It won’t be spectacular.”
I dunno  speeding up GFN 3x sounds pretty spectacular to me![/i]
E.g would save 10 days on a GT1050 DYFL.  

Message boards :
General discussion :
Maths whiz solves 48yearold multiplication problem 