---
tag: 9N8D9E5TB2
kind: statement
role: theorem
name: Cooley–Tukey FFT algorithm
msc: [65T50, 65Y20]
uses: [TST0GH66A5, 0EHM5ZP5QH, 0TGV80E6A4]
about: [TST0GH66A5]
sources:
  - url: https://en.wikipedia.org/wiki/Cooley–Tukey_FFT_algorithm
same_as:
  wikidata: Q5167446
  wikipedia: Cooley–Tukey FFT algorithm
---

## Statement

For an integer $M \ge 1$ let $\omega_M = e^{-2\pi i/M}$, a [[primitive $M$-th root of unity|0EHM5ZP5QH]].
Let $N = N_1 N_2$ with integers $N_1, N_2 \ge 1$, let $x = (x_0, \ldots, x_{N-1}) \in \C^N$, and let $X$ be its [[discrete Fourier transform|TST0GH66A5]], $X_k = \sum_{n=0}^{N-1} x_n \omega_N^{nk}$.
Then for all $0 \le k_1 < N_1$ and $0 \le k_2 < N_2$,
$$X_{k_1 + N_1 k_2} = \sum_{n_2=0}^{N_2-1} \omega_{N_2}^{n_2 k_2} \left[ \omega_N^{n_2 k_1} \sum_{n_1=0}^{N_1-1} x_{N_2 n_1 + n_2}\, \omega_{N_1}^{n_1 k_1} \right].$$
Thus a DFT of length $N$ is obtained in three stages.
First come $N_2$ DFTs of length $N_1$, then $N$ multiplications by the twiddle factors $\omega_N^{n_2 k_1}$, then $N_1$ DFTs of length $N_2$.
In particular, if $N = 2^m$, applying this with $N_1 = 2$ (or $N_2 = 2$) recursively computes $X$ with $O(N \log N)$ arithmetic operations.

## Remarks

The proof is one line: write $n = N_2 n_1 + n_2$ and $k = k_1 + N_1 k_2$ and expand $\omega_N^{nk}$.
The factor $\omega_N^{N_2 N_1 n_1 k_2}$ equals $1$, while $\omega_N^{N_2 n_1 k_1} = \omega_{N_1}^{n_1 k_1}$ and $\omega_N^{N_1 n_2 k_2} = \omega_{N_2}^{n_2 k_2}$.
For $N = 2M$ the radix-2 form reads $X_k = E_k + \omega_N^k O_k$ and $X_{k+M} = E_k - \omega_N^k O_k$ for $0 \le k < M$, where $E$ and $O$ are the DFTs of length $M$ of the even-indexed and odd-indexed entries.
The cost then satisfies $T(N) = 2T(N/2) + O(N)$, so $T(N) = O(N \log N)$.
Direct evaluation of the defining sums costs about $N^2$ multiplications; for $N = 2^{20}$ the ratio is about $5 \times 10^4$.
The splitting is useless when $N$ is prime, since then one factor is $1$.

## Explanations

### L1 human

The discrete Fourier transform of $N$ numbers looks like it needs $N^2$ multiplications.
The Cooley–Tukey idea is to split the input into interleaved pieces, transform each piece, and glue the results with a few extra multiplications.
For $N = 8$: transform the entries with even index and those with odd index separately, then combine.
Repeating the split when $N$ is a power of $2$ brings the cost down to a multiple of $N \log N$.

### L2 human

This is the most common fast Fourier transform.
The index maps $n = N_2 n_1 + n_2$ and $k = k_1 + N_1 k_2$ turn a one-dimensional transform into a two-dimensional one, up to the twiddle factors.
Radix-2, radix-4, split-radix and mixed-radix versions differ only in how $N$ is factored at each step.
When $N_1$ and $N_2$ are coprime, the prime-factor algorithm uses other index maps and avoids the twiddle factors.
Prime lengths need a different reduction, such as Rader's or Bluestein's algorithm.