mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2002-09-25, 10:27   #1
creative1
 
Sep 2002

416 Posts
Exclamation 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
creative1 is offline   Reply With Quote
Old 2002-09-25, 20:01   #2
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

3×13×197 Posts
Default Re: fft explanation for non math guys

Quote:
Originally Posted by creative1
I´m looking for the simple fft explanation for guys that have no idea about math. That´s 13/14 years old guys.
I hate to be skeptical, but I'm not aware of any texts or web pages that explain FFTs in extremely elementary terms. It took me a long time for me to grasp FFT concepts well enough to code one. FFTs are complex beasts. Most FFT articles and textbooks quickly get sidetracked with optimization techniques which contribute nothing to your understanding of what they are and why they work.

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
Prime95 is offline   Reply With Quote
Old 2002-09-26, 03:19   #3
xtreme2k
 
xtreme2k's Avatar
 
Aug 2002

2×3×29 Posts
Default

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 :)
xtreme2k is offline   Reply With Quote
Old 2002-09-26, 13:04   #4
Prime Monster
 
Prime Monster's Avatar
 
Aug 2002

22·5·13 Posts
Default

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
Prime Monster is offline   Reply With Quote
Old 2002-09-26, 17:08   #5
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

22×3×7×139 Posts
Default Re: fft explanation for non math guys

Quote:
Originally Posted by creative1
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
Hmm, it's difficult to explain the deeper theory underlying transforms to even a good student at that age level, but let me try to illustrate the basic features with an analogy you should be able to grasp. The basic idea behind most (if not all) mathematical transforms is to take some problem that appears (or simply is) difficult in its original form and turn it into a problem that is easier (or even trivial) to solve when transformed.

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*x2-y1*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 r-parts together, and add the theta-parts 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 next-higher-order 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 digit-by-digit 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 Fourier-transformed 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 Fourier-transformed form) we do an inverse transform on the single vector resulting from the digit- by-digit multiply of A^ and B^. (Using our x,y-versus-polar analogy, this is analogous to converting the polar-form 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 digit-by-digit 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 grammar-school 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 FFT-based multiply is "asymptotically faster" than grammar school. To put numbers on this: let's consider the grammar-school 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
In words:

For 10-digit numbers, FFT is only around 60% as fast as GS.
For 100-digit numbers, FFT is about 3 times faster.
For 1000-digit numbers, FFT is about 20 times faster.
For million-digit numbers, FFT is about 10,000 times faster.
For billion-digit 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 base-10 vectors, i.e. we form our input vectors simply by separating out the digits of the above base-10 representation of the numbers. One important practical detail here, which I glossed over in my earlier discussion: if we want to FFT-multiply 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 length-2N 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 least-significant digit of each number is leftmost. The Fourier transform of a length-4 vector (a,b,c,d) is given in matrix-multiply form as

Code:
|+1 +1 +1 +1| |a| a+b+c+d
|+1 +i -1 -i|*|b|=(a-c)+i*(b-d)
|+1 -1 +1 -1| |c| a-b+c-d
|+1 -i -1 +i| |d| (a-c)-i*(b-d)
where i = sqrt(-1) is the usual imaginary constant. Doing this for our two input vectors, our transformed vectors are A^ = (3, 2+i, 1, 2-i) and B^ = (5, 3+2i, 1, 3-2i). The Fourier-transformed discrete convolution of A and B is then simply A^*B^, where the '*' means component-by-component (the fancy word is 'dyadic') multiply, which gives (15, 4+7i, 1, 4-7i). To get the digits of the product we're after, we need to inverse-Fourier-transform this vector. For length-4 vectors, the IFT looks just like the FT, but with the signs on the i-terms in the above matrix switched and a factor of one-fourth multiplying the whole thing. (We always have the factor of 1/N for a length-N inverse transform, since we require that doing an FT of a vector followed by an IFT simply give us back our original vector).

That is, the length-4 IFT of our vector (15, 4+7i, 1, 4-7i) has entries

[15+(4+7i)+1+(4-7i)]/4 = 24/4 = 6,
[(15-1)-i*(4+7i-4+7i)]/4 = [14+14]/4 = 7,
[15-(4+7i)+1-(4-7i)]/4 = 8/4 = 2,
[(15-1)+i*(4+7i-4+7i)]/4 = [14-14]/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 least-significant 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 right-hand 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 = a-c
y = b+d
z = b-d

Then,

output 1 = w+y
output 2 = x+i*z
output 3 = w-y
output 4 = y-i*z

Exploiting those types of symmetries in the DFT matrix is what the FFT does.

Last fiddled with by ewmayer on 2008-09-07 at 02:29 Reason: Cleaned up the text munge that resulted from a forum software update
ewmayer is offline   Reply With Quote
Old 2002-10-27, 18:36   #6
creative1
 
Sep 2002

22 Posts
Default

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
creative1 is offline   Reply With Quote
Old 2002-10-28, 14:18   #7
wpolly
 
wpolly's Avatar
 
Sep 2002
Vienna, Austria

3·73 Posts
Default

Quote:
Originally Posted by creative1
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?
[code:1]
|+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!
wpolly is offline   Reply With Quote
Old 2002-10-28, 14:35   #8
creative1
 
Sep 2002

22 Posts
Default

Quote:
Originally Posted by wpolly
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.......
I didn´t understand that last part... the fft that we were using was size 2N right?
and 'replace the i with cos(pi/N)+i sin(pi/N)' you mean:
cos(pi/N)+ sqrt(-1) sin(pi/N) ?
creative1 is offline   Reply With Quote
Old 2002-10-28, 20:24   #9
Kevin
 
Kevin's Avatar
 
Aug 2002
Ann Arbor, MI

433 Posts
Default

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.
Kevin is offline   Reply With Quote
Old 2002-10-28, 21:03   #10
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

22×3×7×139 Posts
Default

Quote:
Originally Posted by Kevin
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.
No, the (n)th complex roots of unity are given by
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 DFT-multiply two general length-2 numbers, one
must zero-pad the input vectors to double the number of input digits, i.e.
one must use a length-4 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 zero-padding.
That's because a length-n discrete cyclic convolution (working with base-X
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 length-2
DFT instead of length-4 (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 DFT-multiply 12 and 23 using base-10 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
least-significant digit of each number is leftmost. The Fourier transform
of a length-2 vector (a,b) is given in matrix-multiply form as

[code:1]
|+1 +1| |a| a+b
|+1 -1|*|b|=a-b .
[/code:1]

Doing this for our two input vectors, our transformed vectors are
A^ = (3, 1) and B^ = (5, 1). The Fourier-transformed 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 inverse-Fourier-transform this vector. For length-2
vectors, the IFT looks just like the FT, but with a factor of one-half
multiplying the whole thing.

That is, the length-2 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 least-significant
first, our result (written in normal decimal order) is 78. The exact
(full) product is 12*23 = 276, which indeed == 78 modulo 99.

-Ernst
ewmayer is offline   Reply With Quote
Old 2002-10-29, 05:12   #11
wpolly
 
wpolly's Avatar
 
Sep 2002
Vienna, Austria

3×73 Posts
Default

Quote:
Originally Posted by creative1
Quote:
Originally Posted by wpolly
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.......
I didn´t understand that last part... the fft that we were using was size 2N right?
and 'replace the i with cos(pi/N)+i sin(pi/N)' you mean:
cos(pi/N)+ sqrt(-1) sin(pi/N) ?
Yes
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 1---------That is, i.
wpolly is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Any technology you guys are excited about? jasong Lounge 31 2015-10-09 20:55
These dell guys can't possibly be serious... Unregistered Hardware 12 2006-11-03 03:53
You guys are famous jasong Sierpinski/Riesel Base 5 1 2006-03-22 01:06
Hi guys ! Crystallize Lounge 6 2003-09-27 13:08
How do you guys do this? ThomRuley Lone Mersenne Hunters 1 2003-05-29 18:17

All times are UTC. The time now is 14:17.


Fri Dec 3 14:17:58 UTC 2021 up 133 days, 8:46, 0 users, load averages: 0.92, 1.14, 1.20

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.