20020925, 10:27  #1 
Sep 2002
4_{8} Posts 
FFT explanation for non math guys
Hi!
I´m looking for the simple fft explanation for guys that have no idea about math. That´s 13/14 years old guys. As programmer I can read the source code and understand every line but i can´t grasp the general concept. I tried seaching for a sipmle explanation and i got algorithms of 10 lines long but i couldn´t find anything that gives a simple example of what´s happening... what i mean let´s try to multiply 2 smalls int 23 and 12 for example... what does happens on a simple fft algorithm? i tried to follow the steps on a paper with a pencil and i couldn´t get it any help? Creative1 
20020925, 20:01  #2  
P90 years forever!
Aug 2002
Yeehaw, FL
2·11·349 Posts 
Re: fft explanation for non math guys
Quote:
You really want to find a text that talks about Fourier Transforms, rather than Fast Fourier Transforms. Good luck in your search, hopefully someone can make a recommendation 

20020926, 03:19  #3 
Aug 2002
2×3×29 Posts 
FT is at least a first year uni subject. I think it is rather diffcult to explain to someone with a mathematic knowledge of a 13/14 year old though :)

20020926, 13:04  #4 
Aug 2002
2^{2}·5·13 Posts 
There are some fairly practical enginering maths books that are not too bad. They do not go too far into theory, but more into application. makes it a tiny bit easier to understand. ;)
Alf 
20020926, 17:08  #5  
∂^{2}ω=0
Sep 2002
República de California
2×13×449 Posts 
Re: fft explanation for non math guys
Quote:
A simple example is vector arithmetic in two dimensions. Vectors (x1,y1) and (x2,y2) are easily added in x,y coordinates  simply add their components to get (x1+x2, y1+y2)  but are harder to multiply together. (I'm thinking here of multiply as defined for complex numbers, i.e. with product = (x1*x2y1*y2, x1*y2+x2*y1).) OTOH, if I transform to polar coordinates and write each one as a pair (r, theta) (with r = sqrt(x^2+y^2) and theta = atan(y/x)), then they are easy to multiply simply multiply the rparts together, and add the thetaparts together to get the product (still in polar coordinates), (r1*r2, theta1+ theta2). By using polar form I've reduced the cost of getting the product from 4 (scalar) multiplies and 2 adds to just 1 multiply and one add. Of course I've also made it harder to do further vector additions  to do that efficiently I'll want to transform the result back to (x,y) coordinates  but that's the tradeoff. Now consider multiplying together two numbers A and B, each having N digits. The way one learns to do this in grammar school is to multiply each digit of B by the rightmost digit of A, then shift B to the left one place (i.e. add a 0 at the right end) and multiply that by the nexthigherorder digit of A, and so forth, then sum all the N intermediate products. That needs on the order of N^2 digit multiplications and a similar number of digit additions  in mathematical terms, it's an O(N^2) ("big oh of N squared" or "order of N squared") algorithm. Now this type of procedure has another name: discrete convolution. It's also used a lot in completely different fields, for instance signal processing  you typical cell phone does a lot of it. Now there's a famous transform which allows us to do discrete convolutions really fast, and it's called the Fast Fourier Transform. If we treat each of our input numbers A and B as a vector with N components (the digits of the number) and do an FFT on each of them, we get a pair of vectors A^ and B^ (that generally look nothing like the inputs) which have a very special property: in Fourier space (which is where we consider the transform to have taken our input vectors), convolution looks just like digitbydigit multiplication. In other words, if we multiply each individual component (just a number) of A^ with the corresponding one of B^, the result is guaranteed to be the Fouriertransformed version of the convolution of A and B. That is, in Fourier space, convolution costs just O(N) operations, much better than our original O(N^2). To get back the result we want (i.e. convolution(A, B), not in Fouriertransformed form) we do an inverse transform on the single vector resulting from the digit bydigit multiply of A^ and B^. (Using our x,yversuspolar analogy, this is analogous to converting the polarform product of our two vectors back to x,y coordinates, using the inverse transform x = r*cos(theta), y = r*sin(theta).) Now, it's an interesting feature of the FFT approach that doing the transform actually costs more than doing the digitbydigit multiply form of convolution that it enables. But doing the transform costs O(N*log2(N)) operations (and the "oh of" notation hides a constant of proportionality which is larger than one  typically around 5 in a good implementation), and of course we need to do two such transforms, so a reasonable estimate of the FFT cost of multiplication is around 10*N*log2(N). But for N sufficiently large, this is cheaper than the grammarschool way. And as N continues to get larger, the speed advantage continues to grow, since the ratio N/log2(N) grows without bound as N tends to infinity. In mathematical terms, we say that FFTbased multiply is "asymptotically faster" than grammar school. To put numbers on this: let's consider the grammarschool way to cost 2N^2 operations (N^2 digit multiplies and roughly the same number of adds, plus the carries in the output digits, which only cost O(N) work, i.e. which don't contribute appreciably to the operation count.) Here is a small table of 2N^2 vs. the opcount for FFT: Code:
N 2N^2 10*n*log2(N)    10 200 332 100 20000 6640 10^3 2*10^6 ~10^5 10^6 2*10^12 ~2*10^8 10^9 2*10^18 ~3*10^11 For 10digit numbers, FFT is only around 60% as fast as GS. For 100digit numbers, FFT is about 3 times faster. For 1000digit numbers, FFT is about 20 times faster. For milliondigit numbers, FFT is about 10,000 times faster. For billiondigit numbers, FFT is nearly ten million times faster. Now to your small example: let's multiply 12 and 23 the FFT way, representing them as base10 vectors, i.e. we form our input vectors simply by separating out the digits of the above base10 representation of the numbers. One important practical detail here, which I glossed over in my earlier discussion: if we want to FFTmultiply two numbers, each having N digits, we expect the product to have as many as 2*N digits, so we actually need to do a length2N FFT to leave room for the digits at the high end that will "fill in" when we do the multiply. That means we need to pad our input vectors with N zeros at the upper end. Thus, our input vectors are A = (2,1,0,0) and B = (3,2,0,0), where the leastsignificant digit of each number is leftmost. The Fourier transform of a length4 vector (a,b,c,d) is given in matrixmultiply form as Code:
+1 +1 +1 +1 a a+b+c+d +1 +i 1 i*b=(ac)+i*(bd) +1 1 +1 1 c ab+cd +1 i 1 +i d (ac)i*(bd) That is, the length4 IFT of our vector (15, 4+7i, 1, 47i) has entries [15+(4+7i)+1+(47i)]/4 = 24/4 = 6, [(151)i*(4+7i4+7i)]/4 = [14+14]/4 = 7, [15(4+7i)+1(47i)]/4 = 8/4 = 2, [(151)+i*(4+7i4+7i)]/4 = [1414]/4 = 0. Since all the output digits happen to be less than 10 and nonnegative, we don't need to do any carry step, and since the outputs are leastsignificant first, our result (written in normal decimal order) is 276. Hope this helped, Ernst p.s.: I was rather cavalier in my use of the term "FFT" above  the proper name for the transform we use is the Discrete Fourier Transform (DFT); FFT is simply a way of efficiently effecting a DFT. For example, a non FFT version of the above calculation would use a standard O(N^2) matrix multiply algorithm to do the DFT. But if you look at the righthand side of the matrix multiply, you see many repeated terms. To get the RHS, all we need to do is the following sequence: w = a+c x = ac y = b+d z = bd Then, output 1 = w+y output 2 = x+i*z output 3 = wy output 4 = yi*z Exploiting those types of symmetries in the DFT matrix is what the FFT does. Last fiddled with by ewmayer on 20080907 at 02:29 Reason: Cleaned up the text munge that resulted from a forum software update 

20021027, 18:36  #6 
Sep 2002
2^{2} Posts 
sorry i delayed so much with this answer but i just realized that there was an answer back here...
thanks alot for the explaination but there still one thing i couldn´t grab how did you create the 'i' matrix to be able to make the transform? everything is was very nice explained but i couldn´t get how you filled that matrix with 1, 1, i, i values where did that come from? and in the case the numbers weren´t 23 and 12 and there was a carry on the multiplication... how would i handle that? Creative1 
20021028, 14:18  #7  
Sep 2002
Vienna, Austria
3·73 Posts 
Quote:
+1 +1 +1 +1 i^0 i^0 i^0 i^0 +1 +i 1 i=i^0 i^1 i^2 i^3 +1 1 +1 1 i^0 i^2 i^4 i^6 +1 i 1 +i i^0 i^3 i^6 i^9 [/code:1] For FFT size 2N, just replace the i with cos(pi/N)+i sin(pi/N)(That is, a 2Nth root of 1)and constuct the matrix as above....... P.S. I am only 14 years old! 

20021028, 14:35  #8  
Sep 2002
100_{2} Posts 
Quote:
and 'replace the i with cos(pi/N)+i sin(pi/N)' you mean: cos(pi/N)+ sqrt(1) sin(pi/N) ? 

20021028, 20:24  #9 
Aug 2002
Ann Arbor, MI
110110001_{2} Posts 
I believe for the example given, a FFT size of 2 was used. The general formula uses cos(pi/n)+i sin(pi/n) , which reduces to i for a FFT size of 2.
P.S. I'm only 15. Guess I'm not the only young cruncher around here. 
20021028, 21:03  #10  
∂^{2}ω=0
Sep 2002
República de California
2·13·449 Posts 
Quote:
exp(i*2*pi/n) = cos(2*pi/n)+i*sin(2*pi/n). The reason one sees the i's in my example is that to DFTmultiply two general length2 numbers, one must zeropad the input vectors to double the number of input digits, i.e. one must use a length4 DFT. Note that for modular multiplication for certain moduli of special form (which happen to include the Mersenne numbers), one can use additional clever tricks to avoid the zeropadding. That's because a lengthn discrete cyclic convolution (working with baseX inputs, where X need not be 10) is really a polynomial multiplication modulo X^n  1. That means that in my example, if I had used a length2 DFT instead of length4 (and recall that I was using X = 10), I would have still obtained the correct result, but only in the sense that it is correct modulo 10^2  1 = 99. Let's try it: We again DFTmultiply 12 and 23 using base10 arithmetic, but this time we don't pad our input vectors with zeros. Thus, our input vectors are A = (2,1) and B = (3,2), where the leastsignificant digit of each number is leftmost. The Fourier transform of a length2 vector (a,b) is given in matrixmultiply form as [code:1] +1 +1 a a+b +1 1*b=ab . [/code:1] Doing this for our two input vectors, our transformed vectors are A^ = (3, 1) and B^ = (5, 1). The Fouriertransformed discrete convolution of A and B is then simply A^*B^, where the '*' means dyadic multiply, which gives (15, 1). To get the digits of the product we're after, we need to inverseFouriertransform this vector. For length2 vectors, the IFT looks just like the FT, but with a factor of onehalf multiplying the whole thing. That is, the length2 IFT of our vector (15, 1) has entries (16, 14)/2 = (8, 7). Since all the output digits happen to be < 10 and nonnegative, we don't need to do any carry step, and since the outputs are leastsignificant first, our result (written in normal decimal order) is 78. The exact (full) product is 12*23 = 276, which indeed == 78 modulo 99. Ernst 

20021029, 05:12  #11  
Sep 2002
Vienna, Austria
3×73 Posts 
Quote:
an 2Nth root of 1 is cos(2pi/2N)+ i*sin(2pi/2N). for the example given, we were using FFT size 4 so we'll have to use the fourth root of 1That is, i. 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Any technology you guys are excited about?  jasong  Lounge  31  20151009 20:55 
These dell guys can't possibly be serious...  Unregistered  Hardware  12  20061103 03:53 
You guys are famous  jasong  Sierpinski/Riesel Base 5  1  20060322 01:06 
Hi guys !  Crystallize  Lounge  6  20030927 13:08 
How do you guys do this?  ThomRuley  Lone Mersenne Hunters  1  20030529 18:17 