Fast Fourier Transform (FFT)

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