### 5.7 Discrete Fourier Transform ¶

`(require 'dft)` or `(require 'Fourier-transform)`

`fft` and `fft-1` compute the Fast-Fourier-Transforms (O(n*log(n))) of arrays whose dimensions are all powers of 2.

`sft` and `sft-1` compute the Discrete-Fourier-Transforms for all combinations of dimensions (O(n^2)).

Function: sft array prot ¶
Function: sft array ¶

  array is an array of positive rank. `sft` returns an array of type prot (defaulting to array) of complex numbers comprising the Discrete Fourier Transform of array.

Function: sft-1 array prot ¶
Function: sft-1 array ¶

  array is an array of positive rank. `sft-1` returns an array of type prot (defaulting to array) of complex numbers comprising the inverse Discrete Fourier Transform of array.

Function: fft array prot ¶
Function: fft array ¶

  array is an array of positive rank whose dimensions are all powers of 2. `fft` returns an array of type prot (defaulting to array) of complex numbers comprising the Discrete Fourier Transform of array.

Function: fft-1 array prot ¶
Function: fft-1 array ¶

  array is an array of positive rank whose dimensions are all powers of 2. `fft-1` returns an array of type prot (defaulting to array) of complex numbers comprising the inverse Discrete Fourier Transform of array.

`dft` and `dft-1` compute the discrete Fourier transforms using the best method for decimating each dimension.

Function: dft array prot ¶
Function: dft array ¶

  `dft` returns an array of type prot (defaulting to array) of complex numbers comprising the Discrete Fourier Transform of array.

Function: dft-1 array prot ¶
Function: dft-1 array ¶

  `dft-1` returns an array of type prot (defaulting to array) of complex numbers comprising the inverse Discrete Fourier Transform of array.

`(fft-1 (fft array))` will return an array of values close to array.

    (fft '#(1 0+i -1 0-i 1 0+i -1 0-i)) ⇒

    #(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)) ⇒

    #(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)