Radix-2 (FFT)

The version of the Cooley-Tukey FFT that splits by 2 at every level, requiring $N$ a power of 2.

A radix-2 FFT is the version of the Cooley-Tukey recursion that splits the input into even and odd halves at every level, which only works cleanly when $N$ is a power of $2$ . Mixed-radix FFTs generalize the same splitting idea to other small factors of $N$ , and Bluestein's algorithm handles an $N$ with no convenient small factors at all -- for instance a large prime.

Examples

Running radix-2 FFT code directly on $N=1{,}000$ samples fails, since $1{,}000$ is not a power of 2; it needs padding or a mixed-radix method instead.