It sounds like this“The FFT is a fast approximation of the real Fourier transform, so it loses some accuracy.”
Thinking the FFT is a rougher version of the transform
Why it feels right
A faster method that gets the same result sounds too good to be true. In most of computing, speed is bought with accuracy: a quick estimate, a rougher image, a lossy file. The word 'fast' in the name makes it sound like the same kind of trade.
Why it’s wrong
The FFT gives exactly the same numbers as the slow method, the discrete Fourier transform. It only organises the sums to avoid repeating work, cutting the steps from about N squared to about N times log N. For a million samples, that is around 50,000 times fewer.
A worked example
The discrete Fourier transform of N samples can be written down directly: each of N outputs is a sum over N inputs, which makes about N times N steps. For a thousand samples that is a million steps; for a million samples a million million.
In 1965 James Cooley and John Tukey published a way to arrange the same sums so that the work is shared. The transform of N samples is built from transforms of two halves, and each of those from halves again, down to single samples. The total comes to about N times log base 2 of N steps. For N = 1,048,576 that is about 21 million steps instead of 1.1 million million, some 50,000 times fewer.
The outputs are mathematically identical, apart from the tiny rounding errors that any computer arithmetic has. The same trick had been found by Gauss around 1805 but not published. The FFT made it practical to analyse audio in real time, to compress images and to run mobile phone radios.
How to catch yourself
- You say the FFT 'approximates' the Fourier transform.
- You expect a large speed-up to cost accuracy.
- You can't say what the FFT is doing differently.
What to hold instead
The FFT gives the same answer as the direct calculation, apart from rounding. It saves work by sharing sub-results between the sums, taking about N log N steps instead of N squared.
Where you’ll meet it
- Reading about real-time audio analysis.
- Understanding why phones can run radios and cameras.
- Choosing between an FFT and a direct sum.
Questions people ask
- Is the FFT an approximation?
- No. It computes exactly the same discrete Fourier transform as the direct method, only with far fewer operations. The only differences are tiny rounding errors.
- Who invented the FFT?
- James Cooley and John Tukey published the modern algorithm in 1965. Carl Friedrich Gauss had found essentially the same idea around 1805 but never published it.