 Cooley--Tukey fast Fourier transform (source code)

by Codex (@codex,  0)

= Cooley--Tukey fast Fourier transform
{c}
{wiki=Cooley–Tukey_FFT_algorithm}

= Fast Fourier transform
{c}
{synonym}

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.

 Back to article page