# 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?

-
Did the 1965 Cooley-Tukey paper use the expression? Else, does Huang quote this 1966 paper: cis.rit.edu/class/simg716/FFT_Fun_Profit.pdf ? –  Francois Ziegler Jun 1 '12 at 18:01
Why is this a [big-list]? –  François G. Dorais Jun 1 '12 at 18:37
I thought it was because it was fast. –  Spice the Bird Jun 1 '12 at 18:45
Huang's paper is satirical. It's called FFT because the Fourier transform "may be computed much more rapidly than by other algorithms" according to Gentleman & Sande. –  Zack Wolske Jun 1 '12 at 18:54
So what is this question asking for? It's called the Fast Fourier transform because its a fast method of calculating a Fourier transform. What else do you want from this question? Is it really a question? –  George Lowther Jun 1 '12 at 21:09

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"."

-
The Fast Fourier Transform--for Fun and Profit was published in November, 1966. Also, there is a paper from L.E. Alsop and A.A. Nowroozi, Faster Fourier Analysis, published in November, 1966, on Journal of Geophysics Research, No. 22, pp. 5482-5483. Unfortunatelly, I have no access to this paper. –  Papiro Jun 4 '12 at 17:37
In case anyone does: dx.doi.org/10.1029/JZ071i022p05482 –  Francois Ziegler Jun 4 '12 at 17:50
@Francois: I got the paper from Alsop and Nowroozi!! On page 5482, we have The data were analyzed not only with the 'fast Fourier transform' but also with a Fourier analysis program prepared by one of the authors (A.A.N), and The amplitudes obtained by the two programs with the known amplitudes are comparedin Table 1. The fast Fourier transform is slightly more accurate... This paper was published on November 15, 1966 but received on July 11, 1966. There is only one reference: Cooly-Tukey's paper "An algorithm for the machine...". –  Papiro Jun 11 '12 at 15:05
Fast Fourier Transforms: for fun and profit was published in Proceeding AFIPS '66 (Fall) Proceedings of the November 7-10, 1966, fall joint computer conference Pages 563-578 ! –  Papiro Jun 11 '12 at 15:14

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.

-
"Satirical mode on" is indicated by symbol :-) in my question. Thanks! –  Papiro Jun 1 '12 at 19:17
boop.org/jan/justso/rhino.htm –  Will Jagy Jun 1 '12 at 20:30
great Soviet mathematician Danisovich Cooleytusky Erm... Does somebody really think this sounds like a Russian/Jewish/Georgean/Armenian... name? "Danisovich" can pass for a patronym of somebody from one of Southern republics (though "Denisovich" would be much better) but the total lack of the first name and the improbable last name ("Coolatovsky" is the closest believable approximation I can think of) certainly diminish the credibility of the story. :) On the other hand, I once read the phrase "the famous Russian mathematician Tsebysup". I'll let you try to figure out who was meant... –  fedja Jun 2 '12 at 1:47
@fedja: was he the older brother of Tsebyinf? –  Igor Rivin Jun 2 '12 at 14:17
(Though of course, "like everything else", the FFT was discovered by Gauss.) –  Emilio Pisanty Jun 3 '12 at 15:14