* Cris Moore <moore@santafe.edu> [Aug 29. 2014 08:45]:
Indeed. Here's are two nice pieces on Gauss, the FFT, and the orbits of Juno and Pallas:
http://www.cs.dartmouth.edu/~rockmore/cse-fft.pdf http://www.cis.rit.edu/class/simg716/Gauss_History_FFT.pdf
To be fair, Gauss never derived O(n log n) for large integer n (with lots of prime factors). But he did understand that a Fourier transform over N=pq points can be treated as p Fourier transforms over q points each, just as Cooley and Tukey did.
- Cris
James W.\ Cooley, Peter A.\ W.\ Lewis, Peter D.\ Welch, {Historical Notes on the Fast Fourier Transform} Proceedings of the IEEE, vol.55. no.10, pp.1675-1677, (October-1967) http://148.204.64.201/paginas%20anexas/voz/articulos%20interesantes/IEEE%20T... reprint: http://www.signallake.com/innovation/FFTHistoryJun67.pdf C.\ Sidney Burrus: {Notes on the FFT}, unpublished, (29-September-1997) <--= date may be incorrect http://jjj.de/fft/fftnote.txt
[...]