## Introduction

In this short article, we will compare a couple of Fast Fourier Transform (FFT) implementations for the .NET platform. The contestants are:

| Accord.NET | AForge.NET | Exocortex.DSP | Math.NET Numerics | NAudio | Lomont | FFTW |

Version: | 3.0.2 | - | 1.2 | 3.11.0 | 1.7.3 | 1.1 | 3.3.4 |

License: | LGPL | LGPL | BSD | MIT | Ms-PL | - | GPL |

Assemblies: | 4 | - | 1 | 1 | 1 | - | 1+1 |

Size: | 728 kb | - | - | 1252 kb | 460 kb | - | 2.3 MB |

Nuget: | yes | yes | no | yes | yes | no | no |

#### Remarks

- Accord.NET is an extension to AForge.NET and the original AForge code is part of the Accord assembly, so the AForge assemblies weren't tested separately.
- The Exocortex project was created in the early .NET 1.0 days. The copy provided with this article was updated to target .NET 4.5 and to use the
`Complex`

type of the `System.Numerics`

namespace.
- NAudio uses a custom
`Complex`

type implementation with single precision real and imaginary part.
- FFTW is a popular, native FFT implementation. It is probably the fastest open source implementation one can find on the internet, so comparison with the managed code is a bit unfair. Still, I thought it might be interesting to see how the code competes.

The FFTW binaries are not distributed with this article. If you want FFTW to be included in the benchmark, go to http://www.fftw.org/install/windows.html and copy *libfftw3-3.dll* and *libfftw3f-3.dll* to the application directory.

## Benchmark

I was particularly interested in 1D FFTs for real valued input (audio processing). The following interface is used for all tests. If you have your own FFT implementation, it should be easy to incorporate it into the benchmark by implementing this interface and instantiate the test in the `Util.LoadTests()`

method.

interface ITest
{
bool Enabled {get; set; }
void Initialize(double[] data);
void FFT(bool forward);
double[] Spectrum(double[] input, bool scale);
}

Take a look at the different tests in the `FFTBench.Benchmark`

namespace to see how to implement the interface properly.

Exocortex, Lomont and FFTW have specialised implementations for real valued data and the code can be expected to be about twice as fast as the standard complex implementation.

Accord.NET, Math.NET and FFTW support input arrays of any size (i.e. the size doesn't have to be a power of 2). Since AForge, Exocortex, NAudio and Lomont support radix 2 only, the benchmark uses arrays with sizes that are a power of 2.

The following table shows the total execution time in milliseconds for FFTs of increasing size:

FFT size | 1024 | 2048 | 4096 | 8192 |
---|

Accord.NET | 2524 | 5615 | 13309 | 26700 |

AForge.NET | 2000 | 4000 | 10016 | 27050 |

Math.NET | 4460 | 7599 | 14926 | 29098 |

NAudio | 1002 | 2004 | 5009 | 11510 |

Exocortex | 1500 | 3000 | 7000 | 22008 |

Lomont | 1000 | 2000 | 4502 | 20500 |

Exocortex (real) | 500 | 1000 | 2501 | 6000 |

Lomont (real) | 500 | 1000 | 2500 | 6000 |

FFTW | - | 500 | 1002 | 5501 |

FFTW (real) | - | - | 500 | 1504 |

FFTWF (real) | - | - | - | 1000 |

Each FFT is actually called *25000* times (the repeat value can be chosen from the user interface), so a single call to Accord's FFT routine for size **8192** would - for example - approximatly be **1ms** (the absolute runtime will certainly be different on different machines; the above benchmark was run on an *AMD Phenom II X2 550* processor (3.1 GHz)).

The next chart shows the benchmark result for the different FFTs of size 4096:

## Interpreting FFT Results

The benchmark application contains a util called *FFT Explorer*. You can open it by clicking on the leftmost icon of the benchmark window.

The *FFT Explorer* lets you select the FFT implementation, an input signal and the FFT size. Three graphs will display the input signal, the spectrum computed by the selected FFT and the signal computed by the inverse FFT.

Let's have a look at an example signal of the `SignalGenerator`

class. The generated signal is a simple sine wave with frequency **1.0 Hz** and amplitude **20.0**:

public static double[] Sine(int n)
{
const int FS = 64;
return MathNet.Numerics.Generate.Sinusoidal(n, FS, 1.0, 20.0);
}

Let the FFT frame size be *n* = **256**. With a sampling rate of **64 Hz** our periodic signal will be repeated exactly four times over the selected window. Be aware that all values are chosen to have an exact match between signal period, sampling rate and FFT size. This way, we won't have to deal with spectral leakage.

Each bin of the FFT output is spaced by the frequency resolution *(sampling rate) / (FFT size)*, which in our case is **64 / 256 = 0.25**. So we expect a peek corresponding to our **1.0 Hz** signal to be in bin number **4** (since **1.0 = 4 * 0.25**).

Due to the nature of the DFT, the spectrum of the signal will get scaled by *n* = **256**, so if no further scaling is done, we expect the value to be **20.0 * 256 / 2** = **2560**. We divide by **2**, since the amplitude is distributed across two bins. The second bin is located at index *256 - 4* = *252* and will have the same magnitude, because, for real valued input signals, the FFT output is (conjugate) symmetric (across *n/2*, the bin corresponding to the Nyquist frequency).

The actual values of the peek won't be consistent between FFT implementations, since there's no common scaling convention. If the FFT size is *n*, then some implementations scale the FFT by *1/n*, some scale the inverse FFT by *1/n* and some scale both by *1/sqrt(n)*. Some don't scale at all (like FFTW).

The following table shows the amplitudes computed by the different FFTs for the above example:

| Accord.NET | AForge.NET | Exocortex.DSP | Math.NET Numerics | NAudio | Lomont | FFTW |

Value: | 2560 | 10 | 2560 | 160 | 10 | 160 | 2560 |

You can see that AForge.NET and NAudio scale by *1/n* and that Math.NET and Lomont scale by *1/sqrt(n)* (both Math.NET and Lomont allow the user to change scaling conventions; the values computed above and used in the benchmark represent the default settings).

## Conclusion

Obviously and not completely unexpected, FFTW is the clear winner. So, if using a native DLL is an option for you, go for it. Looking at the managed code, both Exocortex and Lomont seem to be a good choice. For complex valued data, Lomont is slightly faster. For real valued signals, both perform the same. NAudio also performs pretty well, but uses a custom `Complex`

type and does not support real valued input.

## History

- 15 May 2016 - Initial version
- 14 June 2016 - Add information requested in the comments