Implementing the Fourier transform formula with STL numeric algorithms
The Fourier transformation is a very important and famous formula in signal processing. It was invented nearly 200 years ago, but with computers, the number of use cases for it really skyrocketed. It is used in audio/image/video compression, audio filters, medical imaging devices, cell phone apps that identify music tracks while listening to them on the fly, and so on.
Because of the vastness of general numeric application scenarios (not only because of the Fourier transformation of course), the STL also tries to be useful in the context of numeric computation. The Fourier transformation is only one example among them but a tricky one too. The formula itself looks like the following:
The transformation it describes is basically a sum. Each element of the sum is the multiplication of a data point of the input signal vector, and the expression exp(-2 * i * ...). The maths behind this is a bit scary for everyone who does not...