22#ifndef NUMERICAL_FFT_HPP
23#define NUMERICAL_FFT_HPP
72 const double sum {a + b};
84 const double sum {a + b};
95 double error {high.lo + low.hi};
116 const double first {x.
hi / d};
117 double remainder {std::fma(-first, d, x.hi)};
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));
149 for (std::size_t k {28}; k >= 2; k -= 2) {
163 return x == 0.0 ? 0.0 : x;
169 return {-x.
hi, -x.lo};
183 std::size_t n)
noexcept
185 const std::size_t
eighths {8 * (k % n)};
186 const std::size_t octant {
eighths / n};
188 return {octant, (octant % 2) == 1 ? n -
rest :
rest};
253 for (std::size_t a {0}; a <
m_; ++a) {
256 for (std::size_t b {0}; b *
m_ <= n; ++b) {
262 [[
nodiscard]] std::pair<double_double, double_double>
parts(std::size_t k)
const noexcept
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_]};
275 const auto [re, im] {
parts(k)};
283 std::vector<std::pair<double_double, double_double>>
low_;
284 std::vector<std::pair<double_double, double_double>>
high_;
290 template <std::
floating_po
int R>
293#if defined(__GNUC__) && !defined(__clang__) && defined(__aarch64__)
301 template <std::
floating_po
int R>
303 const std::complex<R>& q)
noexcept
305 const R
rr {p.real() * q.real()};
307 const R
ri {p.real() * q.imag()};
309 return {
rr -
ii,
ri + ir};
314 template <std::
floating_po
int R>
316 const std::complex<R>& v)
noexcept
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)};
324 template <
bool Fused,
325 std::floating_point R>
328 const std::complex<R>& v)
noexcept
334 template <
bool Fused,
335 std::floating_point R>
338 const std::complex<R>& v)
noexcept
346#if defined(NUMERICAL_X86_COMPILED)
347# define NUMERICAL_FFT_LANES_TARGET NUMERICAL_TARGET("avx2,fma")
348# if defined(_MSC_VER) && !defined(__clang__)
349# define NUMERICAL_FFT_LANES_INLINE NUMERICAL_ALWAYS_INLINE
351# define NUMERICAL_FFT_LANES_INLINE NUMERICAL_TARGET("avx2,fma") inline
354# define NUMERICAL_FFT_LANES_TARGET
355# define NUMERICAL_FFT_LANES_INLINE NUMERICAL_ALWAYS_INLINE
358#if defined(NUMERICAL_X86_COMPILED) || defined(NUMERICAL_NEON_COMPILED)
359# define NUMERICAL_FFT_LANES
361# if defined(NUMERICAL_X86_COMPILED)
451 std::size_t
apart)
noexcept
462 const double*
const from {
reinterpret_cast<const double*
>(at)};
475 const double*
const from {
reinterpret_cast<const double*
>(at)};
488 double*
const into {
reinterpret_cast<double*
>(at)};
503 double*
const into {
reinterpret_cast<double*
>(at)};
614 const double*
const from {
reinterpret_cast<const double*
>(at)};
627 const float*
const from {
reinterpret_cast<const float*
>(at)};
640 double*
const into {
reinterpret_cast<double*
>(at)};
651 float*
const into {
reinterpret_cast<float*
>(at)};
663 template <std::
floating_po
int R>
681 template <std::
floating_po
int R>
682 using fft_lanes_of =
typename fft_lanes_register<R>::type;
688 template <std::
floating_po
int R>
689 struct alignas(sizeof(fft_lanes_of<R>))
fft_pack
695 template <std::
floating_po
int R>
703 template <std::
floating_po
int R>
711 template <std::
floating_po
int R>
718 template <std::
floating_po
int R>
726 template <std::
floating_po
int R>
739 template <std::
floating_po
int R>
742 using value_type = R;
769 template <std::
floating_po
int R>
773 template <std::
floating_po
int R>
777 return {a.re + b.re, a.im + b.im};
781 template <std::
floating_po
int R>
785 return {a.re - b.re, a.im - b.im};
789 template <
bool Fused,
790 std::floating_point R>
797 return {
fused(w.real(), v.re, -
ii),
fused(w.real(), v.im, ir)};
805#if defined(NUMERICAL_X86_COMPILED) || defined(NUMERICAL_NEON_COMPILED)
816 std::vector<std::size_t> radices;
817 std::size_t
twos {std::size_t {1} <<
static_cast<unsigned>(std::countr_zero(n))};
820 radices.push_back(4);
824 radices.push_back(16);
827 radices.push_back(8);
831 radices.push_back(4);
838 radices.push_back(
prime);
842 radices.push_back(2);
848 template <std::
floating_po
int R>
861 template <std::
floating_po
int R>
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())};
871 template <std::
floating_po
int R>
875 template <std::
floating_po
int R>
881 std::shared_ptr<const fft_plan<R>>
inner;
900 template <std::
floating_po
int R>
911 template <std::
floating_po
int R>
922 template <std::
floating_po
int R>
939 template <std::
floating_po
int R>
941 std::complex<R>* data,
942 std::complex<R>* work,
948 template <std::
floating_po
int R>
951 return !
plan.bluestein && !
plan.four_step &&
plan.radices.size() % 2 == 1;
968 std::size_t columns {
static_cast<std::size_t
>(std::sqrt(
static_cast<double>(n)))};
969 while (n % columns != 0) {
984 const std::size_t
least {(2 * n) - 1};
985 const std::size_t
power {std::bit_ceil(
least)};
1014 std::size_t largest {1};
1015 for (std::size_t d {2}; d <= n / d; ++d) {
1016 while (n % d == 0) {
1021 return n > 1 ? n : largest;
1029 template <std::
floating_po
int R>
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())}; }};
1036 for (std::size_t k {0}; k < 16; ++k) {
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]);
1052 std::vector<C>
scratch(b.inner->work);
1054 plan.work = b.padded + b.inner->work;
1055 plan.bluestein = std::move(b);
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};
1068 for (std::size_t j1 {0};
j1 < f.columns; ++
j1) {
1069 f.twiddles[(
k2 * f.columns) +
j1] =
narrow(roots.root((
j1 *
k2) % n));
1072 plan.radices.clear();
1074 plan.four_step = std::move(f);
1079 std::vector<std::size_t> starts;
1080 std::vector<std::size_t> steps;
1083 starts.push_back(0);
1084 for (
const std::size_t
radix :
plan.radices) {
1086 starts.push_back(starts.back() + (
current /
radix) - 1);
1090 for (std::size_t m {0}; m <
radix; ++m) {
1097 const unit_roots roots {n};
1098 plan.twiddles.resize(starts.back());
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]));
1112 template <std::
floating_po
int R>
1118 std::shared_ptr<const fft_plan<R>> plan;
1120 static std::mutex guard;
1121 static std::vector<entry> plans;
1123 const auto found {std::find_if(plans.begin(), plans.end(), [n](
const entry& e) { return e.length == n; })};
1124 if (found == plans.end()) {
1127 std::rotate(found, found + 1, plans.end());
1128 return plans.back().plan;
1131 const std::scoped_lock lock {guard};
1132 if (
auto plan {
kept()}) {
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; });
1142 plans.erase(plans.begin());
1144 plans.push_back({n, std::move(built)});
1145 return plans.back().plan;
1149 template <
typename C>
1153 template <
typename C>
1162 template <
bool Fused,
1170 const std::size_t quarter {current / 4};
1171 const std::size_t run {quarter - 1};
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()};
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);
1198 template <
bool Fused,
1199 std::floating_point R>
1202 const std::complex<R>* in,
1203 std::complex<R>* out,
1204 const std::complex<R>* twiddles)
noexcept
1206 radix_four_pass_body<Fused>(current, stride, in, out, twiddles);
1210 template <
typename C>
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;
1234 template <
bool Fused,
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);
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]);
1276 template <
bool Fused,
1277 std::floating_point R>
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
1285 radix_sixteen_pass_body<Fused>(current, stride, in, out, twiddles, sixteenths);
1289 template <std::
floating_po
int R>
1291 const std::complex<R>& v)
noexcept
1293 return {c * v.real(), c * v.imag()};
1298 template <
bool Fused,
1299 std::floating_point R>
1303 const std::complex<R>& v)
noexcept
1305 return {std::fma(c, v.real(), s.real()), std::fma(c, v.imag(), s.imag())};
1309 template <
bool Fused,
1310 std::floating_point R>
1314 const std::complex<R>& v)
noexcept
1319#ifdef NUMERICAL_FFT_LANES
1321 template <std::
floating_po
int R>
1323 const fft_lanes<R>& v)
noexcept
1325 return {c * v.re, c * v.im};
1329 template <
bool Fused,
1330 std::floating_point R>
1334 const fft_lanes<R>& v)
noexcept
1336 return {
fused(c, v.re, s.re),
fused(c, v.im, s.im)};
1349 template <
bool Fused,
1352 std::size_t current,
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) {
1369 const C x0 {in_p[q]};
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];
1379 for (std::size_t k {1}; k <= half; ++k) {
1380 std::size_t power {k};
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) {
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]);
1389 const C i_sines {-sines.imag(), sines.real()};
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);
1404 template <
bool Fused,
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};
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);
1443 template <
bool Fused,
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};
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]);
1490 template <
bool Fused,
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)]};
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);
1534 template <
bool Fused,
1535 std::floating_point R>
1537 std::size_t current,
1539 const std::complex<R> * in,
1540 std::complex<R> * out,
1541 const std::complex<R> * twiddles,
1542 const std::complex<R> * roots,
1546 radix_three_pass_body<Fused>(current, stride, in, out, twiddles, small);
1548 else if (radix == 5) {
1549 radix_five_pass_body<Fused>(current, stride, in, out, twiddles, small);
1551 else if (radix == 8) {
1552 radix_eight_pass_body<Fused>(current, stride, in, out, twiddles, small.half_root_two);
1555 any_radix_pass_body<Fused>(radix, current, stride, in, out, twiddles, roots);
1559#ifdef NUMERICAL_X86_COMPILED
1561 template <std::
floating_po
int R>
1563 std::
size_t current,
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
1572 avx2_radix_three_pass(current, stride, in, out, twiddles, small.half_root_three);
1574 else if (radix == 5) {
1575 avx2_radix_five_pass(current, stride, in, out, twiddles, small.c1, small.c2, small.s1, small.s2);
1577 else if (radix == 8) {
1578 avx2_radix_eight_pass(current, stride, in, out, twiddles, small.half_root_two);
1581 avx2_radix_any_pass(radix, current, stride, in, out, twiddles, roots);
1588 template <std::
floating_po
int R>
1589 NUMERICAL_TARGET(
"avx512f,avx2,fma") void any_radix_pass_avx512(std::
size_t radix,
1590 std::
size_t current,
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
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);
1601 else if (radix == 3) {
1602 avx512_radix_three_pass(current, stride, in, out, twiddles, small.half_root_three);
1604 else if (radix == 5) {
1605 avx512_radix_five_pass(current, stride, in, out, twiddles, small.c1, small.c2, small.s1, small.s2);
1607 else if (radix == 8) {
1608 avx512_radix_eight_pass(current, stride, in, out, twiddles, small.half_root_two);
1611 avx512_radix_any_pass(radix, current, stride, in, out, twiddles, roots);
1617#ifdef NUMERICAL_NEON_COMPILED
1619 template <std::
floating_po
int R>
1620 void any_radix_pass_neon(std::size_t radix,
1621 std::size_t current,
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
1630 neon_radix_three_pass(current, stride, in, out, twiddles, small.half_root_three);
1632 else if (radix == 5) {
1633 neon_radix_five_pass(current, stride, in, out, twiddles, small.c1, small.c2, small.s1, small.s2);
1635 else if (radix == 8) {
1636 neon_radix_eight_pass(current, stride, in, out, twiddles, small.half_root_two);
1639 neon_radix_any_pass(radix, current, stride, in, out, twiddles, roots);
1646 template <
typename C>
1651 for (std::size_t q {0}; q < stride; ++q) {
1653 const C b {in[q + stride]};
1655 out[q + stride] = a - b;
1666 template <std::floating_point R,
1677 bool from_work =
false) noexcept
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) {
1688 sixteen(current, stride, in, out, twiddles, plan.
sixteenths);
1690 else if (radix == 4) {
1691 four(current, stride, in, out, twiddles);
1693 else if (radix == 2) {
1697 other(radix, current, stride, in, out, twiddles, roots, plan.
small);
1698 roots += (radix > 5 && radix != 8) ? radix : 0;
1700 twiddles += (radix - 1) * (current / radix - 1);
1706 std::copy(in, in + n, data);
1721 template <
bool Fused,
1722 std::floating_point R>
1724 std::complex<R>* data,
1725 std::complex<R>* work)
1727 using C = std::complex<R>;
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)};
1734 C*
const input {ahead ? work + m : a};
1735 for (std::size_t j {0}; j < n; ++j) {
1736 input[j] = twiddled<Fused>(b.chirp[j], data[j]);
1738 std::fill(input + n, input + m, C {});
1740 for (std::size_t k {0}; k < m; ++k) {
1741 input[k] = std::conj(twiddled<Fused>(b.spectrum[k], a[k]));
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);
1750#ifdef NUMERICAL_X86_COMPILED
1752 template <std::
floating_po
int R>
1753 NUMERICAL_TARGET(
"avx2,fma") void bluestein_x86(const fft_plan<R>& plan,
1754 std::complex<R>* data,
1755 std::complex<R>* work)
1757 bluestein_body<true>(plan, data, work);
1762#ifdef NUMERICAL_X86_COMPILED
1766 inline constexpr std::size_t fft_avx512_shortest {256};
1770 template <
bool Fused,
1771 std::floating_point R>
1773 const std::complex<R>* w,
1774 std::size_t count)
noexcept
1776 for (std::size_t i {0}; i < count; ++i) {
1777 t[i] = twiddled<Fused>(w[i], t[i]);
1781#ifdef NUMERICAL_X86_COMPILED
1783 template <std::
floating_po
int 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
1788 twiddle_run_body<true>(t, w, count);
1794 template <std::
floating_po
int R>
1796 const std::complex<R>* w,
1798 bool fused)
noexcept
1801 twiddle_run_body<false>(t, w, count);
1804#ifdef NUMERICAL_X86_COMPILED
1805 twiddle_run_x86(t, w, count);
1807 twiddle_run_body<true>(t, w, count);
1816 template <std::
floating_po
int 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,
1822 bool inverse =
false,
1831 template <std::
floating_po
int R>
1833 std::complex<R>* data,
1834 std::complex<R>* work,
1844 bluestein_body<false>(plan, data, work);
1847#ifdef NUMERICAL_X86_COMPILED
1848 bluestein_x86(plan, data, work);
1850 bluestein_body<true>(plan, data, work);
1855 stockham_passes(plan, data, work, radix_four_pass<false, R>, radix_sixteen_pass<false, R>, any_radix_pass<false, R>, in_work);
1858#ifdef NUMERICAL_X86_COMPILED
1860 stockham_passes(plan, data, work, avx512_radix_four_pass<R>, avx512_radix_sixteen_pass<R>, any_radix_pass_avx512<R>, in_work);
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);
1867 stockham_passes(plan, data, work, radix_four_pass<true, R>, radix_sixteen_pass<true, R>, any_radix_pass<true, R>, in_work);
1871#ifdef NUMERICAL_FFT_LANES
1873 template <std::
floating_po
int R>
1876 const fft_lanes<R>* in,
1878 const std::complex<R>* twiddles)
noexcept
1880 radix_four_pass_body<true>(current, stride, in, out, twiddles);
1884 template <std::
floating_po
int R>
1887 const fft_lanes<R>* in,
1889 const std::complex<R>* twiddles,
1890 const std::array<std::complex<R>, 16>& sixteenths)
noexcept
1892 radix_sixteen_pass_body<true>(current, stride, in, out, twiddles, sixteenths);
1896 template <std::
floating_po
int R>
1898 std::size_t current,
1900 const fft_lanes<R>* in,
1902 const std::complex<R>* twiddles,
1903 const std::complex<R>* roots,
1904 const small_radix_constants<R>& small)
noexcept
1907 radix_three_pass_body<true>(current, stride, in, out, twiddles, small);
1909 else if (radix == 5) {
1910 radix_five_pass_body<true>(current, stride, in, out, twiddles, small);
1912 else if (radix == 8) {
1913 radix_eight_pass_body<true>(current, stride, in, out, twiddles, small.half_root_two);
1916 any_radix_pass_body<true>(radix, current, stride, in, out, twiddles, roots);
1927 template <
typename T,
1928 std::floating_point R>
1931 std::size_t in_line,
1932 std::size_t in_step,
1934 std::complex<R>* out,
1935 std::size_t out_line,
1936 std::size_t out_step,
1939 fft_lanes<R>* lines,
1940 fft_lanes<R>* work)
noexcept
1942 const std::size_t points {plan.length};
1944 fft_lanes<R>*
const start {ahead ? work : lines};
1945 for (std::size_t k {0}; k < points; ++k) {
1946 fft_lanes<R> value {};
1948 lanes_read(in + (k * in_step), in_line, value.re.v, value.im.v);
1950 start[k] = {value.re,
inverse ? -value.im : value.im};
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);
1959 lanes_write(out + (k * out_step), out_line, (scale * value.re).v, (scale * value.im).v);
1967 template <
typename T>
1974 template <split_complex C>
1981 template <
typename T>
1985 template <std::
floating_po
int R>
1990 if (norm == fft_norm::ortho) {
1991 return R(1) / std::sqrt(
static_cast<R
>(n));
1993 return (norm == fft_norm::forward) !=
inverse ? R(1) /
static_cast<R
>(n) : R(1);
2002 template <
typename C,
2013 data_ = own_.data();
2018 if (
kept.size() < count) {
2021 data_ =
kept.data();
2025 [[nodiscard]] C*
data() const noexcept
2036#ifdef NUMERICAL_FFT_LANES
2038 template <std::
floating_po
int R>
2039 inline constexpr std::size_t fft_lines_width {fft_lanes_width<R>};
2043 inline constexpr std::size_t fft_lanes_longest {std::size_t {1} << 12};
2045# if defined(NUMERICAL_X86_COMPILED)
2048 inline constexpr std::size_t fft_lanes_together_bytes {std::size_t {1} << 14};
2051 inline constexpr std::size_t fft_lanes_together_bytes {std::size_t {1} << 17};
2060 template <std::
floating_po
int R>
2064 bool together)
noexcept
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;
2071 template <
typename T,
2072 std::floating_point R>
2075 std::size_t in_line,
2076 std::size_t in_step,
2078 std::complex<R>* out,
2079 std::size_t out_line,
2080 std::size_t out_step,
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);
2091 template <std::
floating_po
int R>
2095 template <std::
floating_po
int R>
2105 template <
typename T,
2106 std::floating_point R>
2132 template <std::
floating_po
int R>
2134 const std::complex<R>* data,
2135 std::size_t columns,
2136 std::complex<R>* to,
2137 std::size_t to_rows,
2141 using C = std::complex<R>;
2142 const std::size_t points {plan.
length};
2144 const std::size_t together {groups * fft_lines_width<R>};
2146 const std::size_t work {2 * points *
static_cast<std::size_t
>(std::bit_width(points))};
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));
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;
2163 for (std::size_t b {0}; b < width; ++b) {
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;
2182 template <std::
floating_po
int R>
2184 std::complex<R>* data,
2187 const std::complex<R>* twiddles,
2189 std::complex<R>* out,
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)};
2201 for (std::size_t row {first}; row < first + count; ++row) {
2202 C*
const line {data + (row * apart)};
2204 std::transform(line, line + points, line, [](
const C& v) {
return std::conj(v); });
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};
2219 template <std::
floating_po
int R>
2221 const std::complex<R>* in,
2222 std::complex<R>* out,
2223 std::complex<R>* work,
2229 const std::size_t n1 {f.columns};
2230 const std::size_t n2 {f.rows};
2238 template <
typename T>
2246 template <
typename T>
2257 template <
typename T,
2260 std::ptrdiff_t axis,
2261 const F& f) ->
decltype(f(
source_of(a), axis))
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)};
2266 return f(
source_of(elements),
static_cast<std::ptrdiff_t
>(along));
2268 return std::move(*laid);
2278 template <
typename C>
2286 std::transform(in, in +
kept, to, [](
const C& value) {
return std::conj(value); });
2289 std::copy(in, in +
kept, to);
2291 std::fill(to +
kept, to + points, C {});
2296 template <
typename C>
2300 typename C::value_type scale)
noexcept
2303 std::transform(line, line + points, line, [](
const C& value) {
return std::conj(value); });
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}; });
2312 template <
typename Out>
2320 std::size_t out_points)
2321 : shape {resized(std::move(input_shape), index, out_points)}, out(counted(shape))
2325 [[nodiscard]]
static std::size_t
counted(
const std::vector<std::size_t>& extents)
2327 const std::size_t count {
element_count(extents.begin(), extents.end())};
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");
2335 [[nodiscard]]
static std::vector<std::size_t>
resized(std::vector<std::size_t> extents,
2339 extents[index] = extent;
2346 return tensor<Out> {std::move(shape), std::move(out)};
2356 template <split_complex T>
2358 const std::optional<std::size_t>& n,
2359 std::ptrdiff_t axis,
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));
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)};
2377 const R scale {fft_scale<R>(norm,
inverse, points)};
2379 if (walk.outer == 0) {
2380 return std::move(result).take();
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)};
2385 const T*
const from {a.
data};
2386 const auto finish {[&](
const C& value) {
2387 const C v {
inverse ? std::conj(value) : value};
2388 return scale == R(1) ? v : C {v.real() * scale, v.imag() * scale};
2392 const std::size_t work {2 * points *
static_cast<std::size_t
>(std::bit_width(points))};
2394 if (walk.inner == 1) {
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);
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)};
2407 if (plan->four_step) {
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 {};
2422 return std::move(result).take();
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);
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;
2454 for (std::size_t b {0}; b < width; ++b) {
2455 forward_fft(*plan, lines + (b * points), scratch.data(), fused);
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]);
2463 return std::move(result).take();
2468 template <std::
floating_po
int R>
2471 std::size_t length {0};
2477 template <std::
floating_po
int R>
2483 std::shared_ptr<const real_fft_plan<R>> plan;
2485 static std::mutex guard;
2486 static std::vector<entry> plans;
2488 const auto found {std::find_if(plans.begin(), plans.end(), [n](
const entry& e) { return e.length == n; })};
2489 if (found == plans.end()) {
2492 std::rotate(found, found + 1, plans.end());
2493 return plans.back().plan;
2496 const std::scoped_lock lock {guard};
2497 if (
auto found {
kept()}) {
2501 auto plan {std::make_shared<real_fft_plan<R>>()};
2504 plan->complex = shared_fft_plan<R>(n / 2);
2506 plan->roots.resize((n / 2) + 1);
2508 const std::complex<double>
root {roots.root(k)};
2509 plan->roots[k] = {
static_cast<R
>(
root.real()),
static_cast<R
>(
root.imag())};
2513 plan->complex = shared_fft_plan<R>(n);
2515 const std::scoped_lock lock {guard};
2516 std::erase_if(plans, [n](
const entry& e) {
return e.length == n; });
2518 plans.erase(plans.begin());
2520 plans.push_back({n, plan});
2521 return plans.back().plan;
2525 template <std::
floating_po
int R>
2527 const std::complex<R>* ,
2528 const std::complex<R>* ,
2529 std::complex<R>* )
noexcept
2539 template <std::
floating_po
int R>
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)};
2552 std::copy(line.begin(), line.begin() +
static_cast<std::ptrdiff_t
>((n / 2) + 1), X);
2560 template <std::
floating_po
int R>
2562 const std::complex<R>* X,
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]);
2578 for (std::size_t j {0}; j < n; ++j) {
2579 x[j] = line[j].real() * factor;
2591 template <
bool Fused,
2592 std::floating_point R,
2597 std::complex<R>* work,
2598 Registers registers)
2600 using C = std::complex<R>;
2601 const std::size_t n {plan.
length};
2602 const std::size_t h {n / 2};
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)};
2611 std::copy(line, line + h + 1, X);
2615 C*
const start {ahead ? work + h : z};
2620 std::copy(x, x + n,
reinterpret_cast<R*
>(start));
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) {
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)};
2631 X[k] = even + twiddled<Fused>(plan.
roots[k], odd);
2644 template <
bool Fused,
2645 std::floating_point R,
2648 const std::complex<R>* X,
2650 std::complex<R>* work,
2652 Registers registers)
2654 using C = std::complex<R>;
2655 const std::size_t n {plan.
length};
2656 const std::size_t h {n / 2};
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]);
2664 start[n - k] = X[k];
2667 for (std::size_t j {0}; j < n; ++j) {
2668 x[j] = line[j].real() * scale;
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());
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) {
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()};
2693 start[k] = std::conj(value);
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;
2702#ifdef NUMERICAL_X86_COMPILED
2704 template <std::
floating_po
int R>
2705 NUMERICAL_TARGET(
"avx2,fma") void real_forward_x86(const real_fft_plan<R>& plan,
2708 std::complex<R>* work)
2710 real_forward_body<true>(plan, x, X, work, avx2_real_forward_registers<R>);
2714 template <std::
floating_po
int R>
2715 NUMERICAL_TARGET(
"avx2,fma") void real_inverse_x86(const real_fft_plan<R>& plan,
2716 const std::complex<R>* X,
2718 std::complex<R>* work,
2721 real_inverse_body<true>(plan, X, x, work, scale, avx2_real_inverse_registers<R>);
2727 template <std::
floating_po
int R>
2731 std::complex<R>* work,
2735 real_forward_body<false>(plan, x, X, work, no_registers<R>);
2738#ifdef NUMERICAL_X86_COMPILED
2739 real_forward_x86(plan, x, X, work);
2741 real_forward_body<true>(plan, x, X, work, no_registers<R>);
2746 template <std::
floating_po
int R>
2748 const std::complex<R>* X,
2750 std::complex<R>* work,
2755 real_inverse_body<false>(plan, X, x, work, scale, no_registers<R>);
2758#ifdef NUMERICAL_X86_COMPILED
2759 real_inverse_x86(plan, X, x, work, scale);
2761 real_inverse_body<true>(plan, X, x, work, scale, no_registers<R>);
2772 template <
typename In,
2778 std::size_t in_points,
2783 const std::size_t extent {a.
shape[index]};
2784 const std::size_t out_points {result.shape[index]};
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) {
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());
2795 return std::move(result).take();
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 {};
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];
2814 return std::move(result).take();
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));
2827 return static_cast<std::size_t
>(axis < 0 ? axis + signed_rank : axis);
2837 template <std::
floating_po
int R>
2844 using C = std::complex<R>;
2846 if (result.out.empty()) {
2847 return std::move(result).take();
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};
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) {
2857 std::transform(x, x + points, spectrum, [](R value) {
return C {value, R(0)}; });
2862 for (std::size_t k {1}; k < points - half; ++k) {
2863 spectrum[points - k] = std::conj(spectrum[k]);
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};
2879 template <std::
floating_po
int T>
2881 const std::optional<std::size_t>& n,
2882 std::ptrdiff_t axis,
2886 const char*
const name {
inverse ?
"ifft" :
"fft"};
2888 const std::size_t points {n.value_or(a.
shape[index])};
2890 throw dimension_error(std::string {name} +
": invalid number of data points (0)");
2896 template <std::
floating_po
int T>
2898 const std::optional<std::size_t>& n,
2899 std::ptrdiff_t axis,
2902 using C = std::complex<T>;
2904 const std::size_t points {n.value_or(a.
shape[index])};
2909 if (result.out.empty()) {
2910 return std::move(result).take();
2912 const std::shared_ptr<const real_fft_plan<T>> plan {shared_real_fft_plan<T>(points)};
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) {
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}; });
2926 template <std::
floating_po
int T>
2928 const std::optional<std::size_t>& n,
2929 std::ptrdiff_t axis,
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))};
2940 if (result.out.empty()) {
2941 return std::move(result).take();
2943 const std::shared_ptr<const real_fft_plan<T>> plan {shared_real_fft_plan<T>(points)};
2945 const T factor {fft_scale<T>(norm,
true, points)};
2946 const T scale {points % 2 == 0 ? factor * T(2) : factor};
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) {
2964 template <detail::fft_input T>
2965 requires detail::split_complex<T>
2967 std::optional<std::size_t> n = std::nullopt,
2968 std::ptrdiff_t axis = -1,
2969 fft_norm norm = fft_norm::backward)
2971 return detail::transformed_along(a, axis, [&](
const auto& source, std::ptrdiff_t along) {
2972 return detail::transform_axis(source, n, along, norm,
false);
2988 template <std::
floating_po
int T>
2990 std::optional<std::size_t> n = std::nullopt,
2991 std::ptrdiff_t axis = -1,
2992 fft_norm norm = fft_norm::backward)
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);
3009 template <detail::fft_input T>
3010 requires detail::split_complex<T>
3012 std::optional<std::size_t> n = std::nullopt,
3013 std::ptrdiff_t axis = -1,
3014 fft_norm norm = fft_norm::backward)
3016 return detail::transformed_along(a, axis, [&](
const auto& source, std::ptrdiff_t along) {
3017 return detail::transform_axis(source, n, along, norm,
true);
3031 template <std::
floating_po
int T>
3033 std::optional<std::size_t> n = std::nullopt,
3034 std::ptrdiff_t axis = -1,
3035 fft_norm norm = fft_norm::backward)
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);
3048 template <
typename T>
3050 const std::vector<std::size_t>& shifts)
3052 if (
const auto laid {a.
laid_out()}) {
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]];
3057 return rolled(laid->first, lying).transposed(
view_axes(laid->second));
3059 const std::vector<std::size_t>& shape {a.
shape()};
3061 if (out.empty() || shape.empty()) {
3062 std::copy(a.
data().begin(), a.
data().end(), out.begin());
3063 return tensor<T> {shape, std::move(out)};
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};
3070 std::size_t rest {row};
3071 std::size_t source {0};
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};
3077 source += ((index + n - (shifts[d] % n)) % n) * stride;
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);
3083 std::copy(from + (last - shift), from + last, to);
3085 return tensor<T> {shape, std::move(out)};
3099 template <
typename T>
3101 const std::vector<std::ptrdiff_t>& axes,
3102 bool inverse =
false)
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));
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;
3114 return detail::rolled(a, shifts);
3126 template <
typename T>
3128 std::ptrdiff_t axis = -1,
3129 bool inverse =
false)
3145 template <std::
floating_po
int T>
3147 std::optional<std::size_t> n = std::nullopt,
3148 std::ptrdiff_t axis = -1,
3149 fft_norm norm = fft_norm::backward)
3151 return detail::transformed_along(a, axis, [&](
const auto& source, std::ptrdiff_t along) {
return detail::rfft_of(source, n, along, norm); });
3165 template <std::
floating_po
int T>
3167 std::optional<std::size_t> n = std::nullopt,
3168 std::ptrdiff_t axis = -1,
3169 fft_norm norm = fft_norm::backward)
3171 return detail::transformed_along(a, axis, [&](
const auto& source, std::ptrdiff_t along) {
return detail::irfft_of(source, n, along, norm); });
3177 return norm == fft_norm::backward ? fft_norm::forward : norm == fft_norm::forward ? fft_norm::backward : norm;
3190 template <std::
floating_po
int T>
3192 std::optional<std::size_t> n = std::nullopt,
3193 std::ptrdiff_t axis = -1,
3194 fft_norm norm = fft_norm::backward)
3196 const auto conjugated {[](
const std::complex<T>& v) {
return std::conj(v); }};
3197 return irfft(detail::parallel_map(a, conjugated), n, axis,
swapped(norm));
3209 template <std::
floating_po
int T>
3211 std::optional<std::size_t> n = std::nullopt,
3212 std::ptrdiff_t axis = -1,
3213 fft_norm norm = fft_norm::backward)
3215 const auto conjugated {[](
const std::complex<T>& v) {
return std::conj(v); }};
3216 return detail::parallel_map(
rfft(a, n, axis,
swapped(norm)), conjugated);
3239 template <std::
floating_po
int R>
3244 std::shared_ptr<const real_fft_plan<R>>
real;
3254 template <
bool Fused>
3258 std::complex<R>* spectrum,
3259 std::complex<R>* space)
const
3261 using C = std::complex<R>;
3262 constexpr bool fused {Fused};
3264 const std::size_t h {n / 2};
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];
3271 for (std::size_t k {0}; k < n; ++k) {
3272 y[k] = spectrum[k].real();
3275 else if (type == 2) {
3276 for (std::size_t j {0}; 2 * j < n; ++j) {
3279 for (std::size_t j {0}; (2 * j) + 1 < n; ++j) {
3280 even[n - 1 - j] = u[(2 * j) + 1];
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();
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);
3296 for (std::size_t j {0}; 2 * j < n; ++j) {
3299 for (std::size_t j {0}; (2 * j) + 1 < n; ++j) {
3300 y[(2 * j) + 1] = even[n - 1 - j];
3303 else if (n % 2 == 0) {
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)]});
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();
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]};
3321 for (std::size_t k {0}; k < n; ++k) {
3322 y[k] = signs[k] * spectrum[picks[k]].real();
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};
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)};
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));
3352 template <std::
floating_po
int R>
3357 if (type == 4 && n % 2 == 1) {
3358 line.
complex = shared_fft_plan<R>(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};
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};
3368 const bool sine {b == 1 || b == 3};
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;
3376 const auto half_turn = [&](std::size_t numerator, std::size_t 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())};
3381 line.complex = shared_fft_plan<R>(n / 2);
3382 line.roots.resize(n / 2);
3383 line.turns.resize(n / 2);
3385 line.roots[j] = half_turn((4 * j) + 1, 4 * n);
3386 line.turns[j] = half_turn(j, n);
3390 line.real = shared_real_fft_plan<R>(type == 1 ? 2 * (n - 1) : n);
3392 line.roots.resize((n / 2) + 1);
3400 template <std::
floating_po
int R>
3408 std::shared_ptr<const cosine_line<R>> line;
3410 static std::mutex guard;
3411 static std::vector<entry> lines;
3412 const auto same = [type, n](
const entry& e) {
return e.type == type && e.length == n; };
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;
3420 auto built {std::make_shared<const cosine_line<R>>(make_cosine_line<R>(type, n))};
3421 const std::scoped_lock lock {guard};
3422 std::erase_if(lines, same);
3424 lines.erase(lines.begin());
3426 lines.push_back({type, n, std::move(built)});
3427 return lines.back().line;
3438 template <std::
floating_po
int R>
3442 const std::optional<std::size_t>& n,
3443 std::ptrdiff_t axis,
3445 const std::optional<bool>& orthogonalize,
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));
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) +
")");
3459 if (result.out.empty()) {
3460 return std::move(result).take();
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>};
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) {
3480 R*
const v {u.
data()};
3481 const std::size_t last {points - 1};
3482 for (std::size_t j {0}; j < points; ++j) {
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;
3487 if (weighted &&
cosine && (computed == 1 || computed == 3)) {
3490 if (weighted &&
cosine && computed == 1) {
3491 v[last] *= root_two;
3493 if (weighted && !
cosine && computed == 3) {
3497 R*
const e {even.data()};
3499 e[points + 1] = R(0);
3500 for (std::size_t j {0}; j < points; ++j) {
3502 e[length - 1 - j] = -v[j];
3505 for (std::size_t k {0}; k < points; ++k) {
3506 y[k] = -spectrum.data()[k + 1].imag();
3514 lines->template apply<false>(v, y, even.data(), spectrum.data(), space);
3517 if (!
cosine && computed == 2) {
3518 std::reverse(y, y + points);
3520 if (!
cosine && computed >= 3) {
3521 for (std::size_t k {1}; k < points; k += 2) {
3525 if (weighted &&
cosine && computed <= 2) {
3528 if (weighted &&
cosine && computed == 1) {
3529 y[last] /= root_two;
3531 if (weighted && !
cosine && computed == 2) {
3532 y[last] /= root_two;
3534 if (scale != R(1)) {
3535 std::transform(y, y + points, y, [scale](R value) {
return value * scale; });
3541 template <std::
floating_po
int R>
3545 const std::optional<std::size_t>& n,
3546 std::ptrdiff_t axis,
3548 const std::optional<bool>& orthogonalize,
3573 template <std::
floating_po
int T>
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)
3581 return detail::trig_transform(a, detail::trig_family::cosine, type, n, axis, norm, orthogonalize,
false);
3589 template <std::
floating_po
int T>
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)
3597 return detail::trig_transform(a, detail::trig_family::cosine, type, n, axis, norm, orthogonalize,
true);
3616 template <std::
floating_po
int T>
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)
3624 return detail::trig_transform(a, detail::trig_family::sine, type, n, axis, norm, orthogonalize,
false);
3632 template <std::
floating_po
int T>
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)
3640 return detail::trig_transform(a, detail::trig_family::sine, type, n, axis, norm, orthogonalize,
true);
numerical::buffer, the storage of the library's vectors, matrices and tensors: a std::vector whose el...
#define NUMERICAL_OUT_OF_LINE
Thrown when an argument is outside what an operation takes (a tolerance below 0, an FFT type past 4).
A transform's working space of C: the calling thread's own, kept for the next transform,...
buffer< C > own_
The space past fft_scratch_kept.
C * data() const noexcept
The first element.
fft_scratch(std::size_t count)
Space for count elements.
The roots e^{−2πi k/n} of one n, each as unit_root rounds it, from two tables of about √n angles inst...
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.
std::complex< double > root(std::size_t k) const noexcept
parts rounded once to double, a zero's sign positive.
std::size_t m_
The first table's length.
std::vector< std::pair< double_double, double_double > > high_
cos and sin of (π/4)·b·m/n, b·m up to n.
std::size_t n_
The order of the roots.
unit_roots(std::size_t n)
The tables for the roots of n.
std::vector< std::pair< double_double, double_double > > low_
cos and sin of (π/4)·a/n, a below m.
Thrown when an operation's operands have incompatible shapes.
What every exception NumericAL throws is, beside its standard base (all but std::bad_alloc and std::s...
A dense N-dimensional tensor of T with value semantics, read row-major. Its elements are immutable on...
const std::vector< std::size_t > & shape() const noexcept
The size of each axis.
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...
const buffer< T > & data() const
The elements, row-major. A view's (transposed) are copied out by the first call, one thread copying w...
std::size_t rank() const noexcept
The number of axes (0 for a scalar).
std::size_t size() const noexcept
The total number of elements.
A complex number of float or double, which gemm_split multiplies through the real kernel and the kern...
#define NUMERICAL_FFT_LANES_TARGET
#define NUMERICAL_FFT_LANES_INLINE
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
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...
constexpr std::size_t fft_four_step_least
The fewest bytes of complex numbers a transform takes in four steps (four_step_plan),...
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 ...
bool on_release(void(*step)()) noexcept
Registers step among the calling thread's thread_releases, while a place is left (a workspace past th...
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.
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...
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.
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.
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...
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),...
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...
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.
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-...
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.
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...
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 ...
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.
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.
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.
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...
octant_share reduce_to_octant(std::size_t k, std::size_t n) noexcept
The octant_share of e^{−2πi k/n}.
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...
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.
typename C::value_type fft_real_t
The part type of a complex number (R), or of a register of lines' (fft_pack).
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.
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,...
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.
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,...
double_double dd_div(double_double x, double d) noexcept
x divided by the integer d (exact in a double).
fft_source< T > source_of(const tensor< T > &a)
a's elements, where they lie.
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.
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...
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.
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,...
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 ...
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),...
@ 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...
double_double dd_negate(double_double x) noexcept
x negated, both parts.
constexpr std::size_t fft_scratch_kept
The most elements fft_scratch keeps on a thread between transforms: 1 MiB of complex double.
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.
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...
trig_family
The family of a real trigonometric transform: dct's or dst's.
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.
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.
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.
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...
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.
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).
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.
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.
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,...
constexpr std::size_t fft_split_least
The fewest points of a length with a prime factor p past fft_largest_radix, not prime,...
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'...
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 ...
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...
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.
bool fft_fuses() noexcept
Whether a transform's butterflies fuse their products (fused_product): on every path past the portabl...
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....
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...
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...
std::complex< fft_real_t< C > > fft_root_t
The complex number of C's part type: a pass' factors.
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...
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,...
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...
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,...
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,...
double_double dd_add(double_double x, double_double y) noexcept
The sum of two double-double numbers.
constexpr double_double quarter_pi
π/4 as a double-double number.
constexpr std::size_t fft_lines_width
One line at a time where no register holds lines.
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,...
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,...
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...
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.
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...
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.
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).
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...
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.
double unsigned_zero(double x) noexcept
x with a zero's sign made positive: the twiddle factors' zeros are +0, as their exact values.
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,...
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...
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 ...
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...
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,...
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...
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.
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'...
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).
std::size_t fft_lane_groups(const fft_plan< R > &, bool, std::size_t, bool) noexcept
No registers of lines.
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).
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...
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.
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,...
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...
@ 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....
The NumericAL public API.
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...
std::size_t max_threads()
The threads a kernel may use: the cap if one is set, else the hardware threads (starting none).
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....
matrix< T > operator+(const matrix< T > &a, const matrix< T > &b)
Element-wise sum.
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,...
matrix< T > operator*(const T &scalar, const matrix< T > &m)
Scalar times matrix.
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 ...
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...
@ 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.
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,...
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...
matrix< T > operator-(const matrix< T > &a, const matrix< T > &b)
Element-wise difference.
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...
fft_norm
How a transform and its inverse are scaled, as NumPy's norm.
@ 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 ...
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}.
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,...
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.
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
#define NUMERICAL_ALWAYS_INLINE
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.
std::vector< std::complex< R > > chirp
e^{−πi j²/n}, its exponent j² mod 2n reduced exactly.
std::size_t padded
M: the points the convolution runs at (bluestein_length).
std::shared_ptr< const fft_plan< R > > inner
The plan of M points.
std::vector< std::complex< R > > spectrum
The transform of M points of the chirp's conjugate, wrapped.
The cosine transforms of scipy.fft.dct, unscaled, on one line of n points by a Fourier transform: typ...
std::vector< R > signs
Its factor, ±√2.
std::vector< std::complex< R > > turns
Type 4 of an even n.
std::vector< std::complex< R > > roots
See above.
std::vector< std::size_t > picks
Type 4 of an odd n: the frequency each value is.
std::shared_ptr< const fft_plan< R > > complex
Type 4.
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...
std::shared_ptr< const real_fft_plan< R > > real
Types 1 to 3.
A double-double number: hi + lo, hi the sum rounded to double.
double lo
The trailing part, at most half a unit in the last place of hi.
double hi
The leading part.
The complex type a transform of T computes in: T itself, or a real type's complex.
std::complex< T > type
A real float or double's.
The result of a transform along one axis, allocated before its plan, whose tables grow with the point...
static std::size_t counted(const std::vector< std::size_t > &extents)
The elements of extents.
tensor< Out > take() &&
The result as a tensor.
fft_output(std::vector< std::size_t > input_shape, std::size_t index, std::size_t out_points)
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.
buffer< Out > out
Its elements, uninitialized.
std::vector< std::size_t > shape
The input's shape, the axis out_points long.
The factors and passes of a transform of one length, built once and shared.
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...
std::size_t length
The transform's length.
std::array< std::complex< R >, 16 > sixteenths
e^{−2πi k/16}: a radix-16 butterfly's own factors.
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.
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.
std::size_t work
The working space a transform takes beside its data.
std::optional< bluestein_plan< R > > bluestein
Where the length has a prime factor past fft_largest_radix.
std::vector< std::size_t > radices
Each Stockham pass' radix (fft_radices).
small_radix_constants< R > small
The radix-3 and radix-5 butterflies' constants.
The elements a transform reads where they lie, row-major, of shape shape: a tensor's,...
const T * data
The first element.
std::vector< std::size_t > shape
The extent of each axis.
A transform of n = n1·n2 points in four steps (Bailey's), each a batch of lines the threads share: x ...
std::shared_ptr< const fft_plan< R > > row_plan
The plan of n1 points.
std::vector< std::complex< R > > twiddles
w^{j1·k2}, e^{−2πi j1·k2/n}, at k2·n1 + j1.
std::shared_ptr< const fft_plan< R > > column_plan
The plan of n2 points.
std::size_t columns
n1: the columns, the points of each row.
std::size_t rows
n2: the rows, the points of each column.
e^{−2πi k/n}'s angle reduced to an eighth of a turn by integer arithmetic, 8k = octant·n + rest: the ...
std::size_t share
The angle within it, in units of π/(4n).
std::size_t octant
The eighth of a turn the angle falls in.
What a transform of n real points (or to them) takes: the complex plan of n/2 points for an even n,...
std::shared_ptr< const fft_plan< R > > complex
The complex plan: n/2 points (even n), n (odd).
std::vector< std::complex< R > > roots
e^{−2πi k/n}, k from 0 to n/2 (even n).
The real constants of the radix-3, -5 and -8 butterflies, rounded once from their double-double value...
R half_root_three
√3/2 = sin(2π/3).
R half_root_two
√½ = cos(π/4).
A dense, row-major, N-dimensional tensor and Einstein summation.
Element-wise arithmetic with NumPy's broadcasting, reductions, reshaping and creation of tensors.