Fast Fourier Transform

This demo computes Discrete Fourier Transform and Inverse Discrete Fourier Transform by two ways:

• non-recursively by performing a double-loop
• recursively by using the FFT algorithm

It generates a random array of complex numbers of size 2ⁿ, where n is provided by the user, applies to it DFT followed by an application of IDFT to the result.

For n < 5 the program outputs the original complex numbers and the ones obtained by applying DFT and IDFT. Match of the numbers indicates that the program works correctly.

Recursive FFT/IFFT

Source code