I just want to add, because some people might find it interesting, that a version of the fast Fourier transform was already known to Gauss (though not published in his lifetime). More info can be found in the article "Gauss and the history of the fast Fourier transform" by T. Michael.