Fast Fourier Transforms Part 1: Cooley-Tukey
Summary
The piece explains the Cooley-Tukey FFT algorithm, starting from the DFT definition and introducing W_N. It shows how a single DFT can be decomposed into smaller transforms, analyzes the computational complexity, and notes limitations for prime lengths. It also mentions an interactive visualization and plans for related posts.