Compute the FFT and inverse FFT of a length n complex sequence using the radix 2 Cooley-Tukey algorithm.

Bare bones implementation that runs in O(n log n) time.

Limitations

• assumes length is a power of 2
• not the most memory efficient algorithm (because it uses an object type for representing complex numbers and because it re-allocates memory for the subarray, instead of doing in-place or reusing a single temporary array)

author

- PiotrLi

See also

- https://introcs.cs.princeton.edu/java/97data/FFT.java.html

license

- GPL

 ct_fft(+X:list, -Y:list) is det

Compute the FFT of X, assuming its length is a power of 2.

 ct_ifft(+X:list, -Y:list) is det

Compute the inverse FFT of X, assuming its length is a power of 2.

 ct_cconvolve(+X:list, +Y:list, -Z:list) is det

Compute the circular convolution of X and Y.

 ct_convolve(+X:list, +Y:list, -Z:list) is det

Compute the linear convolution of Y and Y.