= Cooley-Tukey FFT algorithm
{c}
{wiki=Cooley–Tukey_FFT_algorithm}
= Cooley--Tukey fast Fourier transform
{c}
{synonym}
The radix-two Cooley--Tukey algorithm recursively splits a discrete Fourier transform into transforms of the even-indexed and odd-indexed samples. For a power-of-two length this evaluates the transform in $O(m\log m)$ arithmetic operations.
The saving comes from reusing the two shorter <discrete Fourier transforms> for both halves of the output, through an <FFT butterfly>. For $N=2^p$, each level of the <even--odd fast Fourier transform recursion> needs work proportional to $N$, and there are $p=\log_2N$ levels. This gives the $O(N\log N)$ <time complexity> without changing the <discrete Fourier transform> being computed.
James W. Cooley and John W. Tukey published \i[An Algorithm for the Machine Calculation of Complex Fourier Series] in \i[Mathematics of Computation] 19 (1965), pp. 297–301. Their original paper factors a composite length as $N=r_1\cdots r_p$, derives an operation count $N(r_1+\cdots+r_p)$, and discusses powers of two and in-place storage. Its opening explicitly builds on earlier <algorithms> by I. J. Good; the 1965 paper is a landmark computational formulation, rather than the invention of the underlying <Fourier analysis>. Its positive-exponent convention also illustrates why a <Fast Fourier transform>'s exponent sign must be specified.https://janmr.com/files/papers/cooley-tukey.pdf[Cooley and Tukey 1965, original paper, pp. 297–300, equations (1)–(12); scan of the published article]{ref}
Back to article page
