README.md
1PocketFFT
2---------
3
4This is a heavily modified implementation of FFTPack [1,2], with the following
5advantages:
6
7- strictly C99 compliant
8- more accurate twiddle factor computation
9- very fast plan generation
10- worst case complexity for transform sizes with large prime factors is
11 `N*log(N)`, because Bluestein's algorithm [3] is used for these cases.
12
13
14Some code details
15-----------------
16
17Twiddle factor computation:
18
19- making use of symmetries to reduce number of sin/cos evaluations
20- all angles are reduced to the range `[0; pi/4]` for higher accuracy
21- an adapted implementation of `sincospi()` is used, which actually computes
22 `sin(x)` and `(cos(x)-1)`.
23- if `n` sin/cos pairs are required, the adjusted `sincospi()` is only called
24 `2*sqrt(n)` times; the remaining values are obtained by evaluating the
25 angle addition theorems in a numerically accurate way.
26
27Parallel invocation:
28
29- Plans only contain read-only data; all temporary arrays are allocated and
30 deallocated during an individual FFT execution. This means that a single plan
31 can be used in several threads at the same time.
32
33Efficient codelets are available for the factors:
34
35- 2, 3, 4, 5, 7, 11 for complex-valued FFTs
36- 2, 3, 4, 5 for real-valued FFTs
37
38Larger prime factors are handled by somewhat less efficient, generic routines.
39
40For lengths with very large prime factors, Bluestein's algorithm is used, and
41instead of an FFT of length `n`, a convolution of length `n2 >= 2*n-1`
42is performed, where `n2` is chosen to be highly composite.
43
44
45[1] Swarztrauber, P. 1982, Vectorizing the Fast Fourier Transforms
46 (New York: Academic Press), 51
47[2] https://www.netlib.org/fftpack/
48[3] https://en.wikipedia.org/wiki/Chirp_Z-transform
49