Gauss and the history of the fast Fourier transform (Q1065775)

The fast Fourier transform algorithm as a means of calculating the discrete Fourier transform was published in 1965 by \textit{J. W. Cooley} and \textit{J. W. Tukey} in the paper ''An algorithm for the machine calculation of complex Fourier series'' [Math. Comput. 19, 297-301 (1965; Zbl 0127.090)]. It is considered to be a turning point in digital signal processing and in certain areas of numerical analysis. After its publication, some similar algorithms were discovered in older literature of the 20th century, until in 1977 \textit{H. H. Goldstine}, in his ''History of numerical analysis from the 16th through the 19th century'' (1977; Zbl 0402.01005), attributed an algorithm of this kind to C. F. Gauss. This caused the authors to trace the history of Fourier series coefficient calculation back into the 18th and 19th centuries. Their findings are summarized in the following paragraph (p. 272); ''This investigation has once again demonstrated the virtuosity of Carl Friedrich Gauss. In addition, it has shown how certain problems can be timeless, but that their solution can be rediscovered again and again. Burkhardt pointed out this algorithm in 1904 and Goldstine suggested the connection between Gauss and the FFT in 1977, but both of these went largely unnoticed, presumably because they were published in books dealing primarily with history. It was shown that various attempts at efficient algorithms were used in Great Britain and elsewhere in the 19th century, but were unrelated to the work of Gauss and were, in fact, not as general or well- formulated as Gauss' work. Almost one hundred years passed between the publication of Gauss' algorithm and the modern rediscovery of this approach by Cooley and Tukey''.