20020824, 03:40  #1 
Aug 2002
2×3^{3} Posts 
Prime95's FFT Algorithm
I am curious as to which FFT algorithm Prime95 uses. The GIMPs math page discusses FFTs in a very general context.
A 1994 MOC paper by Crandell and Fagin is also referenced. It appears to be praising the DWT eliminate the need for padding the bits of numbers before processing. The article recommends splitradix FFTs. This contradicts what Yves Gallot writes in this paper. Yves reports that 'Four Step' FFTs are much more efficient since the Memory access needed may be minimized. Is this the case for Mersenne Primes and the algorithm you chose? Can the boundary of floating point FFTs be extended by smart rounding techniques? Or are the rounding errors hard to predict? (i.e. if error ~0.5 then round up when approaching boundary and otherwise round down like normal) 
20020824, 04:18  #2  
P90 years forever!
Aug 2002
Yeehaw, FL
2^{2}×1,873 Posts 
Re: Prime95's FFT Algorithm
Quote:
And yes, prime95 uses something similar to the fourstep FFT. Now, what do you mean by "smart rounding"? I just let the Intel FPU do rounding. 

20020925, 10:31  #3 
Sep 2002
2^{2} Posts 
the prime95 algorithm
yep, i couldnt find any explanation about the prime95 algorithm either
is there any paper explaining exaclty what is done? i can only find links to tons of papers and each of them talks about a dif algorithm if we know which is the algorithm that prime95 uses (which is the faster one on pcs) we might try to find something better researching... but at this time i can´t find the exact explanation for what is used on prime95 the best i could find was: prime95 uses a variant of X algorithm which doesn´t help... what is the variant? details guys details :( Creative1 
20020925, 16:38  #4 
Aug 2002
66_{8} Posts 
George,
When I said smart rounding, I mistakenly though that it was possible to determine that the result of the round should be the floor or the ceiling of (x+0.5). I know understand the algorithm better and realize that the rounding is done thousands of times and it is not possible to predict. Michael 
20020925, 20:14  #5  
P90 years forever!
Aug 2002
Yeehaw, FL
2^{2}×1,873 Posts 
Re: the prime95 algorithm
Quote:


20020925, 23:48  #6 
Aug 2002
1100101_{2} Posts 
Ever thought about patent the algorithm?
Sorry cant resistant. Delt with too many patent issues lately. 
20020926, 00:13  #7 
Sep 2002
3^{2}×13 Posts 
The prime95 program (which is copywrited) contains the algorithm and there is enough (!) documentation that George came up with it to prove it in court. The only reason that you'd want a patent on the FFT Algorithm would be to profit of it yourself as any later patent would have to establish that they created and patented the code BEFORE p95 in order to win a suit against George.

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Possible better multiplication algorithm  Triber  Computer Science & Computational Number Theory  17  20151110 17:48 
Polynomial algorithm  diep  Factoring  7  20120929 12:09 
TF algorithm(s)  davieddy  Miscellaneous Math  61  20110706 20:13 
Shor's Algorithm  flouran  Math  3  20091027 09:31 
New Multiplication Algorithm  vector  Miscellaneous Math  10  20071220 18:16 