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:

fft::{ff2::{[n e o p t k];n::#x;
            f::{p::2:#x;e::ff2(*'p);o::ff2({x@1}'p);k::-1;
                t::{k::k+1;cmul(cexp(cdiv(cmul([0 -2];(k*pi),0);n,0));x)}'o;
                (e cadd't),e csub't};
            :[n<2;x;f(x)]};
      n::#x;k::{(2^x)


        all(rndn(;4);fft([1 1 1 1 0 0 0 0]))