Here's how the (boring,

radix-

2)

fast Fourier transform (

FFT) works:

"Recall" that the discrete Fourier transform (DFT; what we're trying to calculate quickly) is defined by

F(j) = Σ_{k=0}^{N-1} f(k) w^{k*j},

where f is a (

periodic)

function defined on N points, F is its

Fourier transform, and

`w=exp(i/(2*pi*N))` is a

primitive N'th

root of

1. Now suppose that N>1 is a

power of 2. Then we can separate out the

sum above by

even and

odd k, to get

F(j) = Σ_{k=0}^{N/2-1} (f(2k) + w^{j} f(2k+1))*w^^{2kj}

which is almost the DFT of the function

g(k) = f(2k) + w^{j} f(2k+1)
g(k+N/2) = f(2k) - w^{j} f(2k+1)

and is not quite N/2-periodic. But if we calculate the Fourier transforms of f at even and odd points:

F_{0}(j) = Σ_{k=0}^{N/2-1} f(2k) w^{2kj}
F_{1}(j) = Σ_{k=0}^{N/2-1} f(2k+1) w^{2kj}

then

F(j) = F_{0}(j) + w^{j} F_{1}(j)

So to calculate one Fourier transform of N points, we must calculate 2 Fourier transforms of N/2 points. This yields time complexity of O(n log n), much better than the naïve algorithm's running time of O(n^2).