## History of the FFT(Note: This is a somewhat technical history, an excerpt from a scholarly article written by one of our authors.) The first appearance of the FFT, like so much of mathematics, can be traced back to A less general but still important version of the FFT, used for the efficient computation of the Hadamard and Walsh transforms, was first published in 1932 by the statistician Yates (F. Yates, "The design and analysis of factorial experiments," Another important predecessor is the work of Danielson and Lanczos (G. C. Danielson and C. Lanczos, "Some improvements in practical Fourier analysis and their application to X-ray scattering from liquids," Despite these early discoveries of an FFT, it wasn’t until Cooley and Tukey’s article (J. W. Cooley and J. W. Tukey, "An algorithm for machine calculation of complex Fourier series," Richard Garwin of IBM was another of the participants at this meeting, and when Tukey showed him this idea he immediately saw a wide range of potential applicability and quickly set to getting this algorithm implemented. He was directed to Cooley and, needing to hide the national security issues, instead told Cooley that he wanted the code for another problem of interest: the determination of the periodicities of the spin orientations in a 3-D crystal of He3. Cooley had other projects going on, and only after quite a lot of prodding did he sit down to program the "Cooley-Tukey" FFT. In short order, Cooley was published almost instantaneously (in 6 months!). This publication, as well as Garwin’s fervent proselytizing, did a lot to help publicize the existence of this (apparently) new fast algorithm. The timing of the announcement was such that usage spread quickly. The roughly simultaneous development of analog to digital converters capable of producing digitized samples of a time-varying voltage at rates of 300,000 samples per second had already initiated something of a digital revolution and was also providing scientists with heretofore unimagined quantities of digital data to analyze and manipulate (just as is the case today!). Even the "standard" applications of Fourier analysis as an analysis tool for waveforms or solving PDEs (partial differential equations) meant that a priori there would be a tremendous interest in the algorithm. But even more, the ability to do this analysis quickly allowed scientists from new areas to try the DFT without having to invest too much time and energy in the exercise. I can do no better than to quote the introduction to the FFT from |

©Burk/Polansky/Repetto/Roberts/Rockmore. All rights reserved.