Fast Fourier transform

Invented by James W. Cooley and John W. Tukey in 1965 (Ref 1). The fast Fourier transform reduces the number of operations from $N^{2}$ to $N\ln N$.

References

1. James W. Cooley and John W. Tukey", "An Algorithm for the Machine Calculation of Complex Fourier Series", Mathematics of Computation 19 pp. 297-301 (1965)

External resources

• Routines to calculate Fourier transforms sample FORTRAN computer code from the book M. P. Allen and D. J. Tildesley "Computer Simulation of Liquids", Oxford University Press (1989).