dft-fft

simple dft fft understand

V = [w_jk] = w^ij with w=nth-root(1) = exp(-2*PI/n*i)

---

• DFT(a) = y <=> y=V*a
• IDFT(y) = a <=> a=V^-1*y/n

fft

A(x) = x*Aodd(x2) + Aeven(x2)

odd=fft(x[1::2])
even=fft(x[::2])
x[i]=odd[i]+w*even[i]
x[i+n/2]=odd[i]-w*even[i]

visit at https://github.com/nnphuc/python-advanced-algorithms/blob/master/fft.py