mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2002-08-24, 03:40   #1
Angular
 
Aug 2002

668 Posts
Default 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)
Angular is offline   Reply With Quote
Old 2002-08-24, 04:18   #2
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

23×7×137 Posts
Default 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.
Prime95 is online now   Reply With Quote
Old 2002-09-25, 10:31   #3
creative1
 
Sep 2002

22 Posts
Default 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
creative1 is offline   Reply With Quote
Old 2002-09-25, 16:38   #4
Angular
 
Aug 2002

5410 Posts
Default

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
Angular is offline   Reply With Quote
Old 2002-09-25, 20:14   #5
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

23×7×137 Posts
Default 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.
Prime95 is online now   Reply With Quote
Old 2002-09-25, 23:48   #6
ebx
 
ebx's Avatar
 
Aug 2002

101 Posts
Default

Ever thought about patent the algorithm?

Sorry cant resistant. Delt with too many patent issues lately.
ebx is offline   Reply With Quote
Old 2002-09-26, 00:13   #7
Deamiter
 
Deamiter's Avatar
 
Sep 2002

11101012 Posts
Default

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.
Deamiter is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 11:00.


Sat Nov 27 11:00:06 UTC 2021 up 127 days, 5:29, 0 users, load averages: 0.73, 0.90, 0.96

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.