2
$\begingroup$

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?

$\endgroup$
  • 6
    $\begingroup$ Why would you give a presentation about the Fourier transform to the non-mathematical public anyway? $\endgroup$ – Lord Soth Apr 17 '13 at 22:03
  • 1
    $\begingroup$ The ultra short version: Divide and conquer. $\endgroup$ – Harald Hanche-Olsen Apr 17 '13 at 22:05
  • 5
    $\begingroup$ FFT is (a particular implementation of) the DFT. $\endgroup$ – kahen Apr 17 '13 at 22:12
  • 2
    $\begingroup$ Yes, and it makes no sense to ask why mergesort is faster than sorting. $\endgroup$ – joriki Apr 17 '13 at 22:24
  • 1
    $\begingroup$ @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. $\endgroup$ – hmakholm left over Monica Apr 17 '13 at 22:29
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – J. M. is a poor mathematician Apr 18 '13 at 8:40
  • $\begingroup$ "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... ;) $\endgroup$ – user1095332 Apr 21 '13 at 19:51
0
$\begingroup$

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}$

*** Please don't kill me.

EDIT: Yeesh - there've been far less self-aware answers. Case in point: a general audience won't give a hoot about the differences in flow diagrams (DIF vs. DIT vs. flow diagrams more capable of being represented in parallel hardware despite output scrambling etc.). The historical perspective is bunk, because it totally runs away from the point: that the FFT is more efficient than running straight from the definition of the DFT. Just end with something about it being efficient. It frankly doesn't matter what, if the audience is actually general and actually with average mathematical background. The more memorable, the better. If this is a major point to make, being composed throughout the entirety of the presentation and breaking composure slightly (else just changing some bit of behavior) for a single slide (or equivalent) will, while not necessarily driving a point home, drive the point right into the audiences' collective faces and they'll remember it.

If it's truly a general audience, content matters far less than delivery.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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