PrimeGrid
Please visit donation page to help the project cover running costs for this month

Toggle Menu

Join PrimeGrid

Returning Participants

Community

Leader Boards

Results

Other

drummers-lowrise

Advanced search

Message boards : General discussion : Maths whiz solves 48-year-old multiplication problem

Author Message
Dr Who Fan
Avatar
Send message
Joined: 26 Sep 06
Posts: 87
ID: 3556
Credit: 9,409,758
RAC: 7,797
321 LLR Silver: Earned 100,000 credits (101,760)Cullen LLR Silver: Earned 100,000 credits (120,652)ESP LLR Silver: Earned 100,000 credits (102,526)Generalized Cullen/Woodall LLR Silver: Earned 100,000 credits (115,730)PPS LLR Silver: Earned 100,000 credits (381,233)PSP LLR Bronze: Earned 10,000 credits (98,948)SoB LLR Silver: Earned 100,000 credits (433,700)SR5 LLR Silver: Earned 100,000 credits (110,499)SGS LLR Silver: Earned 100,000 credits (119,477)TRP LLR Silver: Earned 100,000 credits (100,020)Woodall LLR Silver: Earned 100,000 credits (103,446)321 Sieve Amethyst: Earned 1,000,000 credits (1,026,536)Generalized Cullen/Woodall Sieve (suspended) Ruby: Earned 2,000,000 credits (2,740,001)PPS Sieve Ruby: Earned 2,000,000 credits (2,204,770)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Silver: Earned 100,000 credits (119,708)TRP Sieve (suspended) Gold: Earned 500,000 credits (527,925)AP 26/27 Silver: Earned 100,000 credits (129,458)GFN Gold: Earned 500,000 credits (858,977)
Message 128556 - Posted: 5 Apr 2019 | 7:15:15 UTC

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.

____________

dukebg
Volunteer tester
Avatar
Send message
Joined: 21 Nov 17
Posts: 235
ID: 950482
Credit: 22,083,013
RAC: 1
Found 1 prime in the 2018 Tour de Primes321 LLR Gold: Earned 500,000 credits (506,942)Cullen LLR Gold: Earned 500,000 credits (500,523)ESP LLR Gold: Earned 500,000 credits (655,642)Generalized Cullen/Woodall LLR Gold: Earned 500,000 credits (539,100)PPS LLR Gold: Earned 500,000 credits (688,232)PSP LLR Gold: Earned 500,000 credits (561,629)SoB LLR Ruby: Earned 2,000,000 credits (3,659,676)SR5 LLR Gold: Earned 500,000 credits (505,810)SGS LLR Gold: Earned 500,000 credits (506,024)TRP LLR Gold: Earned 500,000 credits (963,625)Woodall LLR Gold: Earned 500,000 credits (506,044)321 Sieve Gold: Earned 500,000 credits (511,694)Generalized Cullen/Woodall Sieve (suspended) Gold: Earned 500,000 credits (549,916)PPS Sieve Gold: Earned 500,000 credits (701,168)AP 26/27 Gold: Earned 500,000 credits (525,590)GFN Turquoise: Earned 5,000,000 credits (9,675,760)PSA Gold: Earned 500,000 credits (525,639)
Message 128559 - Posted: 5 Apr 2019 | 8:13:58 UTC

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.

dukebg
Volunteer tester
Avatar
Send message
Joined: 21 Nov 17
Posts: 235
ID: 950482
Credit: 22,083,013
RAC: 1
Found 1 prime in the 2018 Tour de Primes321 LLR Gold: Earned 500,000 credits (506,942)Cullen LLR Gold: Earned 500,000 credits (500,523)ESP LLR Gold: Earned 500,000 credits (655,642)Generalized Cullen/Woodall LLR Gold: Earned 500,000 credits (539,100)PPS LLR Gold: Earned 500,000 credits (688,232)PSP LLR Gold: Earned 500,000 credits (561,629)SoB LLR Ruby: Earned 2,000,000 credits (3,659,676)SR5 LLR Gold: Earned 500,000 credits (505,810)SGS LLR Gold: Earned 500,000 credits (506,024)TRP LLR Gold: Earned 500,000 credits (963,625)Woodall LLR Gold: Earned 500,000 credits (506,044)321 Sieve Gold: Earned 500,000 credits (511,694)Generalized Cullen/Woodall Sieve (suspended) Gold: Earned 500,000 credits (549,916)PPS Sieve Gold: Earned 500,000 credits (701,168)AP 26/27 Gold: Earned 500,000 credits (525,590)GFN Turquoise: Earned 5,000,000 credits (9,675,760)PSA Gold: Earned 500,000 credits (525,639)
Message 128561 - Posted: 5 Apr 2019 | 10:43:54 UTC

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 Gallot
Volunteer developer
Project scientist
Send message
Joined: 19 Aug 12
Posts: 518
ID: 164101
Credit: 297,100,702
RAC: 65,373
GFN Double Silver: Earned 200,000,000 credits (297,100,702)
Message 128562 - Posted: 5 Apr 2019 | 11:09:41 UTC - in response to Message 128559.

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.

Profile Doc NoProject donor
Avatar
Send message
Joined: 2 Jan 09
Posts: 132
ID: 33689
Credit: 607,086,314
RAC: 381,138
Discovered 3 mega primes321 LLR Ruby: Earned 2,000,000 credits (4,921,665)Cullen LLR Ruby: Earned 2,000,000 credits (2,917,119)ESP LLR Ruby: Earned 2,000,000 credits (2,517,704)Generalized Cullen/Woodall LLR Ruby: Earned 2,000,000 credits (4,717,201)PPS LLR Sapphire: Earned 20,000,000 credits (28,991,546)PSP LLR Jade: Earned 10,000,000 credits (10,362,000)SoB LLR Sapphire: Earned 20,000,000 credits (21,624,492)SR5 LLR Turquoise: Earned 5,000,000 credits (9,750,498)SGS LLR Ruby: Earned 2,000,000 credits (4,378,393)TRP LLR Ruby: Earned 2,000,000 credits (3,223,165)Woodall LLR Ruby: Earned 2,000,000 credits (4,254,369)Cullen/Woodall Sieve (suspended) Silver: Earned 100,000 credits (360,397)Generalized Cullen/Woodall Sieve (suspended) Ruby: Earned 2,000,000 credits (4,801,060)PPS Sieve Emerald: Earned 50,000,000 credits (71,366,461)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Ruby: Earned 2,000,000 credits (4,364,469)TRP Sieve (suspended) Turquoise: Earned 5,000,000 credits (5,845,234)AP 26/27 Turquoise: Earned 5,000,000 credits (5,486,351)GFN Double Silver: Earned 200,000,000 credits (416,953,870)PSA Silver: Earned 100,000 credits (246,526)
Message 128855 - Posted: 18 Apr 2019 | 20:32:29 UTC
Last modified: 18 Apr 2019 | 20:39:10 UTC

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]

Profile DaveProject donor
Avatar
Send message
Joined: 13 Feb 12
Posts: 2554
ID: 130544
Credit: 796,555,978
RAC: 554,239
Found 2 primes in the 2018 Tour de Primes321 LLR Turquoise: Earned 5,000,000 credits (5,008,573)Cullen LLR Turquoise: Earned 5,000,000 credits (5,005,909)ESP LLR Turquoise: Earned 5,000,000 credits (5,303,526)Generalized Cullen/Woodall LLR Turquoise: Earned 5,000,000 credits (5,202,873)PPS LLR Turquoise: Earned 5,000,000 credits (5,304,786)PSP LLR Turquoise: Earned 5,000,000 credits (5,021,564)SoB LLR Turquoise: Earned 5,000,000 credits (8,851,996)SR5 LLR Turquoise: Earned 5,000,000 credits (5,000,482)SGS LLR Ruby: Earned 2,000,000 credits (4,897,497)TRP LLR Ruby: Earned 2,000,000 credits (3,501,055)Woodall LLR Ruby: Earned 2,000,000 credits (3,007,050)321 Sieve Ruby: Earned 2,000,000 credits (2,206,564)Cullen/Woodall Sieve (suspended) Silver: Earned 100,000 credits (268,250)Generalized Cullen/Woodall Sieve (suspended) Jade: Earned 10,000,000 credits (10,000,502)PPS Sieve Double Silver: Earned 200,000,000 credits (300,002,145)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Jade: Earned 10,000,000 credits (10,000,133)TRP Sieve (suspended) Jade: Earned 10,000,000 credits (10,000,970)AP 26/27 Double Bronze: Earned 100,000,000 credits (107,972,358)GFN Double Bronze: Earned 100,000,000 credits (100,000,025)PSA Double Silver: Earned 200,000,000 credits (200,000,001)
Message 128859 - Posted: 18 Apr 2019 | 21:55:01 UTC - in response to Message 128855.

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.

Post to thread

Message boards : General discussion : Maths whiz solves 48-year-old multiplication problem

[Return to PrimeGrid main page]
DNS Powered by DNSEXIT.COM
Copyright © 2005 - 2019 Rytis Slatkevičius (contact) and PrimeGrid community. Server load 1.47, 1.31, 1.44
Generated 24 Sep 2019 | 9:29:33 UTC