### 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``=` |
``N-1``
`∑`
``j=0``
| `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]`