Prime95's FFT Algorithm
 

I am curious as to which FFT algorithm Prime95 uses. The GIMPs [url=http://www.mersenne.org/math.htm]math page[/url] 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 split-radix FFTs. This contradicts what Yves Gallot writes in [url=http://perso.wanadoo.fr/yves.gallot/papers/weight.html]this paper[/url]. 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)

Re: Prime95's FFT Algorithm
 

[quote="Angular"]The article recommends split-radix FFTs. 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)[/quote]

Yves is correct. All "old" FFT papers that count multiply and add instructions are useless. For a large FFT, the most important factor is reducing memory fetches. On my P4, it can do one floating add and mul per clock cycle, but a fetch from main memory is ~300 clocks. Even with prefetching, you can see that memory access patterns dwarf mul and add operations.

And yes, prime95 uses something similar to the four-step FFT.

Now, what do you mean by "smart rounding"? I just let the Intel FPU do rounding.

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

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

Re: the prime95 algorithm
 

[quote="creative1"]yep, i couldnt find any explanation about the prime95 algorithm either
is there any paper explaining exaclty what is done?
[/quote]

Sorry, no papers are available. I'm not even well enough versed in the FFT terminology (DIF, DIT, four-step, split-radix, butterflies, radix-2, radix-4, radix-8, scrambling, twiddle factors, Cooley-Tukey, and on and on) to tell you exactly what the prime95 FFT algorihtm is. Prime95's FFT may actually defy a label - containing a blend of ideas from many sources.

Ever thought about patent the algorithm?

Sorry cant resistant. Delt with too many patent issues lately.

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.