The DFT is a slow algorithm, over time much faster alternatives have been developed. One of the most popular is the Radix-2 Fast Fourier Transform which was developed in 1965 by Tukey and Cooley. It comes in two flavours - decimation in frequency, and decimation in time. I'll only deal with the latter.

The basic premise behind the Radix-2 Decimation in Time algorithm is that if we
define an *N*-element FFT as:

Then we can express one FFT of

The sub-transforms will only give us values for

It looks a little neater if we split

We can express each one of those

[fft1.c]
My first attempt at implementing this was much faster than the DFT but very
slow for an FFT because it was recursive and allocated memory dynamically to
split *f* into evens and odds. (Because I wanted to see the math work
before I launched into an even slightly complicated implementation)

[fft2.c] My second attempt - I sort the inputs into a bit-reversed order and then use a recursive, in-place FFT. No malloc abuse happens.

[fft3.c] My third attempt - eliminated recursion. There's still plenty of space for optimisation (such as taking advantage of trivial twiddle factors in the first few passes) but this is where I'm calling it quits.

If you're looking for a really fast FFT implementation, try one of these:

rp: The process that transformed Fourier back to the elements of which he was composed.

Graphs by gnuplot.If you spot any mathematical inaccuracies, give me a kick.

[home]

copyright © 2004 Emil Mikulic

First try: 2001/09/25

$Date: 2004/10/09 08:53:25 $