|
NumericAL
A header-only C++20 lexer built on REAL
|
The discrete Fourier transform of a tensor along an axis, as numpy.fft.fft and numpy.fft.ifft compute it.
More...
#include <algorithm>#include <array>#include <bit>#include <cmath>#include <complex>#include <concepts>#include <cstddef>#include <memory>#include <mutex>#include <numbers>#include <optional>#include <string>#include <type_traits>#include <utility>#include <vector>#include "buffer.hpp"#include "fft_kernels.hpp"#include "gemm.hpp"#include "parallel.hpp"#include "simd.hpp"#include "tensor.hpp"#include "tensor_ops.hpp"Go to the source code of this file.
Classes | |
| struct | numerical::detail::double_double |
A double-double number: hi + lo, hi the sum rounded to double. More... | |
| struct | numerical::detail::octant_share |
e^{−2πi k/n}'s angle reduced to an eighth of a turn by integer arithmetic, 8k = octant·n + rest: the octant, and the angle's share of π/4 times n, rest (n − rest in an odd octant, measured back from its end). n is at most 2⁵⁰, so that 8k and the share are exact. More... | |
| class | numerical::detail::unit_roots |
The roots e^{−2πi k/n} of one n, each as unit_root rounds it, from two tables of about √n angles instead of a series a root: the angle's share within its octant (reduce_to_octant) split as a + b·m, m the first table's length, and its cosine and sine those of the sum of the two tables' angles in double-double arithmetic, then placed by the octant and rounded once. The share 0 is the product of two exact (1, 0), so the exact roots stay exact, and a root and its mirror image share their share, so they stay each other's conjugates to the bit. More... | |
| struct | numerical::detail::small_radix_constants< R > |
| The real constants of the radix-3, -5 and -8 butterflies, rounded once from their double-double values. More... | |
| struct | numerical::detail::bluestein_plan< R > |
Bluestein's convolution for a length n with a prime factor past fft_largest_radix. More... | |
| struct | numerical::detail::four_step_plan< R > |
A transform of n = n1·n2 points in four steps (Bailey's), each a batch of lines the threads share: x as n2 rows of n1, x[j1 + n1·j2]; each of its n1 columns transformed in place (column_plan, n2 points, a line's transform as transform_axis's along a first axis); each (k2, j1) times w^{j1·k2} (twiddles); each of its n2 rows transformed (row_plan, n1 points) and written down a column of the output, X[k2 + n2·k1] row k2's k1. Each element's operations fixed by n alone: its bits on any threads. More... | |
| struct | numerical::detail::fft_plan< R > |
| The factors and passes of a transform of one length, built once and shared. More... | |
| struct | numerical::detail::fft_complex< T > |
The complex type a transform of T computes in: T itself, or a real type's complex. More... | |
| struct | numerical::detail::fft_complex< C > |
| fft_complex of a complex type: itself. More... | |
| class | numerical::detail::fft_scratch< C, Slot > |
A transform's working space of C: the calling thread's own, kept for the next transform, up to fft_scratch_kept elements; past it, its own allocation. Each Slot is a space of its own, for spaces of one type in use at once. More... | |
| struct | numerical::detail::fft_source< T > |
The elements a transform reads where they lie, row-major, of shape shape: a tensor's, or an array's a caller lends (the Python binding's NumPy arrays). More... | |
| struct | numerical::detail::fft_output< Out > |
| The result of a transform along one axis, allocated before its plan, whose tables grow with the points: a result past memory refused at once, an empty one planned for nothing. More... | |
| struct | numerical::detail::real_fft_plan< R > |
What a transform of n real points (or to them) takes: the complex plan of n/2 points for an even n, of n for an odd one, and for an even n the roots e^{−2πi k/n} for k up to n/2. More... | |
| struct | numerical::detail::cosine_line< R > |
The cosine transforms of scipy.fft.dct, unscaled, on one line of n points by a Fourier transform: type 1 the real transform of the even extension (2(n − 1) points); type 2 the real transform of the points reordered evens then odds reversed, each frequency turned by roots (e^{−iπk/2n}), as Makhoul's; type 3 its inverse, by the inverse real transform; type 4 of an even n the complex transform of n/2 points, the even ones and the odd ones reversed paired and turned by roots (e^{−iπ(4j+1)/4n}), each frequency by turns (e^{−iπk/n}); of an odd n the complex transform of n points, 8n-th roots split as eighth roots times n-th ones (u n + 8 v = 1, as n is odd): the point 2j + 1 (mod n) the j-th times χ₈(2j + 1) + i χ₋₈(2j + 1), each value ±√2 (signs) times the real part of one frequency (picks), v (2k + 1) or its opposite (mod n), by those characters of u (2k + 1). More... | |
Namespaces | |
| namespace | numerical |
| The NumericAL public API. | |
| namespace | numerical::detail |
Concepts | |
| concept | numerical::detail::fft_input |
The types numerical, :fft transforms: float, double and their complex numbers. | |
Macros | |
| #define | NUMERICAL_FFT_LANES_TARGET |
| #define | NUMERICAL_FFT_LANES_INLINE NUMERICAL_ALWAYS_INLINE |
Typedefs | |
| template<typename C > | |
| using | numerical::detail::fft_real_t = typename C::value_type |
The part type of a complex number (R), or of a register of lines' (fft_pack). | |
| template<typename C > | |
| using | numerical::detail::fft_root_t = std::complex< fft_real_t< C > > |
The complex number of C's part type: a pass' factors. | |
Enumerations | |
| enum class | numerical::fft_norm : unsigned char { numerical::backward , numerical::ortho , numerical::forward } |
How a transform and its inverse are scaled, as NumPy's norm. More... | |
| enum class | numerical::detail::trig_family : unsigned char { numerical::detail::cosine , numerical::detail::sine } |
The family of a real trigonometric transform: dct's or dst's. More... | |
Functions | |
| double_double | numerical::detail::two_sum (double a, double b) noexcept |
a + b exactly, as a sum and its rounding error (Knuth's two-sum). | |
| double_double | numerical::detail::fast_two_sum (double a, double b) noexcept |
a + b exactly where |a| ≥ |b| or a is 0 (Dekker's fast two-sum). | |
| double_double | numerical::detail::dd_add (double_double x, double_double y) noexcept |
| The sum of two double-double numbers. | |
| double_double | numerical::detail::dd_mul (double_double x, double_double y) noexcept |
| The product of two double-double numbers, its cross terms by explicit fused multiply-adds. | |
| double_double | numerical::detail::dd_div (double_double x, double d) noexcept |
x divided by the integer d (exact in a double). | |
| const std::array< double_double, 30 > & | numerical::detail::inverse_factorials () |
| The terms of dd_sin_cos' series: 1/k! for k = 0 to 29, each from the last by dd_div. | |
| std::pair< double_double, double_double > | numerical::detail::dd_sin_cos (double_double t) |
The cosine and sine of t, in [0, π/4], as double-double numbers: their Taylor series in t² by Horner's rule to the term of degree 28 and 29, whose next terms are under 10⁻³² of the sum there. | |
| double | numerical::detail::unsigned_zero (double x) noexcept |
x with a zero's sign made positive: the twiddle factors' zeros are +0, as their exact values. | |
| double_double | numerical::detail::dd_negate (double_double x) noexcept |
x negated, both parts. | |
| octant_share | numerical::detail::reduce_to_octant (std::size_t k, std::size_t n) noexcept |
The octant_share of e^{−2πi k/n}. | |
| std::pair< double_double, double_double > | numerical::detail::place_by_octant (std::size_t octant, double_double c, double_double s) noexcept |
e^{−2πi k/n} from the cosine c and sine s of its angle within the octant octant (reduce_to_octant): as double-double parts, real then imaginary. | |
| std::pair< double_double, double_double > | numerical::detail::octant_sin_cos (std::size_t share, std::size_t n) |
The cosine and sine of (π/4)·share/n by dd_sin_cos. | |
| std::pair< double_double, double_double > | numerical::detail::unit_root_parts (std::size_t k, std::size_t n) |
e^{−2πi k/n} as double-double parts: reduce_to_octant, octant_sin_cos, place_by_octant. | |
| std::complex< double > | numerical::detail::unit_root (std::size_t k, std::size_t n) |
unit_root_parts rounded once to double, a zero's sign positive as the exact value's. | |
| template<std::floating_point R> | |
| R | numerical::detail::rounded_alone (R x) noexcept |
x, held in a register as its rounded value: GCC on arm64 with the complex-arithmetic unit (ARMv8.3's FCMLA: -mcpu=apple-m1, Neoverse V1) recognizes a·b − c·d, a·d + c·b as a complex product and fuses one product into the other's sum whatever -ffp-contract says; elsewhere x as it is. | |
| template<std::floating_point R> | |
| std::complex< R > | numerical::detail::rounded_product (const std::complex< R > &p, const std::complex< R > &q) noexcept |
p · q of complex numbers, each product rounded apart from the sum it enters (statements of their own, rounded_alone). | |
| template<std::floating_point R> | |
| std::complex< R > | numerical::detail::fused_product (const std::complex< R > &w, const std::complex< R > &v) noexcept |
w · v of complex numbers on the vector paths: w.re·v.re − w.im·v.im and w.re·v.im + w.im·v.re, each the second product rounded, the first fused with the sum by std::fma. | |
| template<bool Fused, std::floating_point R> requires Fused | |
| std::complex< R > | numerical::detail::twiddled (const std::complex< R > &w, const std::complex< R > &v) noexcept |
A butterfly's factor times v on the vector paths: fused_product. | |
| template<bool Fused, std::floating_point R> requires (!Fused) | |
| std::complex< R > | numerical::detail::twiddled (const std::complex< R > &w, const std::complex< R > &v) noexcept |
A butterfly's factor times v on the portable path: rounded_product. | |
| std::vector< std::size_t > | numerical::detail::fft_radices (std::size_t n) |
The radix of each Stockham pass of n, or none where n has a prime factor past fft_largest_radix, its powers of two first (4 first, its stride 1, then 16 while 16 points remain, then 8 or 4), then its factors 3, 5 and 7, then each other prime in ascending order, then a lone factor 2 last, where its pass has no factor. | |
| template<std::floating_point R> | |
| small_radix_constants< R > | numerical::detail::make_small_radix_constants () |
small_radix_constants from the roots of order 3 and 5 (unit_root, whose imaginary parts are −sin). | |
| template<std::floating_point R> | |
| void | numerical::detail::forward_fft (const fft_plan< R > &plan, std::complex< R > *data, std::complex< R > *work, bool fused, bool in_work) |
The forward transform of the plan's length into data, work its fft_plan::work, its Stockham passes, or Bluestein's convolution, or its four steps, the products fused where fused (fft_fuses): the input in data, or in work where in_work (only where fft_starts_in_work). | |
| template<std::floating_point R> | |
| bool | numerical::detail::fft_starts_in_work (const fft_plan< R > &plan) noexcept |
Whether a transform under plan, its input placed in its working space (forward_fft's in_work), ends in its data without a copy: an odd number of Stockham passes, no Bluestein's convolution nor four steps. | |
| std::size_t | numerical::detail::four_step_columns (std::size_t n, std::size_t bytes) |
The columns n1 of a transform of n points of bytes each in four steps: the largest divisor of n at most √n, n of at least fft_four_step_least bytes; else 0, one transform of passes. n is taken in passes (its prime factors at most fft_largest_radix: make_fft_plan settles Bluestein's lengths first). Such an n, 2¹⁸ and more (√n at least 512), has a divisor from 16 to √n, so that neither side is short: a prime factor past 15 (at most 61), or else the product of its smallest prime factors first past 15 (at most 15·13). | |
| std::size_t | numerical::detail::bluestein_length (std::size_t n) |
The points of Bluestein's convolution of n points: the power of two at least 2n − 1, or the shortest length of factors 2, 3 and 5 at least 2n − 1 where it is at most 3/5 of that power and the power at least 1024 (passes of 3 and 5 cost more a point than those of 16: ten AVX-512 cores, 4099 points 156 µs over 16 384, 95 over 8640; 1009 points 18 µs over 2048, 30 over 2025; 67 points 1.3 µs over 256, 1.9 over 135). | |
| std::size_t | numerical::detail::largest_prime_factor (std::size_t n) noexcept |
The largest prime factor of n, at least 2. | |
| template<std::floating_point R> | |
| fft_plan< R > | numerical::detail::make_fft_plan (std::size_t n) |
The fft_plan of length n, its roots computed on the threads (each the same on any). | |
| template<std::floating_point R> | |
| std::shared_ptr< const fft_plan< R > > | numerical::detail::shared_fft_plan (std::size_t n) |
The shared fft_plan of length n, built on first use and kept among the fft_plans_kept most recently used. | |
| template<bool Fused, typename C > | |
| void | numerical::detail::radix_four_pass_body (std::size_t current, std::size_t stride, const C *in, C *out, const fft_root_t< C > *twiddles) noexcept |
One Stockham pass of radix 4 over in into out: current points at stride stride, so current · stride is the length. Element q + stride · (p + j · current/4) of the input is the j-th input of butterfly (p, q), whose outputs go to q + stride · (4p + j), the last three times w^{jp} (twiddled), none for p = 0. | |
| template<bool Fused, std::floating_point R> | |
| void | numerical::detail::radix_four_pass (std::size_t current, std::size_t stride, const std::complex< R > *in, std::complex< R > *out, const std::complex< R > *twiddles) noexcept |
radix_four_pass_body of complex numbers, its products as Fused. | |
| template<typename C > | |
| void | numerical::detail::four_point (const C &v0, const C &v1, const C &v2, const C &v3, C *y) noexcept |
A 4-point transform of v0 to v3 into y: the radix-4 butterfly's sums, in its order. | |
| template<bool Fused, typename C > | |
| void | numerical::detail::radix_sixteen_pass_body (std::size_t current, std::size_t stride, const C *in, C *out, const fft_root_t< C > *twiddles, const std::array< fft_root_t< C >, 16 > &sixteenths) noexcept |
One Stockham pass of radix 16 over in into out, as radix_four_pass is of radix 4: each butterfly a 16-point transform as two of 4 points, x_{j1 + 4·j2} first transformed over j2, each result (j1, k2) then times e^{−2πi j1·k2/16} (sixteenths; −i exactly where j1·k2 is 4), then over j1 into output 4·k1 + k2; output k of butterfly p times w^{kp}, none for p = 0. Fused as twiddled. | |
| template<bool Fused, std::floating_point R> | |
| void | numerical::detail::radix_sixteen_pass (std::size_t current, std::size_t stride, const std::complex< R > *in, std::complex< R > *out, const std::complex< R > *twiddles, const std::array< std::complex< R >, 16 > &sixteenths) noexcept |
radix_sixteen_pass_body of complex numbers, its products as Fused. | |
| template<std::floating_point R> | |
| std::complex< R > | numerical::detail::scaled (R c, const std::complex< R > &v) noexcept |
c · v of a real c and a complex v: each part's product, rounded. | |
| template<bool Fused, std::floating_point R> requires Fused | |
| std::complex< R > | numerical::detail::scaled_add (const std::complex< R > &s, R c, const std::complex< R > &v) noexcept |
s + c · v of a complex s, a real c and a complex v on the vector paths: each part one fused multiply-add. | |
| template<bool Fused, std::floating_point R> requires (!Fused) | |
| std::complex< R > | numerical::detail::scaled_add (const std::complex< R > &s, R c, const std::complex< R > &v) noexcept |
| scaled_add on the portable path: the product rounded first. | |
| template<bool Fused, typename C > | |
| void | numerical::detail::any_radix_pass_body (std::size_t radix, std::size_t current, std::size_t stride, const C *in, C *out, const fft_root_t< C > *twiddles, const fft_root_t< C > *roots) noexcept |
One Stockham pass of an odd radix radix, as radix_four_pass is of 4, by the symmetry of its roots (radix_five_pass_body's, any odd r): a_j = x_j + x_{r−j}, b_j = x_j − x_{r−j} (j from 1 to h = (r − 1)/2); X_0 = x_0 + a_1 + … + a_h, and for k from 1 to h, A_k = x_0 + Σ_j cos(2πjk/r)·a_j, B_k = Σ_j sin(2πjk/r)·b_j, each sum in ascending j, its products fused as Fused (scaled_add; the cosines and sines roots' parts, jk reduced mod r by additions), X_k = A_k − i·B_k, X_{r−k} = A_k + i·B_k; output k then times w^{kp}, none for p = 0. Radices 3 and 5 so computed give their own butterflies' bits. Inlined into each caller, so that the x86-64 fused one is built for FMA. | |
| template<bool Fused, typename C > | |
| void | numerical::detail::radix_three_pass_body (std::size_t current, std::size_t stride, const C *in, C *out, const fft_root_t< C > *twiddles, const small_radix_constants< fft_real_t< C > > &k) noexcept |
One Stockham pass of radix 3, as any_radix_pass_body is of any: t = x1 + x2, v = x0 − t/2 (exact halving, one rounding), u = (√3/2)·(x1 − x2); X0 = x0 + t, X1 = v − i·u, X2 = v + i·u, then times w^{kp} as Fused. Inlined into each caller. | |
| template<bool Fused, typename C > | |
| void | numerical::detail::radix_five_pass_body (std::size_t current, std::size_t stride, const C *in, C *out, const fft_root_t< C > *twiddles, const small_radix_constants< fft_real_t< C > > &k) noexcept |
One Stockham pass of radix 5: t1 = x1 + x4, t2 = x2 + x3, t3 = x1 − x4, t4 = x2 − x3; a1 = x0 + c1·t1 + c2·t2, a2 = x0 + c2·t1 + c1·t2, b1 = s1·t3 + s2·t4, b2 = s2·t3 − s1·t4 (each sum in that order, its products fused as Fused); X0 = x0 + t1 + t2, X1 = a1 − i·b1, X4 = a1 + i·b1, X2 = a2 − i·b2, X3 = a2 + i·b2, then times w^{kp}. Inlined into each caller. | |
| template<bool Fused, typename C > | |
| void | numerical::detail::radix_eight_pass_body (std::size_t current, std::size_t stride, const C *in, C *out, const fft_root_t< C > *twiddles, fft_real_t< C > half_root_two) noexcept |
One Stockham pass of radix 8, as radix_four_pass is of 4: a_j = x_j + x_{j+4}, b_j = x_j − x_{j+4} (j below 4), b_j then times e^{−2πi j/8} (√½·(re + im, im − re), (im, −re), √½·(im − re, −(re + im)): each sum then its product, no fused operation, so the same bits on every path); the even outputs a's four_point, the odd ones b's; output k then times w^{kp} as Fused, none for p = 0. half_root_two is √½. | |
| template<bool Fused, std::floating_point R> | |
| void | numerical::detail::any_radix_pass (std::size_t radix, std::size_t current, std::size_t stride, const std::complex< R > *in, std::complex< R > *out, const std::complex< R > *twiddles, const std::complex< R > *roots, const small_radix_constants< R > &small) noexcept |
any_radix_pass_body, its products as Fused. | |
| template<typename C > | |
| void | numerical::detail::radix_two_pass (std::size_t stride, const C *in, C *out) noexcept |
The last pass of an odd power of two: butterflies of radix 2 at stride stride, no factor. | |
| template<std::floating_point R, typename C , typename Four , typename Sixteen , typename Other > | |
| void | numerical::detail::stockham_passes (const fft_plan< R > &plan, C *data, C *work, Four four, Sixteen sixteen, Other other, bool from_work=false) noexcept |
The Stockham passes of the plan over data, work as long, the result in data: radix 4 by four (radix_four_pass's arguments), 16 by sixteen (radix_sixteen_pass's), 2 by radix_two_pass (always the last pass), any other by other (any_radix_pass's: 3 and 5 by their own butterflies). The input in data, or from_work in work (fft_starts_in_work: an odd number of passes then ends in data, where from data the last pass wrote work, copied back). | |
| bool | numerical::detail::fft_fuses () noexcept |
| Whether a transform's butterflies fuse their products (fused_product): on every path past the portable. | |
| template<bool Fused, std::floating_point R> | |
| void | numerical::detail::bluestein_body (const fft_plan< R > &plan, std::complex< R > *data, std::complex< R > *work) |
Bluestein's transform of the plan's length in place in data, work its fft_plan::work, the input times the chirp, padded to M; its transform times the chirp's spectrum; the inverse transform of that (conj(fft(conj ·)), then 1/M, exact for a power of two), times the chirp. Products as Fused. Inlined into each caller. | |
| template<bool Fused, std::floating_point R> | |
| void | numerical::detail::twiddle_run_body (std::complex< R > *t, const std::complex< R > *w, std::size_t count) noexcept |
t[i] = w[i] · t[i] for count elements, as Fused (twiddled). Inlined into each caller. | |
| template<std::floating_point R> | |
| void | numerical::detail::twiddle_run (std::complex< R > *t, const std::complex< R > *w, std::size_t count, bool fused) noexcept |
| twiddle_run_body on the path in use. | |
| template<std::floating_point R> | |
| void | numerical::detail::four_step_fft (const fft_plan< R > &plan, const std::complex< R > *in, std::complex< R > *out, std::complex< R > *work, bool fused, bool inverse=false, R scale=R(1)) |
The transform of the plan's four_step_plan of in into out (in itself or apart from it), work its fft_plan::work (the columns' transforms, then the rows'), the products fused where fused; the inverse's conj(fft(conj x)) and times scale as transform_axis's lines. | |
| template<std::floating_point R> | |
| R | numerical::detail::fft_scale (fft_norm norm, bool inverse, std::size_t n) |
The scale of a transform's output for norm, forward or not, of length n: 1 where none. | |
| template<std::floating_point R> | |
| std::size_t | numerical::detail::fft_lane_groups (const fft_plan< R > &, bool, std::size_t, bool) noexcept |
| No registers of lines. | |
| template<typename T , std::floating_point R> | |
| void | numerical::detail::fft_lines_together (const fft_plan< R > &, const T *, std::size_t, std::size_t, std::size_t, std::complex< R > *, std::size_t, std::size_t, bool, R) noexcept |
| Never called: no registers of lines. | |
| template<std::floating_point R> | |
| void | numerical::detail::columns_fft (const fft_plan< R > &plan, const std::complex< R > *data, std::size_t columns, std::complex< R > *to, std::size_t to_rows, bool fused, bool conjugated) |
The transforms of plan's length along each of the columns columns of data into those of to (data's rows of columns, to's to_rows apart, as many as the plan's points): registers of neighbouring columns where they fill one (fft_lane_groups), the rest up to fft_column_block of them at a time, each row read and written as that many neighbours; the threads share them. Where conjugated, conj(fft(conj x)). | |
| template<std::floating_point R> | |
| void | numerical::detail::twiddled_rows_fft (const fft_plan< R > &plan, std::complex< R > *data, std::size_t rows, std::size_t apart, const std::complex< R > *twiddles, bool fused, std::complex< R > *out, bool inverse, R scale) |
Each of the rows rows of data (apart from one another; conjugated first where inverse) times its run of twiddles (each as long as the rows), then transformed in place (plan's length), then written down a column of out, row r's element k to out[r + rows·k], conjugated where inverse and times scale: fft_four_step_band rows a task, still in the caches, each element of out written among that many neighbours. | |
| template<typename T > | |
| fft_source< T > | numerical::detail::source_of (const tensor< T > &a) |
a's elements, where they lie. | |
| template<typename T , typename F > | |
| auto | numerical::detail::transformed_along (const tensor< T > &a, std::ptrdiff_t axis, const F &f) -> decltype(f(source_of(a), axis)) |
f (f(source, axis), a transform along axis, negative from the last) of a: a transpose's elements as they lie where as_laid_along reads them (each line transformed on its own, its bits the same); any other tensor's row-major. | |
| template<typename C > | |
| void | numerical::detail::fft_load_line (const C *in, std::size_t kept, std::size_t points, bool inverse, C *to) noexcept |
The first kept of points elements of a line, in, into to, conjugated where inverse, then zeros. Its bounds and flags by value: read through a caller's references, each would be loaded again at every element, the writes to to possibly aliasing them, and the loop would not vectorise. | |
| template<typename C > | |
| void | numerical::detail::fft_finish_line (C *line, std::size_t points, bool inverse, typename C::value_type scale) noexcept |
A transformed line of points elements, line, conjugated back where inverse, then times scale where it is not 1; by value for the reason fft_load_line gives. | |
| template<split_complex T> | |
| tensor< T > | numerical::detail::transform_axis (const fft_source< T > &a, const std::optional< std::size_t > &n, std::ptrdiff_t axis, fft_norm norm, bool inverse) |
The transform of complex a along axis, n points (the axis cut or padded with zeros to it, as NumPy's), forward or inverse (conj(fft(conj x)), exact), scaled for norm. Each line gathered, transformed and scattered on its own, the lines shared among the threads: a line's bits are its own. (A real input takes real_transform_of.) | |
| template<std::floating_point R> | |
| std::shared_ptr< const real_fft_plan< R > > | numerical::detail::shared_real_fft_plan (std::size_t n) |
The real_fft_plan of n, shared as shared_fft_plan shares the complex ones. | |
| template<std::floating_point R> | |
| std::size_t | numerical::detail::no_registers (std::size_t, const std::complex< R > *, const std::complex< R > *, std::complex< R > *) noexcept |
No recombination by registers: the scalar loop's from k = 1. | |
| template<std::floating_point R> | |
| void | numerical::detail::real_forward_whole (std::size_t n, const R *x, std::complex< R > *X, bool fused) |
The first n/2 + 1 frequencies of the n real points x into X by the complex transform of n points, the products fused where fused: an even n's line holding an infinity or a NaN, which the recombination of its pairs would turn into NaN (∞ − ∞) where the complex transform carries it. | |
| template<std::floating_point R> | |
| void | numerical::detail::real_inverse_whole (std::size_t n, const std::complex< R > *X, R *x, R factor, bool fused) |
The n real points x from the n/2 + 1 frequencies X by the complex transform of n points (conj(fft(conj ·)) of the Hermitian spectrum, the imaginary parts of X_0 and X_{n/2} read as 0), times factor: an even n's spectrum holding an infinity or a NaN (real_forward_whole). | |
| template<bool Fused, std::floating_point R, typename Registers > | |
| void | numerical::detail::real_forward_body (const real_fft_plan< R > &plan, const R *x, std::complex< R > *X, std::complex< R > *work, Registers registers) |
The transform of n real points x (together) into X (n/2 + 1 complex numbers), work holding n/2 + 1 complex numbers beside the plan's work. An even n = 2h: the h complex numbers x_{2j} + i·x_{2j+1} transformed, then X_k = E_k + w^k·O_k, E_k = (Z_k + conj Z_{h−k})/2, O_k = −i·(Z_k − conj Z_{h−k})/2 (exact halvings and products by ±i; w^k·O_k as Fused), registers (h, Z, roots, X) computing the first of them and returning the next k. An odd n: the complex transform of the points, its first n/2 + 1 outputs. Inlined into each caller. | |
| template<bool Fused, std::floating_point R, typename Registers > | |
| void | numerical::detail::real_inverse_body (const real_fft_plan< R > &plan, const std::complex< R > *X, R *x, std::complex< R > *work, R scale, Registers registers) |
The inverse of real_forward_body, unscaled save its own halvings: n real points x from the n/2 + 1 complex numbers X (the imaginary parts of X_0 and, for an even n, X_{n/2} read as 0, as NumPy's). An even n = 2h: Z_k = E_k + i·O_k, E_k = (X_k + conj X_{h−k})/2, O_k = conj(w^k)·(X_k − conj X_{h−k})/2, then Z's inverse transform (conj(fft(conj ·))), its parts x_{2j} and x_{2j+1}, times scale, registers (h, X, roots, conj Z) computing the first conj Z_k and returning the next k; an odd n: the Hermitian spectrum of n points, its inverse transform's real parts times scale. Inlined into each caller. | |
| template<std::floating_point R> | |
| void | numerical::detail::real_forward (const real_fft_plan< R > &plan, const R *x, std::complex< R > *X, std::complex< R > *work, bool fused) |
| real_forward_body on the path in use. | |
| template<std::floating_point R> | |
| void | numerical::detail::real_inverse (const real_fft_plan< R > &plan, const std::complex< R > *X, R *x, std::complex< R > *work, R scale, bool fused) |
| real_inverse_body on the path in use. | |
| template<typename In , typename Out , typename C , typename Line > | |
| tensor< Out > | numerical::detail::lines_along (const fft_source< In > &a, std::size_t index, std::size_t in_points, fft_output< Out > &&result, std::size_t work, Line line) |
A transform of each line of a along axis index into the lines of result: each line gathered (its first in_points elements, padded with zeros), passed with its output line, both together, and the thread's working space of work elements of C to line, then scattered; a line together and not padded passed where it lies, its output line too. The lines shared among the threads. result holds elements: its callers return an empty one before they plan. | |
| std::size_t | numerical::detail::fft_axis_index (std::ptrdiff_t axis, std::size_t rank, const char *who) |
axis of a tensor of rank rank from 0, NumPy's negative axes read from the end. | |
| template<std::floating_point R> | |
| tensor< std::complex< R > > | numerical::detail::real_input_transform (const fft_source< R > &a, std::size_t index, std::size_t points, bool inverse, R scale) |
The transform of real a along the axis index into all n frequencies, or the inverse transform where inverse: each line's real transform (real_forward, its n/2 + 1 non-negative frequencies), the rest by Hermitian symmetry, X_{n−k} = conj X_k, exactly; a length whose complex transform takes four steps, which half of it does not, by that complex transform, on the threads. The inverse of a real line the conjugate of its transform. Then times scale. | |
| template<std::floating_point T> | |
| tensor< std::complex< T > > | numerical::detail::real_transform_of (const fft_source< T > &a, const std::optional< std::size_t > &n, std::ptrdiff_t axis, fft_norm norm, bool inverse) |
fft or ifft (inverse) of the real elements a: fft of a real tensor's computation, of elements a caller lends. | |
| template<std::floating_point T> | |
| tensor< std::complex< T > > | numerical::detail::rfft_of (const fft_source< T > &a, const std::optional< std::size_t > &n, std::ptrdiff_t axis, fft_norm norm) |
rfft's computation, of real elements a caller lends. | |
| template<std::floating_point T> | |
| tensor< T > | numerical::detail::irfft_of (const fft_source< std::complex< T > > &a, const std::optional< std::size_t > &n, std::ptrdiff_t axis, fft_norm norm) |
irfft's computation, of complex elements a caller lends. | |
| template<detail::fft_input T> requires detail::split_complex<T> | |
| tensor< T > | numerical::fft (const tensor< T > &a, std::optional< std::size_t > n=std::nullopt, std::ptrdiff_t axis=-1, fft_norm norm=fft_norm::backward) |
The discrete Fourier transform of a along axis, as numpy.fft.fft: X_k = Σ_j x_j e^{−2πi jk/n}. | |
| template<std::floating_point T> | |
| tensor< std::complex< T > > | numerical::fft (const tensor< T > &a, std::optional< std::size_t > n=std::nullopt, std::ptrdiff_t axis=-1, fft_norm norm=fft_norm::backward) |
The discrete Fourier transform of real a along axis, as numpy.fft.fft of a real array: its non-negative frequencies by the real transform (rfft's), the others by their Hermitian symmetry, X_{n−k} = conj X_k exactly; a length whose complex transform takes four steps (four_step_plan) as a complex one, on the threads. | |
| template<detail::fft_input T> requires detail::split_complex<T> | |
| tensor< T > | numerical::ifft (const tensor< T > &a, std::optional< std::size_t > n=std::nullopt, std::ptrdiff_t axis=-1, fft_norm norm=fft_norm::backward) |
The inverse discrete Fourier transform of a along axis, as numpy.fft.ifft: x_j = (1/n) Σ_k X_k e^{2πi jk/n} with the default norm. | |
| template<std::floating_point T> | |
| tensor< std::complex< T > > | numerical::ifft (const tensor< T > &a, std::optional< std::size_t > n=std::nullopt, std::ptrdiff_t axis=-1, fft_norm norm=fft_norm::backward) |
The inverse discrete Fourier transform of real a along axis, as numpy.fft.ifft of a real array: the conjugate of its transform (fft of a real tensor), scaled as the inverse. | |
| template<typename T > | |
| tensor< T > | numerical::detail::rolled (const tensor< T > &a, const std::vector< std::size_t > &shifts) |
a rolled along every axis, element j of axis d to (j + shifts[d]) mod n_d, in one copy: each row of the result along its last axis read from its source row, in two contiguous pieces; the rows shared among the threads. | |
| template<typename T > | |
| tensor< T > | numerical::fftshift (const tensor< T > &a, const std::vector< std::ptrdiff_t > &axes, bool inverse=false) |
a with its axes axes rolled so that each one's element 0 lands at its middle, as numpy.fft.fftshift: element j of each to (j + n/2) mod n, an axis given twice rolled twice; or back, as numpy.fft.ifftshift, where inverse. In one copy, whatever the axes. | |
| template<typename T > | |
| tensor< T > | numerical::fftshift (const tensor< T > &a, std::ptrdiff_t axis=-1, bool inverse=false) |
a with its axis axis rolled so that its element 0 lands at its middle, as numpy.fft.fftshift along one axis: element j to (j + n/2) mod n; or back, as numpy.fft.ifftshift, where inverse. | |
| template<std::floating_point T> | |
| tensor< std::complex< T > > | numerical::rfft (const tensor< T > &a, std::optional< std::size_t > n=std::nullopt, std::ptrdiff_t axis=-1, fft_norm norm=fft_norm::backward) |
The discrete Fourier transform of real a along axis, its n/2 + 1 non-negative frequencies, as numpy.fft.rfft. An even n by the complex transform of its n/2 pairs and their recombination, an odd one by the complex transform of its points. | |
| template<std::floating_point T> | |
| tensor< T > | numerical::irfft (const tensor< std::complex< T > > &a, std::optional< std::size_t > n=std::nullopt, std::ptrdiff_t axis=-1, fft_norm norm=fft_norm::backward) |
The inverse of rfft along axis, as numpy.fft.irfft: n real points from the first n/2 + 1 frequencies of a (cut, or padded with zeros), the imaginary parts of the zero frequency and of an even n's last read as 0. | |
| constexpr fft_norm | numerical::swapped (fft_norm norm) noexcept |
norm with its forward and backward exchanged, as NumPy's hfft and ihfft take it. | |
| template<std::floating_point T> | |
| tensor< T > | numerical::hfft (const tensor< std::complex< T > > &a, std::optional< std::size_t > n=std::nullopt, std::ptrdiff_t axis=-1, fft_norm norm=fft_norm::backward) |
The transform of a signal of Hermitian symmetry, its n real points from the non-negative frequencies a, as numpy.fft.hfft: irfft of conj(a), its scaling's direction exchanged. | |
| template<std::floating_point T> | |
| tensor< std::complex< T > > | numerical::ihfft (const tensor< T > &a, std::optional< std::size_t > n=std::nullopt, std::ptrdiff_t axis=-1, fft_norm norm=fft_norm::backward) |
The inverse of hfft, as numpy.fft.ihfft: conj(rfft(a)), its scaling's direction exchanged. | |
| std::size_t | numerical::detail::eighth_inverse (std::size_t n) noexcept |
The inverse of 8 modulo the odd n, in [0, n): by Euclid's algorithm extended. | |
| template<std::floating_point R> | |
| cosine_line< R > | numerical::detail::make_cosine_line (int type, std::size_t n) |
The cosine_line of type on n points, its plan and roots formed: each root e^{−iπa/d} (d of n, 2n or 4n) as unit_roots of 8n rounds e^{−2πi(4n·a/d)/8n}, in double-double arithmetic on the threads, so the same on every platform. | |
| template<std::floating_point R> | |
| std::shared_ptr< const cosine_line< R > > | numerical::detail::shared_cosine_line (int type, std::size_t n) |
The shared cosine_line of type on n points, built on first use and kept among the fft_plans_kept most recently used, as shared_fft_plan keeps its plans. | |
| template<std::floating_point R> | |
| tensor< R > | numerical::detail::trig_transform (const fft_source< R > &source, trig_family family, int type, const std::optional< std::size_t > &n, std::ptrdiff_t axis, fft_norm norm, const std::optional< bool > &orthogonalize, bool inverse) |
dct, idct, dst or idst (family, inverse) of source along axis, as scipy.fft's: the type computed (an inverse's of types 2 and 3 the other), on each line of n points (the axis cut or padded), the sines by the cosines: type 1 the real transform of the odd extension (2(n + 1) points), type 2 the cosines of the points of alternate signs, in reverse order; types 3 and 4 those of the points reversed, of alternate signs. Scaled as norm says, orthogonalize (by default where norm is ortho) the first or last points and values weighted by √2 as SciPy's. The elements of source are read where they lie. | |
| template<std::floating_point R> | |
| tensor< R > | numerical::detail::trig_transform (const tensor< R > &a, trig_family family, int type, const std::optional< std::size_t > &n, std::ptrdiff_t axis, fft_norm norm, const std::optional< bool > &orthogonalize, bool inverse) |
trig_transform of the tensor a. | |
| template<std::floating_point T> | |
| tensor< T > | numerical::dct (const tensor< T > &a, int type=2, std::optional< std::size_t > n=std::nullopt, std::ptrdiff_t axis=-1, fft_norm norm=fft_norm::backward, std::optional< bool > orthogonalize=std::nullopt) |
The discrete cosine transform of real a along axis, as scipy.fft.dct: type 2 by default, y_k = 2 Σ_j x_j cos(πk(2j + 1)/2n); type 1 x_0 + (−1)^k x_{n−1} + 2 Σ_{0<j<n−1} x_j cos(πjk/(n − 1)); type 3 x_0 + 2 Σ_{j>0} x_j cos(πj(2k + 1)/2n); type 4 2 Σ_j x_j cos(π(2j + 1)(2k + 1)/4n). By a Fourier transform of n points (2(n − 1) for type 1). | |
| template<std::floating_point T> | |
| tensor< T > | numerical::idct (const tensor< T > &a, int type=2, std::optional< std::size_t > n=std::nullopt, std::ptrdiff_t axis=-1, fft_norm norm=fft_norm::backward, std::optional< bool > orthogonalize=std::nullopt) |
The inverse of dct of the same type, as scipy.fft.idct: the transform of type 3 for type 2 and of type 2 for type 3 (types 1 and 4 their own), scaled by 1/2n (1/2(n − 1) for type 1) by default. | |
| template<std::floating_point T> | |
| tensor< T > | numerical::dst (const tensor< T > &a, int type=2, std::optional< std::size_t > n=std::nullopt, std::ptrdiff_t axis=-1, fft_norm norm=fft_norm::backward, std::optional< bool > orthogonalize=std::nullopt) |
The discrete sine transform of real a along axis, as scipy.fft.dst: type 2 by default, y_k = 2 Σ_j x_j sin(π(k + 1)(2j + 1)/2n); type 1 2 Σ_j x_j sin(π(j + 1)(k + 1)/(n + 1)); type 3 (−1)^k x_{n−1} + 2 Σ_{j<n−1} x_j sin(π(j + 1)(2k + 1)/2n); type 4 2 Σ_j x_j sin(π(2j + 1)(2k + 1)/4n). Type 1 by a real Fourier transform of 2(n + 1) points, the others by dct's. | |
| template<std::floating_point T> | |
| tensor< T > | numerical::idst (const tensor< T > &a, int type=2, std::optional< std::size_t > n=std::nullopt, std::ptrdiff_t axis=-1, fft_norm norm=fft_norm::backward, std::optional< bool > orthogonalize=std::nullopt) |
The inverse of dst of the same type, as scipy.fft.idst: the transform of type 3 for type 2 and of type 2 for type 3 (types 1 and 4 their own), scaled by 1/2n (1/2(n + 1) for type 1) by default. | |
Variables | |
| constexpr double_double | numerical::detail::quarter_pi {0x1.921fb54442d18p-1, 0x1.1a62633145c07p-55} |
| π/4 as a double-double number. | |
| constexpr std::size_t | numerical::detail::fft_largest_radix {61} |
The largest prime a Stockham pass takes as its radix, by its own r-point sum: a length with a larger prime factor is transformed by Bluestein's convolution. | |
| constexpr std::size_t | numerical::detail::fft_four_step_least {std::size_t {1} << 22} |
The fewest bytes of complex numbers a transform takes in four steps (four_step_plan), whose columns and rows the threads share: fewer stay in the caches through the passes of one transform, faster on a thread alone (ten AVX-512 cores: complex64 2¹⁸ points 1.5 ms in passes, 2.0 in four steps). From 4 MiB (complex128 2¹⁸ points: 5.0 ms in passes, 3.8 in four steps on all threads, 5.4 on one; M1 Pro, one thread, 3.6 against 2.1 ms). By the length and the type alone, so that a transform's bits are its own on any threads. | |
| constexpr std::size_t | numerical::detail::fft_four_step_pad {8} |
| The complex numbers past each row of the four steps' working space: rows a power of two of bytes apart fall in a few sets of the first-level cache, a column's elements evicting one another. | |
| template<std::floating_point R> | |
| constexpr std::size_t | numerical::detail::fft_four_step_band {256 / sizeof(std::complex<R>)} |
| The rows of the four steps' working space a task transforms together, then writes down the columns of the output: 256 bytes of neighbours (four cache lines) for each of a row's elements. | |
| constexpr std::size_t | numerical::detail::fft_split_least {8192} |
The fewest points of a length with a prime factor p past fft_largest_radix, not prime, that takes Bluestein's convolution for p alone, in two steps (four_step_plan: p points one way, n/p the other), n/p at least 16: fewer, or fewer than 16 transforms of p points, run the convolution over the whole length faster (ten AVX-512 cores: 1009·16 points 521 µs whole, 372 in two steps; 67·64 98 against 109; 67·1024 3.7 against 2.6 ms). | |
| constexpr std::size_t | numerical::detail::fft_root_cost {100} |
| A root of unity's cost in parallel_for's units, about a nanosecond each: some 95 ns in double-double (unit_roots::parts). | |
| constexpr std::size_t | numerical::detail::fft_plans_kept {32} |
| The plans kept, the least recently used dropped past it: a plan in use lives on in its holders. | |
| constexpr std::size_t | numerical::detail::fft_scratch_kept {std::size_t {1} << 16} |
The most elements fft_scratch keeps on a thread between transforms: 1 MiB of complex double. | |
| template<std::floating_point R> | |
| constexpr std::size_t | numerical::detail::fft_lines_width {1} |
| One line at a time where no register holds lines. | |
| constexpr std::size_t | numerical::detail::fft_column_block {8} |
| The lines a task of transform_axis takes together along an axis whose lines lie apart: each row read and written as that many neighbours, where one line at a time took one element of each row. | |
The discrete Fourier transform of a tensor along an axis, as numpy.fft.fft and numpy.fft.ifft compute it.
Every length runs in O(n log n). A length whose prime factors are at most 61 runs Stockham passes, each reading and writing in order, their radices fixed by the length alone (fft_radices): its powers of two first (4, then 16 while 16 points remain, then 4), then 3, 5 and 7, then each other prime, a lone factor 2 last. Radices 3 and 5 take their own butterflies, a larger prime its r-point sum. A prime past 61 runs Bluestein's convolution over three transforms of a power of two, or of a length of factors 2, 3 and 5 at most 3/5 of it (bluestein_length). A length of 4 MiB and more runs in four steps (four_step_plan): its columns' transforms, the twiddle factors, its rows'; so does, from 8192 points, a length with a prime factor p past 61 and at least 16 times p (fft_split_least), Bluestein's convolution then of p points alone; a shorter one runs it over the whole length. The twiddle factors are computed in double-double arithmetic by one fixed sequence of operations, each a sum or an explicit fused multiply-add that no compiler may contract otherwise, then rounded once: the same factors on every machine, whatever its sin and cos.
Two sets of bits, each the same on every machine and compiler, any number of threads, a line alone or among others, whatever its axis: the portable path's, whose butterflies round each product apart from its sum (built, as the library's builds are, with no contraction across statements: -ffp-contract=on or off), and the vector paths' (NEON, AMX, AVX2, AVX-512 alike), which fuse them. A change to a length's radices or to a butterfly's arithmetic changes that length's last bits, and is noted as such.
Definition in file fft.hpp.
| #define NUMERICAL_FFT_LANES_INLINE NUMERICAL_ALWAYS_INLINE |