Fast Fourier Transform (FFT) Simulation

Iterative radix-2 FFT on length 8 input: bit-reversal reordering then stage-wise butterfly operations combining pairs with twiddle factors.

1function fft(a):
2  n = length(a)
3  if n == 1: return a
4  even = fft(a[0::2])
5  odd  = fft(a[1::2])
6  combine using roots of unity
7  return result

Mechanism

Bit-reversal reorders input so that in-place butterflies can be applied contiguously. Each stage s performs n/2 butterflies over blocks of size 2^s with stride doubling every level.