If you know how to program, it’s not difficult to write your own discrete Fourier transform and its inverse through a literal implementation of the equations above. However, the “literal” implementation of the transform is computationally expensive. The equation in Algorithm 2.1 has to be applied N times, where N is the number of audio samples. The equation itself has a summation that goes over N elements. Thus, the discrete Fourier transform takes on the order of $$N^{2}$$ operations.
[wpfilebase tag=file id=160 tpl=supplement /]
The fast Fourier transform (FFT) is a more efficient implementation of the Fourier transform that does on the order of $$N\ast log_{2}N$$ operations. The algorithm is made more efficient by eliminating duplicate mathematical operations. The FFT is the version of the Fourier transform that you’ll often see in audio software and applications. For example, Adobe Audition uses the FFT to generate its frequency analysis view, as shown in Figure 2.41.
