Cooley-Tukey Algorithm

From dankwiki
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

This most well-known of FFT algorithms recursively breaks the DFT of N1N2 into DFTs of N1 and N2, approaching O(NlogN) for smooth (highly composite) numbers.