fftea

A simple and efficient FFT implementation.

Supports FFT of power-of-two sized arrays of real or complex numbers, using the Cooley-Tukey algorithm. Also includes some related utilities, such as windowing functions, STFT, and inverse FFT.

This package was built because package:fft is not actively maintained anymore, and wasn’t a particularly efficient implementation. There are a few improvements that make this implementation more efficient:

• The main FFT class is constructed with a given size, so that the twiddle factors only have to be calculated once. This is particularly handy for STFT.
• Doesn’t use a wrapper class for complex numbers, just uses a Float64x2List. Every little wrapper class is a seperate allocation and dereference. For inner loop code, like FFT’s complex number math, this makes a big difference. Float64x2 can also take advantage of SIMD optimisations.
• FFT algorithm is in-place, so no additional arrays are allocated.
• Loop based FFT, rather than recursive.
• Using trigonometric tricks to only calculate a quarter of the twiddle factors.

Usage

Running a basic real-valued FFT:

// myData.length must be a power of two. Eg 2, 4, 8, 16, ...
List<double> myData = ...;

final fft = FFT(myData.length);
final freq = fft.realFft(myData);

freq is a Float64x2List representing a list of complex numbers. See ComplexArray for helpful extension methods on Float64x2List.

For efficiency, avoid recreating the FFT object each time. Instead, create one FFT object of whatever size you need, and reuse it.

Running an STFT to calculate a spectrogram:

// audio.length *doesn't* need to be a power of two. It can be any legnth.
List<double> audio = ...;

final chunkSize = 1024;  // Must be a power of two.
final stft = STFT(chunkSize, Window.hanning(chunkSize));

final spectrogram = <Float64List>[];
stft.run(audio, (Float64x2List freq) {
  spectrogram.add(freq.discardConjugates().magnitudes());
});

The result of a real valued FFT is about half redundant data, so discardConjugates removes that data from the result:

[sum term, …terms…, nyquist term, …conjugate terms…] ^—– These terms are kept ——^ ^- Discarded -^

Then magnitudes discards the phase data of the complex numbers and just keeps the amplitudes, which is usually what you want for a spectrogram.

If you want to know the frequency of one of the elements of the spectrogram, use stft.frequency(index, samplingFrequency), where samplingFrequency is the frequency that audio was recorded at, eg 44100. The maximum frequency (aka nyquist frequency) of the spectrogram will be stft.frequency(chunkSize / 2, samplingFrequency).

See the example for more detailed usage.

Benchmarks

I found some other promising FFT implementations, so I decided to benchmark them too: scidart, and smart_signal_processing.

To run the benchmarks:

1. Go to the bench directory and pub get, cd bench && dart pub get
2. Run dart run bench.dart

fftea gains some of its speed by caching the twiddle factors between runs, and by doing the FFT in-place. So the benchmarks are broken out into cached and in-place variants. Caching and running in-place is also applied to some of the other libraries, where appropriate.

In the table below, “cached” means the construction of the FFT object is not included in the benchmark time. And “in-place” means using the in-place FFT, and the conversion and copying of the input data into whatever format the FFT wants is not included in the benchmark. Run in Ubuntu on a Dell XPS 13.

In practice, you usually know how big your FFT is ahead of time, so it’s pretty easy to construct your FFT object once, to take advantage of the caching. It’s sometimes possible to take advantage of the in-place speed up too, for example if you have to copy your data from another source anyway you may as well construct the flat complex array yourself. Since this isn’t always possible, the “fftea, cached” times are probably the most representative. In that case, fftea is about 60-80x faster than package:fft, and about 30% faster than smart_signal_processing. Not sure what’s going on with scidart, but it seems to be O(n^2).

* Scidart’s FFT doesn’t have an in-place mode, but they do use a custom format, so in-place means that the time to convert to that format is not included in the benchmark.

GitHub

View Github