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.
- 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)
- - PiotrLi
- See also
- - https://introcs.cs.princeton.edu/java/97data/FFT.java.html
- - 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.