Join PrimeGrid
Returning Participants
Community
Leader Boards
Results
Other
drummerslowrise

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

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?  

Michael GoetzVolunteer moderator Project administrator
Send message
Joined: 21 Jan 10 Posts: 13631 ID: 53948 Credit: 278,264,389 RAC: 120,335

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 milliondigit 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 onedigit 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 75898^{524288}+1  


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


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? 