Fast Fourier transform

The fast Fourier transform (FFT) is an algorithm to compute the discrete Fourier transform of a vector in time $O(nlog(n))$, where a naive implementation achieves only $O(n^{2})$ time.

See fast Fourier transform and discrete Fourier transform on Wikipedia.

A Fourier Transform (FFT) is a method of calculating the frequency components in a data set - and the inverse FFT converts back from the frequency domain - 4 applications of the FFT rotates you round the complex plane and leaves you back with the original data.

In this page the FFT is implemented with the Cooley-Tukey algorithm by dividing the transform into two pieces of size N÷2 at each step.

APLX FFT Code

Note that APLX is no longer under development.

This is as given in Robert J. Korsan's article in APL Congress 1973, p 259-268, with just line labels and a few comments added.

• X and Z are two-row matrices representing the input and output real and imaginary data. The data length must be 2*N (N integer), and the algorithm will cope with varying N, unlike many DSP versions which are for fixed N.
• Zero frequency is at Z[1;], maximum frequency in the middle; from there to ¯1↑[1] Z are negative frequencies. i.e. for an input Gaussian they transform a 'bath-tub' to a 'bath-tub'.
• This is an elegant algorithm, and works by transforming the input data into an array of 2×2 FFT Butterflies.

    Z←fft X;N;R;M;L;P;Q;S;T;O
⍝
⍝ Apl Congress 1973, p 267. Robert J. Korsan.
⍝
⍝ Restructure as an array of primitive 2×2 FFT Butterflies
X←(2,R←(M←⌊2⍟N←¯1↑⍴X)⍴2)⍴⍉X
⍝ Build sin and cosine table :
Z←R⍴⍉2 1∘.○○(-(O←?1)-⍳P)÷P←N÷2
⍝
Q←⍳P←M-1+L←0
T←M-~O
loop:→(M≤L←L+1)⍴done
X←(+⌿X),[O+¯0.5+S←M-L](-/Z×-⌿X),[O+P-0.5]+/Z×⌽-⌿X
Z←(((-L)⌽Q),T)⍉R⍴((1+P↑(S-1)⍴1),2)↑Z
→loop
done:Z←⍉(N,2)⍴(+⌿X),[O-0.5]-⌿X