mersenneforum.org > Math Prime95's FFT Algorithm
 Register FAQ Search Today's Posts Mark Forums Read

 2002-08-24, 03:40 #1 Angular   Aug 2002 2×33 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 split-radix 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)
2002-08-24, 04:18   #2
Prime95
P90 years forever!

Aug 2002
Yeehaw, FL

22×1,873 Posts
Re: Prime95's FFT Algorithm

Quote:
 Originally Posted by 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)
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.

 2002-09-25, 10:31 #3 creative1   Sep 2002 22 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
 2002-09-25, 16:38 #4 Angular   Aug 2002 668 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
2002-09-25, 20:14   #5
Prime95
P90 years forever!

Aug 2002
Yeehaw, FL

22×1,873 Posts
Re: the prime95 algorithm

Quote:
 Originally Posted by creative1 yep, i couldnt find any explanation about the prime95 algorithm either is there any paper explaining exaclty what is done?
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.

 2002-09-25, 23:48 #6 ebx     Aug 2002 11001012 Posts Ever thought about patent the algorithm? Sorry cant resistant. Delt with too many patent issues lately.
 2002-09-26, 00:13 #7 Deamiter     Sep 2002 32×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.

 Similar Threads Thread Thread Starter Forum Replies Last Post Triber Computer Science & Computational Number Theory 17 2015-11-10 17:48 diep Factoring 7 2012-09-29 12:09 davieddy Miscellaneous Math 61 2011-07-06 20:13 flouran Math 3 2009-10-27 09:31 vector Miscellaneous Math 10 2007-12-20 18:16

All times are UTC. The time now is 23:57.

Tue May 18 23:57:24 UTC 2021 up 40 days, 18:38, 0 users, load averages: 1.34, 1.31, 1.39