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 : Why is DP FP so important for gpu running llr?

Author Message
dyost
Send message
Joined: 18 Sep 11
Posts: 32
ID: 112367
Credit: 351,699,002
RAC: 0
Eliminated 6 conjecture "k"s321 LLR Ruby: Earned 2,000,000 credits (4,353,688)PPS LLR Sapphire: Earned 20,000,000 credits (49,018,031)SoB LLR Silver: Earned 100,000 credits (253,910)SR5 LLR Jade: Earned 10,000,000 credits (16,031,979)Woodall LLR Bronze: Earned 10,000 credits (24,200)Cullen/Woodall Sieve (suspended) Silver: Earned 100,000 credits (383,381)PPS Sieve Double Bronze: Earned 100,000,000 credits (157,174,405)GFN Double Bronze: Earned 100,000,000 credits (105,119,278)PSA Jade: Earned 10,000,000 credits (19,390,897)
Message 70981 - Posted: 18 Nov 2013 | 6:16:04 UTC

I'm unclear on why dual precision floating point performance is so important for prime calculations on video cards. When I look at the LLR algorithms it seems it would be all done with integer math?

Can someone point me to what algorithms are being used with FP for finding primes?

Profile Michael GoetzProject donor
Volunteer moderator
Project administrator
Avatar
Send message
Joined: 21 Jan 10
Posts: 13631
ID: 53948
Credit: 278,264,389
RAC: 120,335
The "Shut up already!" badge:  This loud mouth has mansplained on the forums over 10 thousand times!  Sheesh!!!Discovered the World's First GFN-19 prime!!!Discovered 1 mega primeFound 1 prime in the 2018 Tour de PrimesFound 1 prime in the 2019 Tour de PrimesFound 1 prime in the 2020 Tour de PrimesFound 2 primes in the 2021 Tour de Primes321 LLR Turquoise: Earned 5,000,000 credits (5,132,712)Cullen LLR Ruby: Earned 2,000,000 credits (4,934,619)ESP LLR Turquoise: Earned 5,000,000 credits (5,107,300)Generalized Cullen/Woodall LLR Ruby: Earned 2,000,000 credits (2,145,754)PPS LLR Sapphire: Earned 20,000,000 credits (20,751,038)PSP LLR Turquoise: Earned 5,000,000 credits (5,197,957)SoB LLR Sapphire: Earned 20,000,000 credits (36,067,618)SR5 LLR Jade: Earned 10,000,000 credits (10,007,110)SGS LLR Ruby: Earned 2,000,000 credits (3,718,606)TRP LLR Turquoise: Earned 5,000,000 credits (5,084,329)Woodall LLR Ruby: Earned 2,000,000 credits (2,963,361)321 Sieve (suspended) Jade: Earned 10,000,000 credits (10,061,196)Cullen/Woodall Sieve (suspended) Ruby: Earned 2,000,000 credits (4,170,256)Generalized Cullen/Woodall Sieve (suspended) Turquoise: Earned 5,000,000 credits (5,059,304)PPS Sieve Sapphire: Earned 20,000,000 credits (22,885,121)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Amethyst: Earned 1,000,000 credits (1,035,522)TRP Sieve (suspended) Ruby: Earned 2,000,000 credits (2,051,121)AP 26/27 Jade: Earned 10,000,000 credits (10,118,303)WW Sapphire: Earned 20,000,000 credits (31,412,000)GFN Emerald: Earned 50,000,000 credits (77,916,132)PSA Jade: Earned 10,000,000 credits (12,445,029)
Message 70982 - Posted: 18 Nov 2013 | 12:34:29 UTC - in response to Message 70981.

I'm unclear on why dual precision floating point performance is so important for prime calculations on video cards. When I look at the LLR algorithms it seems it would be all done with integer math?

Can someone point me to what algorithms are being used with FP for finding primes?


The LLR, Genefer, and similar algorithms require repeatedly doing multiply operations on HUGE numbers.

Multiplying large integers is exceptionally time consuming if done the conventional, intuitive way (i.e., the long multiplication you learn in grammar school). There's a much faster method (hundreds or thousands of times faster) that uses FFTs (Fast Fourier Transforms) to do the multiplication, and doing an FFT uses floating point math. You can use single precision floating point, but then you need twice as many elements in the array used in the FFT, and that's a lot slower. So double precision math is significantly faster when running LLR.

(Genefer is a little different: Like LLR, it also uses FFTs to multiply large integers, but if you used single precision math, you would also be limited to much smaller b values, as well as being significantly slower.)

Read on for a more detailed explanation of grammar school vs. FFT multiplication...

Let's say you need to multiply two million-digit integers. In your head, you can only multiply one digit by one digit, and the computer can only do the same. To multiply those two numbers, you need to do a total of one million times one million (one trillion!) single digit multiplications. Even at computer speeds, repeating something a trillion times takes a long time.

For argument's sake, lets say that taking the FFT of one of those million digit numbers takes as long as doing 100 million one-digit mulitplications. Using the FFT method, you take the FFT of both million digit numbers. That takes 200 million multiplication times. Then, you multipy the individual "digits" in the transformed numbers together. That's one million multiplications. Finally, you take the inverse FFT (another 100 million multiplications) of the resulting number, and you get the result of the multiplication of the two original numbers. Total time using FFTs is 301 million multiplications, whereas the total time using grammar school math is 1,000,000 million multiplications (3300 times faster).

I like to think of it as putting an apple and some cranberries into a blender and making a smoothie. Then reverse the power plug and run the blender backwards for the exact same amount of time, which results in an intact cranapple.
____________
My lucky number is 75898524288+1

dyost
Send message
Joined: 18 Sep 11
Posts: 32
ID: 112367
Credit: 351,699,002
RAC: 0
Eliminated 6 conjecture "k"s321 LLR Ruby: Earned 2,000,000 credits (4,353,688)PPS LLR Sapphire: Earned 20,000,000 credits (49,018,031)SoB LLR Silver: Earned 100,000 credits (253,910)SR5 LLR Jade: Earned 10,000,000 credits (16,031,979)Woodall LLR Bronze: Earned 10,000 credits (24,200)Cullen/Woodall Sieve (suspended) Silver: Earned 100,000 credits (383,381)PPS Sieve Double Bronze: Earned 100,000,000 credits (157,174,405)GFN Double Bronze: Earned 100,000,000 credits (105,119,278)PSA Jade: Earned 10,000,000 credits (19,390,897)
Message 71017 - Posted: 19 Nov 2013 | 4:54:46 UTC - in response to Message 70982.

Thanks for your write up I have some mathin to do :)

Profile TheDawgzProject donor
Avatar
Send message
Joined: 7 Jul 08
Posts: 2235
ID: 25193
Credit: 594,681,706
RAC: 127,761
321 LLR Sapphire: Earned 20,000,000 credits (20,123,442)Cullen LLR Sapphire: Earned 20,000,000 credits (20,189,376)ESP LLR Sapphire: Earned 20,000,000 credits (20,115,673)Generalized Cullen/Woodall LLR Sapphire: Earned 20,000,000 credits (20,124,061)PPS LLR Emerald: Earned 50,000,000 credits (54,965,047)PSP LLR Sapphire: Earned 20,000,000 credits (20,339,896)SoB LLR Jade: Earned 10,000,000 credits (15,180,471)SR5 LLR Sapphire: Earned 20,000,000 credits (20,710,959)SGS LLR Jade: Earned 10,000,000 credits (10,404,749)TRP LLR Sapphire: Earned 20,000,000 credits (20,743,624)Woodall LLR Sapphire: Earned 20,000,000 credits (21,804,003)321 Sieve (suspended) Silver: Earned 100,000 credits (200,220)Cullen/Woodall Sieve (suspended) Turquoise: Earned 5,000,000 credits (6,710,149)Generalized Cullen/Woodall Sieve (suspended) Jade: Earned 10,000,000 credits (10,061,184)PPS Sieve Emerald: Earned 50,000,000 credits (57,182,910)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Ruby: Earned 2,000,000 credits (2,251,279)TRP Sieve (suspended) Ruby: Earned 2,000,000 credits (3,572,416)AP 26/27 Gold: Earned 500,000 credits (543,507)GFN Sapphire: Earned 20,000,000 credits (21,199,917)PSA Double Silver: Earned 200,000,000 credits (248,258,813)
Message 71024 - Posted: 19 Nov 2013 | 14:43:22 UTC

I like to think of it as putting an apple and some cranberries into a blender and making a smoothie. Then reverse the power plug and run the blender backwards for the exact same amount of time, which results in an intact cranapple.

Finally, an explanation of Fat Furry Transforms that TheDawgz can actually understand!!!
____________
There's someone in our head but it's not us.

Message boards : General discussion : Why is DP FP so important for gpu running llr?

[Return to PrimeGrid main page]
DNS Powered by DNSEXIT.COM
Copyright © 2005 - 2021 Rytis Slatkevičius (contact) and PrimeGrid community. Server load 4.68, 4.38, 4.10
Generated 13 Jun 2021 | 20:54:38 UTC