How the Fast Fourier Transform got its name In 1971, T.S. Huang published a paper in IEEE Computer, May-June, pp.15, called How the Fast Fourier Transform Got its Name, available here. 
At the bottom of the paper, he wrotes: "The Chinese emperor's name was Fast, so the method was called the Fast Fourier Transform" :-)
The question is: there is another version for FFT's name? First time the word FAST was used?
 A: Turning my comment above into an answer, for those who don't have acces to the article.
Huang's one page paper is satirical, and explains why the algorithm is named after what is does instead of who invented it. He includes the names of all the major influential people (Cooley, Tukey, Danielson, Lanczos, Good), and describes an international committee who make a list of possible names and their acceptability to different groups. For example, he writes: "The British liked the term 'the Good Scheme,' because they said after all the scheme was very good." and "the Russians said they would go along with the name Danielson-Cooley-Tukey algorithm, because the algorithm was actually invented by the great Soviet mathematician Danisovich Cooleytusky." The Chinese interrupt to say it was really invented 4000 years ago, like everything else, and so it ends up being named after a (fictional) Chinese emporer.
The Gentleman and Sande article in the comments to the question ("... for fun and profit") explains that it is named for what it does, and goes on to detail how it compares to other algorithms.
A: I think the Gentleman-Sande paper Fast Fourier Transforms--for Fun and Profit (1966) is the first where the term appears in writing. A strong hint is that they put it in quotes the first few times, and then drop the quotes. But that also hints at the term having already been used orally before.
On p. 565 they clearly state the obvious reason for the name: "The total number of operations is now proportional to $AB(A+B)$ rather than $(AB)^2$ as it would be for a direct implementation of the definition, hence the name "Fast Fourier Transform"."
