# What is difference between Fourier Transform and Fast Fourier Transform?

If you think about Fourier Transform, in the classical cases, say on the real line, what it is?
You take a function $f$, and you take it's Fourier Transform at particular frequency k, then it’s going to be something like integral over the real line of this exponential factor $$\int_{R}^{}{e^{ik}\cdot{f(x)}}dx$$ So $f$ is a general complex value function.

One way to think about Fourier Transform in the classical case is that if you take the space of all functions that you apply their Fourier Transform to.
To take the space of functions that it defines way in to separate that space into subspaces, which are independently effected by translation, right?

But how to describe the Fast Fourier Transform? What is difference?
Also I need to know is there another kind of Fourier Transform excluding FFT and Discrete Fourier Transform?

Thank you anyway!

• the difference is the speed. Jul 9 '14 at 14:56
• also, fft has more fours (it's fourier)
– Jam
Jul 9 '14 at 15:10
• I thought it was a clever performed discrete FT. Similiar like evaluation of a matrix product $C = A B$, where there exist clever schemes which reduce the number of needed simple operations.
– mvw
Jul 9 '14 at 15:14
• I think that the difference is big! The difference is that the FFT is an algorithm. Mar 22 '15 at 10:10

Fourier Transform is a function.

Fast Fourier Transform is an algorithm.

It is similar to the relationship between division and long division. Division is a function, long division is a way to compute the function.

The Fast Fourier Transform is a particularly efficient way of computing a DFT and its inverse by factorization into sparse matrices. The wiki page does a good job of covering it.

To answer your last question, let's talk about time and frequency. You are right in saying that the Fourier transform separates certain functions (the question of which functions is actually interesting) into their frequency components. For example, the function $f(t) = \cos(6πt) e^{−2πt}$ taken from Wiki has a Fourier transform with maxima corresponding to frequencies at $3$ Hz (supposing we're in seconds).

But, imagine you had a more complex signal and you were interested not just in the frequency components, but when those components occurred in time. To localize in time, you'd need something like a short-time Fourier transform or "windowed" transform. Performing this transform produces a two-variable function in time and frequency. It looks like this $$X(\omega, \tau) = \int_{\mathbb{R}} w(t - \tau) f(t)e^{-2\pi i t \omega} \ dt$$

The resolution that one can know the frequency depends on the width of the windowing function $w$. You might be interested to know how good the resolution can get. Unfortunately, because of the Uncertainty Principle, if we define the variance about zero of the function and its STFT as $D_0(f(t))$ and $D_0(\hat{f}(\omega))$. Then $$D_0(f)D_0(\widehat{f}) \geq \frac{1}{16\pi}.$$ Hence, the resolution has some type minimum granularity.

However, there is a whole field of study devoted to improved time and frequency localization. If you are interested in transforms besides the FT and FFT, then you may want to investigate wavelet analysis. Wavelets in general have better time-frequency resolution than the FT since the "windows" they use are of variable width. In wavelet analysis, $L^2$ is broken up into a nested sequence of subspaces called a multiresolution analysis (MRA) each with a basis consisting of a special scaling function. From this construction, we can build a so-called mother wavelet whose various dilations and translations form a basis for all of $L^2$. The ability to slide and stretch these functions and the diversity of possible mother wavelets yields many different ways of examining a signal in time and scale, beyond those offered by the traditional Fourier transform.

FFT is an algorithm based technique which allows fast (as the name says) calculations of a function in terms of sine and cosine series. Majorly used in Digital Signal Processing.

The recent DSO(Digital Storage Oscilloscopes) use FFT to store the data of a waveform.

Basically FFT helps the program to reduce the number of multiplications of the complex functions in a Fourier Transform.