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 . Such FFT algorithms were evidently first used by Gauss in 1805  and rediscovered in the 1960s by Cooley and Tukey .
Pointers to FFT software are given in §A.7.A.2