Fast Fourier Transform in my opinion is one of the most important algorithms in computing. It is because I personally like this algorithm that I've decided to discuss it. The basis behind fourier transform is in mathematics. Fourier transform is the discovery that a signal in one form can be turned into another form without losing any information. A signal in the time and space domain can be transformed into a signal in the frequency domain. This concept is powerful in a similar way to the ability to use a directed graph to visualize a social network. For clarity the time domain, minutes, seconds, mili-seconds, and so on.
Fourier transform's power becomes apparently when you understand the nature of the electromagnetic spectrum. Information traverses the electromagnetic spectrum as "waves". Fourier transform allows for analysis of this spectrum to be possible. Spectral analysis is made possible and all it's applications by way of Fourier transform.
Signal processing is also a very common element in computer programing. We use signal processing for example to do image processing. We also use signal processing when we are dealing with audio processing. People who like music, who like games, will understand the value of digital signal processors.
Fast Fourier Transform is an efficiency enhancement for the process of Fourier transform.
Below is the code to show you how simple it is to apply FFT in practice
from numpy.fft import fft
from numpy import array
a = array([1.0, 1.0, 1.0, 1.0, 0.0, 0.0, 0.0, 0.0])
print( ' '.join("%5.3f" % abs(f) for f in fft(a)) )
4.000 2.613 0.000 1.082 0.000 1.082 0.000 2.613
Now let's discuss the code. If you don't know Python, the "from" command is how you select a module. So "from numpy.fft import fft"
This imports the FFT module from numpy. What is numpy? Numpy is a package which you can leverage in your programming to do scientific computing. FFT is imported by the import command in Python so that Fast Fourier Transform can be used in your app.
The next step is to import an array. From the Numpy manual:
NumPy’s main object is the homogeneous multidimensional array. It is a table of elements (usually numbers), all of the same type, indexed by a tuple of positive integers. In NumPy dimensions are called axes.
We can also see from the manual how to compute different types of FFT using Numpy:
fft(a[, n, axis, norm]) Compute the one-dimensional discrete Fourier Transform.
ifft(a[, n, axis, norm]) Compute the one-dimensional inverse discrete Fourier Transform.
fft2(a[, s, axes, norm]) Compute the 2-dimensional discrete Fourier Transform
ifft2(a[, s, axes, norm]) Compute the 2-dimensional inverse discrete Fourier Transform.
fftn(a[, s, axes, norm]) Compute the N-dimensional discrete Fourier Transform.
ifftn(a[, s, axes, norm]) Compute the N-dimensional inverse discrete Fourier Transform.
https://docs.scipy.org/doc/numpy/reference/routines.fft.html#standard-ffts
As you can see it is trivially easy to write this code. I chose Python because it's the easiest language to explain for a newbie programmer. Fourier transform is immensely useful. In fact, the concept of heart rate variability which is used with heart rate monitors is calculated by Fast Fourier Transform. The pattern of beats is translated into the frequency domain. It is also possible to use FFT in combination with neural networks (NN) to diagnose by EKG heart related problems. This shows the versatility and life saving potential of FFT.
Clifford, G. D. (2002). Signal processing methods for heart rate variability (Doctoral dissertation, University of Oxford).
Gothwal, H., Kedawat, S., & Kumar, R. (2011). Cardiac arrhythmias detection in an ECG beat signal using fast fourier transform and artificial neural network. Journal of Biomedical Science and Engineering, 4(04), 289.