Editing Fast Fourier transform (section)

===Cooley–Tukey algorithm===
{{Main|Cooley–Tukey FFT algorithm}}

By far the most commonly used FFT is the Cooley–Tukey algorithm. This is a [[divide-and-conquer algorithm]] that [[recursively]] breaks down a DFT of any [[composite number|composite]] size <math display="inline">n = n_1n_2</math> into <math display="inline">n_1</math> smaller DFTs of size <math display="inline">n_2</math>, along with <math>O(n)</math> multiplications by complex [[roots of unity]] traditionally called [[twiddle factor]]s (after Gentleman and Sande, 1966).<ref name="Gentleman_Sande_1966"/>

This method (and the general idea of an FFT) was popularized by a publication of Cooley and Tukey in 1965,<ref name="Cooley_Tukey_1965"/> but it was later discovered<ref name="Heideman_Johnson_Burrus_1984"/> that those two authors had together independently re-invented an algorithm known to [[Carl Friedrich Gauss]] around 1805<ref name="Gauss_1805"/> (and subsequently rediscovered several times in limited forms).

The best known use of the Cooley–Tukey algorithm is to divide the transform into two pieces of size {{math|n/2}} at each step, and is therefore limited to power-of-two sizes, but any factorization can be used in general (as was known to both Gauss and Cooley/Tukey<ref name="Heideman_Johnson_Burrus_1984"/>). These are called the ''radix-2'' and ''mixed-radix'' cases, respectively (and other variants such as the [[split-radix FFT]] have their own names as well).  Although the basic idea is recursive, most traditional implementations rearrange the algorithm to avoid explicit recursion. Also, because the Cooley–Tukey algorithm breaks the DFT into smaller DFTs, it can be combined arbitrarily with any other algorithm for the DFT, such as those described below.