Previous Up Next

2.22.3Fast Fourier Transform : fft

fft takes as argument a list (or a sequence) [a0,..aN-1] where N is a power of two.
fft returns the list [b0,..bN-1] such that, for k=0..N-1

fft([a0,..aN-1])[k]=bk=
N-1
j=0
xjωN-k j

where ωN is a primitive N-th root of the unity.
Input :

fft(0,1,1,0)

Output :

[2.0, -1-i, 0.0, -1+i]

Previous Up Next