Explaining why FFT is faster than naive-DFT for the general public?

How would you explain why the Fast Fourier Transform is faster than the naive algorithm for computing the Discrete Fourier Transform, if you had to give a presentation about it for the general (non-mathematical) public?

• Why would you give a presentation about the Fourier transform to the non-mathematical public anyway? – Lord Soth Apr 17 '13 at 22:03
• The ultra short version: Divide and conquer. – Harald Hanche-Olsen Apr 17 '13 at 22:05
• FFT is (a particular implementation of) the DFT. – kahen Apr 17 '13 at 22:12
• Yes, and it makes no sense to ask why mergesort is faster than sorting. – joriki Apr 17 '13 at 22:24
• @user1095332: Those are not valid analogies to "DFT vs FFT", because DFT and FFT are not different ways of solving a problem. DFT is the name of the problem that FFT is one way to solve. You can't meaningfully put a "vs" between them. – hmakholm left over Monica Apr 17 '13 at 22:29

You may say: When $N$ is a power of $2$, the Cooley-Tukey FFT divides the $N$-DFT problem to two $\frac{N}{2}$ DFT problems. Using the same idea, one may further divide the two $\frac{N}{2}$ DFT problems to four separate $\frac{N}{4}$-DFT problems, and so on... At the end, you have $\log_2 N$ steps with $O(N)$ operations to be performed at each step.

As Harald Hanche-Olsen has suggested, you may say "divide and conquer." The division part is the Cooley-Tukey idea, you divide and divide; at the end you have conquered it all.

No matter what you say, the non-mathematical audience will probably have dozed off by now. You may wake them up by saying "Gauss knew the FFT, but he didn't publish it" to add some drama.

• If OP has time, he may want to distinguish between "decimation in time" (Cooley-Tukey) FFT, and "decimation in frequency" (Sande-Tukey) FFT. Both take $O(n\log\,n)$ effort, but arrange the computations differently. There is a nice discussion in Arndt's Matters Computational. – J. M. is a poor mathematician Apr 18 '13 at 8:40
• "Gauss was a great mathmatician, he knew the FFT in 1805, way before computers were invented, but he didn't publish it, he thought it was useless (for a 16x16 for example)." He would rather die than trying to make it useful, and so he did! Nowadays, the Fast Fourier Transform is one of world’s most important emerging technologies. That's what a call drama... ;) – user1095332 Apr 21 '13 at 19:51

Old question is old, necro answer is necro, but I still had a bit of fun writing them so here ya go.

(all as if speaking to t3h audience)

1. If you tried to calculate the DFT naively, you'd find yourself calculating the same things again and again and again*. The FFT shines by avoiding this redundant work. The moral of the story is that you should leave the toilet seat down if your household primarily consists of females.
2. If anyone remembers the distributive property, you can go from $a*x+a*y$ to $a*(x + y)$, saving you a multiplication. The FFT basically does this to the naive DFT, but many many times over, and the savings add up to the point of saving over a million multiplications for a single DFT calculation of modest sample size**. Using an FFT will cause your computer to praise you as a fair master and it likely won't attempt to kill you in the machine uprising.
3. If you twiddle*** your thumbs enough, a programmer will come up with convolution***-ed code that makes Indiana Jones: Rader's*** of the Lost Ark look reasonable. It'll also be faster than doing the DFT straight from the definition. Fancy that.

* (preemptive disclaimer: to within a phase/twiddle factor)

** $2^{10}$