@code{(require 'dft)} or
@code{(require 'Fourier-transform)}
@ftindex dft, Fourier-transform
@code{fft} and @code{fft-1} compute the Fast-Fourier-Transforms
(O(n*log(n))) of arrays whose dimensions are all powers of 2.
@code{sft} and @code{sft-1} compute the Discrete-Fourier-Transforms
for all combinations of dimensions (O(n^2)).
@defun sft array prot
@defunx sft array
@var{array} is an array of positive rank. @code{sft} returns an
array of type @var{prot} (defaulting to @var{array}) of complex numbers comprising
the @dfn{Discrete Fourier Transform} of @var{array}.
@cindex Discrete Fourier Transform
@end defun
@defun sft-1 array prot
@defunx sft-1 array
@var{array} is an array of positive rank. @code{sft-1} returns an
array of type @var{prot} (defaulting to @var{array}) of complex numbers comprising
the inverse Discrete Fourier Transform of @var{array}.
@end defun
@defun fft array prot
@defunx fft array
@var{array} is an array of positive rank whose dimensions are all
powers of 2. @code{fft} returns an array of type @var{prot} (defaulting to
@var{array}) of complex numbers comprising the Discrete Fourier Transform of
@var{array}.
@end defun
@defun fft-1 array prot
@defunx fft-1 array
@var{array} is an array of positive rank whose dimensions are all
powers of 2. @code{fft-1} returns an array of type @var{prot} (defaulting
to @var{array}) of complex numbers comprising the inverse Discrete Fourier
Transform of @var{array}.
@end defun
@code{dft} and @code{dft-1} compute the discrete Fourier transforms
using the best method for decimating each dimension.
@defun dft array prot
@defunx dft array
@code{dft} returns an array of type @var{prot} (defaulting to @var{array}) of complex
numbers comprising the Discrete Fourier Transform of @var{array}.
@end defun
@defun dft-1 array prot
@defunx dft-1 array
@code{dft-1} returns an array of type @var{prot} (defaulting to @var{array}) of
complex numbers comprising the inverse Discrete Fourier Transform of
@var{array}.
@end defun
@noindent
@code{(fft-1 (fft @var{array}))} will return an array of values close to
@var{array}.
@example
(fft '#(1 0+i -1 0-i 1 0+i -1 0-i)) @result{}
#(0.0 0.0 0.0+628.0783185208527e-18i 0.0
0.0 0.0 8.0-628.0783185208527e-18i 0.0)
(fft-1 '#(0 0 0 0 0 0 8 0)) @result{}
#(1.0 -61.23031769111886e-18+1.0i -1.0 61.23031769111886e-18-1.0i
1.0 -61.23031769111886e-18+1.0i -1.0 61.23031769111886e-18-1.0i)
@end example