4
$\begingroup$

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?

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ 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 ? $\endgroup$
    – Francois Ziegler
    Jun 1, 2012 at 18:01
  • 1
    $\begingroup$ Why is this a [big-list]? $\endgroup$
    – François G. Dorais
    Jun 1, 2012 at 18:37
  • 11
    $\begingroup$ I thought it was because it was fast. $\endgroup$
    – Spice the Bird
    Jun 1, 2012 at 18:45
  • 3
    $\begingroup$ 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. $\endgroup$
    – Zack Wolske
    Jun 1, 2012 at 18:54
  • 2
    $\begingroup$ 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? $\endgroup$
    – George Lowther
    Jun 1, 2012 at 21:09

2 Answers 2

Reset to default
5
$\begingroup$

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

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – Papiro
    Jun 4, 2012 at 17:37
  • $\begingroup$ In case anyone does: dx.doi.org/10.1029/JZ071i022p05482 $\endgroup$
    – Francois Ziegler
    Jun 4, 2012 at 17:50
  • $\begingroup$ @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...". $\endgroup$
    – Papiro
    Jun 11, 2012 at 15:05
  • $\begingroup$ 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 ! $\endgroup$
    – Papiro
    Jun 11, 2012 at 15:14
5
$\begingroup$

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.

Improve this answer
$\endgroup$
8
  • $\begingroup$ "Satirical mode on" is indicated by symbol :-) in my question. Thanks! $\endgroup$
    – Papiro
    Jun 1, 2012 at 19:17
  • 1
    $\begingroup$ boop.org/jan/justso/rhino.htm $\endgroup$
    – Will Jagy
    Jun 1, 2012 at 20:30
  • 1
    $\begingroup$ 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... $\endgroup$
    – fedja
    Jun 2, 2012 at 1:47
  • 1
    $\begingroup$ @fedja: was he the older brother of Tsebyinf? $\endgroup$
    – Igor Rivin
    Jun 2, 2012 at 14:17
  • 1
    $\begingroup$ (Though of course, "like everything else", the FFT was discovered by Gauss.) $\endgroup$
    – Emilio Pisanty
    Jun 3, 2012 at 15:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.