Fast Fourier transform: Difference between revisions

=={{header|Klong}}==

<lang k>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)<n}{1+x}:~1;n#ff2({x,0}'x,&(2^k)-n)}</lang>

Example (rounding to 4 decimal digits):

<lang k> all(rndn(;4);fft([1 1 1 1 0 0 0 0]))</lang>

{{out}}

<pre>[[4.0 0.0]

[1.0 -2.4142]

[0.0 0.0]

[1.0 -0.4142]

[0.0 0.0]

[1.0 0.4142]

[0.0 0.0]

[1.0 2.4142]]</pre>