NumericAL
A header-only C++20 lexer built on REAL
Loading...
Searching...
No Matches
fft.hpp
Go to the documentation of this file.
1
22#ifndef NUMERICAL_FFT_HPP
23#define NUMERICAL_FFT_HPP
24
25#include <algorithm>
26#include <array>
27#include <bit>
28#include <cmath>
29#include <complex>
30#include <concepts>
31#include <cstddef>
32#include <memory>
33#include <mutex>
34#include <numbers>
35#include <optional>
36#include <string>
37#include <type_traits>
38#include <utility>
39#include <vector>
40
41#include "buffer.hpp"
42#include "fft_kernels.hpp"
43#include "gemm.hpp"
44#include "parallel.hpp"
45#include "simd.hpp"
46#include "tensor.hpp"
47#include "tensor_ops.hpp"
48
49namespace numerical {
50
52 enum class fft_norm : unsigned char
53 {
54 backward,
55 ortho,
56 forward,
57 };
58
59 namespace detail {
60
63 {
64 double hi;
65 double lo;
66 };
67
69 [[nodiscard]] inline double_double two_sum(double a,
70 double b) noexcept
71 {
72 const double sum {a + b};
73 const double b_part {sum - a};
74 const double a_part {sum - b_part};
75 const double b_error {b - b_part};
76 const double a_error {a - a_part};
77 return {sum, a_error + b_error};
78 }
79
82 double b) noexcept
83 {
84 const double sum {a + b};
85 const double b_out {sum - a};
86 return {sum, b - b_out};
87 }
88
91 double_double y) noexcept
92 {
93 const double_double high {two_sum(x.hi, y.hi)};
94 const double_double low {two_sum(x.lo, y.lo)};
95 double error {high.lo + low.hi};
96 const double_double part {fast_two_sum(high.hi, error)};
97 error = part.lo + low.lo;
98 return fast_two_sum(part.hi, error);
99 }
100
103 double_double y) noexcept
104 {
105 const double product {x.hi * y.hi};
106 double error {std::fma(x.hi, y.hi, -product)};
107 error = std::fma(x.hi, y.lo, error);
108 error = std::fma(x.lo, y.hi, error);
109 return fast_two_sum(product, error);
110 }
111
114 double d) noexcept
115 {
116 const double first {x.hi / d};
117 double remainder {std::fma(-first, d, x.hi)}; // exact: the quotient's rounding error times d
118 remainder = remainder + x.lo;
119 return fast_two_sum(first, remainder / d);
120 }
121
123 inline constexpr double_double quarter_pi {0x1.921fb54442d18p-1, 0x1.1a62633145c07p-55};
124
126 [[nodiscard]] inline const std::array<double_double, 30>& inverse_factorials()
127 {
128 static const std::array<double_double, 30> table {[] {
129 std::array<double_double, 30> terms {};
130 terms[0] = {1.0, 0.0};
131 for (std::size_t k {1}; k < terms.size(); ++k) {
132 terms[k] = dd_div(terms[k - 1], static_cast<double>(k));
133 }
134 return terms;
135 }()};
136 return table;
137 }
138
143 [[nodiscard]] inline std::pair<double_double, double_double> dd_sin_cos(double_double t)
144 {
145 const std::array<double_double, 30>& terms {inverse_factorials()};
146 const double_double square {dd_mul(t, t)};
147 double_double cosine {terms[28]};
148 double_double sine {terms[29]};
149 for (std::size_t k {28}; k >= 2; k -= 2) { // cos: Σ (−1)ᵏ t²ᵏ/(2k)!, sin: t · Σ (−1)ᵏ t²ᵏ/(2k + 1)!
150 const double_double c {terms[k - 2]};
151 const double_double s {terms[k - 1]};
154 cosine = dd_add(c, {-cosine_step.hi, -cosine_step.lo});
155 sine = dd_add(s, {-sine_step.hi, -sine_step.lo});
156 }
157 return {cosine, dd_mul(sine, t)};
158 }
159
161 [[nodiscard]] inline double unsigned_zero(double x) noexcept
162 {
163 return x == 0.0 ? 0.0 : x;
164 }
165
168 {
169 return {-x.hi, -x.lo};
170 }
171
176 {
177 std::size_t octant;
178 std::size_t share;
179 };
180
182 [[nodiscard]] inline octant_share reduce_to_octant(std::size_t k,
183 std::size_t n) noexcept
184 {
185 const std::size_t eighths {8 * (k % n)};
186 const std::size_t octant {eighths / n};
187 const std::size_t rest {eighths % n};
188 return {octant, (octant % 2) == 1 ? n - rest : rest};
189 }
190
193 [[nodiscard]] inline std::pair<double_double, double_double> place_by_octant(std::size_t octant,
195 double_double s) noexcept
196 {
199 switch (octant) { // the angle (π/4)·(octant + rest/n): within an odd octant, measured back from its end
200 case 1: cosine = s; sine = c; break;
201 case 2: cosine = dd_negate(s); sine = c; break;
202 case 3: cosine = dd_negate(c); sine = s; break;
203 case 4: cosine = dd_negate(c); sine = dd_negate(s); break;
204 case 5: cosine = dd_negate(s); sine = dd_negate(c); break;
205 case 6: cosine = s; sine = dd_negate(c); break;
206 case 7: cosine = c; sine = dd_negate(s); break;
207 default: break; // the first octant as computed
208 }
209 return {cosine, dd_negate(sine)};
210 }
211
213 [[nodiscard]] inline std::pair<double_double, double_double> octant_sin_cos(std::size_t share,
214 std::size_t n)
215 {
216 return dd_sin_cos(dd_mul(quarter_pi, dd_div({static_cast<double>(share), 0.0}, static_cast<double>(n))));
217 }
218
220 [[nodiscard]] inline std::pair<double_double, double_double> unit_root_parts(std::size_t k,
221 std::size_t n)
222 {
224 const auto [c, s] {octant_sin_cos(reduced.share, n)};
225 return place_by_octant(reduced.octant, c, s);
226 }
227
229 [[nodiscard]] inline std::complex<double> unit_root(std::size_t k,
230 std::size_t n)
231 {
232 const auto [re, im] {unit_root_parts(k, n)};
233 return {unsigned_zero(re.hi), unsigned_zero(im.hi)};
234 }
235
245 {
246 public:
247
249 explicit unit_roots(std::size_t n)
250 : n_ {n}, m_ {static_cast<std::size_t>(std::sqrt(static_cast<double>(n))) + 1}
251 {
252 low_.reserve(m_);
253 for (std::size_t a {0}; a < m_; ++a) {
254 low_.push_back(octant_sin_cos(a, n));
255 }
256 for (std::size_t b {0}; b * m_ <= n; ++b) {
257 high_.push_back(octant_sin_cos(b * m_, n));
258 }
259 }
260
262 [[nodiscard]] std::pair<double_double, double_double> parts(std::size_t k) const noexcept
263 {
265 const std::pair<double_double, double_double>& low {low_[reduced.share % m_]};
266 const std::pair<double_double, double_double>& high {high_[reduced.share / m_]};
267 const double_double cosine {dd_add(dd_mul(low.first, high.first), dd_negate(dd_mul(low.second, high.second)))};
268 const double_double sine {dd_add(dd_mul(low.second, high.first), dd_mul(low.first, high.second))};
269 return place_by_octant(reduced.octant, cosine, sine);
270 }
271
273 [[nodiscard]] std::complex<double> root(std::size_t k) const noexcept
274 {
275 const auto [re, im] {parts(k)};
276 return {unsigned_zero(re.hi), unsigned_zero(im.hi)};
277 }
278
279 private:
280
281 std::size_t n_;
282 std::size_t m_;
283 std::vector<std::pair<double_double, double_double>> low_;
284 std::vector<std::pair<double_double, double_double>> high_;
285 };
286
290 template <std::floating_point R>
292 {
293#if defined(__GNUC__) && !defined(__clang__) && defined(__aarch64__)
294 __asm__ ("" : "+w" (x)); // NOLINT(hicpp-no-assembler): no builtin keeps a value from GCC's complex patterns
295#endif
296 return x;
297 }
298
301 template <std::floating_point R>
302 [[nodiscard]] NUMERICAL_ALWAYS_INLINE std::complex<R> rounded_product(const std::complex<R>& p,
303 const std::complex<R>& q) noexcept
304 {
305 const R rr {p.real() * q.real()};
306 const R ii {rounded_alone(p.imag() * q.imag())};
307 const R ri {p.real() * q.imag()};
308 const R ir {rounded_alone(p.imag() * q.real())};
309 return {rr - ii, ri + ir};
310 }
311
314 template <std::floating_point R>
315 [[nodiscard]] NUMERICAL_ALWAYS_INLINE std::complex<R> fused_product(const std::complex<R>& w,
316 const std::complex<R>& v) noexcept
317 {
318 const R ii {w.imag() * v.imag()};
319 const R ir {w.imag() * v.real()};
320 return {std::fma(w.real(), v.real(), -ii), std::fma(w.real(), v.imag(), ir)};
321 }
322
324 template <bool Fused,
325 std::floating_point R>
326 requires Fused
327 [[nodiscard]] NUMERICAL_ALWAYS_INLINE std::complex<R> twiddled(const std::complex<R>& w,
328 const std::complex<R>& v) noexcept
329 {
330 return fused_product(w, v);
331 }
332
334 template <bool Fused,
335 std::floating_point R>
336 requires (!Fused)
337 [[nodiscard]] NUMERICAL_ALWAYS_INLINE std::complex<R> twiddled(const std::complex<R>& w,
338 const std::complex<R>& v) noexcept
339 {
340 return rounded_product(w, v);
341 }
342
343 // The lanes' functions: built for AVX2 with FMA on x86-64, and there inlined by the compiler's choice where the passes'
344 // bodies, built for no unit of their own, are inlined into their callers built for those units (an always-inlined
345 // function of a unit its caller lacks is refused); always inlined elsewhere.
346#if defined(NUMERICAL_X86_COMPILED)
347# define NUMERICAL_FFT_LANES_TARGET NUMERICAL_TARGET("avx2,fma") // NOLINT(cppcoreguidelines-macro-usage): an attribute, which no function can stand for
348# if defined(_MSC_VER) && !defined(__clang__)
349# define NUMERICAL_FFT_LANES_INLINE NUMERICAL_ALWAYS_INLINE // NOLINT(cppcoreguidelines-macro-usage): the same
350# else
351# define NUMERICAL_FFT_LANES_INLINE NUMERICAL_TARGET("avx2,fma") inline // NOLINT(cppcoreguidelines-macro-usage): the same
352# endif
353#else
354# define NUMERICAL_FFT_LANES_TARGET
355# define NUMERICAL_FFT_LANES_INLINE NUMERICAL_ALWAYS_INLINE // NOLINT(cppcoreguidelines-macro-usage): the same
356#endif
357
358#if defined(NUMERICAL_X86_COMPILED) || defined(NUMERICAL_NEON_COMPILED)
359# define NUMERICAL_FFT_LANES // lines transformed a register of them at a time (tested with #ifdef only)
360
361# if defined(NUMERICAL_X86_COMPILED)
365 using fft_lanes_float = __m256;
366
369 __m256d b) noexcept
370 {
371 return avx2_add(a, b);
372 }
373
376 __m256 b) noexcept
377 {
378 return avx2_add(a, b);
379 }
380
383 __m256d b) noexcept
384 {
385 return avx2_sub(a, b);
386 }
387
390 __m256 b) noexcept
391 {
392 return avx2_sub(a, b);
393 }
394
397 __m256d b) noexcept
398 {
399 return avx2_mul(a, b);
400 }
401
404 __m256 b) noexcept
405 {
406 return avx2_mul(a, b);
407 }
408
411 __m256d b,
412 __m256d c) noexcept
413 {
414 return avx2_fma(a, b, c);
415 }
416
419 __m256 b,
420 __m256 c) noexcept
421 {
422 return avx2_fma(a, b, c);
423 }
424
427 {
428 return avx2_negated(a);
429 }
430
433 {
434 return avx2_negated(a);
435 }
436
439 {
440 return avx2_splat(c);
441 }
442
445 {
446 return avx2_splat(c);
447 }
448
451 std::size_t apart) noexcept
452 {
454 }
455
457 NUMERICAL_FFT_LANES_INLINE void lanes_read(const std::complex<double>* at,
458 std::size_t apart,
459 __m256d& re,
460 __m256d& im) noexcept
461 {
462 const double* const from {reinterpret_cast<const double*>(at)}; // NOLINT(cppcoreguidelines-pro-type-reinterpret-cast): a complex number is its two parts ([complex.numbers])
463 const __m256d even {_mm256_set_m128d(_mm_loadu_pd(from + (4 * apart)), _mm_loadu_pd(from))}; // r0 i0 | r2 i2
464 const __m256d odd {_mm256_set_m128d(_mm_loadu_pd(from + (6 * apart)), _mm_loadu_pd(from + (2 * apart)))}; // r1 i1 | r3 i3
465 re = _mm256_unpacklo_pd(even, odd); // r0 r1 | r2 r3
467 }
468
470 NUMERICAL_FFT_LANES_INLINE void lanes_read(const std::complex<float>* at,
471 std::size_t apart,
472 __m256& re,
473 __m256& im) noexcept
474 {
475 const double* const from {reinterpret_cast<const double*>(at)}; // NOLINT(cppcoreguidelines-pro-type-reinterpret-cast): a complex float is eight bytes, read whole
476 const __m256 low {_mm256_set_m128(lanes_two(from + (4 * apart), apart), lanes_two(from, apart))}; // r0 i0 r1 i1 | r4 i4 r5 i5
477 const __m256 high {_mm256_set_m128(lanes_two(from + (6 * apart), apart), lanes_two(from + (2 * apart), apart))}; // r2 i2 r3 i3 | r6 i6 r7 i7
478 re = _mm256_shuffle_ps(low, high, 0x88); // r0 r1 r2 r3 | r4 r5 r6 r7
479 im = _mm256_shuffle_ps(low, high, 0xDD);
480 }
481
483 NUMERICAL_FFT_LANES_INLINE void lanes_write(std::complex<double>* at,
484 std::size_t apart,
485 __m256d re,
486 __m256d im) noexcept
487 {
488 double* const into {reinterpret_cast<double*>(at)}; // NOLINT(cppcoreguidelines-pro-type-reinterpret-cast): a complex number is its two parts ([complex.numbers])
489 const __m256d even {_mm256_unpacklo_pd(re, im)}; // r0 i0 | r2 i2
490 const __m256d odd {_mm256_unpackhi_pd(re, im)}; // r1 i1 | r3 i3
494 _mm_storeu_pd(into + (6 * apart), _mm256_extractf128_pd(odd, 1));
495 }
496
498 NUMERICAL_FFT_LANES_INLINE void lanes_write(std::complex<float>* at,
499 std::size_t apart,
500 __m256 re,
501 __m256 im) noexcept
502 {
503 double* const into {reinterpret_cast<double*>(at)}; // NOLINT(cppcoreguidelines-pro-type-reinterpret-cast): a complex float is eight bytes, written whole
504 const __m256d low {_mm256_castps_pd(_mm256_unpacklo_ps(re, im))}; // r0 i0 r1 i1 | r4 i4 r5 i5
505 const __m256d high {_mm256_castps_pd(_mm256_unpackhi_ps(re, im))}; // r2 i2 r3 i3 | r6 i6 r7 i7
506 const __m128d l0 {_mm256_castpd256_pd128(low)};
507 const __m128d l1 {_mm256_extractf128_pd(low, 1)};
508 const __m128d h0 {_mm256_castpd256_pd128(high)};
509 const __m128d h1 {_mm256_extractf128_pd(high, 1)};
510 _mm_storel_pd(into, l0);
511 _mm_storeh_pd(into + apart, l0);
512 _mm_storel_pd(into + (2 * apart), h0);
513 _mm_storeh_pd(into + (3 * apart), h0);
514 _mm_storel_pd(into + (4 * apart), l1);
515 _mm_storeh_pd(into + (5 * apart), l1);
516 _mm_storel_pd(into + (6 * apart), h1);
517 _mm_storeh_pd(into + (7 * apart), h1);
518 }
519
520# else
525
528 float64x2_t b) noexcept
529 {
530 return vaddq_f64(a, b);
531 }
532
535 float32x4_t b) noexcept
536 {
537 return vaddq_f32(a, b);
538 }
539
542 float64x2_t b) noexcept
543 {
544 return vsubq_f64(a, b);
545 }
546
549 float32x4_t b) noexcept
550 {
551 return vsubq_f32(a, b);
552 }
553
556 float64x2_t b) noexcept
557 {
558 return vmulq_f64(a, b);
559 }
560
563 float32x4_t b) noexcept
564 {
565 return vmulq_f32(a, b);
566 }
567
570 float64x2_t b,
571 float64x2_t c) noexcept
572 {
573 return vfmaq_f64(c, a, b);
574 }
575
578 float32x4_t b,
579 float32x4_t c) noexcept
580 {
581 return vfmaq_f32(c, a, b);
582 }
583
586 {
587 return vnegq_f64(a);
588 }
589
592 {
593 return vnegq_f32(a);
594 }
595
598 {
599 return vdupq_n_f64(c);
600 }
601
604 {
605 return vdupq_n_f32(c);
606 }
607
609 NUMERICAL_ALWAYS_INLINE void lanes_read(const std::complex<double>* at,
610 std::size_t apart,
611 float64x2_t& re,
612 float64x2_t& im) noexcept
613 {
614 const double* const from {reinterpret_cast<const double*>(at)}; // NOLINT(cppcoreguidelines-pro-type-reinterpret-cast): a complex number is its two parts ([complex.numbers])
615 const float64x2_t first {vld1q_f64(from)};
616 const float64x2_t second {vld1q_f64(from + (2 * apart))};
617 re = vzip1q_f64(first, second);
618 im = vzip2q_f64(first, second);
619 }
620
622 NUMERICAL_ALWAYS_INLINE void lanes_read(const std::complex<float>* at,
623 std::size_t apart,
624 float32x4_t& re,
625 float32x4_t& im) noexcept
626 {
627 const float* const from {reinterpret_cast<const float*>(at)}; // NOLINT(cppcoreguidelines-pro-type-reinterpret-cast): a complex number is its two parts ([complex.numbers])
628 const float32x4_t low {vcombine_f32(vld1_f32(from), vld1_f32(from + (2 * apart)))}; // r0 i0 r1 i1
629 const float32x4_t high {vcombine_f32(vld1_f32(from + (4 * apart)), vld1_f32(from + (6 * apart)))}; // r2 i2 r3 i3
630 re = vuzp1q_f32(low, high);
631 im = vuzp2q_f32(low, high);
632 }
633
635 NUMERICAL_ALWAYS_INLINE void lanes_write(std::complex<double>* at,
636 std::size_t apart,
637 float64x2_t re,
638 float64x2_t im) noexcept
639 {
640 double* const into {reinterpret_cast<double*>(at)}; // NOLINT(cppcoreguidelines-pro-type-reinterpret-cast): a complex number is its two parts ([complex.numbers])
641 vst1q_f64(into, vzip1q_f64(re, im));
642 vst1q_f64(into + (2 * apart), vzip2q_f64(re, im));
643 }
644
646 NUMERICAL_ALWAYS_INLINE void lanes_write(std::complex<float>* at,
647 std::size_t apart,
648 float32x4_t re,
649 float32x4_t im) noexcept
650 {
651 float* const into {reinterpret_cast<float*>(at)}; // NOLINT(cppcoreguidelines-pro-type-reinterpret-cast): a complex number is its two parts ([complex.numbers])
652 const float32x4_t first {vzip1q_f32(re, im)}; // r0 i0 r1 i1
653 const float32x4_t last {vzip2q_f32(re, im)}; // r2 i2 r3 i3
654 vst1_f32(into, vget_low_f32(first));
655 vst1_f32(into + (2 * apart), vget_high_f32(first));
656 vst1_f32(into + (4 * apart), vget_low_f32(last));
657 vst1_f32(into + (6 * apart), vget_high_f32(last));
658 }
659
660# endif
661
663 template <std::floating_point R>
664 struct fft_lanes_register;
665
667 template <>
669 {
670 using type = fft_lanes_double;
671 };
672
674 template <>
676 {
677 using type = fft_lanes_float;
678 };
679
681 template <std::floating_point R>
682 using fft_lanes_of = typename fft_lanes_register<R>::type;
683
688 template <std::floating_point R>
689 struct alignas(sizeof(fft_lanes_of<R>)) fft_pack // a register's own alignment, which GCC drops from an alias of it
690 {
692 };
693
695 template <std::floating_point R>
697 fft_pack<R> b) noexcept
698 {
699 return {lanes_add(a.v, b.v)};
700 }
701
703 template <std::floating_point R>
705 fft_pack<R> b) noexcept
706 {
707 return {lanes_sub(a.v, b.v)};
708 }
709
711 template <std::floating_point R>
713 {
714 return {lanes_negated(a.v)};
715 }
716
718 template <std::floating_point R>
720 fft_pack<R> a) noexcept
721 {
722 return {lanes_mul(lanes_splat(c), a.v)};
723 }
724
726 template <std::floating_point R>
728 fft_pack<R> a,
729 fft_pack<R> b) noexcept
730 {
731 return {lanes_fused(lanes_splat(c), a.v, b.v)};
732 }
733
739 template <std::floating_point R>
740 struct fft_lanes
741 {
742 using value_type = R;
743
744 fft_pack<R> re;
745 fft_pack<R> im;
746
749 {
750 return re;
751 }
752
755 {
756 return im;
757 }
758
761 {
762 re = re + other.re;
763 im = im + other.im;
764 return *this;
765 }
766 };
767
769 template <std::floating_point R>
770 inline constexpr std::size_t fft_lanes_width {sizeof(fft_lanes_of<R>) / sizeof(R)};
771
773 template <std::floating_point R>
775 const fft_lanes<R>& b) noexcept
776 {
777 return {a.re + b.re, a.im + b.im};
778 }
779
781 template <std::floating_point R>
783 const fft_lanes<R>& b) noexcept
784 {
785 return {a.re - b.re, a.im - b.im};
786 }
787
789 template <bool Fused,
790 std::floating_point R>
791 requires Fused
792 [[nodiscard]] NUMERICAL_FFT_LANES_INLINE fft_lanes<R> twiddled(const std::complex<R>& w,
793 const fft_lanes<R>& v) noexcept
794 {
795 const fft_pack<R> ii {w.imag() * v.im};
796 const fft_pack<R> ir {w.imag() * v.re};
797 return {fused(w.real(), v.re, -ii), fused(w.real(), v.im, ir)};
798 }
799
800#endif
801
804 inline constexpr std::size_t fft_largest_radix {61};
805#if defined(NUMERICAL_X86_COMPILED) || defined(NUMERICAL_NEON_COMPILED)
806 static_assert(fft_largest_radix / 2 <= fft_most_pairs, "fft_radix_any_pass holds every pair of the largest radix");
807#endif
808
814 [[nodiscard]] inline std::vector<std::size_t> fft_radices(std::size_t n)
815 {
816 std::vector<std::size_t> radices;
817 std::size_t twos {std::size_t {1} << static_cast<unsigned>(std::countr_zero(n))};
818 std::size_t rest {n / twos};
819 if (twos >= 4) {
820 radices.push_back(4);
821 twos /= 4;
822 }
823 for (; twos >= 16; twos /= 16) {
824 radices.push_back(16);
825 }
826 if (twos == 8) {
827 radices.push_back(8); // three factors of 2: one pass, where 4 and 2 took two
828 twos = 1;
829 }
830 for (; twos >= 4; twos /= 4) {
831 radices.push_back(4);
832 }
833 for (std::size_t prime {3}; rest > 1; prime += 2) {
834 if (prime > fft_largest_radix) {
835 return {}; // Bluestein's
836 }
837 for (; rest % prime == 0; rest /= prime) {
838 radices.push_back(prime);
839 }
840 }
841 if (twos == 2) {
842 radices.push_back(2); // last: no factor
843 }
844 return radices;
845 }
846
848 template <std::floating_point R>
858
861 template <std::floating_point R>
863 {
864 const std::complex<double> third {unit_root(1, 3)};
865 const std::complex<double> fifth {unit_root(1, 5)};
866 const std::complex<double> fifth2 {unit_root(2, 5)};
867 return {static_cast<R>(-third.imag()), static_cast<R>(fifth.real()), static_cast<R>(fifth2.real()), static_cast<R>(-fifth.imag()),
868 static_cast<R>(-fifth2.imag()), static_cast<R>(unit_root(1, 8).real())};
869 }
870
871 template <std::floating_point R>
872 struct fft_plan;
873
875 template <std::floating_point R>
877 {
878 std::size_t padded {0};
879 std::vector<std::complex<R>> chirp;
880 std::vector<std::complex<R>> spectrum;
881 std::shared_ptr<const fft_plan<R>> inner;
882 };
883
892 inline constexpr std::size_t fft_four_step_least {std::size_t {1} << 22};
893
896 inline constexpr std::size_t fft_four_step_pad {8};
897
900 template <std::floating_point R>
901 inline constexpr std::size_t fft_four_step_band {256 / sizeof(std::complex<R>)};
902
911 template <std::floating_point R>
913 {
914 std::size_t columns {0};
915 std::size_t rows {0};
916 std::shared_ptr<const fft_plan<R>> column_plan;
917 std::shared_ptr<const fft_plan<R>> row_plan;
918 std::vector<std::complex<R>> twiddles;
919 };
920
922 template <std::floating_point R>
923 struct fft_plan
924 {
925 std::size_t length {0};
926 std::vector<std::size_t> radices;
927 std::vector<std::complex<R>> twiddles;
929 std::vector<std::complex<R>> radix_roots;
931 std::array<std::complex<R>, 16> sixteenths;
932 std::optional<bluestein_plan<R>> bluestein;
933 std::optional<four_step_plan<R>> four_step;
935 std::size_t work {0};
937 };
938
939 template <std::floating_point R>
940 void forward_fft(const fft_plan<R>& plan,
941 std::complex<R>* data,
942 std::complex<R>* work,
943 bool fused,
944 bool in_work = false);
945
948 template <std::floating_point R>
950 {
951 return !plan.bluestein && !plan.four_step && plan.radices.size() % 2 == 1;
952 }
953
962 [[nodiscard]] inline std::size_t four_step_columns(std::size_t n,
963 std::size_t bytes)
964 {
965 if (n < fft_four_step_least / bytes) {
966 return 0;
967 }
968 std::size_t columns {static_cast<std::size_t>(std::sqrt(static_cast<double>(n)))}; // ⌊√n⌋: sqrt rounds correctly, n below 2⁵²
969 while (n % columns != 0) {
970 --columns;
971 }
972 return columns;
973 }
974
982 [[nodiscard]] inline std::size_t bluestein_length(std::size_t n)
983 {
984 const std::size_t least {(2 * n) - 1};
985 const std::size_t power {std::bit_ceil(least)};
986 if (power < 1024) {
987 return power;
988 }
989 std::size_t best {power};
990 for (std::size_t fives {1}; fives < best; fives *= 5) {
991 for (std::size_t odd {fives}; odd < best; odd *= 3) {
992 std::size_t m {odd};
993 while (m < least) {
994 m *= 2;
995 }
996 best = std::min(best, m);
997 }
998 }
999 return 5 * best <= 3 * power ? best : power;
1000 }
1001
1009 inline constexpr std::size_t fft_split_least {8192};
1010
1012 [[nodiscard]] inline std::size_t largest_prime_factor(std::size_t n) noexcept
1013 {
1014 std::size_t largest {1};
1015 for (std::size_t d {2}; d <= n / d; ++d) {
1016 while (n % d == 0) {
1017 largest = d;
1018 n /= d;
1019 }
1020 }
1021 return n > 1 ? n : largest;
1022 }
1023
1026 inline constexpr std::size_t fft_root_cost {100};
1027
1029 template <std::floating_point R>
1031 {
1032 using C = std::complex<R>;
1033 const auto narrow {[](std::complex<double> value) { return C {static_cast<R>(value.real()), static_cast<R>(value.imag())}; }};
1034 fft_plan<R> plan {.length = n, .radices = fft_radices(n), .twiddles = {}, .radix_roots = {}, .sixteenths = {}, .bluestein = {},
1035 .four_step = {}, .work = n, .small = make_small_radix_constants<R>()};
1036 for (std::size_t k {0}; k < 16; ++k) {
1037 plan.sixteenths[k] = narrow(unit_root(k, 16));
1038 }
1039 const std::size_t rough {plan.radices.empty() && n > 1 ? largest_prime_factor(n) : 0};
1040 const bool split {rough != 0 && rough != n && n / rough >= 16 && n >= fft_split_least};
1041 if (rough != 0 && !split) { // Bluestein's: X_k = c_k · Σ_j (x_j c_j) · conj(c_{k−j}), c_j = e^{−πi j²/n}
1042 bluestein_plan<R> b {.padded = bluestein_length(n), .chirp = {}, .spectrum = {}, .inner = {}};
1043 const unit_roots doubled {2 * n};
1044 b.chirp.resize(n);
1045 parallel_for(n, fft_root_cost, [&](std::size_t j) { b.chirp[j] = narrow(doubled.root((j * j) % (2 * n))); });
1046 b.inner = std::make_shared<const fft_plan<R>>(make_fft_plan<R>(b.padded));
1047 b.spectrum.assign(b.padded, C {});
1048 for (std::size_t j {0}; j < n; ++j) {
1049 b.spectrum[j] = std::conj(b.chirp[j]);
1050 b.spectrum[(b.padded - j) % b.padded] = std::conj(b.chirp[j]);
1051 }
1052 std::vector<C> scratch(b.inner->work);
1053 forward_fft(*b.inner, b.spectrum.data(), scratch.data(), false, false); // the portable arithmetic: the same on every path
1054 plan.work = b.padded + b.inner->work; // the convolution's sequence, then its transforms' space
1055 plan.bluestein = std::move(b);
1056 return plan;
1057 }
1058 // Bluestein's along the rows where `p` is the longer side, read where they lie, else down the columns: the
1059 // columns' transforms gather a few of them at a time, each no longer than √n.
1060 const std::size_t columns {split ? std::max(rough, n / rough) : four_step_columns(n, sizeof(C))};
1061 if (columns != 0) {
1062 four_step_plan<R> f {.columns = columns, .rows = n / columns, .column_plan = {}, .row_plan = {}, .twiddles = {}};
1063 f.column_plan = std::make_shared<const fft_plan<R>>(make_fft_plan<R>(f.rows));
1064 f.row_plan = std::make_shared<const fft_plan<R>>(make_fft_plan<R>(f.columns));
1065 f.twiddles.resize(n);
1066 const unit_roots roots {n};
1067 parallel_for(f.rows, f.columns * fft_root_cost, [&](std::size_t k2) {
1068 for (std::size_t j1 {0}; j1 < f.columns; ++j1) {
1069 f.twiddles[(k2 * f.columns) + j1] = narrow(roots.root((j1 * k2) % n));
1070 }
1071 });
1072 plan.radices.clear();
1073 plan.work = f.rows * (f.columns + fft_four_step_pad); // the columns' transforms, then the rows'
1074 plan.four_step = std::move(f);
1075 return plan;
1076 }
1077 // Each pass' runs, one a power: the root of `p·power·stride` for `p` from 1 (0 multiplies by nothing), each
1078 // computed on whichever thread, the same root.
1079 std::vector<std::size_t> starts; // where each run begins among the twiddles, the last their count
1080 std::vector<std::size_t> steps; // each run's `power·stride`
1081 std::size_t current {n};
1082 std::size_t stride {1};
1083 starts.push_back(0);
1084 for (const std::size_t radix : plan.radices) {
1085 for (std::size_t power {1}; power < radix; ++power) {
1086 starts.push_back(starts.back() + (current / radix) - 1);
1087 steps.push_back(power * stride);
1088 }
1089 if (radix > 5 && radix != 8 && radix != 16) {
1090 for (std::size_t m {0}; m < radix; ++m) {
1091 plan.radix_roots.push_back(narrow(unit_root(m, radix)));
1092 }
1093 }
1094 current /= radix;
1095 stride *= radix;
1096 }
1097 const unit_roots roots {n};
1098 plan.twiddles.resize(starts.back());
1099 parallel_for(starts.back(), fft_root_cost, [&](std::size_t at) {
1100 const auto run {static_cast<std::size_t>(std::upper_bound(starts.begin(), starts.end(), at) - starts.begin()) - 1};
1101 const std::size_t p {at - starts[run] + 1};
1102 plan.twiddles[at] = narrow(roots.root(p * steps[run]));
1103 });
1104 return plan;
1105 }
1106
1108 inline constexpr std::size_t fft_plans_kept {32};
1109
1112 template <std::floating_point R>
1113 [[nodiscard]] std::shared_ptr<const fft_plan<R>> shared_fft_plan(std::size_t n)
1114 {
1115 struct entry
1116 {
1117 std::size_t length;
1118 std::shared_ptr<const fft_plan<R>> plan;
1119 };
1120 static std::mutex guard;
1121 static std::vector<entry> plans; // the most recently used last
1122 const auto kept = [n]() -> std::shared_ptr<const fft_plan<R>> { // under the lock
1123 const auto found {std::find_if(plans.begin(), plans.end(), [n](const entry& e) { return e.length == n; })};
1124 if (found == plans.end()) {
1125 return nullptr;
1126 }
1127 std::rotate(found, found + 1, plans.end());
1128 return plans.back().plan;
1129 };
1130 {
1131 const std::scoped_lock lock {guard};
1132 if (auto plan {kept()}) {
1133 return plan;
1134 }
1135 }
1136 // Built with the lock released, so that no transform of another length waits on it; a plan another thread built
1137 // for the same length meanwhile, the same plan, replaced.
1138 auto built {std::make_shared<const fft_plan<R>>(make_fft_plan<R>(n))};
1139 const std::scoped_lock lock {guard};
1140 std::erase_if(plans, [n](const entry& e) { return e.length == n; });
1141 if (plans.size() >= fft_plans_kept) {
1142 plans.erase(plans.begin());
1143 }
1144 plans.push_back({n, std::move(built)});
1145 return plans.back().plan;
1146 }
1147
1149 template <typename C>
1150 using fft_real_t = typename C::value_type;
1151
1153 template <typename C>
1154 using fft_root_t = std::complex<fft_real_t<C>>;
1155
1162 template <bool Fused,
1163 typename C>
1165 std::size_t stride,
1166 const C * in,
1167 C * out,
1168 const fft_root_t<C>* twiddles) noexcept
1169 {
1170 const std::size_t quarter {current / 4};
1171 const std::size_t run {quarter - 1}; // the factors of each power
1172 const std::size_t apart {stride * quarter};
1173 for (std::size_t p {0}; p < quarter; ++p) {
1174 const C* const in_p {in + (stride * p)};
1175 C* const to {out + (stride * 4 * p)};
1176 for (std::size_t q {0}; q < stride; ++q) {
1177 const C a {in_p[q]};
1178 const C b {in_p[q + apart]};
1179 const C c {in_p[q + (2 * apart)]};
1180 const C d {in_p[q + (3 * apart)]};
1181 const C a_plus_c {a + c};
1182 const C a_minus_c {a - c};
1183 const C b_plus_d {b + d};
1184 const C b_minus_d {b - d};
1185 const C i_b_minus_d {-b_minus_d.imag(), b_minus_d.real()}; // i·(b − d), exact
1186 const C first {a_minus_c - i_b_minus_d};
1187 const C second {a_plus_c - b_plus_d};
1188 const C third {a_minus_c + i_b_minus_d};
1189 to[q] = a_plus_c + b_plus_d;
1190 to[q + stride] = p == 0 ? first : twiddled<Fused>(twiddles[p - 1], first);
1191 to[q + 2 * stride] = p == 0 ? second : twiddled<Fused>(twiddles[run + p - 1], second);
1192 to[q + 3 * stride] = p == 0 ? third : twiddled<Fused>(twiddles[(2 * run) + p - 1], third);
1193 }
1194 }
1195 }
1196
1198 template <bool Fused,
1199 std::floating_point R>
1200 void radix_four_pass(std::size_t current,
1201 std::size_t stride,
1202 const std::complex<R>* in,
1203 std::complex<R>* out,
1204 const std::complex<R>* twiddles) noexcept
1205 {
1206 radix_four_pass_body<Fused>(current, stride, in, out, twiddles);
1207 }
1208
1210 template <typename C>
1212 const C& v1,
1213 const C& v2,
1214 const C& v3,
1215 C* y) noexcept
1216 {
1217 const C a_plus_c {v0 + v2};
1218 const C a_minus_c {v0 - v2};
1219 const C b_plus_d {v1 + v3};
1220 const C b_minus_d {v1 - v3};
1221 const C i_b_minus_d {-b_minus_d.imag(), b_minus_d.real()};
1222 y[0] = a_plus_c + b_plus_d;
1223 y[1] = a_minus_c - i_b_minus_d;
1224 y[2] = a_plus_c - b_plus_d;
1225 y[3] = a_minus_c + i_b_minus_d;
1226 }
1227
1234 template <bool Fused,
1235 typename C>
1237 std::size_t stride,
1238 const C* in,
1239 C* out,
1240 const fft_root_t<C>* twiddles,
1241 const std::array<fft_root_t<C>, 16>& sixteenths) noexcept
1242 {
1243 const std::size_t part {current / 16};
1244 const std::size_t run {part - 1};
1245 const std::size_t apart {stride * part};
1246 for (std::size_t p {0}; p < part; ++p) {
1247 const C* const in_p {in + (stride * p)};
1248 C* const to {out + (stride * 16 * p)};
1249 for (std::size_t q {0}; q < stride; ++q) {
1250 std::array<C, 16> inner {};
1252 for (std::size_t j1 {0}; j1 < 4; ++j1) {
1253 four_point(in_p[q + (j1 * apart)], in_p[q + ((j1 + 4) * apart)], in_p[q + ((j1 + 8) * apart)], in_p[q + ((j1 + 12) * apart)],
1254 inner.data() + (4 * j1));
1256 for (std::size_t k2 {1}; k2 < 4 && j1 != 0; ++k2) {
1257 C& value {inner[(4 * j1) + k2]};
1258 value = (j1 * k2) == 4 ? C {value.imag(), -value.real()} : twiddled<Fused>(sixteenths[j1 * k2], value);
1259 }
1260 }
1262 for (std::size_t k2 {0}; k2 < 4; ++k2) {
1263 std::array<C, 4> outputs {};
1264 four_point(inner[k2], inner[4 + k2], inner[8 + k2], inner[12 + k2], outputs.data());
1266 for (std::size_t k1 {0}; k1 < 4; ++k1) {
1267 const std::size_t k {(4 * k1) + k2};
1268 to[q + (stride * k)] = (p == 0 || k == 0) ? outputs[k1] : twiddled<Fused>(twiddles[((k - 1) * run) + p - 1], outputs[k1]);
1269 }
1270 }
1271 }
1272 }
1273 }
1274
1276 template <bool Fused,
1277 std::floating_point R>
1278 void radix_sixteen_pass(std::size_t current,
1279 std::size_t stride,
1280 const std::complex<R>* in,
1281 std::complex<R>* out,
1282 const std::complex<R>* twiddles,
1283 const std::array<std::complex<R>, 16>& sixteenths) noexcept
1284 {
1285 radix_sixteen_pass_body<Fused>(current, stride, in, out, twiddles, sixteenths);
1286 }
1287
1289 template <std::floating_point R>
1290 [[nodiscard]] NUMERICAL_ALWAYS_INLINE std::complex<R> scaled(R c,
1291 const std::complex<R>& v) noexcept
1292 {
1293 return {c * v.real(), c * v.imag()};
1294 }
1295
1298 template <bool Fused,
1299 std::floating_point R>
1300 requires Fused
1301 [[nodiscard]] NUMERICAL_ALWAYS_INLINE std::complex<R> scaled_add(const std::complex<R>& s,
1302 R c,
1303 const std::complex<R>& v) noexcept
1304 {
1305 return {std::fma(c, v.real(), s.real()), std::fma(c, v.imag(), s.imag())};
1306 }
1307
1309 template <bool Fused,
1310 std::floating_point R>
1311 requires (!Fused)
1312 [[nodiscard]] NUMERICAL_ALWAYS_INLINE std::complex<R> scaled_add(const std::complex<R>& s,
1313 R c,
1314 const std::complex<R>& v) noexcept
1315 {
1316 return s + scaled(c, v);
1317 }
1318
1319#ifdef NUMERICAL_FFT_LANES
1321 template <std::floating_point R>
1322 [[nodiscard]] NUMERICAL_FFT_LANES_INLINE fft_lanes<R> scaled(R c,
1323 const fft_lanes<R>& v) noexcept
1324 {
1325 return {c * v.re, c * v.im};
1326 }
1327
1329 template <bool Fused,
1330 std::floating_point R>
1331 requires Fused
1332 [[nodiscard]] NUMERICAL_FFT_LANES_INLINE fft_lanes<R> scaled_add(const fft_lanes<R>& s,
1333 R c,
1334 const fft_lanes<R>& v) noexcept
1335 {
1336 return {fused(c, v.re, s.re), fused(c, v.im, s.im)};
1337 }
1338
1339#endif
1349 template <bool Fused,
1350 typename C>
1352 std::size_t current,
1353 std::size_t stride,
1354 const C* in,
1355 C* out,
1356 const fft_root_t<C>* twiddles,
1357 const fft_root_t<C>* roots) noexcept
1358 {
1359 const std::size_t part {current / radix};
1360 const std::size_t run {part - 1};
1361 const std::size_t apart {stride * part};
1362 const std::size_t half {radix / 2};
1363 for (std::size_t p {0}; p < part; ++p) {
1364 const C* const in_p {in + (stride * p)};
1365 C* const to {out + (stride * radix * p)};
1366 for (std::size_t q {0}; q < stride; ++q) {
1367 std::array<C, fft_largest_radix / 2> sums {};
1368 std::array<C, fft_largest_radix / 2> differences {};
1369 const C x0 {in_p[q]};
1370 C total {x0};
1371 for (std::size_t j {1}; j <= half; ++j) {
1372 const C x {in_p[q + (j * apart)]};
1373 const C y {in_p[q + ((radix - j) * apart)]};
1374 sums[j - 1] = x + y;
1375 differences[j - 1] = x - y;
1376 total = total + sums[j - 1];
1377 }
1378 to[q] = total;
1379 for (std::size_t k {1}; k <= half; ++k) {
1380 std::size_t power {k}; // j·k mod r, kept by additions
1381 C cosines {scaled_add<Fused>(x0, roots[power].real(), sums[0])};
1382 C sines {scaled(-roots[power].imag(), differences[0])};
1383 for (std::size_t j {2}; j <= half; ++j) {
1384 power += k;
1385 power -= power >= radix ? radix : 0;
1386 cosines = scaled_add<Fused>(cosines, roots[power].real(), sums[j - 1]);
1387 sines = scaled_add<Fused>(sines, -roots[power].imag(), differences[j - 1]);
1388 }
1389 const C i_sines {-sines.imag(), sines.real()}; // i·B_k, exact
1390 const C low {cosines - i_sines};
1391 const C high {cosines + i_sines};
1392 to[q + (stride * k)] = p == 0 ? low : twiddled<Fused>(twiddles[((k - 1) * run) + p - 1], low);
1393 to[q + (stride * (radix - k))] = p == 0 ? high : twiddled<Fused>(twiddles[((radix - k - 1) * run) + p - 1], high);
1394 }
1395 }
1396 }
1397 }
1398
1404 template <bool Fused,
1405 typename C>
1407 std::size_t stride,
1408 const C * in,
1409 C * out,
1410 const fft_root_t<C> * twiddles,
1411 const small_radix_constants<fft_real_t<C>>& k) noexcept
1412 {
1413 using R = fft_real_t<C>;
1414 const std::size_t part {current / 3};
1415 const std::size_t run {part - 1};
1416 const std::size_t apart {stride * part};
1417 for (std::size_t p {0}; p < part; ++p) {
1418 const C* const in_p {in + (stride * p)};
1419 C* const to {out + (stride * 3 * p)};
1420 for (std::size_t q {0}; q < stride; ++q) {
1421 const C x0 {in_p[q]};
1422 const C x1 {in_p[q + apart]};
1423 const C x2 {in_p[q + (2 * apart)]};
1424 const C t {x1 + x2};
1425 const C v {x0 - scaled(R(0.5), t)};
1426 const C u {scaled(k.half_root_three, x1 - x2)};
1427 const C iu {-u.imag(), u.real()};
1428 const C y1 {v - iu};
1429 const C y2 {v + iu};
1430 to[q] = x0 + t;
1431 to[q + stride] = p == 0 ? y1 : twiddled<Fused>(twiddles[p - 1], y1);
1432 to[q + 2 * stride] = p == 0 ? y2 : twiddled<Fused>(twiddles[run + p - 1], y2);
1433 }
1434 }
1435 }
1436
1443 template <bool Fused,
1444 typename C>
1446 std::size_t stride,
1447 const C * in,
1448 C * out,
1449 const fft_root_t<C> * twiddles,
1450 const small_radix_constants<fft_real_t<C>>& k) noexcept
1451 {
1452 const std::size_t part {current / 5};
1453 const std::size_t run {part - 1};
1454 const std::size_t apart {stride * part};
1455 for (std::size_t p {0}; p < part; ++p) {
1456 const C* const in_p {in + (stride * p)};
1457 C* const to {out + (stride * 5 * p)};
1458 for (std::size_t q {0}; q < stride; ++q) {
1459 const C x0 {in_p[q]};
1460 const C x1 {in_p[q + apart]};
1461 const C x2 {in_p[q + (2 * apart)]};
1462 const C x3 {in_p[q + (3 * apart)]};
1463 const C x4 {in_p[q + (4 * apart)]};
1464 const C t1 {x1 + x4};
1465 const C t2 {x2 + x3};
1466 const C t3 {x1 - x4};
1467 const C t4 {x2 - x3};
1468 const C a1 {scaled_add<Fused>(scaled_add<Fused>(x0, k.c1, t1), k.c2, t2)};
1469 const C a2 {scaled_add<Fused>(scaled_add<Fused>(x0, k.c2, t1), k.c1, t2)};
1470 const C b1 {scaled_add<Fused>(scaled(k.s1, t3), k.s2, t4)};
1471 const C b2 {scaled_add<Fused>(scaled(k.s2, t3), -k.s1, t4)};
1472 const C ib1 {-b1.imag(), b1.real()};
1473 const C ib2 {-b2.imag(), b2.real()};
1474 const std::array<C, 5> y {(x0 + t1) + t2, a1 - ib1, a2 - ib2, a2 + ib2, a1 + ib1};
1475 to[q] = y[0];
1476 for (std::size_t j {1}; j < 5; ++j) {
1477 to[q + (j * stride)] = p == 0 ? y[j] : twiddled<Fused>(twiddles[((j - 1) * run) + p - 1], y[j]);
1478 }
1479 }
1480 }
1481 }
1482
1490 template <bool Fused,
1491 typename C>
1493 std::size_t stride,
1494 const C* in,
1495 C* out,
1496 const fft_root_t<C>* twiddles,
1497 fft_real_t<C> half_root_two) noexcept
1498 {
1499 const std::size_t part {current / 8};
1500 const std::size_t run {part - 1};
1501 const std::size_t apart {stride * part};
1502 for (std::size_t p {0}; p < part; ++p) {
1503 const C* const in_p {in + (stride * p)};
1504 C* const to {out + (stride * 8 * p)};
1505 for (std::size_t q {0}; q < stride; ++q) {
1506 std::array<C, 4> a {};
1507 std::array<C, 4> b {};
1508 for (std::size_t j {0}; j < 4; ++j) {
1509 const C low {in_p[q + (j * apart)]};
1510 const C high {in_p[q + ((j + 4) * apart)]};
1511 a[j] = low + high;
1512 b[j] = low - high;
1513 }
1514 const auto sum1 {b[1].real() + b[1].imag()};
1515 const auto difference1 {b[1].imag() - b[1].real()};
1516 const auto sum3 {b[3].real() + b[3].imag()};
1517 const auto difference3 {b[3].imag() - b[3].real()};
1518 b[1] = C {half_root_two * sum1, half_root_two * difference1};
1519 b[2] = C {b[2].imag(), -b[2].real()};
1520 b[3] = C {half_root_two * difference3, -(half_root_two * sum3)};
1521 std::array<C, 4> even {};
1522 std::array<C, 4> odd {};
1523 four_point(a[0], a[1], a[2], a[3], even.data());
1524 four_point(b[0], b[1], b[2], b[3], odd.data());
1525 for (std::size_t k {0}; k < 8; ++k) {
1526 const C value {(k % 2) == 0 ? even[k / 2] : odd[k / 2]};
1527 to[q + (stride * k)] = (p == 0 || k == 0) ? value : twiddled<Fused>(twiddles[((k - 1) * run) + p - 1], value);
1528 }
1529 }
1530 }
1531 }
1532
1534 template <bool Fused,
1535 std::floating_point R>
1536 void any_radix_pass(std::size_t radix,
1537 std::size_t current,
1538 std::size_t stride,
1539 const std::complex<R> * in,
1540 std::complex<R> * out,
1541 const std::complex<R> * twiddles,
1542 const std::complex<R> * roots,
1543 const small_radix_constants<R>& small) noexcept
1544 {
1545 if (radix == 3) {
1546 radix_three_pass_body<Fused>(current, stride, in, out, twiddles, small);
1547 }
1548 else if (radix == 5) {
1549 radix_five_pass_body<Fused>(current, stride, in, out, twiddles, small);
1550 }
1551 else if (radix == 8) {
1552 radix_eight_pass_body<Fused>(current, stride, in, out, twiddles, small.half_root_two);
1553 }
1554 else {
1555 any_radix_pass_body<Fused>(radix, current, stride, in, out, twiddles, roots);
1556 }
1557 }
1558
1559#ifdef NUMERICAL_X86_COMPILED
1561 template <std::floating_point R>
1562 NUMERICAL_OUT_OF_LINE NUMERICAL_TARGET("avx2,fma") void any_radix_pass_x86(std::size_t radix,
1563 std::size_t current,
1564 std::size_t stride,
1565 const std::complex<R> * in,
1566 std::complex<R> * out,
1567 const std::complex<R> * twiddles,
1568 const std::complex<R> * roots,
1569 const small_radix_constants<R>& small) noexcept
1570 {
1571 if (radix == 3) {
1572 avx2_radix_three_pass(current, stride, in, out, twiddles, small.half_root_three);
1573 }
1574 else if (radix == 5) {
1575 avx2_radix_five_pass(current, stride, in, out, twiddles, small.c1, small.c2, small.s1, small.s2);
1576 }
1577 else if (radix == 8) {
1578 avx2_radix_eight_pass(current, stride, in, out, twiddles, small.half_root_two);
1579 }
1580 else {
1581 avx2_radix_any_pass(radix, current, stride, in, out, twiddles, roots);
1582 }
1583 }
1584
1588 template <std::floating_point R>
1589 NUMERICAL_TARGET("avx512f,avx2,fma") void any_radix_pass_avx512(std::size_t radix,
1590 std::size_t current,
1591 std::size_t stride,
1592 const std::complex<R> * in,
1593 std::complex<R> * out,
1594 const std::complex<R> * twiddles,
1595 const std::complex<R> * roots,
1596 const small_radix_constants<R>& small) noexcept
1597 {
1598 if (stride % (sizeof(fft_reg<fft_avx512, R>) / sizeof(std::complex<R>)) != 0) {
1599 any_radix_pass_x86(radix, current, stride, in, out, twiddles, roots, small);
1600 }
1601 else if (radix == 3) {
1602 avx512_radix_three_pass(current, stride, in, out, twiddles, small.half_root_three);
1603 }
1604 else if (radix == 5) {
1605 avx512_radix_five_pass(current, stride, in, out, twiddles, small.c1, small.c2, small.s1, small.s2);
1606 }
1607 else if (radix == 8) {
1608 avx512_radix_eight_pass(current, stride, in, out, twiddles, small.half_root_two);
1609 }
1610 else {
1611 avx512_radix_any_pass(radix, current, stride, in, out, twiddles, roots);
1612 }
1613 }
1614
1615#endif
1616
1617#ifdef NUMERICAL_NEON_COMPILED
1619 template <std::floating_point R>
1620 void any_radix_pass_neon(std::size_t radix,
1621 std::size_t current,
1622 std::size_t stride,
1623 const std::complex<R> * in,
1624 std::complex<R> * out,
1625 const std::complex<R> * twiddles,
1626 const std::complex<R> * roots,
1627 const small_radix_constants<R>& small) noexcept
1628 {
1629 if (radix == 3) {
1630 neon_radix_three_pass(current, stride, in, out, twiddles, small.half_root_three);
1631 }
1632 else if (radix == 5) {
1633 neon_radix_five_pass(current, stride, in, out, twiddles, small.c1, small.c2, small.s1, small.s2);
1634 }
1635 else if (radix == 8) {
1636 neon_radix_eight_pass(current, stride, in, out, twiddles, small.half_root_two);
1637 }
1638 else {
1639 neon_radix_any_pass(radix, current, stride, in, out, twiddles, roots);
1640 }
1641 }
1642
1643#endif
1644
1646 template <typename C>
1648 const C* in,
1649 C* out) noexcept
1650 {
1651 for (std::size_t q {0}; q < stride; ++q) {
1652 const C a {in[q]};
1653 const C b {in[q + stride]};
1654 out[q] = a + b;
1655 out[q + stride] = a - b;
1656 }
1657 }
1658
1666 template <std::floating_point R,
1667 typename C,
1668 typename Four,
1669 typename Sixteen,
1670 typename Other>
1672 C* data,
1673 C* work,
1674 Four four,
1675 Sixteen sixteen,
1676 Other other,
1677 bool from_work = false) noexcept
1678 {
1679 const std::size_t n {plan.length};
1680 C* in {from_work ? work : data};
1681 C* out {from_work ? data : work};
1682 const std::complex<R>* twiddles {plan.twiddles.data()};
1683 const std::complex<R>* roots {plan.radix_roots.data()};
1684 std::size_t current {n};
1685 std::size_t stride {1};
1686 for (const std::size_t radix : plan.radices) {
1687 if (radix == 16) {
1688 sixteen(current, stride, in, out, twiddles, plan.sixteenths);
1689 }
1690 else if (radix == 4) {
1691 four(current, stride, in, out, twiddles);
1692 }
1693 else if (radix == 2) { // always the last pass (fft_radices): no factor
1694 radix_two_pass(stride, in, out);
1695 }
1696 else {
1697 other(radix, current, stride, in, out, twiddles, roots, plan.small);
1698 roots += (radix > 5 && radix != 8) ? radix : 0; // 3, 5 and 8 take the plan's constants
1699 }
1700 twiddles += (radix - 1) * (current / radix - 1);
1701 current /= radix;
1702 stride *= radix;
1703 std::swap(in, out);
1704 }
1705 if (in != data) {
1706 std::copy(in, in + n, data);
1707 }
1708 }
1709
1711 [[nodiscard]] inline bool fft_fuses() noexcept
1712 {
1713 return gemm_path_current() != gemm_path::portable;
1714 }
1715
1721 template <bool Fused,
1722 std::floating_point R>
1724 std::complex<R>* data,
1725 std::complex<R>* work)
1726 {
1727 using C = std::complex<R>;
1728 const bluestein_plan<R>& b {*plan.bluestein};
1729 const std::size_t n {plan.length};
1730 const std::size_t m {b.padded};
1731 const R scale {R(1) / static_cast<R>(m)};
1732 C* const a {work};
1733 const bool ahead {fft_starts_in_work(*b.inner)};
1734 C* const input {ahead ? work + m : a}; // where the inner transforms read
1735 for (std::size_t j {0}; j < n; ++j) {
1736 input[j] = twiddled<Fused>(b.chirp[j], data[j]);
1737 }
1738 std::fill(input + n, input + m, C {});
1739 forward_fft(*b.inner, a, work + m, Fused, ahead);
1740 for (std::size_t k {0}; k < m; ++k) {
1741 input[k] = std::conj(twiddled<Fused>(b.spectrum[k], a[k]));
1742 }
1743 forward_fft(*b.inner, a, work + m, Fused, ahead);
1744 for (std::size_t k {0}; k < n; ++k) {
1745 const C value {a[k].real() * scale, -a[k].imag() * scale};
1746 data[k] = twiddled<Fused>(b.chirp[k], value);
1747 }
1748 }
1749
1750#ifdef NUMERICAL_X86_COMPILED
1752 template <std::floating_point R>
1753 NUMERICAL_TARGET("avx2,fma") void bluestein_x86(const fft_plan<R>& plan,
1754 std::complex<R>* data,
1755 std::complex<R>* work)
1756 {
1757 bluestein_body<true>(plan, data, work);
1758 }
1759
1760#endif
1761
1762#ifdef NUMERICAL_X86_COMPILED
1766 inline constexpr std::size_t fft_avx512_shortest {256};
1767
1768#endif
1770 template <bool Fused,
1771 std::floating_point R>
1773 const std::complex<R>* w,
1774 std::size_t count) noexcept
1775 {
1776 for (std::size_t i {0}; i < count; ++i) {
1777 t[i] = twiddled<Fused>(w[i], t[i]);
1778 }
1779 }
1780
1781#ifdef NUMERICAL_X86_COMPILED
1783 template <std::floating_point R>
1784 NUMERICAL_TARGET("avx2,fma") void twiddle_run_x86(std::complex<R>* t,
1785 const std::complex<R>* w,
1786 std::size_t count) noexcept
1787 {
1788 twiddle_run_body<true>(t, w, count);
1789 }
1790
1791#endif
1792
1794 template <std::floating_point R>
1795 void twiddle_run(std::complex<R>* t,
1796 const std::complex<R>* w,
1797 std::size_t count,
1798 bool fused) noexcept
1799 {
1800 if (!fused) {
1801 twiddle_run_body<false>(t, w, count);
1802 return;
1803 }
1804#ifdef NUMERICAL_X86_COMPILED
1805 twiddle_run_x86(t, w, count);
1806#else
1807 twiddle_run_body<true>(t, w, count);
1808#endif
1809 }
1810
1816 template <std::floating_point R>
1817 void four_step_fft(const fft_plan<R>& plan,
1818 const std::complex<R>* in,
1819 std::complex<R>* out,
1820 std::complex<R>* work,
1821 bool fused,
1822 bool inverse = false,
1823 R scale = R(1));
1824
1831 template <std::floating_point R>
1832 void forward_fft(const fft_plan<R>& plan,
1833 std::complex<R>* data,
1834 std::complex<R>* work,
1835 bool fused,
1836 bool in_work)
1837 {
1838 if (plan.four_step) {
1839 four_step_fft(plan, data, data, work, fused);
1840 return;
1841 }
1842 if (plan.bluestein) {
1843 if (!fused) {
1844 bluestein_body<false>(plan, data, work);
1845 return;
1846 }
1847#ifdef NUMERICAL_X86_COMPILED
1848 bluestein_x86(plan, data, work);
1849#else
1850 bluestein_body<true>(plan, data, work);
1851#endif
1852 return;
1853 }
1854 if (!fused) {
1855 stockham_passes(plan, data, work, radix_four_pass<false, R>, radix_sixteen_pass<false, R>, any_radix_pass<false, R>, in_work);
1856 return;
1857 }
1858#ifdef NUMERICAL_X86_COMPILED
1859 if (gemm_path_current() == gemm_path::avx512 && plan.length >= fft_avx512_shortest) {
1860 stockham_passes(plan, data, work, avx512_radix_four_pass<R>, avx512_radix_sixteen_pass<R>, any_radix_pass_avx512<R>, in_work);
1861 return;
1862 }
1863 stockham_passes(plan, data, work, avx2_radix_four_pass<R>, avx2_radix_sixteen_pass<R>, any_radix_pass_x86<R>, in_work);
1864#elif defined(NUMERICAL_NEON_COMPILED)
1865 stockham_passes(plan, data, work, neon_radix_four_pass<R>, neon_radix_sixteen_pass<R>, any_radix_pass_neon<R>, in_work);
1866#else
1867 stockham_passes(plan, data, work, radix_four_pass<true, R>, radix_sixteen_pass<true, R>, any_radix_pass<true, R>, in_work);
1868#endif
1869 }
1870
1871#ifdef NUMERICAL_FFT_LANES
1873 template <std::floating_point R>
1874 NUMERICAL_FFT_LANES_TARGET void lanes_four_pass(std::size_t current,
1875 std::size_t stride,
1876 const fft_lanes<R>* in,
1877 fft_lanes<R>* out,
1878 const std::complex<R>* twiddles) noexcept
1879 {
1880 radix_four_pass_body<true>(current, stride, in, out, twiddles);
1881 }
1882
1884 template <std::floating_point R>
1885 NUMERICAL_FFT_LANES_TARGET void lanes_sixteen_pass(std::size_t current,
1886 std::size_t stride,
1887 const fft_lanes<R>* in,
1888 fft_lanes<R>* out,
1889 const std::complex<R>* twiddles,
1890 const std::array<std::complex<R>, 16>& sixteenths) noexcept
1891 {
1892 radix_sixteen_pass_body<true>(current, stride, in, out, twiddles, sixteenths);
1893 }
1894
1896 template <std::floating_point R>
1897 NUMERICAL_FFT_LANES_TARGET void lanes_any_radix_pass(std::size_t radix,
1898 std::size_t current,
1899 std::size_t stride,
1900 const fft_lanes<R>* in,
1901 fft_lanes<R>* out,
1902 const std::complex<R>* twiddles,
1903 const std::complex<R>* roots,
1904 const small_radix_constants<R>& small) noexcept
1905 {
1906 if (radix == 3) {
1907 radix_three_pass_body<true>(current, stride, in, out, twiddles, small);
1908 }
1909 else if (radix == 5) {
1910 radix_five_pass_body<true>(current, stride, in, out, twiddles, small);
1911 }
1912 else if (radix == 8) {
1913 radix_eight_pass_body<true>(current, stride, in, out, twiddles, small.half_root_two);
1914 }
1915 else {
1916 any_radix_pass_body<true>(radix, current, stride, in, out, twiddles, roots);
1917 }
1918 }
1919
1927 template <typename T,
1928 std::floating_point R>
1929 NUMERICAL_FFT_LANES_TARGET void lanes_transform(const fft_plan<R>& plan,
1930 const T* in,
1931 std::size_t in_line,
1932 std::size_t in_step,
1933 std::size_t kept,
1934 std::complex<R>* out,
1935 std::size_t out_line,
1936 std::size_t out_step,
1937 bool inverse,
1938 R scale,
1939 fft_lanes<R>* lines,
1940 fft_lanes<R>* work) noexcept
1941 {
1942 const std::size_t points {plan.length};
1943 const bool ahead {fft_starts_in_work(plan)};
1944 fft_lanes<R>* const start {ahead ? work : lines}; // where the passes read the lines: they end in `lines`
1945 for (std::size_t k {0}; k < points; ++k) {
1946 fft_lanes<R> value {};
1947 if (k < kept) {
1948 lanes_read(in + (k * in_step), in_line, value.re.v, value.im.v);
1949 }
1950 start[k] = {value.re, inverse ? -value.im : value.im};
1951 }
1952 stockham_passes(plan, lines, work, lanes_four_pass<R>, lanes_sixteen_pass<R>, lanes_any_radix_pass<R>, ahead);
1953 for (std::size_t k {0}; k < points; ++k) {
1954 const fft_lanes<R> value {lines[k].re, inverse ? -lines[k].im : lines[k].im};
1955 if (scale == R(1)) {
1956 lanes_write(out + (k * out_step), out_line, value.re.v, value.im.v);
1957 }
1958 else {
1959 lanes_write(out + (k * out_step), out_line, (scale * value.re).v, (scale * value.im).v);
1960 }
1961 }
1962 }
1963
1964#endif
1965
1967 template <typename T>
1969 {
1970 using type = std::complex<T>;
1971 };
1972
1974 template <split_complex C>
1975 struct fft_complex<C>
1976 {
1977 using type = C;
1978 };
1979
1981 template <typename T>
1982 concept fft_input = std::is_same_v<T, float> || std::is_same_v<T, double> || split_complex<T>;
1983
1985 template <std::floating_point R>
1986 [[nodiscard]] R fft_scale(fft_norm norm,
1987 bool inverse,
1988 std::size_t n)
1989 {
1990 if (norm == fft_norm::ortho) {
1991 return R(1) / std::sqrt(static_cast<R>(n));
1992 }
1993 return (norm == fft_norm::forward) != inverse ? R(1) / static_cast<R>(n) : R(1);
1994 }
1995
1997 inline constexpr std::size_t fft_scratch_kept {std::size_t {1} << 16};
1998
2002 template <typename C,
2003 int Slot = 0>
2005 {
2006 public:
2007
2009 explicit fft_scratch(std::size_t count)
2010 {
2011 if (count > fft_scratch_kept) {
2012 own_.resize(count);
2013 data_ = own_.data();
2014 return;
2015 }
2016 thread_local buffer<C> kept;
2017 [[maybe_unused]] thread_local const bool registered {on_release([] { kept = buffer<C> {}; })};
2018 if (kept.size() < count) {
2019 kept.resize(count); // the most this thread has needed, up to fft_scratch_kept
2020 }
2021 data_ = kept.data();
2022 }
2023
2025 [[nodiscard]] C* data() const noexcept
2026 {
2027 return data_;
2028 }
2029
2030 private:
2031
2033 C* data_ {nullptr};
2034 };
2035
2036#ifdef NUMERICAL_FFT_LANES
2038 template <std::floating_point R>
2039 inline constexpr std::size_t fft_lines_width {fft_lanes_width<R>};
2040
2043 inline constexpr std::size_t fft_lanes_longest {std::size_t {1} << 12};
2044
2045# if defined(NUMERICAL_X86_COMPILED)
2048 inline constexpr std::size_t fft_lanes_together_bytes {std::size_t {1} << 14};
2049# else
2051 inline constexpr std::size_t fft_lanes_together_bytes {std::size_t {1} << 17};
2052# endif
2053
2060 template <std::floating_point R>
2061 [[nodiscard]] std::size_t fft_lane_groups(const fft_plan<R>& plan,
2062 bool fused,
2063 std::size_t lines,
2064 bool together) noexcept
2065 {
2066 const bool fits {together ? plan.length * sizeof(fft_lanes<R>) <= fft_lanes_together_bytes : plan.length <= fft_lanes_longest};
2067 return fused && !plan.bluestein && !plan.four_step && fits ? lines / fft_lines_width<R> : 0;
2068 }
2069
2071 template <typename T,
2072 std::floating_point R>
2073 void fft_lines_together(const fft_plan<R>& plan,
2074 const T* in,
2075 std::size_t in_line,
2076 std::size_t in_step,
2077 std::size_t kept,
2078 std::complex<R>* out,
2079 std::size_t out_line,
2080 std::size_t out_step,
2081 bool inverse,
2082 R scale)
2083 {
2084 const fft_scratch<fft_lanes<R>> space {2 * plan.length};
2085 lanes_transform(plan, in, in_line, in_step, kept, out, out_line, out_step, inverse, scale, space.data(),
2086 space.data() + plan.length);
2087 }
2088
2089#else
2091 template <std::floating_point R>
2092 inline constexpr std::size_t fft_lines_width {1};
2093
2095 template <std::floating_point R>
2096 [[nodiscard]] std::size_t fft_lane_groups(const fft_plan<R>& /*plan*/,
2097 bool /*fused*/,
2098 std::size_t /*lines*/,
2099 bool /*together*/) noexcept
2100 {
2101 return 0;
2102 }
2103
2105 template <typename T,
2106 std::floating_point R>
2107 void fft_lines_together(const fft_plan<R>& /*plan*/,
2108 const T* /*in*/,
2109 std::size_t /*in_line*/,
2110 std::size_t /*in_step*/,
2111 std::size_t /*kept*/,
2112 std::complex<R>* /*out*/,
2113 std::size_t /*out_line*/,
2114 std::size_t /*out_step*/,
2115 bool /*inverse*/,
2116 R /*scale*/) noexcept
2117 {
2118 }
2119
2120#endif
2121
2124 inline constexpr std::size_t fft_column_block {8};
2125
2132 template <std::floating_point R>
2133 void columns_fft(const fft_plan<R>& plan,
2134 const std::complex<R>* data,
2135 std::size_t columns,
2136 std::complex<R>* to,
2137 std::size_t to_rows,
2138 bool fused,
2139 bool conjugated)
2140 {
2141 using C = std::complex<R>;
2142 const std::size_t points {plan.length};
2143 const std::size_t groups {fft_lane_groups(plan, fused, columns, false)};
2144 const std::size_t together {groups * fft_lines_width<R>};
2145 const std::size_t blocks {(columns - together + fft_column_block - 1) / fft_column_block};
2146 const std::size_t work {2 * points * static_cast<std::size_t>(std::bit_width(points))};
2147 parallel_for(groups + blocks, work * std::max(fft_column_block, fft_lines_width<R>), [&](std::size_t task) {
2148 if (task < groups) {
2149 const std::size_t column {task * fft_lines_width<R>};
2150 fft_lines_together(plan, data + column, 1, columns, points, to + column, 1, to_rows, conjugated, R(1));
2151 return;
2152 }
2153 const std::size_t first {together + ((task - groups) * fft_column_block)};
2154 const std::size_t width {std::min(fft_column_block, columns - first)};
2155 fft_scratch<C, 3> scratch {plan.work + (width * points)};
2156 C* const lines {scratch.data() + plan.work};
2157 for (std::size_t k {0}; k < points; ++k) {
2158 for (std::size_t b {0}; b < width; ++b) {
2159 const C value {data[(k * columns) + first + b]};
2160 lines[(b * points) + k] = conjugated ? std::conj(value) : value;
2161 }
2162 }
2163 for (std::size_t b {0}; b < width; ++b) {
2164 forward_fft(plan, lines + (b * points), scratch.data(), fused);
2165 }
2166 for (std::size_t k {0}; k < points; ++k) {
2167 for (std::size_t b {0}; b < width; ++b) {
2168 const C value {lines[(b * points) + k]};
2169 to[(k * to_rows) + first + b] = conjugated ? std::conj(value) : value;
2170 }
2171 }
2172 });
2173 }
2174
2182 template <std::floating_point R>
2184 std::complex<R>* data,
2185 std::size_t rows,
2186 std::size_t apart,
2187 const std::complex<R>* twiddles,
2188 bool fused,
2189 std::complex<R>* out,
2190 bool inverse,
2191 R scale)
2192 {
2193 using C = std::complex<R>;
2194 constexpr std::size_t band {fft_four_step_band<R>};
2195 const std::size_t points {plan.length};
2196 const std::size_t bands {(rows + band - 1) / band};
2197 parallel_for(bands, band * 2 * points * static_cast<std::size_t>(std::bit_width(points)), [&](std::size_t task) {
2198 const std::size_t first {task * band};
2199 const std::size_t count {std::min(band, rows - first)};
2200 const fft_scratch<C, 3> space {plan.work};
2201 for (std::size_t row {first}; row < first + count; ++row) {
2202 C* const line {data + (row * apart)};
2203 if (inverse) {
2204 std::transform(line, line + points, line, [](const C& v) { return std::conj(v); });
2205 }
2206 twiddle_run(line, twiddles + (row * points), points, fused);
2207 forward_fft(plan, line, space.data(), fused);
2208 }
2209 for (std::size_t k {0}; k < points; ++k) {
2210 for (std::size_t r {0}; r < count; ++r) {
2211 const C value {data[((first + r) * apart) + k]};
2212 const C v {inverse ? std::conj(value) : value};
2213 out[first + r + (rows * k)] = scale == R(1) ? v : C {v.real() * scale, v.imag() * scale};
2214 }
2215 }
2216 });
2217 }
2218
2219 template <std::floating_point R>
2220 void four_step_fft(const fft_plan<R>& plan,
2221 const std::complex<R>* in,
2222 std::complex<R>* out,
2223 std::complex<R>* work,
2224 bool fused,
2225 bool inverse,
2226 R scale)
2227 {
2228 const four_step_plan<R>& f {*plan.four_step};
2229 const std::size_t n1 {f.columns};
2230 const std::size_t n2 {f.rows};
2231 const std::size_t ld {n1 + fft_four_step_pad};
2232 columns_fft(*f.column_plan, in, n1, work, ld, fused, inverse); // work[j1 + ld·k2]
2233 twiddled_rows_fft(*f.row_plan, work, n2, ld, f.twiddles.data(), fused, out, inverse, scale); // out[k2 + n2·k1]
2234 }
2235
2238 template <typename T>
2240 {
2241 const T* data;
2242 std::vector<std::size_t> shape;
2243 };
2244
2246 template <typename T>
2247 [[nodiscard]] fft_source<T> source_of(const tensor<T>& a)
2248 {
2249 return {a.data().data(), a.shape()};
2250 }
2251
2257 template <typename T,
2258 typename F>
2259 [[nodiscard]] auto transformed_along(const tensor<T>& a,
2260 std::ptrdiff_t axis,
2261 const F& f) -> decltype(f(source_of(a), axis))
2262 {
2263 const auto rank {static_cast<std::ptrdiff_t>(a.rank())};
2264 const auto index {static_cast<std::size_t>(axis < 0 ? axis + rank : axis)}; // still negative: past any rank, f's to refuse
2265 if (auto laid {as_laid_along(a, index, [&f](const tensor<T>& elements, std::size_t along) {
2266 return f(source_of(elements), static_cast<std::ptrdiff_t>(along));
2267 })}) {
2268 return std::move(*laid);
2269 }
2270 return f(source_of(a), axis);
2271 }
2272
2278 template <typename C>
2279 void fft_load_line(const C * in,
2280 std::size_t kept,
2281 std::size_t points,
2282 bool inverse,
2283 C * to) noexcept
2284 {
2285 if (inverse) {
2286 std::transform(in, in + kept, to, [](const C& value) { return std::conj(value); });
2287 }
2288 else {
2289 std::copy(in, in + kept, to);
2290 }
2291 std::fill(to + kept, to + points, C {});
2292 }
2293
2296 template <typename C>
2297 void fft_finish_line(C * line,
2298 std::size_t points,
2299 bool inverse,
2300 typename C::value_type scale) noexcept
2301 {
2302 if (inverse) {
2303 std::transform(line, line + points, line, [](const C& value) { return std::conj(value); });
2304 }
2305 if (scale != typename C::value_type(1)) {
2306 std::transform(line, line + points, line, [scale](const C& value) { return C {value.real() * scale, value.imag() * scale}; });
2307 }
2308 }
2309
2312 template <typename Out>
2314 {
2315 std::vector<std::size_t> shape;
2317
2318 fft_output(std::vector<std::size_t> input_shape,
2319 std::size_t index,
2320 std::size_t out_points)
2321 : shape {resized(std::move(input_shape), index, out_points)}, out(counted(shape))
2322 {}
2323
2325 [[nodiscard]] static std::size_t counted(const std::vector<std::size_t>& extents)
2326 {
2327 const std::size_t count {element_count(extents.begin(), extents.end())};
2328 if (count > buffer<Out> {}.max_size()) {
2329 throw dimension_error("a transform's result of " + std::to_string(count) + " elements is too big: its size in bytes is larger than the maximum possible size");
2330 }
2331 return count;
2332 }
2333
2335 [[nodiscard]] static std::vector<std::size_t> resized(std::vector<std::size_t> extents,
2336 std::size_t index,
2337 std::size_t extent)
2338 {
2339 extents[index] = extent;
2340 return extents;
2341 }
2342
2344 [[nodiscard]] tensor<Out> take() &&
2345 {
2346 return tensor<Out> {std::move(shape), std::move(out)};
2347 }
2348 };
2349
2356 template <split_complex T>
2358 const std::optional<std::size_t>& n,
2359 std::ptrdiff_t axis,
2360 fft_norm norm,
2361 bool inverse)
2362 {
2363 using C = T;
2364 using R = typename C::value_type;
2365 const auto rank {static_cast<std::ptrdiff_t>(a.shape.size())};
2366 if (axis < -rank || axis >= rank) {
2367 throw dimension_error("fft: axis " + std::to_string(axis) + " is out of bounds for a tensor of rank " + std::to_string(rank));
2368 }
2369 const auto index {static_cast<std::size_t>(axis < 0 ? axis + rank : axis)};
2370 const std::size_t extent {a.shape[index]};
2371 const std::size_t points {n.value_or(extent)};
2372 if (points == 0) {
2373 throw dimension_error("fft: invalid number of data points (0)");
2374 }
2375 fft_output<C> result {a.shape, index, points};
2376 const axis_walk walk {walk_along(result.shape, index)};
2377 const R scale {fft_scale<R>(norm, inverse, points)};
2378 buffer<C>& out {result.out};
2379 if (walk.outer == 0) {
2380 return std::move(result).take();
2381 }
2382 const std::shared_ptr<const fft_plan<R>> plan {shared_fft_plan<R>(points)};
2383 const std::size_t kept {std::min(points, extent)};
2384 const bool fused {fft_fuses()};
2385 const T* const from {a.data};
2386 const auto finish {[&](const C& value) { // conjugated back for the inverse, scaled
2387 const C v {inverse ? std::conj(value) : value};
2388 return scale == R(1) ? v : C {v.real() * scale, v.imag() * scale};
2389 }};
2390 // A line's work as work_per_thread counts it, about a nanosecond a unit: 2·n·log₂ n (a line of 64 points 0.2 µs,
2391 // of 1024 4.6 µs, on one arm64 core), so that 64 lines of 64 points stay on one thread.
2392 const std::size_t work {2 * points * static_cast<std::size_t>(std::bit_width(points))};
2393 const bool ahead {fft_starts_in_work(*plan)};
2394 if (walk.inner == 1) { // each line together: transformed where it lies in the output
2395 const std::size_t groups {fft_lane_groups(*plan, fused, walk.outer, true)};
2396 const std::size_t first {groups * fft_lines_width<R>};
2397 parallel_for(groups + walk.outer - first, work * fft_lines_width<R>, [&](std::size_t task) {
2398 if (task < groups) {
2399 fft_lines_together(*plan, from + (task * fft_lines_width<R> * extent), extent, 1, kept,
2400 out.data() + (task * fft_lines_width<R> * points), points, 1, inverse, scale);
2401 return;
2402 }
2403 const std::size_t line {first + task - groups};
2404 const T* const in {from + (line * extent)};
2405 C* const to {out.data() + (line * points)};
2406 fft_scratch<C> scratch {plan->work};
2407 if (plan->four_step) { // the columns read the line where it lies, the rows write it finished
2408 const C* source {kept == points ? in : nullptr};
2409 if (source == nullptr) {
2410 for (std::size_t k {0}; k < points; ++k) {
2411 to[k] = k < kept ? C(in[k]) : C {};
2412 }
2413 source = to;
2414 }
2415 four_step_fft(*plan, source, to, scratch.data(), fused, inverse, scale);
2416 return;
2417 }
2418 fft_load_line(in, kept, points, inverse, ahead ? scratch.data() : to); // where the passes read it
2419 forward_fft(*plan, to, scratch.data(), fused, ahead);
2420 fft_finish_line(to, points, inverse, scale);
2421 });
2422 return std::move(result).take();
2423 }
2424 // Lines `inner` apart: a register of neighbours at a time where they fill one (fft_lane_groups), the rest up to
2425 // fft_column_block of them at a time, each row read and written as that many neighbours; fewer where that would
2426 // leave the threads under four tasks each. A line's bits are its own either way.
2427 const std::size_t groups {fft_lane_groups(*plan, fused, walk.inner, false)};
2428 const std::size_t together {groups * fft_lines_width<R>};
2429 const std::size_t rest {walk.inner - together};
2430 const std::size_t share {(walk.outer * rest) / (4 * max_threads())};
2431 const std::size_t block {std::clamp(share, std::size_t {1}, fft_column_block)};
2432 const std::size_t blocks {(rest + block - 1) / block};
2433 parallel_for(walk.outer * (groups + blocks), work * std::max(block, fft_lines_width<R>), [&](std::size_t task) {
2434 const std::size_t outer {task / (groups + blocks)};
2435 const std::size_t slot {task % (groups + blocks)};
2436 if (slot < groups) {
2437 const std::size_t column {slot * fft_lines_width<R>};
2438 fft_lines_together(*plan, from + (outer * extent * walk.inner) + column, 1, walk.inner, kept,
2439 out.data() + (outer * points * walk.inner) + column, 1, walk.inner, inverse, scale);
2440 return;
2441 }
2442 const std::size_t first {together + ((slot - groups) * block)};
2443 const std::size_t width {std::min(block, walk.inner - first)};
2444 const T* const in {from + (outer * extent * walk.inner) + first};
2445 C* const to {out.data() + (outer * points * walk.inner) + first};
2446 fft_scratch<C> scratch {plan->work + (width * points)};
2447 C* const lines {scratch.data() + plan->work};
2448 for (std::size_t k {0}; k < points; ++k) {
2449 for (std::size_t b {0}; b < width; ++b) {
2450 const C value {k < kept ? C(in[(k * walk.inner) + b]) : C {}};
2451 lines[(b * points) + k] = inverse ? std::conj(value) : value;
2452 }
2453 }
2454 for (std::size_t b {0}; b < width; ++b) {
2455 forward_fft(*plan, lines + (b * points), scratch.data(), fused);
2456 }
2457 for (std::size_t k {0}; k < points; ++k) {
2458 for (std::size_t b {0}; b < width; ++b) {
2459 to[(k * walk.inner) + b] = finish(lines[(b * points) + k]);
2460 }
2461 }
2462 });
2463 return std::move(result).take();
2464 }
2465
2468 template <std::floating_point R>
2470 {
2471 std::size_t length {0};
2472 std::shared_ptr<const fft_plan<R>> complex;
2473 std::vector<std::complex<R>> roots;
2474 };
2475
2477 template <std::floating_point R>
2478 [[nodiscard]] std::shared_ptr<const real_fft_plan<R>> shared_real_fft_plan(std::size_t n)
2479 {
2480 struct entry
2481 {
2482 std::size_t length;
2483 std::shared_ptr<const real_fft_plan<R>> plan;
2484 };
2485 static std::mutex guard;
2486 static std::vector<entry> plans; // the most recently used last
2487 const auto kept = [n]() -> std::shared_ptr<const real_fft_plan<R>> { // under the lock
2488 const auto found {std::find_if(plans.begin(), plans.end(), [n](const entry& e) { return e.length == n; })};
2489 if (found == plans.end()) {
2490 return nullptr;
2491 }
2492 std::rotate(found, found + 1, plans.end());
2493 return plans.back().plan;
2494 };
2495 {
2496 const std::scoped_lock lock {guard};
2497 if (auto found {kept()}) {
2498 return found;
2499 }
2500 }
2501 auto plan {std::make_shared<real_fft_plan<R>>()};
2502 plan->length = n;
2503 if (n % 2 == 0) {
2504 plan->complex = shared_fft_plan<R>(n / 2);
2505 const unit_roots roots {n};
2506 plan->roots.resize((n / 2) + 1);
2507 parallel_for((n / 2) + 1, fft_root_cost, [&](std::size_t k) {
2508 const std::complex<double> root {roots.root(k)};
2509 plan->roots[k] = {static_cast<R>(root.real()), static_cast<R>(root.imag())};
2510 });
2511 }
2512 else {
2513 plan->complex = shared_fft_plan<R>(n);
2514 }
2515 const std::scoped_lock lock {guard};
2516 std::erase_if(plans, [n](const entry& e) { return e.length == n; }); // another thread's meanwhile, the same plan
2517 if (plans.size() >= fft_plans_kept) {
2518 plans.erase(plans.begin());
2519 }
2520 plans.push_back({n, plan});
2521 return plans.back().plan;
2522 }
2523
2525 template <std::floating_point R>
2526 [[nodiscard]] std::size_t no_registers(std::size_t /*h*/,
2527 const std::complex<R>* /*from*/,
2528 const std::complex<R>* /*roots*/,
2529 std::complex<R>* /*into*/) noexcept
2530 {
2531 return 1;
2532 }
2533
2539 template <std::floating_point R>
2541 const R* x,
2542 std::complex<R>* X,
2543 bool fused)
2544 {
2545 using C = std::complex<R>;
2546 const std::shared_ptr<const fft_plan<R>> plan {shared_fft_plan<R>(n)};
2547 std::vector<C> line(n + plan->work);
2548 for (std::size_t j {0}; j < n; ++j) {
2549 line[j] = C {x[j], R(0)};
2550 }
2551 forward_fft(*plan, line.data(), line.data() + n, fused);
2552 std::copy(line.begin(), line.begin() + static_cast<std::ptrdiff_t>((n / 2) + 1), X);
2553 }
2554
2560 template <std::floating_point R>
2562 const std::complex<R>* X,
2563 R* x,
2564 R factor,
2565 bool fused)
2566 {
2567 using C = std::complex<R>;
2568 const std::shared_ptr<const fft_plan<R>> plan {shared_fft_plan<R>(n)};
2569 const std::size_t h {n / 2};
2570 std::vector<C> line(n + plan->work);
2571 line[0] = C {X[0].real(), R(0)};
2572 line[h] = C {X[h].real(), R(0)};
2573 for (std::size_t k {1}; k < h; ++k) {
2574 line[k] = std::conj(X[k]); // conjugated for conj(fft(conj ·))
2575 line[n - k] = X[k];
2576 }
2577 forward_fft(*plan, line.data(), line.data() + n, fused);
2578 for (std::size_t j {0}; j < n; ++j) {
2579 x[j] = line[j].real() * factor;
2580 }
2581 }
2582
2591 template <bool Fused,
2592 std::floating_point R,
2593 typename Registers>
2595 const R* x,
2596 std::complex<R>* X,
2597 std::complex<R>* work,
2598 Registers registers)
2599 {
2600 using C = std::complex<R>;
2601 const std::size_t n {plan.length};
2602 const std::size_t h {n / 2};
2603 const bool ahead {fft_starts_in_work(*plan.complex)}; // the input placed where the passes end in their data
2604 if (n % 2 == 1) {
2605 C* const line {work};
2606 C* const start {ahead ? work + n : line};
2607 for (std::size_t j {0}; j < n; ++j) {
2608 start[j] = C {x[j], R(0)};
2609 }
2610 forward_fft(*plan.complex, line, work + n, Fused, ahead);
2611 std::copy(line, line + h + 1, X);
2612 return;
2613 }
2614 C* const z {work};
2615 C* const start {ahead ? work + h : z};
2616 if (!all_finite(x, n)) {
2617 real_forward_whole(n, x, X, Fused);
2618 return;
2619 }
2620 std::copy(x, x + n, reinterpret_cast<R*>(start)); // NOLINT(cppcoreguidelines-pro-type-reinterpret-cast): the pairs (x[2j], x[2j+1]) as complex numbers, a complex number being its two parts ([complex.numbers])
2621 forward_fft(*plan.complex, z, work + h, Fused, ahead);
2622 X[0] = C {z[0].real() + z[0].imag(), R(0)};
2623 X[h] = C {z[0].real() - z[0].imag(), R(0)};
2624 for (std::size_t k {registers(h, z, plan.roots.data(), X)}; k < h; ++k) {
2625 const C a {z[k]};
2626 const C b {std::conj(z[h - k])};
2627 const C sum {a + b};
2628 const C difference {a - b};
2629 const C even {sum.real() * R(0.5), sum.imag() * R(0.5)};
2630 const C odd {difference.imag() * R(0.5), -difference.real() * R(0.5)}; // −i·d/2
2631 X[k] = even + twiddled<Fused>(plan.roots[k], odd);
2632 }
2633 }
2634
2644 template <bool Fused,
2645 std::floating_point R,
2646 typename Registers>
2648 const std::complex<R>* X,
2649 R* x,
2650 std::complex<R>* work,
2651 R scale,
2652 Registers registers)
2653 {
2654 using C = std::complex<R>;
2655 const std::size_t n {plan.length};
2656 const std::size_t h {n / 2};
2657 const bool ahead {fft_starts_in_work(*plan.complex)}; // the input placed where the passes end in their data
2658 if (n % 2 == 1) {
2659 C* const line {work};
2660 C* const start {ahead ? work + n : line};
2661 start[0] = C {X[0].real(), R(0)};
2662 for (std::size_t k {1}; k <= h; ++k) {
2663 start[k] = std::conj(X[k]); // conjugated for conj(fft(conj ·))
2664 start[n - k] = X[k];
2665 }
2666 forward_fft(*plan.complex, line, work + n, Fused, ahead);
2667 for (std::size_t j {0}; j < n; ++j) {
2668 x[j] = line[j].real() * scale;
2669 }
2670 return;
2671 }
2672 bool finite {std::isfinite(X[0].real()) && std::isfinite(X[h].real())};
2673 for (std::size_t k {1}; k < h; ++k) {
2674 finite = finite && std::isfinite(X[k].real()) && std::isfinite(X[k].imag());
2675 }
2676 if (!finite) {
2677 real_inverse_whole(n, X, x, scale * R(0.5), Fused); // scale holds the half sums' 2, exact
2678 return;
2679 }
2680 C* const z {work};
2681 C* const start {ahead ? work + h : z};
2682 const C first {X[0].real(), R(0)};
2683 const C last {X[h].real(), R(0)};
2684 start[0] = std::conj(C {(first.real() + last.real()) * R(0.5), (first.real() - last.real()) * R(0.5)});
2685 for (std::size_t k {registers(h, X, plan.roots.data(), start)}; k < h; ++k) {
2686 const C a {X[k]};
2687 const C b {std::conj(X[h - k])};
2688 const C sum {a + b};
2689 const C difference {a - b};
2690 const C even {sum.real() * R(0.5), sum.imag() * R(0.5)};
2691 const C odd {twiddled<Fused>(std::conj(plan.roots[k]), C {difference.real() * R(0.5), difference.imag() * R(0.5)})};
2692 const C value {even.real() - odd.imag(), even.imag() + odd.real()}; // E + i·O
2693 start[k] = std::conj(value);
2694 }
2695 forward_fft(*plan.complex, z, work + h, Fused, ahead);
2696 for (std::size_t j {0}; j < h; ++j) {
2697 x[2 * j] = z[j].real() * scale;
2698 x[(2 * j) + 1] = -z[j].imag() * scale;
2699 }
2700 }
2701
2702#ifdef NUMERICAL_X86_COMPILED
2704 template <std::floating_point R>
2705 NUMERICAL_TARGET("avx2,fma") void real_forward_x86(const real_fft_plan<R>& plan,
2706 const R* x,
2707 std::complex<R>* X,
2708 std::complex<R>* work)
2709 {
2710 real_forward_body<true>(plan, x, X, work, avx2_real_forward_registers<R>);
2711 }
2712
2714 template <std::floating_point R>
2715 NUMERICAL_TARGET("avx2,fma") void real_inverse_x86(const real_fft_plan<R>& plan,
2716 const std::complex<R>* X,
2717 R* x,
2718 std::complex<R>* work,
2719 R scale)
2720 {
2721 real_inverse_body<true>(plan, X, x, work, scale, avx2_real_inverse_registers<R>);
2722 }
2723
2724#endif
2725
2727 template <std::floating_point R>
2729 const R* x,
2730 std::complex<R>* X,
2731 std::complex<R>* work,
2732 bool fused)
2733 {
2734 if (!fused) {
2735 real_forward_body<false>(plan, x, X, work, no_registers<R>);
2736 return;
2737 }
2738#ifdef NUMERICAL_X86_COMPILED
2739 real_forward_x86(plan, x, X, work);
2740#else
2741 real_forward_body<true>(plan, x, X, work, no_registers<R>);
2742#endif
2743 }
2744
2746 template <std::floating_point R>
2748 const std::complex<R>* X,
2749 R* x,
2750 std::complex<R>* work,
2751 R scale,
2752 bool fused)
2753 {
2754 if (!fused) {
2755 real_inverse_body<false>(plan, X, x, work, scale, no_registers<R>);
2756 return;
2757 }
2758#ifdef NUMERICAL_X86_COMPILED
2759 real_inverse_x86(plan, X, x, work, scale);
2760#else
2761 real_inverse_body<true>(plan, X, x, work, scale, no_registers<R>);
2762#endif
2763 }
2764
2772 template <typename In,
2773 typename Out,
2774 typename C,
2775 typename Line>
2777 std::size_t index,
2778 std::size_t in_points,
2779 fft_output<Out>&& result,
2780 std::size_t work,
2781 Line line)
2782 {
2783 const std::size_t extent {a.shape[index]};
2784 const std::size_t out_points {result.shape[index]};
2785 const axis_walk walk {walk_along(result.shape, index)};
2786 buffer<Out>& out {result.out};
2787 const std::size_t kept {std::min(in_points, extent)};
2788 const In* const from {a.data};
2789 if (walk.inner == 1 && in_points <= extent) { // each line together, none padded: read and written where it lies
2790 parallel_for(walk.outer, 5 * (in_points + out_points) * static_cast<std::size_t>(std::bit_width(in_points + out_points)),
2791 [&](std::size_t number) {
2792 fft_scratch<C, 0> space {work};
2793 line(from + (number * extent), out.data() + (number * out_points), space.data());
2794 });
2795 return std::move(result).take();
2796 }
2797 parallel_for(walk.outer * walk.inner, 5 * (in_points + out_points) * static_cast<std::size_t>(std::bit_width(in_points + out_points)),
2798 [&](std::size_t number) {
2799 const std::size_t outer {number / walk.inner};
2800 const std::size_t inner {number % walk.inner};
2801 const In* const in {from + (outer * extent * walk.inner) + inner};
2802 Out* const to {out.data() + (outer * out_points * walk.inner) + inner};
2803 fft_scratch<C, 0> space {work};
2804 fft_scratch<In, 1> gathered {in_points};
2805 fft_scratch<Out, 2> line_out {out_points};
2806 for (std::size_t k {0}; k < in_points; ++k) {
2807 gathered.data()[k] = k < kept ? in[k * walk.inner] : In {};
2808 }
2809 line(gathered.data(), line_out.data(), space.data());
2810 for (std::size_t k {0}; k < out_points; ++k) {
2811 to[k * walk.inner] = line_out.data()[k];
2812 }
2813 });
2814 return std::move(result).take();
2815 }
2816
2819 [[nodiscard]] inline std::size_t fft_axis_index(std::ptrdiff_t axis,
2820 std::size_t rank,
2821 const char* who)
2822 {
2823 const auto signed_rank {static_cast<std::ptrdiff_t>(rank)};
2824 if (axis < -signed_rank || axis >= signed_rank) {
2825 throw dimension_error(std::string {who} + ": axis " + std::to_string(axis) + " is out of bounds for a tensor of rank " + std::to_string(rank));
2826 }
2827 return static_cast<std::size_t>(axis < 0 ? axis + signed_rank : axis);
2828 }
2829
2837 template <std::floating_point R>
2839 std::size_t index,
2840 std::size_t points,
2841 bool inverse,
2842 R scale)
2843 {
2844 using C = std::complex<R>;
2845 fft_output<C> result {a.shape, index, points};
2846 if (result.out.empty()) {
2847 return std::move(result).take();
2848 }
2849 const bool whole {four_step_columns(points, sizeof(C)) != 0};
2850 const std::shared_ptr<const real_fft_plan<R>> plan {whole ? nullptr : shared_real_fft_plan<R>(points)};
2851 const std::shared_ptr<const fft_plan<R>> complex {whole ? shared_fft_plan<R>(points) : nullptr};
2852 const bool fused {fft_fuses()};
2853 const std::size_t half {points / 2};
2854 const std::size_t work {whole ? complex->work : (points % 2 == 0 ? half : points) + plan->complex->work};
2855 return lines_along<R, C, C>(a, index, points, std::move(result), work, [&](const R* x, C* spectrum, C* space) {
2856 if (whole) {
2857 std::transform(x, x + points, spectrum, [](R value) { return C {value, R(0)}; });
2858 forward_fft(*complex, spectrum, space, fused);
2859 }
2860 else {
2861 real_forward(*plan, x, spectrum, space, fused);
2862 for (std::size_t k {1}; k < points - half; ++k) {
2863 spectrum[points - k] = std::conj(spectrum[k]);
2864 }
2865 }
2866 if (inverse || scale != R(1)) {
2867 std::transform(spectrum, spectrum + points, spectrum, [inverse, scale](const C& v) {
2868 const C w {inverse ? std::conj(v) : v};
2869 return C {w.real() * scale, w.imag() * scale};
2870 });
2871 }
2872 });
2873 }
2874
2879 template <std::floating_point T>
2881 const std::optional<std::size_t>& n,
2882 std::ptrdiff_t axis,
2883 fft_norm norm,
2884 bool inverse)
2885 {
2886 const char* const name {inverse ? "ifft" : "fft"};
2887 const std::size_t index {fft_axis_index(axis, a.shape.size(), name)};
2888 const std::size_t points {n.value_or(a.shape[index])};
2889 if (points == 0) {
2890 throw dimension_error(std::string {name} + ": invalid number of data points (0)");
2891 }
2892 return real_input_transform(a, index, points, inverse, fft_scale<T>(norm, inverse, points));
2893 }
2894
2896 template <std::floating_point T>
2898 const std::optional<std::size_t>& n,
2899 std::ptrdiff_t axis,
2900 fft_norm norm)
2901 {
2902 using C = std::complex<T>;
2903 const std::size_t index {fft_axis_index(axis, a.shape.size(), "rfft")};
2904 const std::size_t points {n.value_or(a.shape[index])};
2905 if (points == 0) {
2906 throw dimension_error("rfft: invalid number of data points (0)");
2907 }
2908 fft_output<C> result {a.shape, index, (points / 2) + 1};
2909 if (result.out.empty()) {
2910 return std::move(result).take();
2911 }
2912 const std::shared_ptr<const real_fft_plan<T>> plan {shared_real_fft_plan<T>(points)};
2913 const bool fused {fft_fuses()};
2914 const T scale {fft_scale<T>(norm, false, points)};
2915 const std::size_t half {points / 2};
2916 const std::size_t work {(points % 2 == 0 ? half : points) + plan->complex->work};
2917 return lines_along<T, C, C>(a, index, points, std::move(result), work, [&](const T* x, C* spectrum, C* space) {
2918 real_forward(*plan, x, spectrum, space, fused);
2919 if (scale != T(1)) {
2920 std::transform(spectrum, spectrum + half + 1, spectrum, [scale](const C& v) { return C {v.real() * scale, v.imag() * scale}; });
2921 }
2922 });
2923 }
2924
2926 template <std::floating_point T>
2927 [[nodiscard]] tensor<T> irfft_of(const fft_source<std::complex<T>>& a,
2928 const std::optional<std::size_t>& n,
2929 std::ptrdiff_t axis,
2930 fft_norm norm)
2931 {
2932 using C = std::complex<T>;
2933 const std::size_t index {fft_axis_index(axis, a.shape.size(), "irfft")};
2934 const std::size_t extent {a.shape[index]};
2935 const std::size_t points {n.value_or(extent == 0 ? 0 : 2 * (extent - 1))};
2936 if (points == 0) {
2937 throw dimension_error("irfft: invalid number of data points (0)");
2938 }
2939 fft_output<T> result {a.shape, index, points};
2940 if (result.out.empty()) {
2941 return std::move(result).take();
2942 }
2943 const std::shared_ptr<const real_fft_plan<T>> plan {shared_real_fft_plan<T>(points)};
2944 const bool fused {fft_fuses()};
2945 const T factor {fft_scale<T>(norm, true, points)};
2946 const T scale {points % 2 == 0 ? factor * T(2) : factor}; // an even n's half sums
2947 const std::size_t half {points / 2};
2948 const std::size_t work {(points % 2 == 0 ? half : points) + plan->complex->work};
2949 return lines_along<C, T, C>(a, index, half + 1, std::move(result), work, [&](const C* spectrum, T* x, C* space) {
2950 real_inverse(*plan, spectrum, x, space, scale, fused);
2951 });
2952 }
2953 } // namespace detail
2954
2964 template <detail::fft_input T>
2965 requires detail::split_complex<T>
2966 [[nodiscard]] tensor<T> fft(const tensor<T>& a,
2967 std::optional<std::size_t> n = std::nullopt,
2968 std::ptrdiff_t axis = -1,
2969 fft_norm norm = fft_norm::backward)
2970 {
2971 return detail::transformed_along(a, axis, [&](const auto& source, std::ptrdiff_t along) {
2972 return detail::transform_axis(source, n, along, norm, false);
2973 });
2974 }
2975
2988 template <std::floating_point T>
2989 [[nodiscard]] tensor<std::complex<T>> fft(const tensor<T>& a,
2990 std::optional<std::size_t> n = std::nullopt,
2991 std::ptrdiff_t axis = -1,
2992 fft_norm norm = fft_norm::backward)
2993 {
2994 return detail::transformed_along(a, axis, [&](const auto& source, std::ptrdiff_t along) {
2995 return detail::real_transform_of(source, n, along, norm, false);
2996 });
2997 }
2998
3009 template <detail::fft_input T>
3010 requires detail::split_complex<T>
3011 [[nodiscard]] tensor<T> ifft(const tensor<T>& a,
3012 std::optional<std::size_t> n = std::nullopt,
3013 std::ptrdiff_t axis = -1,
3014 fft_norm norm = fft_norm::backward)
3015 {
3016 return detail::transformed_along(a, axis, [&](const auto& source, std::ptrdiff_t along) {
3017 return detail::transform_axis(source, n, along, norm, true);
3018 });
3019 }
3020
3031 template <std::floating_point T>
3032 [[nodiscard]] tensor<std::complex<T>> ifft(const tensor<T>& a,
3033 std::optional<std::size_t> n = std::nullopt,
3034 std::ptrdiff_t axis = -1,
3035 fft_norm norm = fft_norm::backward)
3036 {
3037 return detail::transformed_along(a, axis, [&](const auto& source, std::ptrdiff_t along) {
3038 return detail::real_transform_of(source, n, along, norm, true);
3039 });
3040 }
3041
3042 namespace detail {
3048 template <typename T>
3049 [[nodiscard]] tensor<T> rolled(const tensor<T>& a,
3050 const std::vector<std::size_t>& shifts)
3051 {
3052 if (const auto laid {a.laid_out()}) { // a transpose: its elements rolled as they lie, each axis by its own shift
3053 std::vector<std::size_t> lying(shifts.size());
3054 for (std::size_t k {0}; k < lying.size(); ++k) {
3055 lying[k] = shifts[laid->second[k]];
3056 }
3057 return rolled(laid->first, lying).transposed(view_axes(laid->second));
3058 }
3059 const std::vector<std::size_t>& shape {a.shape()};
3060 buffer<T> out(a.data().size());
3061 if (out.empty() || shape.empty()) { // an empty tensor, or a number: itself
3062 std::copy(a.data().begin(), a.data().end(), out.begin());
3063 return tensor<T> {shape, std::move(out)};
3064 }
3065 const std::size_t rank {shape.size()};
3066 const std::size_t last {shape.back()};
3067 const std::size_t rows {out.size() / last};
3068 const std::size_t shift {shifts.back() % last};
3069 parallel_for(rows, memory_element_weight * last, [&](std::size_t row) {
3070 std::size_t rest {row};
3071 std::size_t source {0}; // the source row's first element
3072 std::size_t stride {last};
3073 for (std::size_t d {rank - 1}; d-- > 0;) {
3074 const std::size_t n {shape[d]};
3075 const std::size_t index {rest % n};
3076 rest /= n;
3077 source += ((index + n - (shifts[d] % n)) % n) * stride;
3078 stride *= n;
3079 }
3080 const T* const from {a.data().data() + source};
3081 T* const to {out.data() + (row * last)};
3082 std::copy(from, from + (last - shift), to + shift); // element j to j + shift
3083 std::copy(from + (last - shift), from + last, to);
3084 });
3085 return tensor<T> {shape, std::move(out)};
3086 }
3087 } // namespace detail
3088
3099 template <typename T>
3100 [[nodiscard]] tensor<T> fftshift(const tensor<T>& a,
3101 const std::vector<std::ptrdiff_t>& axes,
3102 bool inverse = false)
3103 {
3104 const auto rank {static_cast<std::ptrdiff_t>(a.rank())};
3105 std::vector<std::size_t> shifts(a.rank(), 0);
3106 for (const std::ptrdiff_t axis : axes) {
3107 if (axis < -rank || axis >= rank) {
3108 throw dimension_error("fftshift: axis " + std::to_string(axis) + " is out of bounds for a tensor of rank " + std::to_string(rank));
3109 }
3110 const auto index {static_cast<std::size_t>(axis < 0 ? axis + rank : axis)};
3111 const std::size_t n {a.shape()[index]};
3112 shifts[index] += inverse ? n - (n / 2) : n / 2;
3113 }
3114 return detail::rolled(a, shifts);
3115 }
3116
3126 template <typename T>
3127 [[nodiscard]] tensor<T> fftshift(const tensor<T>& a,
3128 std::ptrdiff_t axis = -1,
3129 bool inverse = false)
3130 {
3131 return fftshift(a, std::vector<std::ptrdiff_t> {axis}, inverse);
3132 }
3133
3145 template <std::floating_point T>
3146 [[nodiscard]] tensor<std::complex<T>> rfft(const tensor<T>& a,
3147 std::optional<std::size_t> n = std::nullopt,
3148 std::ptrdiff_t axis = -1,
3149 fft_norm norm = fft_norm::backward)
3150 {
3151 return detail::transformed_along(a, axis, [&](const auto& source, std::ptrdiff_t along) { return detail::rfft_of(source, n, along, norm); });
3152 }
3153
3165 template <std::floating_point T>
3166 [[nodiscard]] tensor<T> irfft(const tensor<std::complex<T>>& a,
3167 std::optional<std::size_t> n = std::nullopt,
3168 std::ptrdiff_t axis = -1,
3169 fft_norm norm = fft_norm::backward)
3170 {
3171 return detail::transformed_along(a, axis, [&](const auto& source, std::ptrdiff_t along) { return detail::irfft_of(source, n, along, norm); });
3172 }
3173
3175 [[nodiscard]] constexpr fft_norm swapped(fft_norm norm) noexcept
3176 {
3177 return norm == fft_norm::backward ? fft_norm::forward : norm == fft_norm::forward ? fft_norm::backward : norm;
3178 }
3179
3190 template <std::floating_point T>
3191 [[nodiscard]] tensor<T> hfft(const tensor<std::complex<T>>& a,
3192 std::optional<std::size_t> n = std::nullopt,
3193 std::ptrdiff_t axis = -1,
3194 fft_norm norm = fft_norm::backward)
3195 {
3196 const auto conjugated {[](const std::complex<T>& v) { return std::conj(v); }}; // a transpose's as its elements lie
3197 return irfft(detail::parallel_map(a, conjugated), n, axis, swapped(norm));
3198 }
3199
3209 template <std::floating_point T>
3210 [[nodiscard]] tensor<std::complex<T>> ihfft(const tensor<T>& a,
3211 std::optional<std::size_t> n = std::nullopt,
3212 std::ptrdiff_t axis = -1,
3213 fft_norm norm = fft_norm::backward)
3214 {
3215 const auto conjugated {[](const std::complex<T>& v) { return std::conj(v); }}; // a transpose's as its elements lie
3216 return detail::parallel_map(rfft(a, n, axis, swapped(norm)), conjugated);
3217 }
3218
3219 namespace detail {
3220
3222 enum class trig_family : unsigned char
3223 {
3224 cosine,
3225 sine
3226 };
3227
3239 template <std::floating_point R>
3241 {
3242 int type {1};
3243 std::size_t n {0};
3244 std::shared_ptr<const real_fft_plan<R>> real;
3245 std::shared_ptr<const fft_plan<R>> complex;
3246 std::vector<std::complex<R>> roots;
3247 std::vector<std::complex<R>> turns;
3248 std::vector<std::size_t> picks;
3249 std::vector<R> signs;
3250
3254 template <bool Fused>
3256 R* y,
3257 R* even,
3258 std::complex<R>* spectrum,
3259 std::complex<R>* space) const
3260 {
3261 using C = std::complex<R>;
3262 constexpr bool fused {Fused};
3263 const auto product = [] (const C& w, const C& v) NUMERICAL_INLINE_LAMBDA { return twiddled<Fused>(w, v); };
3264 const std::size_t h {n / 2};
3265 if (type == 1) {
3266 std::copy(u, u + n, even);
3267 for (std::size_t k {1}; k + 1 < n; ++k) {
3268 even[(2 * (n - 1)) - k] = u[k];
3269 }
3270 real_forward(*real, even, spectrum, space, fused);
3271 for (std::size_t k {0}; k < n; ++k) {
3272 y[k] = spectrum[k].real();
3273 }
3274 }
3275 else if (type == 2) {
3276 for (std::size_t j {0}; 2 * j < n; ++j) {
3277 even[j] = u[2 * j];
3278 }
3279 for (std::size_t j {0}; (2 * j) + 1 < n; ++j) {
3280 even[n - 1 - j] = u[(2 * j) + 1];
3281 }
3282 real_forward(*real, even, spectrum, space, fused);
3283 for (std::size_t k {0}; k <= h; ++k) {
3284 const C z {product(roots[k], spectrum[k])};
3285 y[k] = R(2) * z.real();
3286 if (k > 0 && k < n - k) {
3287 y[n - k] = R(-2) * z.imag();
3288 }
3289 }
3290 }
3291 else if (type == 3) {
3292 for (std::size_t k {0}; k <= h; ++k) {
3293 spectrum[k] = product(std::conj(roots[k]), C {u[k], k == 0 ? R(0) : -u[n - k]}) * R(0.5);
3294 }
3295 real_inverse(*real, spectrum, even, space, n % 2 == 0 ? R(4) : R(2), fused); // twice the whole sum
3296 for (std::size_t j {0}; 2 * j < n; ++j) {
3297 y[2 * j] = even[j];
3298 }
3299 for (std::size_t j {0}; (2 * j) + 1 < n; ++j) {
3300 y[(2 * j) + 1] = even[n - 1 - j];
3301 }
3302 }
3303 else if (n % 2 == 0) { // the even points and the odd ones reversed as one complex line of n/2
3304 for (std::size_t j {0}; j < h; ++j) {
3305 spectrum[j] = product(roots[j], C {u[2 * j], u[n - 1 - (2 * j)]});
3306 }
3307 forward_fft(*complex, spectrum, space, fused);
3308 for (std::size_t k {0}; k < h; ++k) {
3309 const C z {product(turns[k], spectrum[k])};
3310 y[2 * k] = R(2) * z.real();
3311 y[n - 1 - (2 * k)] = R(-2) * z.imag();
3312 }
3313 }
3314 else { // an odd n: one transform of n points, the point 2j + 1 (mod n) the j-th times (χ₈ + i χ₋₈)(2j + 1)
3315 for (std::size_t j {0}; j < n; ++j) {
3316 const std::size_t a {(2 * j) + 1};
3317 const std::size_t residue {a % 8};
3318 spectrum[a < n ? a : a - n] = C {residue == 1 || residue == 7 ? u[j] : -u[j], residue <= 3 ? u[j] : -u[j]};
3319 }
3320 forward_fft(*complex, spectrum, space, fused);
3321 for (std::size_t k {0}; k < n; ++k) {
3322 y[k] = signs[k] * spectrum[picks[k]].real();
3323 }
3324 }
3325 }
3326 };
3327
3329 [[nodiscard]] inline std::size_t eighth_inverse(std::size_t n) noexcept
3330 {
3331 std::int64_t r0 {static_cast<std::int64_t>(n)};
3332 std::int64_t r1 {8 % r0};
3333 std::int64_t t0 {0};
3334 std::int64_t t1 {1};
3335 while (r1 != 0) {
3336 const std::int64_t q {r0 / r1};
3337 const std::int64_t r2 {r0 - (q * r1)};
3338 const std::int64_t t2 {t0 - (q * t1)};
3339 r0 = r1;
3340 r1 = r2;
3341 t0 = t1;
3342 t1 = t2;
3343 }
3344 return static_cast<std::size_t>(((t0 % static_cast<std::int64_t>(n)) + static_cast<std::int64_t>(n)) % static_cast<std::int64_t>(n));
3345 }
3346
3352 template <std::floating_point R>
3353 [[nodiscard]] cosine_line<R> make_cosine_line(int type,
3354 std::size_t n)
3355 {
3356 cosine_line<R> line {type, n, nullptr, nullptr, {}, {}, {}, {}};
3357 if (type == 4 && n % 2 == 1) { // 8v ≡ 1 (mod n), u = (1 − 8v)/n, and the characters of u (2k + 1) mod 8
3358 line.complex = shared_fft_plan<R>(n);
3359 const std::size_t v {eighth_inverse(n)};
3360 const auto u_eighth {static_cast<std::size_t>((((1 - (8 * static_cast<std::int64_t>(v))) / static_cast<std::int64_t>(n)) % 8) + 8) % 8};
3361 const R root_two {std::numbers::sqrt2_v<R>};
3362 std::size_t s {v % n}; // v (2k + 1) mod n
3363 line.picks.resize(n);
3364 line.signs.resize(n);
3365 for (std::size_t k {0}; k < n; ++k) {
3366 const std::size_t b {((2 * k) + 1) * u_eighth % 8};
3367 const bool cosine {b == 1 || b == 7}; // χ₈(u b) = 1
3368 const bool sine {b == 1 || b == 3}; // χ₋₈(u b) = 1
3369 line.picks[k] = cosine == sine ? (n - s) % n : s;
3370 line.signs[k] = cosine ? root_two : -root_two;
3371 s = (s + (2 * v)) % n;
3372 }
3373 return line;
3374 }
3375 const unit_roots eighths {8 * n};
3376 const auto half_turn = [&](std::size_t numerator, std::size_t denominator) { // e^{−iπ·numerator/denominator}
3377 const std::complex<double> root {eighths.root(numerator * (4 * n / denominator))};
3378 return std::complex<R> {static_cast<R>(root.real()), static_cast<R>(root.imag())};
3379 };
3380 if (type == 4) { // n even
3381 line.complex = shared_fft_plan<R>(n / 2);
3382 line.roots.resize(n / 2);
3383 line.turns.resize(n / 2);
3384 parallel_for(n / 2, fft_root_cost, [&](std::size_t j) {
3385 line.roots[j] = half_turn((4 * j) + 1, 4 * n);
3386 line.turns[j] = half_turn(j, n);
3387 });
3388 return line;
3389 }
3390 line.real = shared_real_fft_plan<R>(type == 1 ? 2 * (n - 1) : n);
3391 if (type != 1) {
3392 line.roots.resize((n / 2) + 1);
3393 parallel_for((n / 2) + 1, fft_root_cost, [&](std::size_t k) { line.roots[k] = half_turn(k, 2 * n); });
3394 }
3395 return line;
3396 }
3397
3400 template <std::floating_point R>
3401 [[nodiscard]] std::shared_ptr<const cosine_line<R>> shared_cosine_line(int type,
3402 std::size_t n)
3403 {
3404 struct entry
3405 {
3406 int type;
3407 std::size_t length;
3408 std::shared_ptr<const cosine_line<R>> line;
3409 };
3410 static std::mutex guard;
3411 static std::vector<entry> lines; // the most recently used last
3412 const auto same = [type, n](const entry& e) { return e.type == type && e.length == n; };
3413 {
3414 const std::scoped_lock lock {guard};
3415 if (const auto found {std::find_if(lines.begin(), lines.end(), same)}; found != lines.end()) {
3416 std::rotate(found, found + 1, lines.end());
3417 return lines.back().line;
3418 }
3419 }
3420 auto built {std::make_shared<const cosine_line<R>>(make_cosine_line<R>(type, n))}; // the lock released
3421 const std::scoped_lock lock {guard};
3422 std::erase_if(lines, same);
3423 if (lines.size() >= fft_plans_kept) {
3424 lines.erase(lines.begin());
3425 }
3426 lines.push_back({type, n, std::move(built)});
3427 return lines.back().line;
3428 }
3429
3438 template <std::floating_point R>
3439 [[nodiscard]] tensor<R> trig_transform(const fft_source<R>& source,
3440 trig_family family,
3441 int type,
3442 const std::optional<std::size_t>& n,
3443 std::ptrdiff_t axis,
3444 fft_norm norm,
3445 const std::optional<bool>& orthogonalize,
3446 bool inverse)
3447 {
3448 using C = std::complex<R>;
3449 const std::string name {std::string {inverse ? "i" : ""} + (family == trig_family::cosine ? "dct" : "dst")};
3450 if (type < 1 || type > 4) {
3451 throw argument_error(name + ": type must be 1, 2, 3 or 4, not " + std::to_string(type));
3452 }
3453 const std::size_t index {fft_axis_index(axis, source.shape.size(), name.c_str())};
3454 const std::size_t points {n.value_or(source.shape[index])};
3455 if (points == 0 || (family == trig_family::cosine && type == 1 && points < 2)) {
3456 throw dimension_error(name + ": invalid number of data points (" + std::to_string(points) + ")");
3457 }
3458 fft_output<R> result {source.shape, index, points};
3459 if (result.out.empty()) {
3460 return std::move(result).take();
3461 }
3462 const int computed {inverse && (type == 2 || type == 3) ? 5 - type : type};
3463 const bool cosine {family == trig_family::cosine};
3464 const double period {static_cast<double>(type != 1 ? 2 * points : (cosine ? 2 * (points - 1) : 2 * (points + 1)))};
3465 const double factor {norm == fft_norm::ortho ? 1.0 / std::sqrt(period) : ((norm == fft_norm::forward) != inverse ? 1.0 / period : 1.0)};
3466 const R scale {static_cast<R>(factor)};
3467 const bool weighted {orthogonalize.value_or(norm == fft_norm::ortho)};
3468 const R root_two {std::numbers::sqrt2_v<R>};
3469 const bool fused {fft_fuses()}; // the path's, at this call
3470 const bool odd_one {!cosine && computed == 1};
3471 const std::size_t length {odd_one ? 2 * (points + 1) : (computed == 1 ? 2 * (points - 1) : points)};
3472 const std::shared_ptr<const cosine_line<R>> lines {odd_one ? std::make_shared<const cosine_line<R>>(cosine_line<R> {1, points, shared_real_fft_plan<R>(length), nullptr, {}, {}, {}, {}})
3473 : shared_cosine_line<R>(computed, points)};
3474 const std::size_t work {computed == 4 ? lines->complex->work
3475 : (length % 2 == 0 ? length / 2 : length) + lines->real->complex->work};
3476 return lines_along<R, R, C>(source, index, points, std::move(result), work, [&](const R* x, R* y, C* space) {
3477 fft_scratch<R, 3> u {points};
3478 fft_scratch<R, 4> even {length};
3479 fft_scratch<C, 5> spectrum {std::max(length / 2 + 1, 2 * points)};
3480 R* const v {u.data()};
3481 const std::size_t last {points - 1};
3482 for (std::size_t j {0}; j < points; ++j) { // the sines' order and signs
3483 const bool reversed {!cosine && computed >= 3};
3484 const R value {reversed ? x[last - j] : x[j]};
3485 v[j] = !cosine && computed == 2 && j % 2 == 1 ? -value : value;
3486 }
3487 if (weighted && cosine && (computed == 1 || computed == 3)) {
3488 v[0] *= root_two;
3489 }
3490 if (weighted && cosine && computed == 1) {
3491 v[last] *= root_two;
3492 }
3493 if (weighted && !cosine && computed == 3) {
3494 v[0] *= root_two; // the last point, reversed
3495 }
3496 if (odd_one) {
3497 R* const e {even.data()};
3498 e[0] = R(0);
3499 e[points + 1] = R(0);
3500 for (std::size_t j {0}; j < points; ++j) {
3501 e[1 + j] = v[j];
3502 e[length - 1 - j] = -v[j];
3503 }
3504 real_forward(*lines->real, e, spectrum.data(), space, fused);
3505 for (std::size_t k {0}; k < points; ++k) {
3506 y[k] = -spectrum.data()[k + 1].imag();
3507 }
3508 }
3509 else {
3510 if (fused) { // each product a fused one: where std::fma is the instruction
3511 run_fused([&](std::size_t) NUMERICAL_INLINE_LAMBDA { lines->template apply<true>(v, y, even.data(), spectrum.data(), space); });
3512 }
3513 else {
3514 lines->template apply<false>(v, y, even.data(), spectrum.data(), space);
3515 }
3516 }
3517 if (!cosine && computed == 2) {
3518 std::reverse(y, y + points);
3519 }
3520 if (!cosine && computed >= 3) {
3521 for (std::size_t k {1}; k < points; k += 2) {
3522 y[k] = -y[k];
3523 }
3524 }
3525 if (weighted && cosine && computed <= 2) {
3526 y[0] /= root_two;
3527 }
3528 if (weighted && cosine && computed == 1) {
3529 y[last] /= root_two;
3530 }
3531 if (weighted && !cosine && computed == 2) {
3532 y[last] /= root_two;
3533 }
3534 if (scale != R(1)) {
3535 std::transform(y, y + points, y, [scale](R value) { return value * scale; });
3536 }
3537 });
3538 }
3539
3541 template <std::floating_point R>
3542 [[nodiscard]] tensor<R> trig_transform(const tensor<R>& a,
3543 trig_family family,
3544 int type,
3545 const std::optional<std::size_t>& n,
3546 std::ptrdiff_t axis,
3547 fft_norm norm,
3548 const std::optional<bool>& orthogonalize,
3549 bool inverse)
3550 {
3551 return transformed_along(a, axis, [&](const fft_source<R>& source, std::ptrdiff_t along) {
3552 return trig_transform(source, family, type, n, along, norm, orthogonalize, inverse);
3553 });
3554 }
3555 } // namespace detail
3556
3573 template <std::floating_point T>
3574 [[nodiscard]] tensor<T> dct(const tensor<T>& a,
3575 int type = 2,
3576 std::optional<std::size_t> n = std::nullopt,
3577 std::ptrdiff_t axis = -1,
3578 fft_norm norm = fft_norm::backward,
3579 std::optional<bool> orthogonalize = std::nullopt)
3580 {
3581 return detail::trig_transform(a, detail::trig_family::cosine, type, n, axis, norm, orthogonalize, false);
3582 }
3583
3589 template <std::floating_point T>
3590 [[nodiscard]] tensor<T> idct(const tensor<T>& a,
3591 int type = 2,
3592 std::optional<std::size_t> n = std::nullopt,
3593 std::ptrdiff_t axis = -1,
3594 fft_norm norm = fft_norm::backward,
3595 std::optional<bool> orthogonalize = std::nullopt)
3596 {
3597 return detail::trig_transform(a, detail::trig_family::cosine, type, n, axis, norm, orthogonalize, true);
3598 }
3599
3616 template <std::floating_point T>
3617 [[nodiscard]] tensor<T> dst(const tensor<T>& a,
3618 int type = 2,
3619 std::optional<std::size_t> n = std::nullopt,
3620 std::ptrdiff_t axis = -1,
3621 fft_norm norm = fft_norm::backward,
3622 std::optional<bool> orthogonalize = std::nullopt)
3623 {
3624 return detail::trig_transform(a, detail::trig_family::sine, type, n, axis, norm, orthogonalize, false);
3625 }
3626
3632 template <std::floating_point T>
3633 [[nodiscard]] tensor<T> idst(const tensor<T>& a,
3634 int type = 2,
3635 std::optional<std::size_t> n = std::nullopt,
3636 std::ptrdiff_t axis = -1,
3637 fft_norm norm = fft_norm::backward,
3638 std::optional<bool> orthogonalize = std::nullopt)
3639 {
3640 return detail::trig_transform(a, detail::trig_family::sine, type, n, axis, norm, orthogonalize, true);
3641 }
3642} // namespace numerical
3643
3644#endif // NUMERICAL_FFT_HPP
numerical::buffer, the storage of the library's vectors, matrices and tensors: a std::vector whose el...
#define NUMERICAL_OUT_OF_LINE
Definition buffer.hpp:30
Thrown when an argument is outside what an operation takes (a tolerance below 0, an FFT type past 4).
Definition vector.hpp:87
A transform's working space of C: the calling thread's own, kept for the next transform,...
Definition fft.hpp:2005
buffer< C > own_
The space past fft_scratch_kept.
Definition fft.hpp:2032
C * data() const noexcept
The first element.
Definition fft.hpp:2025
fft_scratch(std::size_t count)
Space for count elements.
Definition fft.hpp:2009
The roots e^{−2πi k/n} of one n, each as unit_root rounds it, from two tables of about √n angles inst...
Definition fft.hpp:245
std::pair< double_double, double_double > parts(std::size_t k) const noexcept
e^{−2πi k/n} as double-double parts: cos(A + B) = cA·cB − sA·sB, sin(A + B) = sA·cB + cA·sB.
Definition fft.hpp:262
std::complex< double > root(std::size_t k) const noexcept
parts rounded once to double, a zero's sign positive.
Definition fft.hpp:273
std::size_t m_
The first table's length.
Definition fft.hpp:282
std::vector< std::pair< double_double, double_double > > high_
cos and sin of (π/4)·b·m/n, b·m up to n.
Definition fft.hpp:284
std::size_t n_
The order of the roots.
Definition fft.hpp:281
unit_roots(std::size_t n)
The tables for the roots of n.
Definition fft.hpp:249
std::vector< std::pair< double_double, double_double > > low_
cos and sin of (π/4)·a/n, a below m.
Definition fft.hpp:283
Thrown when an operation's operands have incompatible shapes.
Definition vector.hpp:76
What every exception NumericAL throws is, beside its standard base (all but std::bad_alloc and std::s...
Definition vector.hpp:40
A dense N-dimensional tensor of T with value semantics, read row-major. Its elements are immutable on...
Definition tensor.hpp:88
const std::vector< std::size_t > & shape() const noexcept
The size of each axis.
Definition tensor.hpp:326
std::optional< std::pair< tensor, std::vector< std::size_t > > > laid_out() const
Where this view reaches each of its elements once from the first (a transpose's, transposed): its axe...
Definition tensor.hpp:291
const buffer< T > & data() const
The elements, row-major. A view's (transposed) are copied out by the first call, one thread copying w...
Definition tensor.hpp:370
std::size_t rank() const noexcept
The number of axes (0 for a scalar).
Definition tensor.hpp:314
std::size_t size() const noexcept
The total number of elements.
Definition tensor.hpp:320
The types numerical, :fft transforms: float, double and their complex numbers.
Definition fft.hpp:1982
A complex number of float or double, which gemm_split multiplies through the real kernel and the kern...
Definition simd.hpp:188
#define NUMERICAL_FFT_LANES_TARGET
Definition fft.hpp:354
#define NUMERICAL_FFT_LANES_INLINE
Definition fft.hpp:355
The transform's radix-4 and radix-16 passes in registers of complex numbers, written once for every u...
The matrix product kernel behind matrix * matrix and the einsum matmul path.
#define NUMERICAL_UNROLL_BLOCK
Definition gemm.hpp:72
tensor< std::complex< T > > 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 calle...
Definition fft.hpp:2880
constexpr std::size_t fft_four_step_least
The fewest bytes of complex numbers a transform takes in four steps (four_step_plan),...
Definition fft.hpp:892
constexpr std::size_t fft_column_block
The lines a task of transform_axis takes together along an axis whose lines lie apart: each row read ...
Definition fft.hpp:2124
bool on_release(void(*step)()) noexcept
Registers step among the calling thread's thread_releases, while a place is left (a workspace past th...
Definition buffer.hpp:65
std::pair< double_double, double_double > octant_sin_cos(std::size_t share, std::size_t n)
The cosine and sine of (π/4)·share/n by dd_sin_cos.
Definition fft.hpp:213
void 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_f...
Definition fft.hpp:1671
R 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.
Definition fft.hpp:1986
std::complex< double > 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.
Definition fft.hpp:229
tensor< T > 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 t...
Definition fft.hpp:3049
void 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),...
Definition fft.hpp:2220
void 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...
Definition fft.hpp:1492
axis_walk walk_along(const std::vector< std::size_t > &shape, std::size_t axis)
axis_walk of shape along axis; outer and inner 0 where the result is empty.
std::pair< double_double, double_double > 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.
Definition fft.hpp:220
std::complex< R > 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-...
Definition fft.hpp:1301
std::size_t 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.
Definition fft.hpp:2819
void 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 ro...
Definition fft.hpp:2133
constexpr std::size_t fft_root_cost
A root of unity's cost in parallel_for's units, about a nanosecond each: some 95 ns in double-double ...
Definition fft.hpp:1026
void 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.
Definition fft.hpp:2747
std::shared_ptr< const real_fft_plan< R > > shared_real_fft_plan(std::size_t n)
The real_fft_plan of n, shared as shared_fft_plan shares the complex ones.
Definition fft.hpp:2478
std::complex< R > twiddled(const std::complex< R > &w, const std::complex< R > &v) noexcept
A butterfly's factor times v on the vector paths: fused_product.
Definition fft.hpp:327
void 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...
Definition fft.hpp:1236
octant_share reduce_to_octant(std::size_t k, std::size_t n) noexcept
The octant_share of e^{−2πi k/n}.
Definition fft.hpp:182
void run_fused(const Body &body)
body(0), where std::fma is the instruction (with_fma_instruction) on an x86-64 processor with AVX2 an...
Definition tensor.hpp:698
std::size_t eighth_inverse(std::size_t n) noexcept
The inverse of 8 modulo the odd n, in [0, n): by Euclid's algorithm extended.
Definition fft.hpp:3329
typename C::value_type fft_real_t
The part type of a complex number (R), or of a register of lines' (fft_pack).
Definition fft.hpp:1150
void 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.
Definition fft.hpp:1772
tensor< T > 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,...
Definition fft.hpp:2357
std::complex< R > scaled(R c, const std::complex< R > &v) noexcept
c · v of a real c and a complex v: each part's product, rounded.
Definition fft.hpp:1290
T square(const T &x)
x · x, by the type's own product (a complex one's C Annex G, as the library's *).
std::complex< R > 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,...
Definition fft.hpp:302
double_double dd_div(double_double x, double d) noexcept
x divided by the integer d (exact in a double).
Definition fft.hpp:113
fft_source< T > source_of(const tensor< T > &a)
a's elements, where they lie.
Definition fft.hpp:2247
void 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.
Definition fft.hpp:1795
void 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 co...
Definition fft.hpp:2594
void 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.
Definition fft.hpp:2728
void 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,...
Definition fft.hpp:2540
tensor< R > 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 ...
Definition fft.hpp:3439
bool 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),...
Definition fft.hpp:949
@ split
arm64's real kernel's (gemm_split): Re a·Re b from zero, −Im a·Im b fused into it; Re a·Im b,...
auto 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 t...
Definition fft.hpp:2259
double_double dd_negate(double_double x) noexcept
x negated, both parts.
Definition fft.hpp:167
constexpr std::size_t fft_scratch_kept
The most elements fft_scratch keeps on a thread between transforms: 1 MiB of complex double.
Definition fft.hpp:1997
double_double dd_mul(double_double x, double_double y) noexcept
The product of two double-double numbers, its cross terms by explicit fused multiply-adds.
Definition fft.hpp:102
void 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...
Definition fft.hpp:1445
trig_family
The family of a real trigonometric transform: dct's or dst's.
Definition fft.hpp:3223
void 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.
Definition fft.hpp:2107
void 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.
Definition fft.hpp:1200
void 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.
Definition fft.hpp:1647
constexpr std::size_t fft_four_step_band
The rows of the four steps' working space a task transforms together, then writes down the columns of...
Definition fft.hpp:901
constexpr std::size_t fft_plans_kept
The plans kept, the least recently used dropped past it: a plan in use lives on in its holders.
Definition fft.hpp:1108
void parallel_for(std::size_t count, std::size_t work_per_index, const Body &body)
Runs body(i) for every i in [0, count).
Definition parallel.hpp:790
std::size_t 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.
Definition fft.hpp:2526
void 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.
Definition fft.hpp:1536
void 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,...
Definition fft.hpp:2279
constexpr std::size_t fft_split_least
The fewest points of a length with a prime factor p past fft_largest_radix, not prime,...
Definition fft.hpp:1009
gemm_path gemm_path_current() noexcept
The path the next double product takes: the most capable one under the cap that runs here (each path'...
Definition gemm.hpp:148
void 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 ...
Definition fft.hpp:2183
tensor< Out > 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 firs...
Definition fft.hpp:2776
tensor< std::complex< T > > 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.
Definition fft.hpp:2897
bool fft_fuses() noexcept
Whether a transform's butterflies fuse their products (fused_product): on every path past the portabl...
Definition fft.hpp:1711
std::complex< R > 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....
Definition fft.hpp:315
std::shared_ptr< const cosine_line< R > > 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...
Definition fft.hpp:3401
std::shared_ptr< const fft_plan< R > > 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 u...
Definition fft.hpp:1113
std::complex< fft_real_t< C > > fft_root_t
The complex number of C's part type: a pass' factors.
Definition fft.hpp:1154
std::size_t 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 mo...
Definition fft.hpp:962
std::vector< std::size_t > 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,...
Definition fft.hpp:814
void 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 co...
Definition fft.hpp:2647
std::size_t bluestein_length(std::size_t n)
The points of Bluestein's convolution of n points: the power of two at least 2n − 1,...
Definition fft.hpp:982
bool all_finite(const R *x, std::size_t count) noexcept
Whether the count values at x are all finite: a NaN or an infinity has every exponent bit set,...
Definition simd.hpp:1392
double_double dd_add(double_double x, double_double y) noexcept
The sum of two double-double numbers.
Definition fft.hpp:90
constexpr double_double quarter_pi
π/4 as a double-double number.
Definition fft.hpp:123
constexpr std::size_t fft_lines_width
One line at a time where no register holds lines.
Definition fft.hpp:2092
void forward_fft(const fft_plan< R > &plan, std::complex< R > *data, std::complex< R > *work, bool fused, bool in_work=false)
The forward transform of the plan's length into data, work its fft_plan::work, its Stockham passes,...
Definition fft.hpp:1832
void 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,...
Definition fft.hpp:1723
void 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 halv...
Definition fft.hpp:1406
void 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.
Definition fft.hpp:1211
void 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(con...
Definition fft.hpp:2561
T root(const T &x)
The square root of a scalar, as std::sqrt gives it.
std::size_t largest_prime_factor(std::size_t n) noexcept
The largest prime factor of n, at least 2.
Definition fft.hpp:1012
small_radix_constants< R > make_small_radix_constants()
small_radix_constants from the roots of order 3 and 5 (unit_root, whose imaginary parts are −sin).
Definition fft.hpp:862
void two_sum(double a, double b, double &sum, double &error) noexcept
The sum of a and b as sum rounded and error exact (Knuth's two-sum: no order of magnitudes needed).
void 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...
Definition fft.hpp:2297
std::vector< std::size_t > view_axes(const std::vector< std::size_t > &order)
The axes that put the elements of a tensor laid out in order (tensor::laid_out, its view's axes in th...
tensor< T > 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.
Definition fft.hpp:2927
double unsigned_zero(double x) noexcept
x with a zero's sign made positive: the twiddle factors' zeros are +0, as their exact values.
Definition fft.hpp:161
std::size_t element_count(It first, It last)
The elements a shape's extents [first, last) hold: 0 where one of them is 0, whatever the others,...
Definition vector.hpp:151
tensor< std::complex< R > > 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 i...
Definition fft.hpp:2838
constexpr std::size_t fft_largest_radix
The largest prime a Stockham pass takes as its radix, by its own r-point sum: a length with a larger ...
Definition fft.hpp:804
auto as_laid_along(const tensor< T > &t, std::size_t axis, const F &f) -> std::optional< decltype(f(t, axis))>
Along axis of a transpose (laid_along): f (f(elements, axis)) of its elements as they lie along the m...
void 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 i...
Definition fft.hpp:1164
cosine_line< R > 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,...
Definition fft.hpp:3353
std::pair< double_double, double_double > 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): a...
Definition fft.hpp:193
void 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.
Definition fft.hpp:1278
std::pair< double_double, double_double > 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'...
Definition fft.hpp:143
fft_plan< R > make_fft_plan(std::size_t n)
The fft_plan of length n, its roots computed on the threads (each the same on any).
Definition fft.hpp:1030
std::size_t fft_lane_groups(const fft_plan< R > &, bool, std::size_t, bool) noexcept
No registers of lines.
Definition fft.hpp:2096
double_double fast_two_sum(double a, double b) noexcept
a + b exactly where |a| ≥ |b| or a is 0 (Dekker's fast two-sum).
Definition fft.hpp:81
constexpr std::size_t fft_four_step_pad
The complex numbers past each row of the four steps' working space: rows a power of two of bytes apar...
Definition fft.hpp:896
const std::array< double_double, 30 > & inverse_factorials()
The terms of dd_sin_cos' series: 1/k! for k = 0 to 29, each from the last by dd_div.
Definition fft.hpp:126
constexpr std::size_t memory_element_weight
The weight of an element a pass bound by the memory writes or moves, against a multiply-add,...
Definition parallel.hpp:760
void 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 (ra...
Definition fft.hpp:1351
@ fused
std::fma, where every target has the instruction.
R rounded_alone(R x) noexcept
x, held in a register as its rounded value: GCC on arm64 with the complex-arithmetic unit (ARMv8....
Definition fft.hpp:291
The NumericAL public API.
Definition amx.hpp:44
std::vector< T, detail::default_init_allocator< T > > buffer
The storage of vector, matrix and tensor, namely a std::vector whose buffer<T>(n) and resize(n) leave...
Definition buffer.hpp:443
std::size_t max_threads()
The threads a kernel may use: the cap if one is set, else the hardware threads (starting none).
Definition parallel.hpp:995
T sum(const tensor< T > &t)
The sum of every element, by pairwise halving (0 for an empty tensor), on the threads where they are ...
tensor< T > 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....
Definition fft.hpp:3100
matrix< T > operator+(const matrix< T > &a, const matrix< T > &b)
Element-wise sum.
Definition matrix.hpp:162
tensor< T > 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,...
Definition fft.hpp:3617
matrix< T > operator*(const T &scalar, const matrix< T > &m)
Scalar times matrix.
Definition matrix.hpp:188
tensor< T > 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 ...
Definition fft.hpp:3166
tensor< T > 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...
Definition fft.hpp:3011
@ amx
The Apple AMX coprocessor, fused multiply-adds; the products it does not suit on the NEON path's tile...
tensor< T > sqrt(const tensor< T > &a)
The square root of every element: std::sqrt of a real one, detail::complex_sqrt of a complex one.
@ reduced
Q is m × k, R k × n, k = min(m, n): NumPy's default.
constexpr fft_norm swapped(fft_norm norm) noexcept
norm with its forward and backward exchanged, as NumPy's hfft and ihfft take it.
Definition fft.hpp:3175
tensor< T > 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,...
Definition fft.hpp:3574
tensor< T > 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 typ...
Definition fft.hpp:3590
matrix< T > operator-(const matrix< T > &a, const matrix< T > &b)
Element-wise difference.
Definition matrix.hpp:175
tensor< T > 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 typ...
Definition fft.hpp:3633
fft_norm
How a transform and its inverse are scaled, as NumPy's norm.
Definition fft.hpp:53
@ backward
The forward transform unscaled, the inverse scaled by 1/n (NumPy's default).
@ forward
The forward transform scaled by 1/n, the inverse unscaled.
@ ortho
Both scaled by 1/√n: a unitary pair.
tensor< T > 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 ...
Definition fft.hpp:3191
tensor< T > 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}.
Definition fft.hpp:2966
tensor< std::complex< T > > 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,...
Definition fft.hpp:3146
matrix< T > inverse(matrix< T > a)
The inverse of a square matrix.
tensor< T > remainder(const tensor< T > &a, const tensor< T > &b)
a % b element by element, broadcast, as numpy.remainder (Python's: of b's sign; a real by zero fmod's...
tensor< std::complex< T > > 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.
Definition fft.hpp:3210
A minimal std::thread parallel-for for the hot kernels.
The native vector of float and double the kernels hold their lanes in (GNU vector extensions,...
#define NUMERICAL_INLINE_LAMBDA
Definition simd.hpp:33
#define NUMERICAL_ALWAYS_INLINE
Definition simd.hpp:25
The extents and strides that walk a tensor of shape with axis axis taken out: outer positions before ...
Bluestein's convolution for a length n with a prime factor past fft_largest_radix.
Definition fft.hpp:877
std::vector< std::complex< R > > chirp
e^{−πi j²/n}, its exponent j² mod 2n reduced exactly.
Definition fft.hpp:879
std::size_t padded
M: the points the convolution runs at (bluestein_length).
Definition fft.hpp:878
std::shared_ptr< const fft_plan< R > > inner
The plan of M points.
Definition fft.hpp:881
std::vector< std::complex< R > > spectrum
The transform of M points of the chirp's conjugate, wrapped.
Definition fft.hpp:880
The cosine transforms of scipy.fft.dct, unscaled, on one line of n points by a Fourier transform: typ...
Definition fft.hpp:3241
std::vector< R > signs
Its factor, ±√2.
Definition fft.hpp:3249
std::vector< std::complex< R > > turns
Type 4 of an even n.
Definition fft.hpp:3247
std::vector< std::complex< R > > roots
See above.
Definition fft.hpp:3246
std::vector< std::size_t > picks
Type 4 of an odd n: the frequency each value is.
Definition fft.hpp:3248
std::shared_ptr< const fft_plan< R > > complex
Type 4.
Definition fft.hpp:3245
void apply(const R *u, R *y, R *even, std::complex< R > *spectrum, std::complex< R > *space) const
y from u, even (the real transform's points) and spectrum its spaces, space the plan's; the path's pr...
Definition fft.hpp:3255
std::shared_ptr< const real_fft_plan< R > > real
Types 1 to 3.
Definition fft.hpp:3244
A double-double number: hi + lo, hi the sum rounded to double.
Definition fft.hpp:63
double lo
The trailing part, at most half a unit in the last place of hi.
Definition fft.hpp:65
double hi
The leading part.
Definition fft.hpp:64
The complex type a transform of T computes in: T itself, or a real type's complex.
Definition fft.hpp:1969
std::complex< T > type
A real float or double's.
Definition fft.hpp:1970
The result of a transform along one axis, allocated before its plan, whose tables grow with the point...
Definition fft.hpp:2314
static std::size_t counted(const std::vector< std::size_t > &extents)
The elements of extents.
Definition fft.hpp:2325
tensor< Out > take() &&
The result as a tensor.
Definition fft.hpp:2344
fft_output(std::vector< std::size_t > input_shape, std::size_t index, std::size_t out_points)
Definition fft.hpp:2318
static std::vector< std::size_t > resized(std::vector< std::size_t > extents, std::size_t index, std::size_t extent)
extents, the one at index made extent.
Definition fft.hpp:2335
buffer< Out > out
Its elements, uninitialized.
Definition fft.hpp:2316
std::vector< std::size_t > shape
The input's shape, the axis out_points long.
Definition fft.hpp:2315
The factors and passes of a transform of one length, built once and shared.
Definition fft.hpp:924
std::optional< four_step_plan< R > > four_step
Where the length is at least fft_four_step_least, or splits off a prime past fft_largest_radix (fft_s...
Definition fft.hpp:933
std::size_t length
The transform's length.
Definition fft.hpp:925
std::array< std::complex< R >, 16 > sixteenths
e^{−2πi k/16}: a radix-16 butterfly's own factors.
Definition fft.hpp:931
std::vector< std::complex< R > > radix_roots
Each pass of a prime radix past 5: e^{−2πi m/r} for m below r, the passes in order.
Definition fft.hpp:929
std::vector< std::complex< R > > twiddles
Each pass' factors from p = 1: its w^p run, then its w^{2p} run, to its w^{(r−1)p} run.
Definition fft.hpp:927
std::size_t work
The working space a transform takes beside its data.
Definition fft.hpp:935
std::optional< bluestein_plan< R > > bluestein
Where the length has a prime factor past fft_largest_radix.
Definition fft.hpp:932
std::vector< std::size_t > radices
Each Stockham pass' radix (fft_radices).
Definition fft.hpp:926
small_radix_constants< R > small
The radix-3 and radix-5 butterflies' constants.
Definition fft.hpp:936
The elements a transform reads where they lie, row-major, of shape shape: a tensor's,...
Definition fft.hpp:2240
const T * data
The first element.
Definition fft.hpp:2241
std::vector< std::size_t > shape
The extent of each axis.
Definition fft.hpp:2242
A transform of n = n1·n2 points in four steps (Bailey's), each a batch of lines the threads share: x ...
Definition fft.hpp:913
std::shared_ptr< const fft_plan< R > > row_plan
The plan of n1 points.
Definition fft.hpp:917
std::vector< std::complex< R > > twiddles
w^{j1·k2}, e^{−2πi j1·k2/n}, at k2·n1 + j1.
Definition fft.hpp:918
std::shared_ptr< const fft_plan< R > > column_plan
The plan of n2 points.
Definition fft.hpp:916
std::size_t columns
n1: the columns, the points of each row.
Definition fft.hpp:914
std::size_t rows
n2: the rows, the points of each column.
Definition fft.hpp:915
e^{−2πi k/n}'s angle reduced to an eighth of a turn by integer arithmetic, 8k = octant·n + rest: the ...
Definition fft.hpp:176
std::size_t share
The angle within it, in units of π/(4n).
Definition fft.hpp:178
std::size_t octant
The eighth of a turn the angle falls in.
Definition fft.hpp:177
What a transform of n real points (or to them) takes: the complex plan of n/2 points for an even n,...
Definition fft.hpp:2470
std::shared_ptr< const fft_plan< R > > complex
The complex plan: n/2 points (even n), n (odd).
Definition fft.hpp:2472
std::vector< std::complex< R > > roots
e^{−2πi k/n}, k from 0 to n/2 (even n).
Definition fft.hpp:2473
The real constants of the radix-3, -5 and -8 butterflies, rounded once from their double-double value...
Definition fft.hpp:850
R half_root_three
√3/2 = sin(2π/3).
Definition fft.hpp:851
R half_root_two
√½ = cos(π/4).
Definition fft.hpp:856
A dense, row-major, N-dimensional tensor and Einstein summation.
Element-wise arithmetic with NumPy's broadcasting, reductions, reshaping and creation of tensors.