11 September 2025
Fast Fourier Transforms Part 1: Cooley-Tukey
by Connor Boyle
tags: mathematicssoftware
I’m planning to write a series of posts about fast Fourier transform algorithms. This first post covers the Cooley-Tukey algorithm, which is the original and most well-known FFT algorithm.
The Discrete Fourier Transform
If \(x\) is a sequence of complex numbers with a length \(\lvert x \rvert\) and a starting index of 0, then the discrete Fourier transform of \(x\), \(\mathcal{F} \{ x \}\), is defined as follows:
\[|\mathcal{F} \{ x \}| = |x|\] \[\mathcal{F} \{ x \}[k] = \sum_{j=0}^{|x|-1} x[j] \cdot e^{-i 2 \pi jk \frac{1}{|x|}}\]
Since complex exponentation is so commonly used in Fourier transforms, we’ll define a helpful term \(W_N\) as follows:
\[W_N \triangleq e^{-i 2 \pi \frac{1}{N}}\]
... continue reading