Editing Cooley–Tukey FFT algorithm (section)

== History ==
This algorithm, including its recursive application, was invented around 1805 by [[Carl Friedrich Gauss]], who used it to interpolate the trajectories of the [[asteroid]]s [[2 Pallas|Pallas]] and [[3 Juno|Juno]], but his work was not widely recognized (being published only posthumously and in [[Neo-Latin]]).<ref name="Gauss_1866">{{cite book |author-first=Carl Friedrich |author-last=Gauss |author-link=Carl Friedrich Gauss |chapter-url=https://babel.hathitrust.org/cgi/pt?id=uc1.c2857678;view=1up;seq=279 |title=Nachlass |chapter=Theoria interpolationis methodo nova tractata |type=Unpublished manuscript |trans-chapter=Theory regarding a new method of interpolation |series=Werke |location=Göttingen, Germany |publisher=Königlichen Gesellschaft der Wissenschaften zu Göttingen |date=1866 |volume=3 |pages=265–303 |language=la, de}}</ref><ref name=Heideman84>Heideman, M. T., D. H. Johnson, and [[C. Sidney Burrus|C. S. Burrus]], "[https://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1162257 Gauss and the history of the fast Fourier transform]," IEEE ASSP Magazine, 1, (4), 14–21 (1984)</ref> Gauss did not analyze the asymptotic computational time, however. Various limited forms were also rediscovered several times throughout the 19th and early 20th centuries.<ref name=Heideman84/>  FFTs became popular after [[James Cooley]] of [[International Business Machines|IBM]] and [[John Tukey]] of [[Princeton University|Princeton]] published a paper in 1965 reinventing<ref name=Heideman84/> the algorithm and describing how to perform it conveniently on a computer.<ref name=CooleyTukey65>{{cite journal |last1=Cooley |first1=James W. |first2=John W. |last2=Tukey |title=An algorithm for the machine calculation of complex Fourier series |journal=[[Mathematics of Computation|Math. Comput.]] |volume=19 |issue= 90|pages=297–301 |year=1965 |doi=10.2307/2003354 |jstor=2003354 |doi-access=free }}</ref>

Tukey reportedly came up with the idea during a meeting of President Kennedy's Science Advisory Committee discussing ways to detect [[nuclear testing|nuclear-weapon tests]] in the [[Soviet Union]] by employing seismometers located outside the country. These sensors would generate seismological time series.  However, analysis of this data would require fast algorithms for computing DFTs due to the number of sensors and length of time. This task was critical for the ratification of the proposed nuclear test ban so that any violations could be detected without need to visit Soviet facilities.<ref>{{cite journal |last1=Cooley |first1=James W. |first2=Peter A. W. |last2=Lewis |first3=Peter D. |last3=Welch |title=Historical notes on the fast Fourier transform |journal=IEEE Transactions on Audio and Electroacoustics |volume=15 |issue=2 |pages=76–79 |year=1967 |doi=10.1109/tau.1967.1161903 |url=http://www.ece.ucdavis.edu/~bbaas/281/papers/CooleyLewisWelch.1967.HistNotesFFT.pdf|citeseerx=10.1.1.467.7209 }}</ref><ref>Rockmore, Daniel N., ''Comput. Sci. Eng.'' '''2''' (1), 60 (2000). [http://www.cs.dartmouth.edu/~rockmore/cse-fft.pdf The FFT — an algorithm the whole family can use] Special issue on "top ten algorithms of the century "{{cite journal |author=Barry A. Cipra |title=The Best of the 20th Century: Editors Name Top 10 Algorithms |journal=SIAM News |volume=33 |number=4 |url=http://amath.colorado.edu/resources/archive/topten.pdf |access-date=2009-03-31 |url-status=dead |archive-url=https://web.archive.org/web/20090407080904/http://amath.colorado.edu/resources/archive/topten.pdf |archive-date=2009-04-07 }}</ref>  Another participant at that meeting, [[Richard Garwin]] of IBM, recognized the potential of the method and put Tukey in touch with Cooley. However, Garwin made sure that Cooley did not know the original purpose. Instead, Cooley was told that this was needed to determine periodicities of the spin orientations in a 3-D crystal of [[helium-3]].  Cooley and Tukey subsequently published their joint paper, and wide adoption quickly followed due to the simultaneous development of [[Analog-to-digital converter]]s capable of sampling at rates up to 300&nbsp;kHz.

The fact that Gauss had described the same algorithm (albeit without analyzing its asymptotic cost) was not realized until several years after Cooley and Tukey's 1965 paper.<ref name=Heideman84/>  Their paper cited as inspiration only the work by [[I. J. Good]] on what is now called the [[prime-factor FFT algorithm]] (PFA);<ref name=CooleyTukey65/> although Good's algorithm was initially thought to be equivalent to the Cooley–Tukey algorithm, it was quickly realized that PFA is a quite different algorithm (working only for sizes that have [[relatively prime]] factors and relying on the [[Chinese remainder theorem]], unlike the support for any composite size in Cooley–Tukey).<ref>James W. Cooley, Peter A. W. Lewis, and Peter W. Welch, "Historical notes on the fast Fourier transform," ''Proc. IEEE'', vol. '''55''' (no. 10), p. 1675–1677 (1967).</ref>