Cool algorithms + implementations.
Discrete Fourier Transform (DFT) is defined as the discrete Z-transform sampled at each root of unity.
where 
is the N-th root of unity.
It has the following feature, which leads to Fast Fourier Transform (FFT) algorithm:
where 
, 
.
The 
and 
are defined and can be calculated by recursively applying FFT to even and odd subsequences of original signal 
.
Replacing 
in 
and 
by the following observation:
we'll get
We now see that consists of even terms of 
, and 
consists of odd terms of . QED.
Originally and 
are both arrays of length 
. However, in the last step we need to add the corresponding element from both into 
of length 
.
The key is the fact that and are both periodical. So, 
. This also holds for .
We can calculate like this:
int M = N / 2;
for (int k = 0; k < N; k++) {
F[k] = Fe[k % M] + RU(k, N) * Fo[k % M];
}