Benchmarking the FFT algorithm

[Rob_Ward]

I recently did a demonstration of the Fast Fourier Transform (FFT) algorithm and how to manipulate it.

One thing we were able to discover was that the FFT breaks an N element array into a grid N1 x N2 = N and computes multiplications along one axis and additions along the other.  Since the additions are less computationally intensive than the multiplications this optimises the Discrete Fourier Transform (DFT).

Naturally the larger N becomes the longer it will take, but when N is prime, you cannot generate the grid required for optimisation, so when benchmaring it the longest data points indicator usually contains a high number of prime numbers.

Enjoy.

Rob!