FFT Theory

Problem

Compute length-n DFT faster than naive O(n^2) summation: X[k] = sum a[j] * exp(-2*pi*i*j*k / n). Use parity split to form two size n/2 transforms.

Recursive Decomposition

Polynomial view: A(x) = Σ a_j x^j. Partition indices by parity:

Evaluate at roots of unity ω_n^k gives two n/2 transforms E[k], O[k] plus combination with twiddle factors:

Each level performs O(n) twiddle multiplies; height log2 n.

Pseudocode

1function fft(a):
2  n = length(a)
3  if n == 1: return a
4  even = fft(a[0::2])
5  odd  = fft(a[1::2])
6  combine using roots of unity
7  return result

Key Insights

• Symmetry: w_n^(k + n/2) = -w_n^k halves needed evaluations.
• Iterative form uses bit-reversal reordering for in-place layout.
• Inverse FFT differs only by conjugation and scaling 1/n.
• Extensions: mixed radix, Bluestein for prime lengths.