Forums

mixed radix fft (radix 2 and radix 5)

Started by Jenny September 18, 2003
I am looking for a mixed radix 2 and 5 fft algorithm in C. I have
download some algorithm from www.fftw.com but don't know how to
install it(I am using windows XP not unix). Basically I have to do a
10, 100, 1000,... fft by using mixed radix(2,5)algorithm. Does anyone
can give me some information about the algorithm? Where can I
download?

Thanks!

Jenny
qiuping18@hotmail.com (Jenny)...
> I am looking for a mixed radix 2 and 5 fft algorithm in C. I have > download some algorithm from www.fftw.com but don't know how to > install it(I am using windows XP not unix). Basically I have to do a > 10, 100, 1000,... fft by using mixed radix(2,5)algorithm. Does anyone > can give me some information about the algorithm? Where can I > download?
(It sounds like you are looking for an implementation, not an algorithm, but I digress. Also, fftw.com is an investment firm; you mean fftw.org, I think.) We don't use Windows ourselves, but you can download Windows installation instructions, as well as precompiled binaries, from our web page (www.fftw.org/install/windows.html). Alternatively, there are a few other C codes that handle mixed factorizations and are available online. See our benchmark (www.fftw.org/speed) for the different codes that we compare for non-powers-of-two (links at http://www.fftw.org/benchfft/ffts.html). Cordially, Steven G. Johnson
qiuping18@hotmail.com (Jenny) wrote in message news:<a4d3198d.0309172330.3cb63028@posting.google.com>...
> I am looking for a mixed radix 2 and 5 fft algorithm in C. I have > download some algorithm from www.fftw.com but don't know how to > install it(I am using windows XP not unix). Basically I have to do a > 10, 100, 1000,... fft by using mixed radix(2,5)algorithm. Does anyone > can give me some information about the algorithm? Where can I > download? > > Thanks! > > Jenny
An algorithm of the type you are looking for is in netlib. Try at http://gams.nist.gov or google for "Clive Temperton" who did the work on which the radix 2,3,5 algorithms I know are based. If you cannot find anything I could mail a variant of the netlib code (my mail adress is "spammable"). (note: in part f2c converted code, not extremely legible but works - minor modifications to the type declarations might be necessary for Visual C++ because I use it with gcc on windows) Sorry, I don't like/use fftw and cannot assist with the implementation. Robert
Robert Malek wrote:
> > Sorry, I don't like/use fftw and cannot assist with the > implementation.
I'm curious. What is your objection to FFTW? Erik -- +-----------------------------------------------------------+ Erik de Castro Lopo nospam@mega-nerd.com (Yes it's valid) +-----------------------------------------------------------+ Microsoft is not the answer. Microsoft is the question. NO is the answer.
yeren@gmx.de (Robert Malek) wrote...
> Try at http://gams.nist.gov > or google for "Clive Temperton" who did the work on which the radix > 2,3,5 algorithms I know are based.
Actually, the oldest mixed-radix algorithm is by Gauss (and Cooley and Tukey also described the mixed-radix case, and even thought that the optimal radix was 3!). The earliest mixed-radix source code I can think of offhand is by Singleton in 1968 (code is still available at netlib). Of course, you may be referring to the "GPFA" code by Temperton, which uses a mixture of the Cooley-Tukey algorithm and the Prime-Factor (Good-Thomas) algorithm if I recall correctly, rather than "straight" mixed-radix Cooley-Tukey. (Prime-Factor only works for factors that are relatively prime, e.g. to separate all of the powers of two from all of the powers of 3.) Usually, I find FFTPACK to be faster than the GPFA code (see our benchmarks), though. (All of these codes are in Fortran, which is why I didn't mention them in my earlier posting. Of course, if you are willing to use f2c...) Steven
> I'm curious. What is your objection to FFTW?
To tell the truth: I think it is too complex and big a package for my purposes. With a piece of sourcecode I don't need to "install" some package for different platforms. Robert