Aelian.FFT 1.0.4

Aelian.FFT

A highly optimized fast fourier transform implementation for .NET 8 and up, written in 100% pure c#, so there are no dependencies on native libraries.

It utilizes an in-place iterative Radix-2 Cooley-Tukey algorithm tuned for SIMD, and has support for both complex-valued and real-valued input.

To my knowledge, it is the fastest .NET FFT implementation that is freely and publicly available.

Usage

Initialization

using Aelian.FFT;

// Call Initialize () once when your program is loading
FastFourierTransform.Initialize ();

Transforming complex-valued data

var ComplexBuffer = new System.Numerics.Complex[4096];

// Fill ComplexBuffer with meaningful data here

FastFourierTransform.FFT ( ComplexBuffer, /* forward: */ true );

Transforming real-valued data

var RealBuffer = new double[4096];

// Fill RealBuffer with meaningful data here

FastFourierTransform.RealFFT ( RealBuffer, /* forward: */ true );

Or, alternatively, using the supplied Aelian.FFT.SignalData class to make working with in-place real-valued FFTs easier:

var MySignalData = SignalData.CreateFromRealSize ( 4096 );

// Fill MySignalData with meaningful data here

var RealValuedSamples = MySignalData.AsReal ();
FastFourierTransform.RealFFT ( RealValuedSamples, /* forward: */ true );

var ComplexSpectrum = MySignalData.AsComplex ();

Note that Aelian.FFT utilizes an in-place algorithm, which means your input data is overwritten with output data. This saves costly memory allocation and memory access penalties, but might not always be the most convenient or intuitive approach.

Limitations

Certain optimizations in Aelian.FFT consist of precomputing values in tables. These tables take up some memory and take a short time to initialize. They have a fixed maximum size that limits the maximum input size for the FFT.

The current limit for Constants.MaxTableDepth is 18, which limits the maximum FFT input to 65,536 samples (or 32,768 complex values). Increasing the value of Constants.MaxTableDepth also increases the memory usage exponentially, so while it is certainly possible to process larger FFT's by increasing this value, it is currently set to what I considered to be a reasonable limit.

In the future I might make this value configurable.

Benchmarks comparing Aelian.FFT to other .NET FFT implementations

Benchmarks ran on a 11th Gen Intel Core i9-11900K 3.50GHz, 1 CPU, 16 logical and 8 physical cores, using .NET 8.0.5 (8.0.524.21615), X64 RyuJIT AVX2

The following alternative implementations were used in this benchmark:

• Chris Lomont's C# Fast Fourier Transform
• NAudio
• MathNet.Numerics
• FftSharp
• NWaves

Real-valued input

Each benchmark represents running 10,000 transforms with an input of 4096 real values:

Note that NAudio does not have a real-valued FFT, so it is omitted from this benchmark.

* The split data overload of RealFFT is faster than the interleaved one, since it can skip unzipping and rezipping, but it is also less practical since it splits out the real-valued samples in even and odd arrays.

Complex-valued input

Each benchmark represents running 10,000 transforms with an input of 4096 complex values:

* NAudio only supports its own Complex value type using 32-bit floats, so while it is faster in case of an inverse FFT, its output is also far less precise.

If you know of a .NET FFT implementation that you think belongs in this list, please let me know.