Fast Fourier Transform (FFT)
- Implement the (naïve, with complex numbers) Cooley-Tukey algorithm for FFT.
Check that the scaling is indeed O(N×log(N)).
- Implement an application of FFT at your choice.
- Get rid of the array copying in the naïve implementation.