Editing Cooley–Tukey FFT algorithm (section)

=== Pseudocode ===
In [[pseudocode]], the below procedure could be written:<ref name="Johnson08"/>

 ''X''<sub>0,...,''N''−1</sub> ← '''ditfft2'''(''x'', ''N'', ''s''):             ''DFT of (x''<sub>0</sub>, ''x<sub>s</sub>'', ''x''<sub>2''s''</sub>, ..., ''x''<sub>(''N''-1)''s''</sub>):
     '''if''' ''N'' = 1 '''then'''
         ''X''<sub>0</sub> ← ''x''<sub>0</sub>                                     ''trivial size-1 DFT base case''
     '''else'''
         ''X''<sub>0,...,''N''/2−1</sub> ← '''ditfft2'''(''x'', ''N''/2, 2''s'')             ''DFT of (x''<sub>0</sub>, ''x''<sub>2''s''</sub>, ''x''<sub>4''s''</sub>, ..., ''x''<sub>(''N''-2)''s''</sub>)
         ''X<sub>N</sub>''<sub>/2,...,''N''−1</sub> ← '''ditfft2'''(''x''+s, ''N''/2, 2''s'')           ''DFT of (x<sub>s</sub>'', ''x<sub>s</sub>''<sub>+2''s''</sub>, ''x<sub>s</sub>''<sub>+4''s''</sub>, ..., ''x''<sub>(''N''-1)''s''</sub>)
         '''for''' k = 0 to (N/2)-1 '''do'''                      ''combine DFTs of two halves:''
             p ← ''X<sub>k</sub>''
             q ← exp(−2π''i''/''N'' ''k'') ''X<sub>k</sub>''<sub>+''N''/2</sub>
             ''X<sub>k</sub>'' ← p + q 
             ''X<sub>k</sub>''<sub>+''N''/2</sub> ← p − q
         '''end for'''
     '''end if'''

Here, <code>'''ditfft2'''</code>(''x'',''N'',1), computes ''X''=DFT(''x'') [[In-place algorithm|out-of-place]] by a radix-2 DIT FFT, where ''N'' is an integer power of 2 and ''s''=1 is the [[stride of an array|stride]] of the input ''x'' [[Array data structure|array]].  ''x''+''s'' denotes the array starting with ''x<sub>s</sub>''.

(The results are in the correct order in ''X'' and no further [[bit-reversal permutation]] is required; the often-mentioned necessity of a separate bit-reversal stage only arises for certain in-place algorithms, as described below.)

High-performance FFT implementations make many modifications to the implementation of such an algorithm compared to this simple pseudocode.  For example, one can use a larger base case than ''N''=1 to amortize the overhead of recursion, the [[twiddle factor]]s <math>\exp[-2\pi i k/ N]</math> can be precomputed, and larger radices are often used for [[cache (computing)|cache]] reasons; these and other optimizations together can improve the performance by an order of magnitude or more.<ref name="Johnson08">S. G. Johnson and M. Frigo, "[http://cnx.org/content/m16336/ Implementing FFTs in practice]," in ''Fast Fourier Transforms'' (C. S. Burrus, ed.), ch. 11, Rice University, Houston TX: Connexions, September 2008.</ref>  (In many textbook implementations the [[depth-first]] recursion is eliminated in favor of a nonrecursive [[breadth-first]] approach, although depth-first recursion has been argued to have better [[memory locality]].<ref name="Johnson08"/><ref name=Singleton67/>) Several of these ideas are described in further detail below.