Re: FFT for N Not a Power of 2

On Nov 21, 12:36 pm, Phil Hobbs
<pcdhSpamMeSensel...@xxxxxxxxxxxxxxxxxx> wrote:
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.  

Actually, the chirp-Z algorithm is not a transform, it is an algorithm
to express either a DFT or a more general Z transform in terms of a
convolution of the same length, which can then be zero-padded and
evaluated via a pair of FFTs of longer composite length. (Google
"Bluestein's FFT algorithm"). There is also Rader's algorithm for
DFTs of prime N, which turn it into a convolution of (composite) size
N-1, via some number theory on the indices (google "Rader's FFT
algorithm"). But you're right that these algorithms, while O(N log
N), are typically several times slower than algorithms for nearby
highly-composite sizes.

As another poster pointed out, if N is a power of 2, the fastest
implementations (at least on general-purpose CPUs with caches etc)
typically do not use a classic radix-2 algorithm, but instead use
larger radices (see http://cnx.org/content/m16336/latest/ for some
explanations of why). Also, it is no longer the case that power-of-
two N's are necessarily the most efficient; any highly-composite Ns
(with prime factors < 10, say) can be transformed with similar
efficiency with an optimized library, so padding to a power of two is
not necessarily desirable. e.g. with FFTW on my Intel Core 2, n=3840
is faster than n=4096.

But I agree that this is all probably off-topic relative to the OP's
problem.

Regards,
Steven G. Johnson
.

Relevant Pages

  • Re: Inverse chirp z
    ... It looks like chirp z and especially inverse transform is ... you have to separate the algorithm from the ... variant of Bluestein's 1968 FFT algorithm, ...
    (comp.dsp)
  • Re: How to fft huge data arrays?
    ... For my little project i need to fft large data arrays, ... applying some sort of filter to a sound file. ... The Fast Fourier Transform, FFT, is a fast way to implement the ... algorithm, and it will be way simpler to implement. ...
    (comp.dsp)
  • Re: How to fft huge data arrays?
    ... > For my little project i need to fft large data arrays, ... applying some sort of filter to a sound file. ... The Fast Fourier Transform, FFT, is a fast way to implement the ... algorithm (for very small filters the time-domain methof may ...
    (comp.dsp)
  • Re: Discrete Deconvolution
    ... transform of a signal that happens to be of finite extent, the FFT thinks that it's taking the transform of a signal that repeats, that is that s= sfor an N-point FFT. ... Usually this is a whopping big discontinuity, which makes the algorithm report lots of really high-frequency content which simply isn't there in the real signal. ... This big problem is solved by windowing, as a way to get the algorithm to cough up an approximate Fourier transform that has some hope of being close. ...
    (comp.dsp)
  • Re: "Discrete Hartley transform" vs " Discrete Fouuier transform"
    ... transform to think about from time to time. ... advantages from FHT algorithms for power-of-two sizes have, sadly, not ... Use Ron Mayer's algorithm from the early 1990's, ... trig tables and test it yourself. ...
    (comp.dsp)
Quantcast