A collection of Fast Fourier Transform algorithms implemented in C++20.
It’s a collection of Fast Fourier Transform algorithms, featured in Joel Yliluoma’s master’s thesis (“pro gradu”) in University of Helsinki.
Supported algorithms:
defs.hh
: Definitions for complex types and complex vectors.exp.hh
and exp.cc
: A module for handling exp-vectors containing $e^{-i2\pi x/N}$ values.factor.hh
and factor.cc
: A module for integer factorization utilities.dft.hh
and dft.cc
: The naive DFT. Also works as a fallback for any algorithm. Contains optimized FFTs for sizes ≤ 4.fft_fftw.hh
and fft_fftw.cc
: FFT through libFFTW3.fft_radix2.hh
and fft_radix2.cc
: Fast FFT for powers-of-two lengths (Cooley-Tukey radix-2).fft_tukey.hh
and fft_tukey.cc
: Generic Cooley-Tukey algorithm. Requires that the input length is a composite number.fft_rader.hh
and fft_rader.cc
: Rader’s FFT. Requires that the input length is a prime number. Performs sub-FFTs using FFT_any for length $N-1$.fft_bluestein.hh
and fft_bluestein.cc
: Bluestein’s FFT. Performs sub-FFTs using FFT_any for length $m$. Provided are three versions:FFT_bluestein
selects smallest convolution length $m ≥ 2N-1$ such that $m$ consists of only these factors: 2, 3, 5 or 7.FFT_bluestein_pow2
selects smallest convolution length $m ≥ 2N-1$ such that $m$ consists of only these factors: 2.FFT_bluestein_fac2_3
selects smallest convolution length $m ≥ 2N-1$ such that $m$ consists of only these factors: 2 or 3.fft_any.hh
and fft_any.cc
: Combined FFT. Uses heuristics to decide the fastest method for any input size (excluding FFTW).Also
render.cc
: See belowplanner.cc
: A tool for generating FFTW wisdom filesThe program render.cc
is used to render
speed comparison graphs for the thesis.
This tool was created because LibreOffice Calc
was too sluggish to operate with CSV files
containing tens of thousands of rows and multiple columns.
The program main.cc
in the speech/
branch
is used for analyzing vowel formants in speech by FFT.