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=0N-1 f(k) wk*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=0N/2-1 (f(2k) + wj f(2k+1))*w^2kj
which is almost the DFT of the function
g(k) = f(2k) + wj f(2k+1)
g(k+N/2) = f(2k) - wj f(2k+1)
and is not quite N/2-periodic. But if we calculate the Fourier transforms of f at even and odd points:
F0(j) = Σk=0N/2-1 f(2k) w2kj
F1(j) = Σk=0N/2-1 f(2k+1) w2kj
then
F(j) = F0(j) + wj F1(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).