Re: FFT for N Not a Power of 2

Bill Davy wrote:
"Phil Hobbs" <pcdhSpamMeSenseless@xxxxxxxxxxxxxxxxxx> wrote in message news:4922B772.7090503@xxxxxxxxxxxxxxxxxxxxx
W. eWatson wrote:
It would seem that the FFT is applicable to only data with a number of observations that are a power of 2. Is that correct? If so, does one only remove the largest number of observations that are a power of 2, while ignoring the remainder?
No.

There are FFT algorithms that work for any N, including prime numbers, but they're a few times less efficient than radix-2 FFTs.


Not sure that's right. I have a feeling that radix 4 and perhaps radix 8 are more efficient than radix 2 and that some transforms (I seem recall one by Singleton in an IEEE publication) used large factors. And somewhere there is a program that will generate an efficient FFT program for a specified number. Of course, if it's a prime, you're stuffed.


You're only stuffed if you're Tukey. ;) The fast algorithsm for prime N iiuc involve taking two different chirp-Z transforms in a row, but they're still N log N algorithms, like the Cooley-Tukey and Sande-Tukey algorithms. It's true that the quicker FFTs, e.g. FFTW don't use a pure radix-2 approach--but it sounds as though the OP is trying to understand FFT spectral estimation. Misapplied FFTs are famous for generating reasonable-looking wrong answers, so becoming clear on what's actually going on is the first order of business.


Cheers,

Phil Hobbs
.

Relevant Pages

  • Re: FFT
    ... N an integral power of two, since those algorithms are by far the easiest. ... accurate FFT. ...
    (microsoft.public.dotnet.general)
  • Re: FFT for N Not a Power of 2
    ... remove the largest number of observations that are a power of 2, ... There are FFT algorithms that work for any N, including prime numbers, but ... I have a feeling that radix 4 and perhaps radix 8 ...
    (sci.optics)
  • Re: Really FFT?
    ... Is it then really a FFT (CPU ~ O(n ln n)) of a mere FT? ... FFT radix that wastes CPU time. ... means that padding to the next power of two is not such a bad idea ...
    (sci.math.num-analysis)
  • Re: MATLABs FFT
    ... Some take advantage of being a power of 4. ... Is MATLAB's FFT smart in ... Also, is MATLAB's FFT an exact solution of the DFT, or ... does it use one of the approximating FFT algorithms? ...
    (comp.soft-sys.matlab)
  • Re: FFT algoritms
    ... trying to infer, from the illustration, what the rhyme or reason there ... place algorithms without bit-reversal. ... if you compare a highly optimized in-order FFT like FFTW ... One reason to be cautious here is that O&S is comparing apples and ...
    (comp.dsp)