Fast fourier transform
From AMS Glossary
fast Fourier transform
(Abbreviated FFT.) An algorithm to compute rapidly the digital form of the discrete Fourier transform.
The procedure requires that the length of the data series undergoing transformation be an integral power of two, which is often achieved by truncating the series or extending it with zeros. More flexible mixed-radix algorithms have been developed that allow data series of any length. They gain efficiency as the prime factors of the length become small, and they are equivalent to the FFT when the data series length is a power of two.