19 lines
446 B
Plaintext
19 lines
446 B
Plaintext
import <Utilities/Complex.sl>;
|
|
import <Utilities/Math.sl>;
|
|
import <Utilities/Sequence.sl>;
|
|
|
|
fft(x(1)) :=
|
|
let
|
|
n := size(x);
|
|
|
|
top := fft(x[range(1,n-1,2)]);
|
|
bottom := fft(x[range(2,n,2)]);
|
|
|
|
d[i] := makeComplex(cos(2.0*pi*i/n), -sin(2.0*pi*i/n)) foreach i within 0...(n / 2 - 1);
|
|
|
|
z := complexMultiply(d, bottom);
|
|
in
|
|
x when n <= 1
|
|
else
|
|
complexAdd(top,z) ++ complexSubtract(top,z);
|