Problem Statement

Calculate the   FFT   (Fast Fourier Transform)   of an input sequence. The most general case allows for complex numbers at the input and results in a sequence of equal length, again of complex numbers. If you need to restrict yourself to real numbers, the output should be the magnitude   (i.e.:   sqrt(re2 + im2))   of the complex result. The classic version is the recursive Cooley–Tukey FFT. Wikipedia has pseudo-code for that. Further optimizations are possible but not required.

Let's start with the solution:

F fft(x)
   V n = x.len
   I n <= 1
      R x
   V even = fft(x[(0..).step(2)])
   V odd  = fft(x[(1..).step(2)])
   V t = (0 .< n I/ 2).map(k -> exp(-2i * math:pi * k / @n) * @odd[k])
   R (0 .< n I/ 2).map(k -> @even[k] + @t[k]) [+]
     (0 .< n I/ 2).map(k -> @even[k] - @t[k])

print(fft([Complex(1.0), 1.0, 1.0, 1.0, 0.0, 0.0, 0.0, 0.0]).map(f -> ‘#1.3’.format(abs(f))).join(‘ ’))