Cooley--Tukey fast Fourier transform

The radix-two Cooley--Tukey algorithm recursively splits a discrete Fourier transform into transforms of the even-indexed and odd-indexed samples. For a power-of-two length this evaluates the transform in $O(m\log m)$ arithmetic operations.

For ${\omega }_m=e^{-2\pi i/m}$ and length-$m/2$ transforms $E_k,O_k$ of the even and odd samples,