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?
Asked
Active
Viewed 2,801 times
2
-
7Why would you give a presentation about the Fourier transform to the non-mathematical public anyway? – Lord Soth Apr 17 '13 at 22:03
-
To show how cool it is, that you can do something like a Fourier transform faster ;) – user1095332 Apr 17 '13 at 22:04
-
1The ultra short version: Divide and conquer. – Harald Hanche-Olsen Apr 17 '13 at 22:05
-
@user Hmm, if that is the intention, you may better talk about fast integer (or matrix multiplication) (as a side suggestion). Maybe these will be more intuitive. – Lord Soth Apr 17 '13 at 22:05
-
5FFT is (a particular implementation of) the DFT. – kahen Apr 17 '13 at 22:12
-
@kahen I know, just like mergesort is just a way of sorting as well ... :| – user1095332 Apr 17 '13 at 22:13
-
2Yes, and it makes no sense to ask why mergesort is faster than sorting. – joriki Apr 17 '13 at 22:24
-
As @kahen says, FFT is the way DFT is computed. Yes, it is cool. Yes, it will be worse than antique Greek to the unwashed masses. Look for something more tangible. – vonbrand Apr 17 '13 at 22:25
-
@joriki How about selection sort vs mergesort? N^2 vs NlogN? DFT vs FFT? – user1095332 Apr 17 '13 at 22:25
-
1@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
-
It appears that you're confusing the naive algorithm for computing a DFT with the DFT itself. – joriki Apr 17 '13 at 22:29
-
@HenningMakholm It wasn't clear what I intended to say? – user1095332 Apr 18 '13 at 00:25
-
@user1095332. This is mathematics we are dealing with. Precision is paramount.So, you can talk about the discrete Fourier transform, and the two ways to compute it: the naïve $O(n^2)$ method and the fast $O(n\log,n)$ method. – J. M. ain't a mathematician Apr 18 '13 at 08:38
2 Answers
3
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.
J. M. ain't a mathematician
- 75,051
Lord Soth
- 7,750
- 20
- 37
-
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. ain't a mathematician Apr 18 '13 at 08: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
0
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)
- 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.
- 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.
- 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.
user
- 163
- 6