Daqarta
Data AcQuisition And Real-Time Analysis
Scope - Spectrum - Spectrogram - Signal Generator
Software for Windows  The following is from the Daqarta Help system:

# Fast Fourier Transform (FFT)

The Discrete Fourier Transform is a general application of Fourier Transform theory using digital methods. But it's rather slow, since all input samples N must be multiplied by sine and cosine values at each frequency, for N/2 different frequencies, giving N^2 total multiplications. That's over 1 million if N = 1024 (as used by Daqarta), and multiplication is one of the slower instructions on most computers. Back in the '60s, however, a couple of clever gents named Cooley and Tukey noticed that the set of DFT calculations contains a lot of redundancy and wasted effort.

For one thing, everywhere the sine or cosine reference tables hold a zero, there is no point multiplying the input sample... just use the zero directly. Likewise, everyhere the multipliers are +1, the input value could just be copied directly. If the multiplier is -1, we only need a sign change.

Similarly, a particular input sample may end up being multiplied by the same numerical value for the sine or cosine components of many different reference frequencies. For example, the value of 0.7071 is repeated every 45 degrees around a sine or cosine cycle with only sign changes. And since each sample will be multiplied by all the different input frequencies, it turns out that many of them will use the same values on the same sample. We could do a single multiply of each input sample by each of these recurring values, and then just use that result (maybe with a sign change) for all future needs in that set of input samples.

These recurring conditions happen a lot, especially if the number of samples happens to be a power of 2. The whole operation becomes an accounting nightmare of keeping track of which redundant value should be plugged in where, but Cooley and Tukey came up with a method to keep everything straight, and the Fast Fourier Transform (FFT) was born. Subsequent workers have come up with all sorts of enhancements, but the basic idea remains: Don't waste time doing the same thing twice.

Where the number of multiplications in a typical DFT quadruples when the N is doubled, for a typical FFT it only slightly more than doubles. For N = 1024, the FFT turns out to be about 100 times faster than the DFT. GO: