Jan's Fast Fourier Transform
Compile time FFT algorithm that is based on the article "A Simple and Efficient FFT Implementation in C++" by Volodymyr Myrnyy. To improve on the accuracy, sine and cosine tables are used that hold trigonometric constants that are used by the FFT algorithm. These tables are computed with quad-double precision numbers to improve on the accuracy. See project gensincos in the code for the computation of these tables.
Use CMake to make a solution or project file. All dependencies are delivered with the code, but you need to call
git submodule update --init
to download the qdouble submodule.
Benchmark with FFTW (https://www.fftw.org)
Tested on Windows with FFTW 3.3.10.
FFTW is slightly faster and sligthly more accurate, but the results of JFFT are in the same ballpark. So why should you opt for JFFT instead of FFTW? Depends on your use case: you cannot compile FFTW yourself but need to download precompiled binaries from the website. JFFT on the other hand is easy to use in your projects. Just take the files jfft.h and sincos.h from folder jfft in the code repository and you're good to go. They will compile on any system.
The benchmark starts from a signal with values
[0.5 1.5 2.5 3.5 4.5 5.5 ... ]
where even spots represent the real value and odd spots represent the imaginary value of the signal.
The timing below is the time spent to do a forward and inverse Fourier transform on different sizes of the input signal (see value n for the actual size).
The error is the l2 distance between the original input signal and the signal after the forward and inverse Fourier transform was applied. Theoretically both signals should be the same.
*********************
FFTW
*********************
P = 10 n = 1024
FFTW took 0.0008885 seconds.
Error = 6.75265e-12
*********************
JFFT
*********************
P = 10 n = 1024
JFFT took 5.54e-05 seconds.
Error = 8.66112e-12
*********************
FFTW
*********************
P = 11 n = 2048
FFTW took 0.0003013 seconds.
Error = 1.97668e-11
*********************
JFFT
*********************
P = 11 n = 2048
JFFT took 0.0001372 seconds.
Error = 2.56608e-11
*********************
FFTW
*********************
P = 12 n = 4096
FFTW took 0.0004355 seconds.
Error = 5.2571e-11
*********************
JFFT
*********************
P = 12 n = 4096
JFFT took 0.0001851 seconds.
Error = 8.32846e-11
*********************
FFTW
*********************
P = 13 n = 8192
FFTW took 0.0004297 seconds.
Error = 1.91029e-10
*********************
JFFT
*********************
P = 13 n = 8192
JFFT took 0.0003238 seconds.
Error = 2.41285e-10
*********************
FFTW
*********************
P = 14 n = 16384
FFTW took 0.0011613 seconds.
Error = 5.86723e-10
*********************
JFFT
*********************
P = 14 n = 16384
JFFT took 0.0006223 seconds.
Error = 6.52764e-10
*********************
FFTW
*********************
P = 15 n = 32768
FFTW took 0.0013515 seconds.
Error = 1.75577e-09
*********************
JFFT
*********************
P = 15 n = 32768
JFFT took 0.002997 seconds.
Error = 1.86269e-09
*********************
FFTW
*********************
P = 16 n = 65536
FFTW took 0.0047178 seconds.
Error = 5.6436e-09
*********************
JFFT
*********************
P = 16 n = 65536
JFFT took 0.0031128 seconds.
Error = 5.75984e-09
*********************
FFTW
*********************
P = 17 n = 131072
FFTW took 0.0084528 seconds.
Error = 1.76568e-08
*********************
JFFT
*********************
P = 17 n = 131072
JFFT took 0.0067238 seconds.
Error = 1.76641e-08
*********************
FFTW
*********************
P = 18 n = 262144
FFTW took 0.0195919 seconds.
Error = 4.92333e-08
*********************
JFFT
*********************
P = 18 n = 262144
JFFT took 0.0175861 seconds.
Error = 4.76694e-08
*********************
FFTW
*********************
P = 19 n = 524288
FFTW took 0.0289038 seconds.
Error = 1.17298e-07
*********************
JFFT
*********************
P = 19 n = 524288
JFFT took 0.0589453 seconds.
Error = 1.45623e-07
*********************
FFTW
*********************
P = 20 n = 1048576
FFTW took 0.0718137 seconds.
Error = 3.72092e-07
*********************
JFFT
*********************
P = 20 n = 1048576
JFFT took 0.092877 seconds.
Error = 4.2469e-07
*********************
FFTW
*********************
P = 21 n = 2097152
FFTW took 0.174699 seconds.
Error = 1.08052e-06
*********************
JFFT
*********************
P = 21 n = 2097152
JFFT took 0.195441 seconds.
Error = 1.24236e-06
*********************
FFTW
*********************
P = 22 n = 4194304
FFTW took 0.368795 seconds.
Error = 3.18871e-06
*********************
JFFT
*********************
P = 22 n = 4194304
JFFT took 0.431756 seconds.
Error = 3.53914e-06
*********************
FFTW
*********************
P = 23 n = 8388608
FFTW took 0.694458 seconds.
Error = 9.07594e-06
*********************
JFFT
*********************
P = 23 n = 8388608
JFFT took 0.913373 seconds.
Error = 9.94399e-06
*********************
FFTW
*********************
P = 24 n = 16777216
FFTW took 1.43651 seconds.
Error = 2.67524e-05
*********************
JFFT
*********************
P = 24 n = 16777216
JFFT took 1.97148 seconds.
Error = 2.97006e-05
*********************
FFTW
*********************
P = 25 n = 33554432
FFTW took 3.04035 seconds.
Error = 7.21638e-05
*********************
JFFT
*********************
P = 25 n = 33554432
JFFT took 4.34667 seconds.
Error = 8.65019e-05
GFFT stands for Generic FFT and is the implementation that was presented in the article "A Simple and Efficient FFT Implementation in C++" by Volodymyr Myrnyy. It is thus similar to JFFT except for the precomputed sine and cosine tables.
JFFT is slightly faster, but more importantly is the accuracy that is a lot better for JFFT, due to the high precision sine and cosine tables that were used.
The benchmark starts from a signal with values
[0.5 1.5 2.5 3.5 4.5 5.5 ... ]
where even spots represent the real value and odd spots represent the imaginary value of the signal.
The timing below is the time spent to do a forward and inverse Fourier transform on different sizes of the input signal (see value n for the actual size).
The error is the l2 distance between the original input signal and the signal after the forward and inverse Fourier transform was applied. Theoretically both signals should be the same.
*********************
GFFT
*********************
P = 10 n = 1024
GFFT took 5.07e-05 seconds.
Error = 2.77469e-11
*********************
JFFT
*********************
P = 10 n = 1024
JFFT took 5.12e-05 seconds.
Error = 8.66112e-12
*********************
GFFT
*********************
P = 11 n = 2048
GFFT took 9.34e-05 seconds.
Error = 7.41851e-11
*********************
JFFT
*********************
P = 11 n = 2048
JFFT took 5.32e-05 seconds.
Error = 2.56608e-11
*********************
GFFT
*********************
P = 12 n = 4096
GFFT took 0.0002041 seconds.
Error = 3.30917e-10
*********************
JFFT
*********************
P = 12 n = 4096
JFFT took 0.0001165 seconds.
Error = 8.32846e-11
*********************
GFFT
*********************
P = 13 n = 8192
GFFT took 0.0004587 seconds.
Error = 8.60276e-10
*********************
JFFT
*********************
P = 13 n = 8192
JFFT took 0.0002485 seconds.
Error = 2.41285e-10
*********************
GFFT
*********************
P = 14 n = 16384
GFFT took 0.0009951 seconds.
Error = 2.6341e-09
*********************
JFFT
*********************
P = 14 n = 16384
JFFT took 0.0007858 seconds.
Error = 6.52764e-10
*********************
GFFT
*********************
P = 15 n = 32768
GFFT took 0.0019709 seconds.
Error = 1.17166e-08
*********************
JFFT
*********************
P = 15 n = 32768
JFFT took 0.0011322 seconds.
Error = 1.86269e-09
*********************
GFFT
*********************
P = 16 n = 65536
GFFT took 0.0044781 seconds.
Error = 7.70487e-08
*********************
JFFT
*********************
P = 16 n = 65536
JFFT took 0.0027097 seconds.
Error = 5.75984e-09
*********************
GFFT
*********************
P = 17 n = 131072
GFFT took 0.0098262 seconds.
Error = 4.26797e-07
*********************
JFFT
*********************
P = 17 n = 131072
JFFT took 0.0059191 seconds.
Error = 1.76641e-08
*********************
GFFT
*********************
P = 18 n = 262144
GFFT took 0.0206693 seconds.
Error = 1.85389e-06
*********************
JFFT
*********************
P = 18 n = 262144
JFFT took 0.0137888 seconds.
Error = 4.76694e-08
*********************
GFFT
*********************
P = 19 n = 524288
GFFT took 0.0450895 seconds.
Error = 6.78293e-06
*********************
JFFT
*********************
P = 19 n = 524288
JFFT took 0.0316258 seconds.
Error = 1.45623e-07
*********************
GFFT
*********************
P = 20 n = 1048576
GFFT took 0.105294 seconds.
Error = 1.84731e-05
*********************
JFFT
*********************
P = 20 n = 1048576
JFFT took 0.0769551 seconds.
Error = 4.2469e-07
*********************
GFFT
*********************
P = 21 n = 2097152
GFFT took 0.25631 seconds.
Error = 6.26402e-05
*********************
JFFT
*********************
P = 21 n = 2097152
JFFT took 0.201158 seconds.
Error = 1.24236e-06
*********************
GFFT
*********************
P = 22 n = 4194304
GFFT took 0.537161 seconds.
Error = 0.000295987
*********************
JFFT
*********************
P = 22 n = 4194304
JFFT took 0.430878 seconds.
Error = 3.53914e-06
*********************
GFFT
*********************
P = 23 n = 8388608
GFFT took 1.13658 seconds.
Error = 0.00085578
*********************
JFFT
*********************
P = 23 n = 8388608
JFFT took 0.921224 seconds.
Error = 9.94399e-06
*********************
GFFT
*********************
P = 24 n = 16777216
GFFT took 2.47917 seconds.
Error = 0.00287892
*********************
JFFT
*********************
P = 24 n = 16777216
JFFT took 2.02032 seconds.
Error = 2.97006e-05
*********************
GFFT
*********************
P = 25 n = 33554432
GFFT took 5.20966 seconds.
Error = 0.0120375
*********************
JFFT
*********************
P = 25 n = 33554432
JFFT took 4.36226 seconds.
Error = 8.65019e-05
See project bench2nr in the code repository for the Numerical Recipes algorithm.
The benchmark starts from a signal with values
[0.5 1.5 2.5 3.5 4.5 5.5 ... ]
where even spots represent the real value and odd spots represent the imaginary value of the signal.
The timing below is the time spent to do a forward and inverse Fourier transform on different sizes of the input signal (see value n for the actual size).
The error is the l2 distance between the original input signal and the signal after the forward and inverse Fourier transform was applied. Theoretically both signals should be the same.
*********************
Numerical Recipes FFT
*********************
P = 10 n = 1024
Numerical Recipes FFT took 3.52e-05 seconds.
Error = 1.68084e-11
*********************
JFFT
*********************
P = 10 n = 1024
JFFT took 4.73e-05 seconds.
Error = 8.66112e-12
*********************
Numerical Recipes FFT
*********************
P = 11 n = 2048
Numerical Recipes FFT took 6.17e-05 seconds.
Error = 5.20885e-11
*********************
JFFT
*********************
P = 11 n = 2048
JFFT took 6.36e-05 seconds.
Error = 2.56608e-11
*********************
Numerical Recipes FFT
*********************
P = 12 n = 4096
Numerical Recipes FFT took 0.0001897 seconds.
Error = 2.55807e-10
*********************
JFFT
*********************
P = 12 n = 4096
JFFT took 0.000138 seconds.
Error = 8.32846e-11
*********************
Numerical Recipes FFT
*********************
P = 13 n = 8192
Numerical Recipes FFT took 0.0004294 seconds.
Error = 7.61365e-10
*********************
JFFT
*********************
P = 13 n = 8192
JFFT took 0.0004379 seconds.
Error = 2.41285e-10
*********************
Numerical Recipes FFT
*********************
P = 14 n = 16384
Numerical Recipes FFT took 0.0009259 seconds.
Error = 2.38421e-09
*********************
JFFT
*********************
P = 14 n = 16384
JFFT took 0.000566 seconds.
Error = 6.52764e-10
*********************
Numerical Recipes FFT
*********************
P = 15 n = 32768
Numerical Recipes FFT took 0.0024159 seconds.
Error = 1.27958e-08
*********************
JFFT
*********************
P = 15 n = 32768
JFFT took 0.0011664 seconds.
Error = 1.86269e-09
*********************
Numerical Recipes FFT
*********************
P = 16 n = 65536
Numerical Recipes FFT took 0.0062476 seconds.
Error = 7.92988e-08
*********************
JFFT
*********************
P = 16 n = 65536
JFFT took 0.0026459 seconds.
Error = 5.75984e-09
*********************
Numerical Recipes FFT
*********************
P = 17 n = 131072
Numerical Recipes FFT took 0.0141679 seconds.
Error = 4.12748e-07
*********************
JFFT
*********************
P = 17 n = 131072
JFFT took 0.0092858 seconds.
Error = 1.76641e-08
*********************
Numerical Recipes FFT
*********************
P = 18 n = 262144
Numerical Recipes FFT took 0.0335481 seconds.
Error = 1.80861e-06
*********************
JFFT
*********************
P = 18 n = 262144
JFFT took 0.0151345 seconds.
Error = 4.76694e-08
*********************
Numerical Recipes FFT
*********************
P = 19 n = 524288
Numerical Recipes FFT took 0.096015 seconds.
Error = 6.76875e-06
*********************
JFFT
*********************
P = 19 n = 524288
JFFT took 0.0329845 seconds.
Error = 1.45623e-07
*********************
Numerical Recipes FFT
*********************
P = 20 n = 1048576
Numerical Recipes FFT took 0.370845 seconds.
Error = 1.83267e-05
*********************
JFFT
*********************
P = 20 n = 1048576
JFFT took 0.083529 seconds.
Error = 4.2469e-07
*********************
Numerical Recipes FFT
*********************
P = 21 n = 2097152
Numerical Recipes FFT took 0.985585 seconds.
Error = 6.30989e-05
*********************
JFFT
*********************
P = 21 n = 2097152
JFFT took 0.199259 seconds.
Error = 1.24236e-06
*********************
Numerical Recipes FFT
*********************
P = 22 n = 4194304
Numerical Recipes FFT took 2.28663 seconds.
Error = 0.000294101
*********************
JFFT
*********************
P = 22 n = 4194304
JFFT took 0.447993 seconds.
Error = 3.53914e-06
*********************
Numerical Recipes FFT
*********************
P = 23 n = 8388608
Numerical Recipes FFT took 5.28164 seconds.
Error = 0.000851496
*********************
JFFT
*********************
P = 23 n = 8388608
JFFT took 0.93264 seconds.
Error = 9.94399e-06
*********************
Numerical Recipes FFT
*********************
P = 24 n = 16777216
Numerical Recipes FFT took 12.4231 seconds.
Error = 0.00288371
*********************
JFFT
*********************
P = 24 n = 16777216
JFFT took 2.01482 seconds.
Error = 2.97006e-05
*********************
Numerical Recipes FFT
*********************
P = 25 n = 33554432
Numerical Recipes FFT took 29.2235 seconds.
Error = 0.0120259
*********************
JFFT
*********************
P = 25 n = 33554432
JFFT took 4.76568 seconds.
Error = 8.65019e-05
React
Typescript
Django
Laravel
Facebook
Microsoft
Google
Alibaba
D3
Tencent