1.Previous
3.Next

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.

Other FFT algorithms

For with coprime and , one can use the prime-factor (Good-Thomas) algorithm (PFA), based on the Chinese remainder theorem,

1.Previous
3.Next