Task

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.




 
(define -∏*2 (complex 0 (* -2 PI)))
 
(define (fft xs N)
	(if (<= N 1) xs
	(let* [
		(N/2 (/ N 2))
		(even (fft (for/vector ([i (in-range 0 N 2)]) [xs i]) N/2))
		(odd  (fft (for/vector ([i (in-range 1 N 2)]) [xs i]) N/2))
		]
	(for ((k N/2)) (vector*= odd k  (exp (/ (* -∏*2 k) N ))))
	(vector-append (vector-map + even odd) (vector-map - even odd)))))
 
(define data #( 1 1 1 1  0 0 0 0 ))
 
(fft data 8)
    → #( 4+0i 1-2.414213562373095i 0+0i 1-0.4142135623730949i 
       0+0i 1+0.4142135623730949i 0+0i 1+2.414213562373095i)
 