text:
Talk:Fast Fourier transform

old comments on citations
Hey, does anyone have an issue number for the citation? The citation reads:

Cooley, James W., and John W. Tukey, 1965, "An algorithm for the machine calculation of complex Fourier series," Math. Comput. 19: 297–301

But there is no issue number.

 * A scan of the paper (of uncertain legality) can be found here. I believe it was in the April issue, but strangely enough the scanned pages don't list the journal issue or volume.  In any case, the volume and page number uniquely identify the article, and should be sufficient to look it up in your library.  —Steven G. Johnson 21:59, 2 April 2007 (UTC)

The "Other FFT Algorithms" segment is just an unreadable blob of text; I've separated the algorithms out (I think), which doesn't look as nice but is easier to read. Frankly, however, the whole thing ought to be rewritten for coherency, or expanded and put into its own section. I'm not qualified to do either of those things.
 * I think breaking this into more than three paragraphs is overkill. As for expanding it, any additional information about the FFT algorithms in question should go in a separate article, like for Prime-factor FFT algorithm and Rader's FFT algorithm. —Steven G. Johnson 23:58, 29 May 2006 (UTC)

More information on 2d or 3d FFT's would be super.

Alex.Szatmary

 * Done. At least as a start (the fancier multidimensional algorithms such as vector-radix could eventually use their own pages).  —Steven G. Johnson 04:41, August 23, 2005 (UTC)

More information about the practical uses of FFT (e.g. how it is used for digital signal processing) would be very useful. If I ever find out what it does, I may write it up myself... Jevon 12:11, 23 November 2005 (UTC)

 * As is described in the first paragraph, information about applications belongs in discrete Fourier transform. —Steven G. Johnson 16:34, 23 November 2005 (UTC)
 * Ramčević@gmail.com 178.237.217.117 (talk) 12:06, 6 April 2023 (UTC)

in finite fields
The whole article seems to address floating-point arithmetics as an approximation to the complex field.

However, the same algorithms may be used in any field where there is a nth prime root of the unit, where n is the length of the vector, including finite fields GF(pk). Since the multiplicative group of a finite field is cyclic, the condition for the existence of such a root is n | pk-1. If k=1, such a field is easily implementable in machine by modular arithmetics.

There is an algorithm for multiplying long integers by
 * consider them written in base $$\beta$$: $$a=\sum a_k.\beta^k$$ and $$b=\sum b_k.\beta^k$$, as polynomials
 * transforming them by FFT modulo p
 * writing the convolution product $$a.b=\sum c_k.\beta^k$$ where $$c_k=\sum_{j=0}^k a_j.b_{k-j}$$
 * computing this convolution product by inverse FFT of the product of the two FFTs
 * doing a little carrying.

A little web search brings up: J. M. Pollard, Mathematics of Computation, Vol. 25, No. 114. (Apr., 1971), pp. 365-374. Stable URL: http://links.jstor.org/sici?sici=0025-5718%28197104%2925%3A114%3C365%3ATFFTIA%3E2.0.CO%3B2-U

I'm not an expert in the field, so I don't think comfortable writing about this. I'll look how GNU MP does it. David.Monniaux 22:07, 13 October 2006 (UTC)

 * Only one section of the article discusses floating-point approximation, so I'm not sure why you're saying that the "whole article" is concerned with this. However, it's true that the article is concerned with algorithms for the discrete Fourier transform over vectors of complex numbers.   It's certainly true that many of the algorithms have direct analogues for any finite field (although I can give counter-examples of some that can't, such as the Rader-Brenner algorithm); in particular, those algorithms that only use the fact that $$\omega_N$$ is a primitive root of unity (e.g. Cooley-Tukey, PFA, Rader...) are generalizable in this way.  But such transforms are generally given different names, like the number theoretic transform. —Steven G. Johnson 22:49, 13 October 2006 (UTC)

 * I've added a brief mention of such generalizations in the introductions. Any further details belong in articles like number theoretic transform.  —Steven G. Johnson 23:02, 13 October 2006 (UTC)

 * Ah, interesting. I actually didn't know different names were used in English (I learned mathematics in French :-) ). David.Monniaux 08:27, 14 October 2006 (UTC)

example
Past century, I was frustrated with complexity of FFT progtams suggested in the literature. I believe, beginners can add all the accessories and improvements, if the short algorithm alreaady works. So, I add the short portable example. If you can write even shorter copylefted example, it may be even better. dima 03:23, 24 January 2007 (UTC)

 * I removed this. First, Wikipedia is not a code repository, and using a particular programming language (as opposed to English pseudo-code) is inappropriate in a mathematical article.  Second, it makes the common mistake of confusing an "FFT algorithm" (which is usually considered in the literature to be an abstract decomposition of the DFT) with an "FFT implementation". Third, an example of the Cooley-Tukey algorithm would belong on Cooley-Tukey FFT algorithm, not here.  Fourth, that page already gives the radix-2 example, but as math and English, not C++ code.  Fifth, your code was far from minimal.  Here is a shorter (but still not minimal) example in C (using the C99 complex type) that you would call with , for   a power of 2:

void rec_fft(int sign, int N, complex double *x, complex double *y, int is, int os) {     if (N == 1) *y = *x; else { int N2 = N/2; rec_fft(sign, N2, x, y, is*2, os); rec_fft(sign, N2, x+is, y+os*N2, is*2, os); complex double omega = 1.0, omega1 = cexp(sign * I * 6.2831853071795864769 / N); for (int i = 0; i < N2; ++i) { complex double a = y[os*i], b = omega * y[os*(i + N2)]; y[os*i] = a + b;               y[os*(i + N2)] = a - b;                omega *= omega1; }     } }

 * (Making the code work out-of-place, and recursively, allows you to basically copy the two-line mathematical derivation of the radix-2 case, and leads to the simplest implementations because you don't have to worry about bit-reversal etc. It is not nearly as fast as a highly optimized code, but then again no textbook radix-2 FFT is remotely optimal these days.)  If you want a code library that is pretty short and simple and of reasonable speed, Google "kissfft".

 * I would also disagree that "beginners can add all the accessories and improvements". A typical textbook radix-2 FFT implementation is an extremely poor starting point for a full-featured, highly-optimized FFT program.

 * —Steven G. Johnson 07:00, 25 January 2007 (UTC)

I am not sure why we need both a Fast Fourier transform and Cooley-Tukey FFT algorithm, but I do believe that a simple C program could be useful in one of them. I believe C is popular enough that it is easier to read C code than the usual pseudo code. Note that the recursive form is convenient for understanding, but not the way to write a production algorithm. It does make a good example of the recursive nature of the FFT, and it is nice to have a simple one to play with, where one can cut and paste, and try out on their own computer. Gah4 (talk) 08:13, 24 October 2015 (UTC)

 * We need two articles because Cooley–Tukey is only one of many algorithms for the FFT, and FFT algorithms are a vast subject (with thousands of papers about them). And, in fact, the recursive form is [an excellent way](https://cnx.org/contents/Fujl6E8i@5.8:ulXtQbN7@15/Implementing-FFTs-in-Practice) to write a [production FFT algorithm](http://fftw.org/). — Steven G. Johnson (talk) 21:15, 19 May 2021 (UTC)

Example
Dear Steven G. Johnson.

You could declare that any examples of algorithmic codes are prohibited at Wiki, and I would understand;

but you seem to believe, that the kissfft, as well as your example, are simpler than the example you have removed.

I just checked the kissfft; the "minimal" version requires several files insteaad of two;

and the files required are significantly longer than the example you removed;

even the istructiuons of use in the README file are 4792 byte long.

In addition, the use is not straight-forward; it requires skills and/or assistance, because some additional files are supposed to be pre-installed at the user's computer, for example, the bench-user.h header required by the shortest example doit.c

As for the example you suggest, it requires 6 arguments instead of 3, and therefore is not simpler. I would recommend your example to the article recursion.

Sincerely, Dima.

 * I didn't say that kissfft was simpler than the code you posted; kissfft is more full-featured, faster, and supports non-power-of-two sizes, among other things, and so it is more complicated. But it is still pretty simple and easy to learn from; while still being vastly better than a textbook radix-2 code.  (Nor does it require any code to be preinstalled; you're apparently confused because the kissfft author included an optional test program based on the benchfft framework.  Kissfft only requires you to compile one .c file, along with two .h files; everything else is optional extras.)  I mentioned it to help you since you claimed to be frustrated with the complexity of what you found on the web.  (You can find zillions of textbook radix-2 FFT codes on the web and usenet similar to the one you posted, by the way—i.e. nested bit-reversal loops followed or preceded by nested butterfly loops—some of it dating back to the 1960s.  Nowadays, however, these are mainly useful as pedagogical exercises and bear little resemblance to the programs actually used for serious numerical calculations.)

 * Regarding the code I posted above as an example, you have a very odd way of measuring complexity if you measure it by the number of arguments, as opposed to by the number of instructions. And the whole idea of most FFT algorithms is based on recursion; implementations that do not use recursion explicitly and work in-place are certainly possible and even common, but are more complicated (require more instructions and are conceptually less direct) than the simplest non-recursive out-of-place versions.  If you want to actually understand FFTs and why they work, as opposed to cutting-and-pasting code, you need to understand recursion.  And if you don't need to understand the guts of FFTs, and just want to use them to do something, then it hardly matters whether the code is 5 lines or 500 lines as long as it has the features you require and a reasonable API.

 * (Not to mention the fact that any user who has trouble with a 5k README file is unlikely to be capable of using a fast Fourier transform in a reasonable way, in my opinion.)

 * In any case, as I said, Wikipedia is not a code repository, and it doesn't matter whether we agree on the relative merits of different FFT implementations because none of them belongs in the article. Nor are Wikipedia articles on mathematical subjects intended to address the problem of installing and compiling and calling source code on a user's computer.  Creating a code repository for numerical code, while a worthwhile mission  (and being addressed elsewhere, see e.g. GNU Scientific Library) is quite a different problem from that of creating an encyclopedia.  (I didn't say that algorithmic source code is "prohibited" on Wikipedia, just that it's not appropriate here. Code fragments would be appropriate, for example, in an article on programming languages or techniques.)  Of course, if you want to create your own numerical code library (somewhere else, perhaps on Wikibooks) for "minimal" simplistic numerical codes, as a pedagogical tool, knock yourself out.

 * —Steven G. Johnson 04:23, 27 January 2007 (UTC)

Dear Steven. Thank you for the explanaiton. I had to modify your code (the compiler complained about "complex double"), and the modification below seems to work well. Is such modification portable? using namespace std; void rec_fft(int sign, int N, complex *x, complex *y, int is, int os) { if (N==1) *y = *x; else{ int N2 = N/2; rec_fft(sign, N2, x, y, is*2, os); rec_fft(sign, N2, x+is, y+os*N2, is*2, os); double f=sign*2*M_PI/N; complex omega =1., omega1=complex (cos(f), sin(f)); for(int i=0; i<N2; ++i) {      complex a = y[os*i], b = omega * y[os*(i + N2)]; y[os*i] = a + b;               y[os*(i + N2)] = a - b;                omega *= omega1; }     } } main{ int n,N=8,m=1; //play with values of N and m;        complex x[N],y[N]; for(n=0;n<N;n++){x[n]=complex (cos(2*M_PI/N*n),sin(-2*M_PI/N*n));} rec_fft(1,N,x,y,1,1); for(n=0;n<N;n++){printf("%1d %6.3f %6.3f %6.3f %6.3f\n",                       n,x[n].real,x[n].imag,y[n].real,y[n].imag);} } I agree with your argumentation and I like your code. If it is still too large for Wiki, will you consider to post your example somewhere, and to supply the link at the FFT article? For Wiki, it is better than "kissfft": such example requires neither installation nor instruction. Sincerely, dima 05:23, 27 January 2007 (UTC)
 * 1) include

 * (The reason you had to modify it is that I posted C code, whereas you are using C++. C++ does not support C's complex-number types.)

 * No, I don't think it's appropriate for Wikipedia. This is an encyclopedia article on a mathematical topic, not an article on C or C++ programming.  Readers can follow the links, or use Google, if they want code in their language of choice.  As for posting it somewhere else and linking to it, that's a bit too much like sneaking around Wikipedia policy.  For Wikipedia to cite or link to a web page, it should generally be notable already.  That is, if you create a page with the above code, and it becomes popular (e.g. lots of people link to it, it ranks high in Google, etcetera), then Wikipedia can link to it.  Using Wikipedia to try and make a site popular is linkspam and is prohibited by policy.

 * Also, the code above still requires installation—you still need to compile it. And it still requires instruction: you have to clearly define what its inputs and outputs are, at least (and remember that there are several different conventions for the DFT).  Moreover, who is the audience?  If you just want to use an FFT code, then I would strongly recommend something more sophisticated.  And if the above code is intended for instructional purposes, then it needs a lot more explanation because you have to explain how the code works.

 * (I hereby release my code above into the public domain, by the way. Feel free to use it wherever you want outside Wikipedia.)

 * —Steven G. Johnson 07:26, 27 January 2007 (UTC)

To Steven G. Johnson, Hello - I think this isn't the place for a debate on what Wikipedia is for, but I feel I must speak up with regard to the inclusion of a bit of C++/C code to illustrate an implementation of the FFT algorithm. First of all, FFT is not purely a "maths topic" - it is a maths implementation of a very important tool, and understanding how it works or how it can be applied is vital to many of us who use Wikipedia as a resource for knowledge. Too many articles on Wikipedia dealing with technical (and particularly mathematical) topics are so badly written as to leave the reader stunned and frustrated. The C example here can only help and does nothing to contaminate the topic in any way. If one leaves Wikipedia more confused than when they arrived, something is wrong. All the academic writing styles in the world are of no use whatsoever if they cannot convey simple concepts to the reader who is interested in the topic. I encourage fully the contributions of -every- reader of Wikipedia who feels that a few examples or explanations in styles other than that in which the article was first written would go a long way to satisfy the needs of people who take the trouble to come here and read about the topic in question. It is all about language - and as it stands, the language used in most articles of this kind leaves a lot to be desired. A C code example is just another language like maths short-hand which this article is riddled with. Even pure maths and TeX shorthand is not the only way of illustrating an algorithm. For those who are not familiar with maths shorthand, you might just as well write the article in Chinese. It would still be valid but it wouldn't be understood to those who only know English. With kind regards- Sam, UK — Preceding unsigned comment added by 46.233.70.199 (talk) 19:20, 19 February 2014 (UTC)

Separate pages for code examples?
Why not add create a Wikipedia article called "Fast Fourier Transform Example" and link there?

I think the goal of the project is to preserve human knowledge. It does not seem right to me to post example elsewhere. It is guaranteed to disappear / be irrelevant.

Above looks simple and easy to understand, I'm all for keeping it. Separately is fine, if that is better stylistically. —Preceding unsigned comment added by 68.162.147.222 (talk) 19:51, 20 December 2007 (UTC)

The FFT acronym
On the Polish Wikipedia, we had a discussion regarding the proper term for the FFT algorithm. It turned out that transformata, which some believed is closer in meaning to the English word transform, was more frequently used, even though the other word, transformacja (transformation, translated literally), was more appropriate as the name for FFT. Now I'm in doubt about which of the words: transformation or transform is the proper term for the operator or operation that maps a vector to its discrete Fourier transform. Is there a distinction between the operator (which we on pl-wiki agreed was closer to transformation) and its result, or is transform used in both meanings? Note that fast Fourier transformation is also used in English publications, online or otherwise (like the first entry in FFT). Safek (talk) 08:00, 1 May 2008 (UTC)

 * In English, "fast Fourier transform" is far more common than "fast Fourier transformation", but the two are used more or less interchangeably as far as I can tell. But English is a bit funny because "transform" was originally exclusively a verb, and acquired a noun usage sometime over the last 200 years according to the OED.  And, even in this sense, "transform" originally referred to the result of a transformation, but nowadays is used for the transformation itself (the "operator") too.  Of course, in English, "FFT" can also be used as an adjective, as in "FFT algorithm."  I have no idea what Polish does, but our usual practice on Wikipedia is to go with the most common usage, and accept the fact that living languages are often illogical.  Language and notation are ultimately determined by usage and convention; there is no absolute "right" and "wrong" unlike for mathematical facts.  —Steven G. Johnson (talk) 23:54, 1 May 2008 (UTC)

 * Thanks for your reply. It turns out Polish is undergoing the same process as English. However, it hasn't gone that far yet, so on pl-wiki we are trying to stand by the more accurate word and explain the difference between the words. Safek (talk) 12:37, 2 May 2008 (UTC)

FFT WTF
Can I be provocative? This is the worst article I have ever found on Wikipedia.

I have a decent understanding of mathematics and calculus. I am an experienced programmer. I have used Wikipedia as a source for explanations of programming techniques and algorithms which I have successfully coded up and put into action, including the manipulation of 3-d data and drawing complex shapes.

I would like to produce rough and ready frequency spectra and frequency/time plots for audio signals (bat calls) using a standard microprocessor (not a custom DSP chip).

I know that FFT is the usual technique for doing such analysis and hoped Wikipedia would start me on the right road.

The article doesn't even explain what FFT is in plain english.

It could start "Fourier transformation is a technique for analysing the frequency components of a signal. Fast fourier transform is a mathematical technique that allows this do be done rapidly using limited computing power, and as such is a basic building block for digital signal processing. The technique is a critical element to the past decade's explosion in applications using the real time digital processing of sounds and video, from mobile phones to high definition television." - but i don't know if that (which is my understanding) is correct or not.

Worse still, it doesn't explain any of the mathematics or theory in a non-mathematical way. It certainly doesn't explain how FFT lends itself to the processing of digital signals.

At the moment the article says "this subject is the province of graduate mathematicians only", which I feel is against the whole spirit of Wikipedia.

The Yowser (talk) 14:52, 8 October 2008 (UTC)

 * Well, the first line reference the Discrete Fourier Transform, and the first line of that page references the Fourier Transform. If you want to understand their use in signal processing, those are the article you should read.  Those still might not answer your questions, but this is not the right place.  Gah4 (talk) 02:31, 13 August 2009 (UTC)

... or perhaps I am thick?

 * The details of the specific algorithms are all described by sub-articles, so it's not surprising that you didn't find the "numerical recipe" you were looking for here.   As explained in the article, there are many, many FFT algorithms, and the purpose of this article is to give an overview of what is out there.  You probably want Cooley-Tukey FFT algorithm if you want a description of the most common specific algorithm in enough detail to implement it.   As for explaining the algorithm in a "non-mathematical way", it already says that the most common algorithm (Cooley-Tukey) is a divide-and-conquer algorithm that works by breaking a transform of size n down into smaller transforms, most commonly of size n/2; for any more detail than that, you need mathematics.  As for your proposed introduction, FFTs don't compute Fourier transforms in general, they only compute DFTs, so that's not appropriate here.  If the reader wants to learn about Fourier transforms, they should go to another article, as is pointed out explicitly in the introductory paragraph.  Your criticism would be a lot more useful if it wasn't addressed by things already explicitly stated in the article.  —Steven G. Johnson (talk) 15:06, 8 October 2008 (UTC)

 * Some of those criticisms accepted, and I fully accept that WP is not an "algorithm mine" (though I personally wish it was full of well commented pseudo-code examples!). But, surely, the following questions could be answered in a non-mathematical way:

What is FFT?

 * "an algorithm to compute the discrete Fourier transform (DFT) and its inverse". — Steven G. Johnson (talk) 19:33, 7 February 2013 (UTC)

What problems does it solve?

What does it tell you about a signal?

What information do you need on the signal and what information do you get?

 * All described in the article on discrete Fourier transform. It wouldn't be appropriate to duplicate that information here, which is why we write "see discrete Fourier transform for properties and applications of the transform". — Steven G. Johnson (talk) 19:33, 7 February 2013 (UTC)

What, in plain english, is the basic method of getting an FFT?

 * The simplest algorithm "is a divide and conquer algorithm that recursively breaks down a DFT of any composite size N = N1 N2 into many smaller DFTs of sizes N1 and N2."

In my mind a simple way would be to sample a signal at a regular frequency. You use a simple statistical technique to identify the size of the component of the signal at that frequency. You then extract that component, half the frequency and repeat the exercise. You end up with a histogram with groups f, f/2, f/4 ,f/8... each on representing the size of that component.

 * It sounds like you want information on the discrete Fourier transform (i.e. the mathematical operation that FFTs are a sophisticated algorithm for), not on FFTs. — Steven G. Johnson (talk) 19:33, 7 February 2013 (UTC)

Now there isn't enough information in the article for me to decide whether that is the case, or if I'm completely up the wrong tree.

Another example, you wouldn't have an entry for commutativity that had as its introduction "is a mathematical property of certain functions such that f(x,y)=f(y,x). Or would you?

You might want to check out podcasts of In Our Time (BBC Radio 4) to see how complex mathematical concepts can be described without recourse to any formulae at all - check out the programme on infinity. And there is, of course Godel, Escher, Bach though I don't expect every Wikipedian to reach that level of lucidity :)

Oh, and thanks for the Cooley-Tukey suggestion, but I already found that as part of a recursive loop around several articles ending 'FT' that all reference another article ending 'FT' for a proper explanation...

The Yowser (talk) 13:28, 9 October 2008 (UTC)
 * That is a problem with most math and science articles on WP, they are written for people that don't need to look up the subject.

Afterthought the article on Fourier Transformation is better than the others - I'm going to asd a link to it from the introduction, Although the 2002 article had pretty good introduction:

http://en.wikipedia.org/w/index.php?title=Fast_Fourier_transform&oldid=60732

The Yowser (talk) 13:59, 10 October 2008 (UTC)

 * (The 2002 article was simpler by being wrong. It assumed the only algorithm was Cooley-Tukey, and only described the radix-2 case.)

Another Terrible Wikipedia Article
The FFT is actually very simple and needs no Maths to explain, but this page is totally inaccessible to an intelligent layperson.

As Einstein said, “If you can't explain it to a six year old, you don't understand it yourself.” Gutta Percha (talk) 06:08, 16 October 2011 (UTC)

--- Have to agree: This article is totally incomprehensible to the layperson and doesn't even explain the purpose or give any practical uses by way of example. 1st April 2013 — Preceding unsigned comment added by 109.224.137.15 (talk) 22:30, 1 April 2013 (UTC)

I absolutely agree with the above sentiments. This page is full of jargon and completely out of line with Wikipedia's scope as listed here: [], particularly items 6, 7, and 8. I'm a fairly well educated person, although math isn't my specialty I have been exposed to lots of it. This article reads like an in-depth technical piece, completely inaccessible for someone who, for instance, saw the term "Fast Fourier transform" in a scientific paper's methods section and just wants to get a brief overview of what the technique does. There are other outlets for teaching or showcasing the depth of your knowledge about frequency analysis techniques. This, however, is Wikipedia. Sirenology (talk) 18:42, 6 May 2013 (UTC)

 * Not constructive. What, specifically, should the article explain, or explain differently?  Explaining the discrete Fourier transform and frequency analysis (the most common request) is outside of the scope of this article — you want the discrete Fourier transform and Fourier analysis articles for that.  For instance, we already write:
 * This operation is useful in many fields (see discrete Fourier transform for properties and applications of the transform)
 * We shouldn't duplicate discrete Fourier transform here; it would be like explaining why matrices are useful in the Strassen algorithm article, or what sorting is good for in the Quicksort article. — Steven G. Johnson (talk) 18:51, 6 May 2013 (UTC)

 * OK, first of all, thank you for your time and effort spent on this Wiki article. You are obviously very knowledgeable in this field and have made great contributions to this article.  My beef is that, when I go to the Wikipedia page on "Fast Fourier transform", I want to be able to read the article and gain some general context and understanding of the procedure, what it does, what are the applications.  Although I am not a mathematician or a statistician, I am capable of comprehending things if laid out clearly and in common language, as Wikipedia articles are supposed to be (see my citation above).  As it was written (before some edits earlier today), this article was useless to someone not familiar with the jargon.  I did find some very helpful posts on other websites (e.g., Stack Overflow) which accomplished exactly this.  SO my constructive criticism is---and this has already been accomplished to a degree by edits earlier today---you should create an overview paragraph that lays out, jargon free, what a FFT does.  A "for dummies", if you will.  Then the dummies could stop there and the mathematics students could read on.  Thank you again for your contributions- Sirenology (talk) 21:56, 6 May 2013 (UTC)

Numerical estimates
I strongly believe some simple numerical estimates should be included. Many of the readers who find this page will have no recollection of log, or how slowly it grows with N. This is very important; a fast car is twice as fast as a normal car, but a fast Fourier transform is a hundred times as fast.

Clearly, it cannot be stated that a *general* O(N^2) process is slower than an O(NlogN) process by N/log(N). But in this case we know (from decades of work) that the constants are quite near 1, so the calculation is justified. It's also quite reasonable in practice. If you implement the DFT in the obvious way (using a table for the coefficients), such as:

Then a tuned FFT (I tried fftw) is about 230 times faster than the code above for N=1024. Given that FFTw is a factor of several faster than naive FFTs such as Numerical Recipes, the speedups of all realistic FFT implementations should be within a factor of a few of N/log2(N). So it's is quite realistic in practice. LouScheffer (talk) 04:28, 9 October 2008 (UTC)

 * Before trying this experiment, I looked for any experiments in the literature compaing the DFT and the FFT. I thought the early papers might have some, but could not find any.   In a way it's a tribute to the FFT that people only compare FFTs against each other, since they all beat DFTs by huge margins.  But in a very introductory article, likely to be read by (very) non-specialists, it would be great to say by how much.  I added some ballpark figures to the intro, but a reference would be nice.  LouScheffer (talk) 12:39, 9 October 2008 (UTC)

 * Another piece of evidence that numerical values may be helpful might be in "What Is the Fast Fourier Transform?", Proceedings of the IEEE, VOL. 55. NO. 10, October 1967. This is an introduction to the FFT, aimed at a technical audience, and includes the sentence "For example, if N = 1024= 210, then N . log N = 10 240[7][9]. Conventional methods for computing (1) for N = 1024 would require an effort proportional to N2 = 1 048 576, more than 50 times that required with the FFT."  Also, they felt they needed to footnote the calculation of log2(1024) - this is not obvious to everyone.  Of course this is only counting multiplies, assuming a simple FFT strategy, etc., but it's still helpful to see the big picture, IMO. LouScheffer (talk) 14:11, 9 October 2008 (UTC)

 * In what other mathematical article would one witness the argument, Yes, I know this analysis is wrong, but it happens to work out roughly okay in this particular case, so I'll present it anyway? The constant factors can vary by orders of magnitude depending on the implementation details, depending on which FFT algorithm is chosen, depending on the factorization of N, the size of N, etc.

 * Your insistence on saying "the FFT" goes to the heart of the intellectual bankruptcy of this whole approach. There are many FFT algorithms that are totally distinct and have totally different constant factors; talking about the absolute performance of "the FFT" is nonsense (albeit excusable in 1967 when the existence of other algorithms was not well appreciated; there are still plenty of people who make the same mistake today, but now it is indisputably a mistake, like the common notions that FFTs don't exist for prime sizes or that powers of 2 are always the fastest).  And even for a "single" algorithm like Cooley-Tukey, the performance easily varies by a factor of 20 between implementations, especially for large N.  And the "constant" factor in the N log N itself varies by a factor of 5 or more as N varies, e.g. when you go out of cache (see fftw.org/speed, which plots the "constant" factor vs. N).

 * In summary, based on one data point, you are putting numbers in the article that could easily be off by one or two orders of magnitude, depending on the circumstances. This kind of nonsense has no place in an encyclopedia article.

 * —Steven G. Johnson (talk) 15:55, 9 October 2008 (UTC)

 * Sure, what you are saying is true, and should be considered by anyone to whom FFT performance is important. However, Wikipedia should (I believe) first give the big picture, then the gory details.  The big picture is that FFTs are faster by *roughly* N/log(N), with all the caveats you mentioned.  Also, I suspect the average Wikipedia reader has less technical and mathematical background than an IEEE Proceeding reader of 1967, where they felt they needed a numerical example.  As a side note, I suspect you are one of the few people on the planet who would consider different FFT algorithms totally distinct; most folks, I surmise, might lump them in a common family when compared to, for example, singular value decomposition or gradient descent.LouScheffer (talk) 21:08, 9 October 2008 (UTC)

 * Would you therefore refer to "the" fast sorting algorithm, since all O(n log n) sorting algorithms solve the same problem (as opposed to SVD etc.)? No one does as far as I know, because everyone in CS knows there are many different sorting algorithms that achieve the same complexity—it's almost the first thing one learns about algorithms.  With FFTs, the difference is that one algorithm (Cooley-Tukey) is so dominant that few people are aware that there are very different ways to solve the same problem (and few people, even in DSP, really learn the details of any FFT algorithm to begin with); and, even for those who do know, often they are writing in a context where it is clear what algorithm they are referring to, so they can afford to be sloppy.  But of course, they are all in the same family: that's why we call them all fast Fourier transforms, even if none of them is the fast Fourier transform.

 * "Things should be simplified as much as possible, but no simpler." I agree that we should try to present the big picture, but I think we should try to avoid presenting analyses that are wrong. —Steven G. Johnson (talk) 22:56, 9 October 2008 (UTC)

Does anyone else have an opinion on these issues? If so, please weigh in! LouScheffer (talk) 21:08, 9 October 2008 (UTC)

Hi, Im just a grad student looking for information for a project, and I cannot find what is the physical meaning of the power spectrum for the FFT: I know how to calculate it with the complex conjugates, and I have found an interesting algoritmus, but no clue how to interpret the data. ThaNks guys1 —Preceding unsigned comment added by Minsk380 (talk • contribs) 12:38, 20 January 2009 (UTC)

Length of LEDE
Hi! My feeling is that the LEDE should hit all the main points, and be short enough to fit on one screen without scrolling. The longer lede version is better at this. Adding extra divisions, in my mind, makes it worse since it pushes introductory text off the first screen, where readers are most likely to see it. Note that many featured articles (see for example Hubble Space Telescope have ledes of this length. LouScheffer (talk) 11:04, 11 October 2008 (UTC)

 * I agree; a lede that fits comfortably without scrolling is perfectly fine, and it's not clear how the reader will be helped by breaking up the current lede. In any case, if you want to split it up, you can't simply add headers, you need to rewrite the text.  Just adding headers without changing the text breaks up the train of thought, and makes the lede inadequate because crucial information (e.g. a clear definition of FFTs) is relegated to a later section.  (If it really needed to be shortened, my inclination would be to put the explanation of how much slower O(N^2) is than O(N log N) into a subsection.  The main purpose of the lede should be to delineate the subject of the article.  But again, this would require some rewriting, not just adding headers and cut-and-paste.) —Steven G. Johnson (talk) 23:07, 11 October 2008 (UTC)

Oh Notation
"Θ(N2) to Θ(N log N) remains." Say. Shouldn't those thetas be capital letter Os?--72.75.86.157 (talk) 07:56, 16 October 2008 (UTC)

 * Technically, no. —Steven G. Johnson (talk) 15:12, 16 October 2008 (UTC)

 * But as the user points out we make it all the way through the article using Big Oh notation until this point. Does it really make sense to switch to a slightly different concept without comment, link, etc?  Thenub314 (talk) 06:50, 17 October 2008 (UTC)

 * I've added a comment and link. The problem is that saying FFTs reduce the complexity from O(N^2) to O(N log N) is literally false.  FFT algorithms are still O(N^2) in addition to being O(N log N), because "O" only denotes an upper bound.  —Steven G. Johnson (talk) 14:12, 17 October 2008 (UTC)

 * I am very confused by this second sentence. Big Theta implies Big-Oh, so saying the complexity is O(N log N) is true.  I agree that every worse upper bound is still an upper bound, so the algorithms are also O(N3), etc.  But there is nothing literally false about saying FFTs reduce the complexity from O(N^2) to O(N log N). Thenub314 (talk) 07:13, 18 October 2008 (UTC)

 * If you say that they reduce the complexity from O(N^2) to O(N log N), you are literally saying that they are no longer O(N^2), which is false. —Steven G. Johnson (talk) 20:02, 18 October 2008 (UTC)

About complexity
I have readed the article and I don't understand why the original transformation cost is O(N^2). It is just a sum for 0..N-1 so it should be O(N). If I want to compute X_i I just need to iterate N times. —Preceding unsigned comment added by 62.43.167.123 (talk) 16:47, 13 January 2009 (UTC)

 * Each output is a sum of N terms, so is O(N). But there are N outputs, so you need to do N sums, so it is N O(N) = O(N2).  —Steven G. Johnson (talk) 21:37, 22 May 2009 (UTC)

Huh?
Could someone please write a new opening paragraph with a more pedestrian explanation of what FFT is?

Reading this, I feel like an illiterate who can't count trying to read an advanced calculus book. —Preceding unsigned comment added by 208.127.100.174 (talk) 09:22, 22 August 2009 (UTC)
 * I also think that people with finished university education in mathematical or physical area do not need Wikipedia to read about FFT as they already know about it enough. For others the article seems getting unreadable Audriusa (talk) 13:53, 29 November 2010 (UTC)

One of the worst articles I've ever read
I'd like to pile on about how terrible this article is. I came here to refresh myself on FFTs, and this article is completely different from how FFT's are explained in the books and signal processing classes I've taken. It doesn't really define FFTs, or even explain how they eliminate computations, and is overly mathematical. It doesn't even mention FFT butterflies, or the W operator!

Let me make my suggestions: The FFTs are a set of algorithms which help reduce the number of calculations required for computing the DFT. In general, the FFT reduces the number of calculations by choosing parameters of the bank so that they are harmonically and symmetrically related, and consolidate the operations, namely the phase calculations. For example, if a bank's size is 4, then a phase rotation of 2*d_theta, which is 180 degrees, simply becomes a negative sign, while a phase rotation of 3*d_theta becomes -1*d_theta, eliminating 2 calculations through harmonic symmetry.

166.19.102.20 (talk) 13:35, 3 February 2011 (UTC)

Often in the DSP world, the term FFT is used where DFT would be mathematically correct. One should read the DFT page before this one, if one doesn't understand the idea of DFT. Most likely, the DFT page also references a Fourier Transform page, though Fourier Series is closer to correct. Gah4 (talk) 14:12, 3 February 2011 (UTC)

 * It also sounds like the anon didn't notice that there are sub-articles describing the specific algorithms; this article is necessarily less specific because it has to summarize all the algorithms. In many courses and textbooks, only the Cooley–Tukey FFT algorithm is described, often only for power-of-two sizes, so you may get the false impression that there is only one FFT algorithm — a clue to this mistake is the misleading phrase "the FFT".  If you come here expecting that false impression to be reinforced, you will be disappointed.  If you want information specifically on the Cooley–Tukey algorithm (which does talk about butterflies), you can read that sub-article.  — Steven G. Johnson (talk) 14:27, 3 February 2011 (UTC

Gauss
but it was later discovered (Heideman & Burrus, 1984) that those two authors had independently re-invented an algorithm known to Carl Friedrich Gauss around 1805 (and subsequently rediscovered several times in limited forms).': ''This is a wrong statement. In the Gauss paper there are no Fast Forier Transform, Discrete Fourier Transform, or even ordinary Fourier Transform --- everbody can see it in the Gauss paper undependetly on the Latin language used by Gauss, since all formulas are NOT in Latin.'' The source (Heideman & Burrus, 1984) isn't appropriate, since the paper was written not my mathematicians, published not in mathematical journal and didn't come the process of math.reviews. The authors evidently have no knowledges in computational complexity.However, even by formulas presented in Gauss work easy to see there are no any FFT algorithms there.Riemann'sZeta (talk) 09:27, 2 April 2011 (UTC)

 * First of all, this is original research, because your claims directly contradict the published research (Heideman & Burrus, who are world-renowned experts on fast Fourier transform algorithms). (By the way, most FFT research is published in IEEE and other engineering journals.)  Note also that many other published secondary sources echo the same information (for example, this millennial review article).  If you disagree, you are free to try to publish your own article in a reputable journal, but Wikipedia is not the place to push your iconoclastic views.

 * Second, I have a copy of Gauss's Theoria interpolationis notes (and I know some Latin), and it is easy to verify that he does very clearly describe trigonometric interpolation via a DFT and the inverse DFT, and he also very clearly describes a Cooley-Tukey FFT algorithm (he performs a radix-3 step to subdivide an N=12 transform into 3 N=4 transforms, and explicitly mentions the possibility of additional subdivisions for N with more factors). Of course, he doesn't call it a "Fourier" transform, and his notation is different from modern notation [he writes everything out in terms of sines and cosines, and doesn't use subscripts but instead uses primes (IIRC the cosine coefficients are $$\alpha'$$, $$\alpha$$, $$\alpha'$$ and so on)], but once you get past the notational differences the equivalence is clear.  (Oh, and by the way, if you read the Heideman & Burrus article they explain in great detail what Gauss is doing, and you can look at Gauss' notes to verify that Gauss is doing what they say he is.)  But I write this only for the information of other editors; I don't have to convince you, because the published secondary sources are absolutely unambiguous on this point and the WP:OR policy applies.

 * — Steven G. Johnson (talk) 17:32, 2 April 2011 (UTC)\

What you wrote --- it's nonsense! This is not Fast Fourier Transform! What you describe it's ordinary transformations of trigonometric series, it's possible to find analogius expressions in many Gauss works. You wrote Haidemann and Burrus are specialists in fast algorithms --- what other papers did they write before? — Preceding unsigned comment added by Riemann'sZeta (talk • contribs) 20:44, 4 April 2011 (UTC)

May be, it would be appropriate to write that there is an opinion (ref. to Heidemann and Burrus) that in the paper of Gauss (ref to this Gauss work + scan of this work in Latin, original work with all formulas) the prototype of the FFT is described. In such form you give a possibility to everybody to judge yourself. In the present form you misinform the readers!Riemann'sZeta (talk) 20:54, 4 April 2011 (UTC)

 * Computation of the coefficients of trigonometric interpolation for equispaced points is a discrete Fourier transform. If you don't understand this, you don't understand what the DFT is (or how trigonometric interpolation works).

 * C. S. Burrus has written hundreds of papers on signal processing, and is widely known for his papers on FFT algorithms. Heideman is also well known (e.g. for this paper).

 * The attribution of FFT algorithms to Gauss is not just the idiosyncratic opinion of two authors; it has been widely accepted in the field. I already mentioned the millenial review article by Rockmore, which cites it approvingly, but the paper has been cited dozens of other times.  Notably, Jim Cooley himself approvingly cited the Heideman and Burrus article, and agreed that earliest known FFT was due to Gauss: James W. Cooley, "The re-discovery of the fast Fourier transform algorithm,"  Mikrochimica Acta vol. 3, pp. 33–45 (1987).

 * — Steven G. Johnson (talk) 22:49, 4 April 2011 (UTC)

Additions to Bounds on Complexity and Operation Counts
I attempted to add a recent result on some FFT operation bounds proven by SAT solvers to the subsection "Bounds on Complexity and Operation Counts" but my changes were reverted due to conflict of interest. (I thought I was OK since the result refers to a peer-reviewed journal.) I'd appreciate review and possible inclusion by some independent person(s). You can see the additions I tried to make under the article history (changes on 6 December 2011 by Haynals). — Preceding unsigned comment added by Haynals (talk • contribs) 22:06, 6 December 2011 (UTC)

 * I agree that your paper, which is an unusual approach to this problem, seems worth mentioning in this context, and have added back a somewhat amended description. — Steven G. Johnson (talk) 04:13, 7 December 2011 (UTC)

Why power of two?
Just wondering. Why do most of the algorithms I've seen require the input array length to be a power of 2? 68.173.113.106 (talk) 00:06, 1 March 2012 (UTC)

 * 2 isthe smallest prime, so the algorithms are simplest in that case...this is why many textbooks only show that case, andin particular they usually only show Cooley-Tukey for power-of-two sizes. FFT algorithms exist for any size, though, even prime sizes. — Steven G. Johnson (talk) 00:37, 1 March 2012 (UTC)

An additional reason is that FFT algorithms are typically implemented on binary computers, for which some operations (such as modulo and multiplication) are much more efficient when they have an argument of the form 2ⁿ.
 * While this is a superficially plausible theory, it is not really accurate as far as I can tell (nor can I recall seeing this justification in any of the early papers). As a practical matter, one can always arrange the computation so that the differencing in indexing performance between (e.g.) 2ⁿ and 3ⁿ is negligible: for example, in a traditional textbook-style breadth-first Cooley-Tukey implementation, the multiplication or division by the radix only needs to be done once per pass over the array (with the rest of the indexing computations being additions). — Steven G. Johnson (talk) 14:51, 30 July 2013 (UTC)
 * Even in Cooley-Tukey the factor 2ⁿ pops up in many places, e.g. when the for-loops all run from 0 to 2ⁿ-1, i.e. all-zeroes to N ones. . That's the ideal loop, and there are a lot of loops. (O(NlogN)). I'm not at all claiming that it is impossible; I'm just indicating why (as a programmer not a mathematician) you'd prefer such powers of 2. — Preceding unsigned comment added by 2001:980:396E:1:D86C:31F5:6801:F457 (talk) 09:24, 1 August 2013 (UTC)
 * I've implemented numerous FFTs, and this is a negligible issue from a practical programming standpoint as well as a mathematical viewpoint. You have to look at where you multiply or divide by the radix, and you'll see that this is typically only done at most O(log N) times, and hence is negligible.   A more substantial issue is that the twiddle factors for power-of-two radix butterfly operations often simplify (e.g. to ±1, ±i, and (±1±i)/√2), so it is easier to implement optimized radix-4, radix-8, and radix-16 Cooley–Tukey steps than it is to implement, say, radix-10 efficiently. — Steven G. Johnson (talk) 15:10, 13 June 2014 (UTC)

Known exploits?
Are there known exploits of the FFT, by say using the power of two nature to design visual camouflage or radio jamming so that the interference is ignored? Hcobb (talk) 12:40, 1 August 2013 (UTC)
 * 1 Your comment makes no sense. #2 FFTs are rarely used in modern signal processing because you need to do something to the FFT data to get something useful out of it. Wavelets provided that kind of discrimination. — Preceding unsigned comment added by 24.12.228.160 (talk) 04:19, 7 December 2013 (UTC)

The FFT is used in DSP, probably more than it should be. Note that the DFT, and so FFT, expect periodic inputs, and generate periodic outputs. If used for non-periodic data, they can give surprising results. The usual solution is called windowing, which mostly involves smoothing the ends, such that there isn't a sharp discontinuity (high frequencies) at the ends. If not done properly, there might be some exploits. I don't know any exploits, and am not sure what kind you were asking about. Gah4 (talk) 05:31, 27 July 2015 (UTC)

Fixed point
The artice references a non-existent page on fixed point FFT, but even more the section makes assumptions about the fixed point arithmetic used. If one uses enough bits, fixed point should be just as good, or likely better, than floating point. At each stage of a radix-2 algorithm the magnitude can potentially be twice as big, so should have an additional bit. Since most DSP work is done in fixed point, this is an important consideration. Gah4 (talk) 00:09, 27 July 2015 (UTC)

Lower bounds using matrix entropy
Hi, I invite interested experts to review and accept the changes I made on August 19, 2015 at 10:33. The changes discuss my new contribution to lower bounding Fourier computation using matrix entropy. They were reverted by another Wikipedia user due to conflict of interest and lack of independent sources. For a link to a view of the changes (with comparison to current version, please go here Thanks Nir.ailon (talk) 07:27, 23 August 2015 (UTC)

Very hard to read. I added one intuitive 'negative frequency' section that many people search for
I also believe that this article is extremely difficult to read. I read this article many times trying to understand the FFT, and gave up. After looking at other sources and experimenting myself, I came back to this page and things made sense...but only in retrospect. It had no utility in me learning the material.

One thing that this article explains INCORRECTLY in the time-frequency relationships section is the meaning of the negative frequencies, and the existence of negative frequencies when taking the transform of real valued data or complex data. Redundancy and negative frequencies only come about from the transformation of real valued data, transforming complex data does not result in half of the dataset being conjugate and redundant. As a new user, I won't delete this section, but I strongly recommend that this section is remedied.

What I did as my first wikipedia edit is to add a new section, 'Meaning of 'negative frequencies' from fast Fourier transforming real valued data.' I was only able to determine this piece of information through my own study and experimentation. The meaning of the negative frequencies is an extremely sought after piece of information that is found virtually nowhere on the internet. Dangerously, I can only find people who convey that it is describing how i.e. a wheel can be viewed as spinning clockwise at +Hz or counterclockwise at -Hz, which is perhaps intuitively pleasing but not at all the mathematical meaning of the negative frequencies.

While I leave it to the more experienced wikipedia community to decide what to do with this section, I ask that if you have a different understanding of the meaning of these negative frequencies, please contact me and we will discuss. If you feel that this section should belong on another page, great! Whatever you do, please, leave this information up...the work of science, technology, and engineering really needs this piece of information! — Preceding unsigned comment added by Draak13 (talk • contribs) 20:03, 23 October 2015 (UTC)

Yes the idea of negative frequencies isn't well understood. Though since transforms of real data are common, the mentioned symmetry is very common. I didn't check well enough to say what should be done to it. In the case of discrete transforms, like the FFT, the result is periodic and can be shifted such that all frequencies are positive. In the continuous Fourier transform case, one can't shift away the negative frequencies. The wheel example works because of frequency aliasing in sampled (discrete) data. It is an example where negative frequencies come into play that is fairly easy to understand, especially in the signal processing domain. Gah4 (talk) 08:28, 24 October 2015 (UTC)

But this is just the issue; the idea of negative frequencies IS well understood, but only by those who have taken the time to personally experiment with it! You said you didn't check well enough...does that mean you didn't read it? That this section of sought after intuitive information was deleted, and that the more abstract time-frequency relationships section which puts out misinformation remains, is frustrating. — Preceding unsigned comment added by 128.115.190.43 (talk) 18:38, 24 November 2015 (UTC)

Image Examples Misleading
In looking at the example set forth by the first three images on this page, and their captions, it seems to imply that the FFT algorithm is by nature less precise than the integral version of the DFT, and that this loss in accuracy is acceptable given the decreased computational complexity. Perhaps I'm understanding something wrong, but I thought that the FFT was able to compute the DFT with the same accuracy as the integral DFT, and yet still at decreased computational complexity. If this is true, this example seems to be misleading to a reader simply browsing the beginning of this page.

 * The discrete Fourier transform (DFT) has no integrals. I think you are confusing it with a Fourier transform or Fourier series. — Steven G. Johnson (talk) 15:15, 1 October 2016 (UTC)

 * Well you can integrate over delta functions if you like that better. A digital image is assumed to have been frequency band limited before sampling. (There are low-pass spatial filters on cameras with lenses good enough to need them.) An image with a finite number of sample points over a finite spatial extent can be represented with a finite number of spatial frequencies. Those frequencies are produced by the DFT/FFT.  Gah4 (talk) 17:06, 1 October 2016 (UTC)

A Response to Image Examples Misleading
I've been an occasional vistor to this article, but I have to admit that previously I took very little notice of the diagrams on display, until I saw your comments about them. I agree, they are a little misleading. Perhaps I can make a few points to help clarify the situation. The first point to note is that where the FFT does provide output data, this agrees with that data provided by the DFT. What the FFT does not do, is provide information about the intervening spaces and so the red line on the third diagram has no meaning. As the data from the FFT meets the Nyquist criterion, then we should be able to resurrect an analogue version of the spectrum from the frequency domain samples. Once we have this plot, we can find the output at any intervening frequency we might choose. However, what Nyquist does not make clear is the fact that when the waveform to be generated is near the Nyquist limit, an awful lot of samples have to be included in any algorithm we choose to use. Just linking a few local points by a smooth line just will not do! One way of producing a continuous output might be to feed implulses with strengths proportional to the data values into a sharp-cut linear-phase low pass filter. Such a filter has a very long time delay (so the filter has lots of data in it on which to derive a convolved output). Unfortunately it is a filter that is hard to build. Another way forward, since we are dealing here with FFTs, is to use "zero padding", to achieve extra frequency points in the output data. If new data is generated at a sufficient number of points, these can then be safely linked by simple linear interpolation to give us a reasonably accurate analogue plot. Say we add to our input waveform defined at n = 0 to n = N-1 a sequence of zeros, seven times as long, to make the whole sequence n = 0 to n = 8.N-1. We find that the output of the FFT will now have data at extra, intervening, frequency points. This should be made clear by considering the time-frequency relationships. Before:  there are N data points, of duration T secs, and the frequency resolution of the FFT output  is 1/T Hz. After:  there are 8.N data points, of duration 8.T secs, and the frequency resolution of the output is 1/(8.T) Hz, i.e. there are now seven extra data points between the original outputs. Of course, there is a penalty incurred from doing this. The FFT that now has to be calculated is much, much bigger than the one we had before. Consequently, the benefits of the FFT are less clear cut (but, at least, values approaching the true peak values are obtained). One final aside, the outputs of the original FFT did not show the true peak values of the spectra (unlike the DFT). This may occur whenever the input data is not truly cyclic within the input window of the FFT and the technical term for this is "Spectral Leakage". As this is a common problem with signal data, techniques to deal with it are a major topic of Digital Signal Processing. I hope that helps! D1ofBerks (talk) 15:22, 11 December 2015 (UTC)

 * I think you're confusing the DFT with the DTFT. An FFT computes exactly the DFT, nothing more, nothing less — the DFT, by definition, only gives discretely sampled frequency outputs.  A DTFT, in contrast, is defined for a continuous (albeit periodic) set of frequencies.   With regard to the image, that could certainly be the subject of a DFT with fine enough sampling; you're right that an FFT in this case would be overkill because most of the spectrum is zero, though.  I don't think the image is a wonderful illustration of an FFT algorithm; a butterfly diagram or similar seems like it would be more appropriate for the algorithm itself.  On the other hand, a lot of readers of this article seem to want a brief introduction of what Fourier analysis (in general) is about before delving into algorithms. — Steven G. Johnson (talk) 15:14, 1 October 2016 (UTC)

No, I'm not confused. Zero padding of waveform samples is a well known technique, used to interpolate the frequency data of DFTs and FFTs. (This issue arose when the third diagram, now missing, erroneously implied that linear interpolation could be used to find magnitude values at frequencies between data points).

As an example of zero padding, I have used the waveform and spectrum parameters from the original diagrams which were displayed, but are now missing, i.e. a combination of cosines, of duration 10s, sampled at 1ms intervals. A zoomed-in portion of the spectrum, similar to the original third figure, is shown below. The transform has results spaced at 0.1Hz intervals, shown by blue circles in the figure. Increasing the duration of the FFT by 10x, by zero padding, gives additional spectral values spaced at 0.01 Hz, shown by red crosses.

The Discrete-time Fourier transform (DTFT), has been mentioned. It is true that the same results can be obtained, at the same frequency points, by means of DTFT, the but the time needed to do the calculations is many thousand times greater than that for the zero-padded FFT. However, we shouldn't dismiss the DTFT out of hand. Although it is much slower than the FFT, it does have some advantages, especially when results are needed at only a few frequencies, or when the magnitude at some non-standard frequency is required. With the DFT and FFT, only results at a discrete set of frequencies are available. For example, at frequency 56.60 Hz, the basic FFT, the padded FFT, and the DTFT can all provide  a result, and the three are the same (= 1.693). On the other hand, only the DTFT can calculate a result directly for a peculiar frequency, lets say, 56.584111 Hz (= 1.924). . D1ofBerks (talk) 18:18, 30 November 2016 (UTC)

The recently added first figure in the lede section is good but has two issues.
The recently added first figure in the lede section is good but has two issues.

First, It is not a "Complex Cosine" which would be the cosine of a complex number. A correct description would be "A periodic signal with four harmonics." If this was the only problem I would just fix it. Second, The DFT depicted is incorrect unless a window has been applied and/or something else has occurred. The duration of the sample is an exact multiple of the signal period and its harmonics. To be specific, the period of the fundamental is 0.1 seconds and the sample duration is 0.5 seconds. In this case, there should be no spectral leakage into adjacent harmonics. If a window is applied to the data prior to the DFT then you can see spectral leakage. However, the long tail of peaks following 50Hz suggests that something else was done. I'm not sure what it was but it might be that the actual sample duration was not a multiple of 0.1 seconds. Either the DFT is incorrect for the time sample shown, or there is other processing that needs to be describe. I'd rather see a straight DFT of the time sample as shown without any other processing.

I'm reverting it now because of the these issues, of I encourage the editor that posted it to make corrections and repost. Constant314 (talk) 22:20, 20 November 2016 (UTC)

Sparse Fourier Transform
I think it would be appropriate to include a link to this paper: https://arxiv.org/abs/1201.2501 but I'm a little intimidated by the way the article is structured, and I haven't delved deeply into Fourier transforms. Perhaps somebody else would care to take a crack at it? MatthewWilcox (talk) 19:28, 15 February 2017 (UTC)

Floating point
The article says: All of the FFT algorithms discussed above compute the DFT exactly (in exact arithmetic, i.e. neglecting floating-point errors). As far as I know, the FFT gives better floating point results (smaller error), than the direct (non-fast) implementation of DFT. I don't happen to have a reference, but if true it would be nice to say so here. Gah4 (talk) 04:30, 14 May 2017 (UTC)
 * I think that you are right. The FFT gets there in fewer operations than direct computation so you would expect it to be closer than a direct computation with finite precision arithmetic, but I don't think that is what is meant.  I think it means that, given perfect arithmetic, then the FFT produces exactly the same results as any other method of computing the DFT with perfect arithmetic. Constant314 (talk) 05:35, 14 May 2017 (UTC)
 * Oh, yes. It was just that it reminded me of the separate question of rounding error in the FFT. Gah4 (talk) 16:05, 14 May 2017 (UTC)

 * This exact point is made, with references, in the "Accuracy" section of the article.  (It's not just because it requires fewer operations, by the way, it's because of pairwise summation.)  — Steven G. Johnson (talk) 21:19, 19 May 2021 (UTC)

Table
Regarding the removal of the table, it seems to me that WP:CALC would allow the table, but then again, it doesn't seem all that interesting or useful. People who need it, likely have a calculator nearby, or could write a program to print out the table that they need. On the other hand, a little Javascript would allow for a calculator on the page. Gah4 (talk) 08:57, 23 June 2017 (UTC)

 * You can evaluate an expression, provided that the expression is from a reliable source and properly cited. There is no telling where those numbers came from and the are probably implementation specific. Constant314 (talk) 14:36, 23 June 2017 (UTC)

External links modified
Hello fellow Wikipedians,

I have just modified 3 external links on Fast Fourier transform. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:
 * Added archive https://web.archive.org/web/20120426031804/http://jsat.ewi.tudelft.nl/content/volume7/JSAT7_13_Haynal.pdf to http://jsat.ewi.tudelft.nl/content/volume7/JSAT7_13_Haynal.pdf
 * Added archive https://web.archive.org/web/20100430161231/http://www.cmlab.csie.ntu.edu.tw/cml/dsp/training/coding/transform/fft.html to http://www.cmlab.csie.ntu.edu.tw/cml/dsp/training/coding/transform/fft.html
 * Added archive https://web.archive.org/web/20130928020959/http://www.borgdesign.ro/fft.zip to http://www.borgdesign.ro/fft.zip

When you have finished reviewing my changes, you may follow the instructions on the template below to fix any issues with the URLs.

Cheers.— InternetArchiveBot  (Report bug) 16:13, 28 September 2017 (UTC)

Even the "exact" FFT algorithms have errors when finite-precision floating-point arithmetic is used
The article says: Even the "exact" FFT algorithms have errors when finite-precision floating-point arithmetic is used. I believe this isn't quite right. It isn't the finiteness, but the actual precision. If sums are done with enough extra precision, then they should be as exact as fixed point. (Though fixed point also needs extra bits.) If you do sums in the same precision as the input, then you get rounding errors. (But as noted in the article, usually less rounding error than non-fast DFT.) Single precision transforms could sum in double precision (on most hardware). Some have extra precision for intermediate values for sums of double precision input data. Gah4 (talk) 16:14, 5 November 2019 (UTC)

 * No, that's not correct. The coefficients of the FFT (roots of unity, i.e. sines and cosines) are not exactly representable in *any* precision (for N > 4), so there will almost always be some roundoff errors for any finite precision.   "Exact as fixed point" is also wrong — floating-point FFTs are generally *much* more accurate than fixed-point FFTs.  See the scalings and references in the "Accuracy" section of the article. — Steven G. Johnson (talk) 21:22, 19 May 2021 (UTC)

How can the amplitudes of the low frequencies in the time domain be higher, while being shown as low amplitude in the frequency domain?
The first schematic shows the highest peaks for the lowest frequency at 10 Hz while the frequency domain shows it as the lowest amplitude. It would be nice if one could clarify that, not only here but also in the article itself for the readers because it's confusing.2003:E0:5F2D:2C33:E2DC:9FCC:25BE:1149 (talk) 08:53, 6 September 2020 (UTC)
 * The figure is accurate. The 50th harmonic is the strongest.  Your eyeball analyzer is focused on the envelope. Constant314 (talk) 16:07, 6 September 2020 (UTC)
 * Yes! You're actually right! I was confused! I reversed the whole thing but now it makes sense of course. 2A02:908:2D17:AD00:60F2:2C8C:BE6A:D0D (talk) 16:50, 6 September 2020 (UTC)

title: Talk:Fast Fourier transform


text:
Talk:Prince Albert Victor, Duke of Clarence and Avondale

Second in Line of Succession "after Queen Victoria"
This is wrong, Prince Albert Victor was indeed 2nd in the line of succession but not "after Queen Victoria", since Victoria was the monarch at the time she can't have been in the line of succession to herself! He was second in succession after his father only.

Ripper claim
Since the allegations about Eddy as Jack the Ripper have been conclusively disproved, I think they should form only a small footnote in this article, with a link to the 'Jack the Ripper suspects' wiki page for Ripperologsts to linger over. Valetude (talk) 17:33, 18 January 2019 (UTC)
 * Articles should cover material with due proportion, taking into account their relative coverage in reliable sources. The Ripper claims are a major part of his notability and so are represented fairly in this article. DrKay (talk) 21:17, 18 January 2019 (UTC)
 * There's only one paragraph on it anyway. That's hardly excessive. Celia Homeford (talk) 09:42, 21 January 2019 (UTC)
 * In fact, this spurious claim appears twice in the article. Once at the end of the opening general section, and again under Fictional Portrayals (where it is correctly labelled as a 'conspiracy theory'). In my view, this fictional claim, which dates from the late twentieth century and has been comprehensively debunked, should be relegated to the 'Fictional Portrayals' section and not feature in the opening section at all. Fine to address it lower down in the article because the claim has been in such wide circulation in recent decades, but not balanced to include a fictional claim in this opening section. The emphasis here should be on facts, not fiction. — Preceding unsigned comment added by 2a02:a46b:8acf:1:6cbf:ce75:4f1a:230f (talk • contribs) 07:18, 4 January 2022 (UTC)

Last sentence of first paragraph of article
At present this ends with the words "... but did not become king as he died before his father and grandmother.". I would argue that the reference to his grandmother (ie Queen Victoria) should be deleted. The fact that Queen Victoria outlived Albert Victor is irrelevant to whether or not he could become king; there are no circumstances in which he could have become king given that he predeceased his father. If QV had died before Prince Albert Victor himself died, King Edward would have come to the throne sooner that much sooner; but he would still have continued to be king until 1910 and would still have been succeeded by George V. Sbishop
 * I think "he did not become king because he died before his father" would imply that died before his father but after his grandmother. "He did not become king because he died before his father and grandmother" clarifies that he died when he was second-in-line, before his father inherited the throne. Celia Homeford (talk) 08:36, 19 May 2021 (UTC)
 * Agreed. Or: "He did not become king because he died while still second-in-line to the throne, after his father". Is that clearer? Johnbod (talk) 14:04, 19 May 2021 (UTC)

What about the conspiracy theory that he died in the 1930s?
Is it worth including reference to the conspiracy theory that Prince Eddy was kept prisoner at Glamis Castle and died in the 1930s? There is an apparent picture of him in the twentieth century which shows a person painting using an easel (which might be him or might not be as the case may be). I'm not arguing strongly for inclusion, just asking the question. — Preceding unsigned comment added by 165.120.220.103 (talk) 17:39, 13 June 2022 (UTC)

Murder & Gay conspiracy theories
There is no way the sections I have removed about conspiracy theories involving him being "jack the ripper" and being gay, should be even remotely included in the lede of the article. They are unencyclopedic rumours, with zero evidence, and are mere speculation, that aren't relevant to the lede of the article. Those sections, if they should even be included due to their inaccurate, gossipy nature, be left for the main body of the article. Macktheknifeau (talk) 16:47, 8 September 2022 (UTC)
 * See above: . DrKay (talk) 17:00, 8 September 2022 (UTC)
 * I can see that Dr Kay is at risk of breaching WP:3RR, by reverting edits three times in quick succession, without any discussion about them when asked to start one here. There is a clear need to discuss the situation and come to a consensus, instead of you barrelling your way by reverting any edit you disagree with.Macktheknifeau (talk) 17:13, 8 September 2022 (UTC)
 * BREAKING NEWS: Pot calls kettle black. DrKay (talk) 17:23, 8 September 2022 (UTC)

Sexuality
Was he gay? Was he straight? Why does it matter? Historically, and particularly during this period, people's lives were ruined if they were charged with being gay, which was punishable by imprisonment and hard labor which resulted in death. The charge could be leveraged, even if someone wasn't gay, for political purposes, to ruin people's reputations, get them fired, etc. This practice continues today and being gay is punishable in some countries still by death. At the time all effort would have been made to cover up the homosexuality of the heir to the throne. No evidence would have been allowed to exist. Plus to "prove" someone was homosexual was nearly impossible at the time. That accounts survived points to the fact that he could have been gay. It's important not to erase homosexuals from history, as has been attempted since history began. Trevordavid (talk) 20:10, 5 April 2024 (UTC)
 * See WP:RGW. DrKay (talk) 20:38, 5 April 2024 (UTC)
 * Interesting. I think simply deleting the sentence about him not being gay lets readers come to there own conclusion. We don't know if he was gay or straight or bi. But by explicitly stating he was not gay is biased. Trevordavid (talk) 21:58, 5 April 2024 (UTC)
 * It's what the source says. DrKay (talk) 06:19, 6 April 2024 (UTC)
 * While I'm tracking down that source, don't you think that both the sentences about him not being at the brothel and not being gay, as well as the sentence about him being Jack the Ripper are "trying to right past wrongs?". They are seeking to clear him name, when simply stating what was rumored at the time should suffice. Trevordavid (talk) 17:33, 6 April 2024 (UTC)
 * No. Your characterization of Hyde as "homophobic" is wholly unfair. He did more than any other contemporary politician campaigning for gay rights, even to the extent of sacrificing his political career. DrKay (talk) 18:07, 6 April 2024 (UTC)

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/


text:
Battle of Mingolsheim

The Battle of Mingolsheim (Schlacht bei Mingolsheim) was fought on 27 April 1622, near the German village of Wiesloch, 14 mi south of Heidelberg (and 8 km south of Wiesloch), between a Protestant army under General von Mansfeld and the Margrave of Baden-Durlach against a Roman Catholic army under Count Tilly.

Early in the spring of 1621, a mercenary force under the command of Georg Friedrich, Margrave of Baden-Durlach, crossed the Rhine River from Alsace to junction with a force under Ernst von Mansfeld. Combined, the armies aimed to prevent a link-up between Count Tilly and Gonzalo Fernández de Córdoba, arriving with an army 20,000 strong from the Spanish Netherlands under orders from General Ambrosio Spinola. Tilly met the Protestant army at its rear guard and drove upon it. This attack was successful until he engaged the main Protestant body, and was then rebuffed. Tilly retreated and bypassed the stationary Protestant army to link up with de Córdoba later that month. After the battle, Mansfeld found himself at a distinct disadvantage until the armies of Christian of Brunswick could arrive from the north. The two armies would engage later in the month at the Battle of Wimpfen.

title: Battle of Mingolsheim


text:
Project plan

A project plan, according to the Project Management Body of Knowledge (PMBOK), is: "...a formal, approved document used to guide both project execution and project control. The primary uses of the project plan are to document planning assumptions and decisions, facilitate  communication among project stakeholders, and document approved scope, cost, and schedule baselines.  A project plan may be sumarized or detailed."

The latest edition of the PMBOK (v6) uses the term project charter to refer to the contract that the project sponsor and project manager use to agree on the initial vision of the project (scope, baseline, resources, objectives, etc.) at a high level. In the PMI methodology described in the PMBOK v5, the project charter and the project management plan are the two most important documents for describing a project during the initiation and planning phases.

PRINCE2 defines a project plan as:

 * "...a statement of how and when a project's objectives are to be achieved, by showing the major products, milestones, activities and resources required on the project."

The project manager creates the project management plan following input from the project team and key project stakeholders. The plan should be agreed and approved by at least the project team and its key stakeholders.

Many project management processes are mentioned in PMBOK® Guide, but determining which processes need to be used based on the needs of the project which is called Tailoring is part of developing the project management plan.

Purpose
The objective of a project plan is to define the approach to be used by the project team to deliver the intended project management scope of the project.

At a minimum, a project plan answers basic questions about the project:
 * Why? - What is the problem or value proposition addressed by the project? Why is it being sponsored?
 * What? - What is the work that will be performed on the project? What are the major products/deliverables?
 * Who? - Who will be involved and what will be their responsibilities within the project? How will they be organized?
 * When? - What is the project timeline and when will particularly meaningful points, referred to as milestones, be complete?

Plan contents
To be a complete project plan according to industry standards such as the PMBOK or PRINCE2, the project plan must also describe the execution, management and control of the project. This information can be provided by referencing other documents that will be produced, such as a procurement plan or construction plan, or it may be detailed in the project plan itself.

The project plan typically covers topics used in the project execution system and includes the following main aspects:

 * Scope management
 * Requirements management
 * Schedule management
 * Financial management
 * Quality management
 * Resource management
 * Stakeholder management – New from PMBOK 5
 * Communications management
 * Project change management
 * Risk management

Details
The project plan document may include the following sections:

 * Introduction: A high-level overview of the project.
 * Project management approach: The roles and authority of team members. It represents the executive summary of the project management plan.
 * Project scope: The scope statement from the Project charter should be used as a starting point with more details about what the project includes and what it does not include (in-scope and out-of-scope).
 * Milestone list: A list of the project milestones (the stop points that helps evaluating the progress of the project). This list includes the milestone name, a description about the milestone, and the date expected.
 * Schedule baseline and work breakdown structure: The WBS which consists of work packages and WBS dictionary, which defines these work packages, as well as schedule baseline, which is the reference point for managing project progress, are included here.
 * Project management plans: This section contains all management plans of all project aspects.
 * Change management plan
 * Communication management plan
 * Cost management plan
 * Procurement management plan
 * Project scope management plan
 * Schedule management plan
 * Quality management plan
 * Risk management plan
 * HR or staffing management plan
 * Resource calendar: Identify key resources needed for the project and their times and durations of need.
 * Cost baseline: This section includes the budgeted total of each phase of the project and comments about the cost.
 * Quality baseline: Acceptable levels of quality.
 * Sponsor acceptance: Some space for the project sponsor to sign off the document.

title: Project plan


text:
Land speed record

The land speed record (LSR) or absolute land speed record is the highest speed achieved by a person using a vehicle on land. By a 1964 agreement between the Fédération Internationale de l'Automobile (FIA) and Fédération Internationale de Motocyclisme (FIM), respective governing bodies for racing in automobiles and motorcycles (two or three wheels), both bodies recognise as the absolute LSR whatever is the highest speed record achieved across any of their various categories. While the three-wheeled Spirit of America set an FIM-validated LSR in 1963, all subsequent LSRs are by vehicles in FIA Category C ("Special Vehicles") in either class JE (jet engine) or class RT (rocket powered).

FIA LSRs are officiated and validated by its regional or national affiliate organizations. Speed measurement is standardized over a course measuring either 1 km or 1 mile, averaged over two runs with flying start (commonly called "passes") going in opposite directions within one hour. A new record mark must exceed the previous one by at least one percent to be validated.

History
Until 1829 the fastest land transport was horses. The first regulator was the Automobile Club de France, which proclaimed itself arbiter of the record in about 1902.

Different clubs had different standards and did not always recognize the same world records until 1924, when the Association Internationale des Automobile Clubs Reconnus (AIACR) introduced new regulations: two passes in opposite directions (to negate the effects of wind) averaged with a maximum of 30 minutes (later more) between runs, average gradient of the racing surface not more than 1 percent, timing gear accurate within 0.01sec, and cars must be wheel-driven. National or regional auto clubs (such as AAA and SCTA) had to be AIACR members to ensure records would be recognized. The AIACR became the FIA in 1947. Controversy arose in 1963: Spirit of America was not recognized due to its being a three-wheeler (leading the Fédération Internationale de Motocyclisme to certify it as a three-wheel motorcycle record when the FIA refused) and not wheel-driven so the FIA introduced a special jet and rocket propelled class. No holder of the absolute record since has been wheel-driven.

In the U.S. and Australia, record runs are often done on salt flats, so the cars are often called salt cars.

Women's land speed record

The FIA does not recognize separate men's and women's land speed records, because the records are set using motorized vehicles, and not muscle-powered vehicles, so the gender of the driver does not matter; however, unofficial women's records have long been claimed, seemingly starting with Dorothy Levitt's 1906 record in Blackpool, England, and, unlike the FIA and other car-racing organisations, Guinness World Records does recognize gender-based land speed records.

In 1906, Dorothy Levitt broke the women's world speed record for the flying kilometer, recording a speed of 96 mph and receiving the sobriquet the "Fastest Girl on Earth". She drove a six-cylinder Napier motorcar, a 100 hp development of the K5, in a speed trial in Blackpool.

in 1963, Paula Murphy drove a Studebaker Avanti to 163 mph at the Bonneville Salt Flats as part of Andy Granatelli's attempt on the overall record. In 1964, she was asked by the tire company Goodyear to try to improve her own record, which she raised to 226.37 mph in Walt Arfons's jet dragster Avenger. The rival tire company Firestone and Art Arfons hit back against Goodyear and Walt Arfons when Betty Skelton drove Art's Cyclops to achieve a two-way average of 277.52 mph in September 1965.

Five weeks later, Goodyear hit back against Firestone with Lee Breedlove. While recordkeeping has not been as extensive, a report in 1974 confirmed that a record was held by Lee Breedlove, the wife of then overall record holder Craig Breedlove, who piloted her husband's Spirit of America – Sonic I to a record 308.506 mph in 1965. According to author Rachel Kushner, Craig Breedlove had talked Lee into taking the car out for a record attempt in order to monopolize the salt flats for the day and block one of his competitors from making a record attempt.

In 1976, the women's absolute record was set by Kitty O'Neil, in the jet-powered, three-wheeled SMI Motivator, at the Alvord Desert. Held back by her contract with a sponsor and using only 60 percent of her car's power, O'Neil reached an average speed of 512.710 mph.

On October 9, 2013, driver Jessi Combs, in a vehicle of the North American Eagle Project running at the Alvord Desert, raised the women's four-wheel land speed class record with an official run of 392.954 mph, surpassing Breedlove's 48-year-old record. Combs continued with the North American Eagle Project, whose ongoing target is the overall land speed record; as part of that effort, Combs was killed, on August 27, 2019, during an attempt to raise the four-wheel record. In late June 2020, the Guinness Book of Records reclassified the August 27, 2019 speed runs as meeting its requirements, and Combs was posthumously credited with the record at 841.338 kph, noting she was the first to break the record in 40 years.

1963–present (jet and rocket propulsion)
Craig Breedlove's mark of 407.447 mph, set in Spirit of America in September 1963, was initially considered unofficial. The vehicle breached the FIA regulations on two grounds: it had only three wheels, and it was not wheel-driven, since its jet engine did not supply power to its axles. Some time later, the Fédération Internationale de Motocyclisme (FIM) created a non-wheel-driven category, and ratified Spirit of America's time for this mark. On July 17, 1964, Donald Campbell's Bluebird CN7 posted a speed of 403.10 mph on Lake Eyre, Australia. This became the official FIA LSR, although Campbell was disappointed not to have beaten Breedlove's time. In October, several four-wheel jet-cars surpassed the 1963 mark, but were eligible for neither FIA nor FIM ratification. The confusion of having three different LSRs lasted until December 11, 1964, when the FIA and FIM met in Paris and agreed to recognize as an absolute LSR the higher speed recorded by either body, by any vehicles running on wheels, whether wheel-driven or not.

title: Land speed record


text:
List of tallest buildings in Brazil

This list of the tallest buildings in Brazil ranks Brazilian skyscrapers in order by height. Most of Brazil's tallest buildings are located in Balneário Camboriú, Goiânia and São Paulo, which is the biggest financial and residential center of the country. The majority of these buildings are residential.

At 294 m the twin towers Yachthouse Residence Club, in Balneário Camboriú, are the tallest buildings in Brazil. The first skyscraper in Brazil was the 105-meter-tall Martinelli Building in São Paulo, completed in 1929.

title: List of tallest buildings in Brazil


text:
Gabriel Naudé

Gabriel Naudé (2 February 1600 – 10 July 1653) was a French librarian and scholar. He was a prolific writer who produced works on many subjects including politics, religion, history and the supernatural. An influential work on library science was the 1627 book Advice on Establishing a Library. Naudé was later able to put into practice all the ideas he had put forth in Advice, when he was given the opportunity to build and maintain the Bibliothèque Mazarine, the library of Cardinal Jules Mazarin at Paris.

Naudé was a precursor of Pierre Bayle and Fontenelle.

Biography
Naudé was born in Paris in early 1600 to a family of modest means. His father was a lowly official and his mother a young illiterate woman. He was described by his teachers as tenacious and passionate about his education. Naudé entered college at a young age where he studied philosophy and grammar. Later he studied medicine at Paris and Padua (where he attended Cesare Cremonini's lessons), and became physician to Louis XIII.

At the age of twenty, Naudé published his first book Le Marfore ou Discours Contre les Lisbelles. The work would bring him to the attention of Henri de Mesme, président à mortier of the Parlement of Paris. Mesme offered Naudé the job of librarian to his personal collection. Mesmes had a large library for the period (about 8,000 volumes) and it was open to scholars who had the appropriate references. Naudé's service in Mesme's library would give him experience which he would use later to write the book Advice on Establishing a Library. Naudé wrote Advice for Mesme as a guide for building and maintaining his library. In 1629 he became librarian to Cardinal Guidi di Bagno in Rome, and on Bagni's death in 1641 librarian to Cardinal Francesco Barberini.

At the desire of Cardinal Richelieu he began a controversy with the Benedictines, denying Jean Gerson's authorship of De Imitatione Christi. Richelieu intended to make Naudé his librarian, and on his death Naudé accepted a similar offer from Cardinal Mazarin. For the next ten years he devoted himself to bringing together from all parts of Europe the assemblage of books known as the Bibliothèque Mazarine. Mazarin had brought with him to Paris a collection numbering over 5,000 volumes. Like Naudé, he believed in an open library to be used by the public for the public good. In 1642 he purchased a building to house his library and he instructed Naudé to build up the finest collection possible.

The fastest way was to absorb entire libraries into the collection, advice that Naudé included in his book. Naudé plundered second hand book sellers, and Mazarin instructed his ambassadors, government officials and generals to collect books for him. Naudé was able to travel Europe, and during one trip that lasted several months he collected over 14,000 volumes. By 1648 the library had built up to an estimated at 40,000 volumes. It was open on a regular basis and had built up a sizable number (almost 100) of regular patrons, and several staff members to keep it functioning properly. It became the first in France to be open for all, without references.

Mazarin's library was sold by the Parlement of Paris during the troubles of the Fronde, and Queen Christina invited Naudé to Stockholm. He was not happy in Sweden, and on Mazarin's appeal that he should re-form his scattered library, Naudé returned at once. His health was broken, however, and he died on the return journey, in Abbeville on 10 July 1653.

The friend of Gui Patin, of Pierre Gassendi and all the liberal thinkers of his time, Naudé was no mere bookworm; his books show traces of the critical spirit which made him a worthy colleague of the humorists and scholars who prepared the way for the better known writers of the siècle de Louis XIV.

Career as a librarian
Naudé, in his career as a librarian, "opposed censorship, and encouraged library owners to allow others to use their books, a practice he considered a great honor for the owner – an honor equal to that of having the opportunity to build a fine library." Naudé found it favorable to collect original format of books and to keep the volumes collected intact. He was a true believer of considering the needs of those that would access them and felt strong consideration to be sought from the experts in each particular field. He was adamant about collecting in all languages, about all religions, subject matters, and literature. During his career in librarianship, Naudé helped instruct collectors and libraries in the selection and acquisition of their titles and how to create catalogs for their libraries. He was a major proponent of scouring secondhand bookshops and print shops for valuable and hard to find literary works. "When Naudé has been in town, the booksellers' shops seem devastated as by a whirlwind. Having bought up in every last one of them all the books, whether in manuscript or in print, dealing in any language whatever with any subject or division of learning no matter what, he has left the stores stripped and bare."

Naudé also had interesting ideas on the locale where a library should be located. "While centrally located within the community it serves, a library should be at some distance from the noisiest streets. It should, if possible, be situated between some spacious court and a pleasant garden, from which it may enjoy good light, a wide and agreeable prospect, and pure air, unpolluted by marshes, sinks, or dunghills; the whole arrangement so well planned and ordered that it is compelled to share nothing unpleasant or obviously inconvenient."

Probably the most famous library that Naudé helped shape, and in which he served as librarian, was the Bibliothéque Mazarine in Paris, the library of Cardinal Jules Mazarin in the rue de Richelieu. Naudé spent ten years of his life improving and shaping the Bibliothéque. It became the first publicly accessible library in France because of Naudé's insistence and was open to the public as early as 1644.

As a librarian and scholar, Naudé proposed "to direct a wealthy collector into paths of bibliothecarian righteousness" as a result of his belief that the current century had advanced far beyond their predecessors with regard to the quantity and quality of the information or resources that they had access to. Naudé's seminal work on library science, Advice on Establishing a Library, served as an early instruction manual or guide for private collectors who were interested in the book acquisition and maintenance process. Naudé encouraged collectors (and fellow librarians) to organize their books meticulously by "their number and the range of their subject matter, the criteria of selection, and the means of procurement", in addition to the arrangement of the building(s) that book collections may be stored in and other potential methods of book cataloging. Naudé's knowledge and expertise left a lasting impact on both the library community and the world at large, with his influence guiding collectors, scholars, politicians, and religious leaders.

Artistic portrayals
Naudé is the subject of Peter Briscoe's novel, The Best Read Man in France.

Works
Including works edited by him, a list of ninety-two pieces is given in the Naudaeana. The principal ones are:

 * Le Marfore, ou discours contre les libelles (Paris, 1620), very rare, reprinted 1868;
 * Instruction à la France sur la vérité de l'histoire des Frères de la Roze-Croix (1623, 1624), displaying their impostures;
 * Apologie pour tous les grands personages faussement soupçonnez de magie (1625, 1653, 1669, 1712), Pythagoras, Socrates, Thomas Aquinas Jerome Cardan and Solomon are among those defended;
 * Advis pour dresser une bibliothèque (1627, 1644, 1676; translated by John Evelyn, 1661), full of sound and liberal views on librarianship and considered as a founding stone of library science;
 * Addition à l'histoire de Louys XI (1630), this includes an account of the origin of printing;
 * Bibliographia politica (Venice, 1633, etc.; in French, 1642);
 * De studio liberali syntagma (1632, 1654), a practical treatise found in most collections of directions for studies;
 * De studio militari syntagma (1637), esteemed in its day;
 * Considérations politiques sur les coups d'état (1639). A disciple of Machiavelli, he considered that politics must be rendered "autonomous from morality, sovereign in relation to religion"

A Bibliotheca Pontificia was completed and seen into print by Louis Jacob.

Advice on establishing a library
Advice, written as a set of instructions for a private collector, was based on Naudé's own experience and research. In the introduction to his book, Naudé wrote that he is not an expert in the field of librarianship but he presented what he believed to be the most important ideas. He based some of the opinions in Advice on his own experience in Mesme's library, and wrote out for Mesme the accepted practices and principles of librarians of the time. Chapters each covered topics such as number of books, selecting the books, procuring the books, and so forth.

Naudé's first chapter poses the question, "Why establish a library?" He answers the question with a simple message; there is no greater honor than building a great library and sharing it with the public. Naudé believes libraries should model themselves after the best libraries of the world. The first task is to create a plan. Before a person can erect a library, he must educate himself on the subject of collecting and organizing books. A person must also seek the guidance of those who have already built their own libraries or are in the process. He suggests studying and copying the catalogues of other libraries.

Naudé devotes an entire chapter to book selection, remarked upon throughout. The first authors who need to be purchased are those considered experts in their respective fields. No matter whether they are ancient or modern works, if a book were held in high regard by practitioners of a particular field then it should be present in any collection. In addition, any well known interpretations or commentaries that exist are a necessity. Naudé suggested purchasing books in the original languages because meaning can often be lost in translation. He stood strongly against censorship of any kind. Naudé believed that every book has a reader regardless of the subject, and that information should be free and available. Readers could always find use of a book, even if that use were to refute the ideas presented on its pages. Certain books are popular at times but later forgotten: he argued that it would be beneficial to a library if there were multiple copies of these books to accommodate the popular tastes of the times.

In his chapter on book acquisition, Naudé offered concise tips. The easiest way is to purchase another library in its entirety. Naudé went on to praise second-hand book sellers who often provided good books at cheap prices. Naudé himself browsed book-binding and printing shops for used paper, and once had discovered a rare manuscript that a book binder was using as scrap paper.

Naudé included a chapter in Advice for arranging the books. In discussing arrangement he quoted Cicero's De Oratore: "It is order that gives light to memory" (from De Oratore 2.353 ). He gave instructions that he considered logical. His subject headings included theology, philosophy, jurisprudence, medicine, history, mathematics and humanities. Naudé would add other subject heading in later years but these categories best represented the known body of knowledge in the world. Each section, he said, should be divided into subheadings and begin with the principal authors followed by the commentaries.

title: Gabriel Naudé