### 2.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]`