6
$\begingroup$

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

$\endgroup$
8
$\begingroup$

FFT is an algorithm for computing the DFT. It is faster than the more obvious way of computing the DFT according to the formula.

Trying to explain DFT to the general public is already a stretch. Also, they probably don't know what an algorithm is. Perhaps you could say that there's a fast way of computing the DFT, and that's one more reason why it's so useful.

$\endgroup$
  • $\begingroup$ Should I change the 'DFT' to 'the naive algorithm for computing a DFT'? $\endgroup$ – user1095332 Apr 17 '13 at 22:44
  • 1
    $\begingroup$ That would be better. $\endgroup$ – Yuval Filmus Apr 17 '13 at 22:57
  • $\begingroup$ Apparently the public can be introduced to the DFT as "roots of unity filter". But in some ways the continuous FT may be easier to explain using a picture like this $\endgroup$ – isomorphismes Jun 19 '14 at 10:43
4
$\begingroup$

FFT algorithms are faster ways of doing DFT. It is a family of algorithms and not a single algorithm. How it becomes faster can be explained based on the heart of the algorithm: Divide And Conquer. So rather than working with big size Signals, we divide our signal into smaller ones, and perform DFT of these smaller signals. At the end we add all the smaller DFT to get actual DFT of the big signal. This gives great benefit asymptotically. So for large values of N, we save a lot!! We shall see how much in a while.

Let us try to understand it more with little bit of high school maths:

DFT computation for N point signal takes: N^2 multiplications (this is clear from the basic defintion, you have N points, and for each of the points you have to multiply N complex sinusoids).

Now if we dvivide our N-point signal into two signals S1 and S2 of length N/2, and then perform DFT of these smaller signals, we will be doing (N/2)^2 multiplication for each of the S1 and S2. So total no. of mulitplications performed in calculating DFT of S1 and S2 will be 2 * (N/2)^2. Then to get actual DFT of N point signal we need to add these componets. So we can see that we actually need approximately (see Note below) 2 * (N/2)^2= (n^2)/2 which is half that in case of N point signal.

This reduction of half is a result of dividing the siganls once. But if we continue deviding the signals again and again, we will end up in reducing the amount of computations in each step by an amount which is much lesser than N^2. In fact the over all no. of compuations using this method comes of the order of N*logN.

To get an idea of how fast this is as compared to direct DFT, consider a computer which can execute 1 mulitiplication operation in 1 nano-seconds. Assume that we have a signal having total of N= 10^9 points.

Total number of nanoseconds spent for evaluating DFT by direct method (i.e not using FFT)on the given Computer= N^2= 10 ^ 18 Nano seconds, which is approximately 31 years. While using FFT we shall spent N*logN = (10^9)*log (10^9)= (10^9)*9*log10 = (10^9) * 9 * 3.32 which is approximately equal to 30 * (10^9) or approximately 30secs!!

So using direct DFT you will spend 31 years while using the devide and conquer approach as in FFT you will get the same output only in 3o seconds!! Now its up to you which method will you prefer :-).

The bottom line is that a lot of problem in nature can be solved much easily if they are small in size. The total effort in solving many small sized problems, is often much smaller than in case of solving one big problem; especially, if the size of the problem is very big such as the above example explained.
This is the basic idea on which FFT algorithms are based upon.

Note: I said 'approximately' because it turns out that we cannot add them directly, and indeed we need a mulitplication factor, actually a phase factor, before combining them. But this is still much lesser that no. of multiplicatiosns we need to do in calculating DFT of S1 and S2, so we can neglect this additional multiplication for large values of N.

Dvide and Conquer: an analogy in military

The concept has been used historically in military. For example Sun Tzu (c. 6th century BCE) a Chinese general, military strategist, and author of The Art of War, writes:

It is the rule in war,

1- if ten times the enemy's strength, surround them;

2- if five times, attack them;

3- if double, be able to divide them;

4- if equal,engage them;

5- if fewer, be able to evade them;

6- if weaker, be able to avoid them.

Sun Tzu enter image description here

FFT works on rule no. 3. Rule 1 and 2 tells that if your computer is very powerful enough, then probably you will not be interested in adopting any 'Dvide and Conquer' approach, becasue the gain in doing so will be very less. Also rule no 4 to 6 tells that when your computer is too weak, forget about conquering the problem, by dividing the problem size. You will have to search some other ways. One such way could be Randomization

$\endgroup$
  • $\begingroup$ @user1095332 Total number of nanoseconds spent for evaluating DFT by direct method (i.e not using FFT)on the given Computer= N^2= 10 ^ 18 Nano seconds. what source code is required to calculate convert 10^18 Ns seconds into year? $\endgroup$ – gpuguy Apr 20 '13 at 11:37
0
$\begingroup$

For a non maths audience this will be hard, I suggest you keep it as short as possible or omit it entirely but here's my attempt

A DFT is a large matrix that you multiply your input vector by, the naive implementation involves doing n^2 multiplications for an n point DFT (there are a whole bunch of additions too, but at least in hardware the cost of the multiplications will dominate)

An FFT can be seen as transforming the DFT matrix into multiple matrices which when multiplied together give you the same result, crucially some of the terms in the FFT matricies are 0 so all multiplications with these terms can be omitted meaning you end up with fewer multiplications overall.

$\endgroup$
0
$\begingroup$

Calculating one value of X(k) in the frequency domain costs N complex multiplications, so calculating all N of them one by one, "starting over" every time, costs N times N is N^2 complex multiplications.

However, if you first calculate the DFT of all even entries ((N/2)^2 multiplications) and all odd entries (another (N/2)^2 multiplications), for a total of N^2 / 2 multiplications, you can calculate the full DFT from those with just another N/2 multiplications and N additions. For large N that last step can be ignored, and thus you gained a factor of two. If N is a power of two N=2^q, then you can repeat this trick q times by doing it also for the smaller DFTs of the even and odd entries, winning q times a factor 2, thus it becomes N^2 / (2^q) = N^2 / N = N multiplications, but you have to do that q = log2(N) times, so in the asymptotical case you end up with something of the order N log(N).

To see why you can combine the DFTs of even and odd entries in such an easy way, you must realize that you're just summing entries multiplied with evenly spaced complex numbers on the unit circle in the complex plane (Nth roots of 1, which all lay on a circle). So, if you treat the odd entries as the only input for some DFT then you you're only a single rotation away from what you need for the full DFT: the rotation to bring the entries back to where they should be. A rotation means a multiplication, hence N/2 extra multiplications before you can combine the two smaller DFTs with just additions.

Note that the same trick can be applied when N doesn't factor into just 2^q, but when it can be factored into many small prime numbers. For example, if N=p^q you can repeat q times a stage where you calculate p DFT's each of N/p points and then combine those with (p-1)N/p multiplications (rotating p-1 of the DFT's of the previous stage) and (p-1)N additions, for each of the q stages.

$\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.