Fast Fourier Transform

The major drawback of the discrete Fourier transform (DFT) is its slowness. DFT is so slow that a real-time Fourier transform is unrealistic, except for very powerful computers. The discovery of the Fast Fourier Transform (FFT) algorithms by Cooley and Tuckey changed this. While the DFT  requires about N² multiplications (N is the number of signal samples), the FFT needs only 0.5*N*log₂(N) steps. This results, for example, in an improvement of a factor of 200 in calculation time for 1024 data points.

Note that the FFT is just a faster way to perform the DFT. So the FFT is not an approximation - it delivers the same results with the same precision as the DFT.

The basic idea behind the FFT is to split an N-point DFT into two N/2-point DFTs. This is possible because of the periodicity of the complex exponential function. The idea of splitting a transform into two smaller ones can be carried on until only two data points are left (given that we started at an integer power of 2). More details on the algorithm can be found in numerous publications.