Join PrimeGrid
Returning Participants
Community
Leader Boards
Results
Other
drummers-lowrise
|
Message boards :
General discussion :
Maths whiz solves 48-year-old multiplication problem
| Author |
Message |
|---|
|
|
|
From University of New South Wales: “Maths whiz solves 48-year-old 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.archives-ouvertes.fr/hal-02070778/document
And the actual paper does go into modern FFT-based 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 big-O 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.archives-ouvertes.fr/hal-02070778/document
And the actual paper does go into modern FFT-based 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.
"FFT-based algorithms" can be replaced by a simple recursive algorithm.
See https://cr.yp.to/arith/tangentfft-20070809.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önhage-Strassen 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/mathematicians-discover-the-perfect-way-to-multiply/
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/mathematicians-discover-the-perfect-way-to-multiply/
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 48-year-old multiplication problem |
