The term fast Fourier transform (FFT) refers to an efficient implementation of the discrete Fourier transform (DFT) for highly compositeA.1 transform lengths . When computing the DFT as a set of inner products of length each, the computational complexity is . When is an integer power of 2, a Cooley-Tukey FFT algorithm delivers complexity , where denotes the log-base-2 of , and means ``on the order of ''. Such FFT algorithms were evidently first used by Gauss in 1805  and rediscovered in the 1960s by Cooley and Tukey .
In this appendix, a brief introduction is given for various FFT algorithms. A tutorial review (1990) is given in . Additionally, there are some excellent FFT ``home pages'':