How to solve the Fast Fourier transform

As pointed out in the comments, FFT is a fast way of computing DFT, but what is the Discrete Fourier Transfrom? Well, there are many characterizations, but there is one standard definition (you can find it e.g. on http://en.wikipedia.org/wiki/Discrete_Fourier_transform, please also note, that some definitions scale the transform by $\frac{1}{\sqrt{N}}$.): DFT of sequence $x_0, \ldots, x_{N-1}$ is a sequence $X_0, \ldots, X_{N-1}$ such that $$ X_n = \sum_{k=0}^{N-1} x_k \omega^{nk} $$ where $\omega = e^{\frac{-2\pi i}{N}}$ is the $N$-th root of unity ($N$ is the length of your sequence). This might not be intuitive, so I will explain it in other words: Let the input sequence $x_0, \ldots, x_{N-1}$ represent a polynomial $P(z) = x_0 + x_1 z + x_2 z^2 + \ldots x_{N-1} z^{N-1}$. Then $X_n = P(\omega^n)$. So, DFT is nothing special, but an evaluation of polynomial of $N-1$ degree in $N$ points. Remember that the values of polynomial in $N$ different points constitute a good representation of polynomial of degree $N-1$ (e.g. there is the inverse DFT). However, the fact that makes DFT such great thing is the points at which this polynomial is evaluated: the roots of unity. And from that single fact follows a lot of marvelous properties. For example this allows for efficient computation of the formula, and also for efficient inversion. Moreover it is a linear transformation (because it is a simple evaluation), and has nice properties regarding http://en.wikipedia.org/wiki/Convolution. However, there is one more property which is intrinsic to DFT: it converts http://en.wikipedia.org/wiki/Discrete_Fourier_transform#The_shift_theorem, and for that there is a http://blog.sigfpe.com/2011/06/another-elementary-way-to-approach.html which may help you to understand DFT. Finally there is also the "think-about-a-signal intuition" which talks about how sines and cosines in harmonic representation of your function resonate or cancel-out with the sines and cosines in DFT (that is $e^{2\pi i t} = \cos(2\pi t) + i\sin(2\pi t)$), but you can find a lot on this on the net, e.g. http://techhouse.brown.edu/~dmorris/projects/tutorials/fourier_tutorial.pdf, GIYF. Hope that helps!