@node Fft, Foreach, Expand, Commands

@iftex
@syntax Fft.
@end iftex
@example
Syntax: FFT n pexpr1 pexpr2 WORD1 WORD
@end example
@pindex FFT

   Fourier transform 2 vectors (treated as the real and imaginary parts
of a complex vector), returning the answer in the two vectors @code{WORD1} and
@code{WORD2}. The input vectors may be the names of vectors or expressions in
parentheses. The direction is specified by @code{n}, either +1 for a forward
transform, or -1 for an inverse.

   The dimension of the vectors need not be a power of 2, but the transform
is more efficient if it is. The worst case is when @i{n} is prime, in
which case this command performs a slow Fourier transform in @i{O(n^2)} time.