Prime95's FFT Algorithm

Angular · 2002-08-24, 03:40

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)

Prime95 · 2002-08-24, 04:18

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.

creative1 · 2002-09-25, 10:31

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

Angular · 2002-09-25, 16:38

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

Prime95 · 2002-09-25, 20:14

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.

ebx · 2002-09-25, 23:48

Ever thought about patent the algorithm?

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

Deamiter · 2002-09-26, 00:13

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.

2002-08-24, 03:40	#1
Angular Aug 2002 2·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 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-09-25, 10:31	#3
creative1 Sep 2002 4₈ 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

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Possible better multiplication algorithm	Triber	Computer Science & Computational Number Theory	17	2015-11-10 17:48
Polynomial algorithm	diep	Factoring	7	2012-09-29 12:09
TF algorithm(s)	davieddy	Miscellaneous Math	61	2011-07-06 20:13
Shor's Algorithm	flouran	Math	3	2009-10-27 09:31
New Multiplication Algorithm	vector	Miscellaneous Math	10	2007-12-20 18:16

2002-09-25, 16:38	#4
Angular Aug 2002 2×3³ 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, 23:48	#6
ebx Aug 2002 101 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 3²·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.