Editing Fast Fourier transform (section)

==History==
The development of fast algorithms for DFT was prefigured in [[Carl Friedrich Gauss]]'s unpublished 1805 work on the orbits of asteroids [[2 Pallas|Pallas]] and [[3 Juno|Juno]]. Gauss wanted to interpolate the orbits from sample observations;<ref name="Gauss_1866"/><ref name="Heideman_Johnson_Burrus_1985"/> his method was very similar to the one that would be published in 1965 by [[James Cooley]] and [[John Tukey]], who are generally credited for the invention of the modern generic FFT algorithm. While Gauss's work predated even [[Joseph Fourier]]'s 1822 results, he did not analyze the method's [[Computational complexity|complexity]], and eventually used other methods to achieve the same end.

Between 1805 and 1965, some versions of FFT were published by other authors. [[Frank Yates]] in 1932 published his version called ''interaction algorithm'', which provided [[Fast Walsh–Hadamard transform|efficient computation of Hadamard and Walsh transforms]].<ref name="Yates_1937"/> Yates' algorithm is still used in the field of statistical design and analysis of experiments. In 1942, [[G. C. Danielson]] and [[Cornelius Lanczos]] published their version to compute DFT for [[x-ray crystallography]], a field where calculation of Fourier transforms presented a formidable bottleneck.<ref name="Danielson_Lanczos_1942"/><ref name="Lanczos_1956"/> While many methods in the past had focused on reducing the constant factor for <math display="inline">O(n^2)</math> computation by taking advantage of symmetries, Danielson and Lanczos realized that one could use the periodicity and apply a doubling trick to "double [{{mvar|n}}] with only slightly more than double the labor", though like Gauss they did not do the analysis to discover that this led to <math display="inline">O(n \log n)</math> scaling.<ref name="Cooley_Lewis_Welch_1967"/> In 1958, [[I. J. Good]] published a paper establishing the [[prime-factor FFT algorithm]] that applies to discrete Fourier transforms of size <math display="inline">n=n_1 n_2</math>, where <math>n_1</math> and <math>n_2</math> are coprime.<ref>{{Cite journal |last=Good |first=I. J. |date=July 1958 |title=The Interaction Algorithm and Practical Fourier Analysis |url=https://academic.oup.com/jrsssb/article/20/2/361/7027226?login=false |journal=Journal of the Royal Statistical Society, Series B (Methodological) |volume=20 |issue=2 |pages=361–372 |doi=10.1111/j.2517-6161.1958.tb00300.x}}</ref>

James Cooley and John Tukey independently rediscovered these earlier algorithms<ref name="Heideman_Johnson_Burrus_1985"/> and published a [[Cooley–Tukey FFT algorithm|more general FFT]] in 1965 that is applicable when {{mvar|n}} is composite and not necessarily a power of 2, as well as analyzing the <math display="inline">O(n \log n)</math> scaling.<ref name="Cooley_Tukey_1965"/> Tukey came up with the idea during a meeting of [[President Kennedy]]'s Science Advisory Committee where a discussion topic involved detecting nuclear tests by the Soviet Union by setting up sensors to surround the country from outside. To analyze the output of these sensors, an FFT algorithm would be needed. In discussion with Tukey, [[Richard Garwin]] recognized the general applicability of the algorithm not just to national security problems, but also to a wide range of problems including one of immediate interest to him, determining the periodicities of the spin orientations in a 3-D crystal of Helium-3.<ref name="Cooley_1987"/> Garwin gave Tukey's idea to Cooley (both worked at [[Thomas J. Watson Research Center|IBM's Watson labs]]) for implementation.<ref name="Garwin_1969"/> Cooley and Tukey published the paper in a relatively short time of six months.<ref name="Rockmore_2000"/> As Tukey did not work at IBM, the patentability of the idea was doubted and the algorithm went into the public domain, which, through the computing revolution of the next decade, made FFT one of the indispensable algorithms in [[digital signal processing]].