Fast computation of Discrete Fourier Transforms using the Cooley-Tuckey algorithm.

Time complexity is O(n log n) in the size of the input.

Input dimensions must be powers of two, else `error`

.

The `fft`

and `ifft`

functions (and friends) also compute the roots of unity needed.
If you need to transform several arrays with the same extent then it is faster to
compute the roots once using `calcRootsOfUnity`

or `calcInverseRootsOfUnity`

,
then call `fftWithRoots`

directly.

The inverse transforms provided also perform post-scaling so that `ifft`

is the true inverse of `fft`

.
If you don't want that then call `fftWithRoots`

directly.

The functions `fft2d`

and `fft3d`

require their inputs to be squares (and cubes) respectively.
This allows them to reuse the same roots-of-unity when transforming along each axis. If you
need to transform rectanglular arrays then call `fftWithRoots`

directly.

- fft :: Shape sh => Array (sh :. Int) Complex -> Array (sh :. Int) Complex
- ifft :: Shape sh => Array (sh :. Int) Complex -> Array (sh :. Int) Complex
- fft2d :: Array DIM2 Complex -> Array DIM2 Complex
- ifft2d :: Array DIM2 Complex -> Array DIM2 Complex
- fft3d :: Array DIM3 Complex -> Array DIM3 Complex
- ifft3d :: Array DIM3 Complex -> Array DIM3 Complex
- fftWithRoots :: forall sh. Shape sh => Array (sh :. Int) Complex -> Array (sh :. Int) Complex -> Array (sh :. Int) Complex

# Documentation

fft :: Shape sh => Array (sh :. Int) Complex -> Array (sh :. Int) ComplexSource

Compute the DFT along the low order dimension of an array.

ifft :: Shape sh => Array (sh :. Int) Complex -> Array (sh :. Int) ComplexSource

Compute the inverse DFT along the low order dimension of an array.

fft2d :: Array DIM2 Complex -> Array DIM2 ComplexSource

Compute the DFT of a square matrix.
If the matrix is not square then `error`

.

fft3d :: Array DIM3 Complex -> Array DIM3 ComplexSource

Compute the DFT of a 3d cube.
If the array is not a cube then `error`

.