From: fcrary@rintintin.colorado.edu (Frank Crary) Subject: Re: Why Numerical Recipes in C stink Date: 16 Dec 1999 02:24:47 GMT Newsgroups: sci.math.num-analysis Keywords: FFT requires code length a power of 2? In article , wrote: >>Strictly speaking, fast fourier transforms only work for 2^k length >>arrays. The fact that Numerical Recipes doesn't provide code to handle >>arrays of other lengths isn't Press et al.'s fault; it is inherent to >>the technique. Code that does handle arrays of any length is really >>doing a mix of fast and slow fourier transforms, using the FFT approach >>to the extent that it can, and defaulting to slower techniques when >>it has to. >Strictly speaking, this is false. =) Nothing is special about the number >"2" in Cooley-Tukey FFT algorithms--it simply happens to be the smallest >number you can (usefully) divide a problem by, and hence radix-2 >implementations tend to be the simplest and most popular in textbooks. A >radix-3 Cooley-Tukey FFT algorithm is equally O(n lg n), and makes no use >of the radix-2 algorithm. I'm inclined to disagree with that, although it might be a matter of semantics and what we mean by ``FFT''. As I understand it, in the end, you have to do n log(n) calculations, and those calculations scale as m^2, where m is the factor you use. (E.g. m=2 in the example I used, m=3 in your example, etc., and I'll ignore the fact that you can use a mix of factors.) So, yes, you could do a radix-3 FFT, but it would be 9/4 times slower than a radix-2 FFT. Since FFT stands for ``Fast Fourier Transform,'' I'm not sure I'd call that a FFT. On the other hand, the techniques are very similar and the scaling is still n log(n), so other people might be quite happy calling that a FFT. Frank Crary CU Boulder ============================================================================== From: "E. Robert Tisdale" Subject: Re: Why Numerical Recipes in C stink Date: Thu, 16 Dec 1999 02:47:01 +0000 Newsgroups: sci.math.num-analysis Frank Crary wrote: > I'm inclined to disagree with that, > although it might be a matter of semantics > and what we mean by ``FFT''. As I understand it, > in the end, you have to do n log(n) calculations, > and those calculations scale as m^2, > where m is the factor you use. > (E.g. m=2 in the example I used, m=3 in your example, etc., > and I'll ignore the fact that you can use a mix of factors.) > So, yes, you could do a radix-3 FFT, > but it would be 9/4 times slower than a radix-2 FFT. > Since FFT stands for ``Fast Fourier Transform,'' > I'm not sure I'd call that a FFT. On the other hand, > the techniques are very similar and the scaling is still n log(n), > so other people might be quite happy calling that a FFT. No. A radix r FFT is r/lg(r) more complex than a radix 2 FFT. Take a look at The C++ Scalar, Vector, Matrix and Tensor class library at http://www.netwood.net/~edwin/svmt/ and read the document in .../svmt/doc/fft.pdf E. Robert Tisdale