### 5.22.3 Fast Fourier Transform : fft

fft takes as argument a list (or a sequence)
[a_{0},..a_{N-1}] where N is a power of two.

fft returns the list [b_{0},..b_{N-1}] such that,
for k=0..N-1

fft([a_{0},..a_{N-1}])[k]=b_{k}= | | x_{j}ω_{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]