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.




#import nat
#import flo
 
f = <1+0j,1+0j,1+0j,1+0j,0+0j,0+0j,0+0j,0+0j>    # complex sequence of 4 1's and 4 0's
 
g = c..mul^*D(sqrt+ float+ length,..u_fw_dft) f  # its fft
 
#cast %jLW
 
t = (f,g)