Editing Cooley–Tukey FFT algorithm (section)

{{Short description|Fast Fourier Transform algorithm}}
{{Use American English|date = March 2019}}
The '''Cooley–Tukey algorithm''', named after [[James Cooley|J. W. Cooley]] and [[John Tukey]], is the most common [[fast Fourier transform]] (FFT) algorithm.  It re-expresses the [[discrete Fourier transform]] (DFT) of an arbitrary [[composite number|composite]] size <math>N = N_1N_2</math> in terms of ''N''<sub>1</sub> smaller DFTs of sizes ''N''<sub>2</sub>, [[recursion|recursively]], to reduce the computation time to O(''N'' log ''N'') for highly composite ''N'' ([[smooth number]]s). Because of the algorithm's importance, specific variants and implementation styles have become known by their own names, as described below.

Because the Cooley–Tukey algorithm breaks the DFT into smaller DFTs, it can be combined arbitrarily with any other algorithm for the DFT.  For example, [[Rader's FFT algorithm|Rader's]] or [[Bluestein's FFT algorithm|Bluestein's]] algorithm can be used to handle large prime factors that cannot be decomposed by Cooley–Tukey, or the [[prime-factor FFT algorithm|prime-factor algorithm]] can be exploited for greater efficiency in separating out [[relatively prime]] factors.

The algorithm, along with its recursive application, was invented by [[Carl Friedrich Gauss]]. Cooley and Tukey independently rediscovered and popularized it 160 years later.