Hacker News Reader

An Algorithm for the Machine Calculation of Complex Fourier Series

James W. Cooley and John W. Tukey

Mathematics of Computation Vol. 19, No. 90 (Apr., 1965), pp. 297-301

https://www.jstor.org/stable/2003354

Apparently this FFT was first discovered by Gauss (1805). http://www.cis.rit.edu/class/simg716/Gauss_History_FFT.pdf

As a follow-up, let me recommend Püschel & Moura (2006) “Algebraic Signal Processing Theory”, https://arxiv.org/pdf/cs/0612077.pdf and Püschel’s other papers about similar topics.

Or in a different direction, DJB (2008), “Fast multiplication and its applications”, http://cr.yp.to/lineartime/multapps-20080515.pdf

Interesting to note that Fourier's two works were published in 1807 and 1822, so that work by Gauss also predates Fourier.

Reply on news.ycombinator.com