GCC Code Coverage Report

Directory: src/
Coverage: low: ≥ 0% medium: ≥ 75.0% high: ≥ 90.0%
Coverage Exec / Excl / Total
Lines: 100.0% 219 / 0 / 219
Functions: 100.0% 36 / 0 / 36
Branches: 84.6% 214 / 144 / 397
fft/engines/ntt.hpp
Line Branch Exec Source
1 #pragma once
2
3 #include <algorithm>
4 #include <cassert>
5 #include <span>
6 #include <utility>
7 #include <vector>
8
9 #include "fft/core.hpp"
10 #include "fft/engine.hpp"
11
12 namespace ecnerwala::fft::engines {
13
14 template <typename num> struct ntt {
15 using value_type = num;
16 static constexpr bool commutative = true;
17 using core = fft_core<num>;
18
21/28
✓ Branch 8 → 9 taken 1325993 times.
✗ Branch 8 → 20 not taken.
✓ Branch 9 → 10 taken 48 times.
✗ Branch 9 → 14 not taken.
✓ Branch 12 → 13 taken 1647972 times.
✓ Branch 12 → 14 taken 322072 times.
✓ Branch 15 → 16 taken 20 times.
✓ Branch 20 → 21 taken 644051 times.
✗ Branch 38 → 39 not taken.
✓ Branch 38 → 40 taken 628 times.
✓ Branch 40 → 41 taken 628 times.
✗ Branch 49 → 50 not taken.
✓ Branch 49 → 51 taken 608 times.
✓ Branch 51 → 52 taken 608 times.
✓ Branch 64 → 65 taken 6 times.
✓ Branch 70 → 71 taken 173 times.
✓ Branch 84 → 85 taken 6 times.
✗ Branch 89 → 90 not taken.
✓ Branch 90 → 91 taken 65 times.
✓ Branch 96 → 97 taken 40 times.
✗ Branch 116 → 117 not taken.
✗ Branch 123 → 124 not taken.
✓ Branch 245 → 246 taken 160 times.
✓ Branch 253 → 254 taken 160 times.
✓ Branch 327 → 328 taken 64 times.
✓ Branch 329 → 330 taken 64 times.
✓ Branch 335 → 336 taken 64 times.
✓ Branch 337 → 338 taken 64 times.
 43564082 struct transformed {
19 vector<num> v;
20
3/6
✗ Branch 2 → 3 not taken.
✓ Branch 2 → 4 taken 96 times.
✗ Branch 38 → 39 not taken.
✓ Branch 38 → 40 taken 628 times.
✗ Branch 49 → 50 not taken.
✓ Branch 49 → 51 taken 608 times.
 23461933 int size() const { return sz(v); }
21 };
22 using product = transformed;
23 static constexpr int unit_scale = 0;
24 template <int A = 0> using transformed_t = transformed;
25 template <int K = 0> using product_t = product;
26
27 2656936 static transformed transform(std::span<const num> a, int n) {
28 2656936 assert(sz(a) <= 2 * n);
29 2656936 transformed r;
30
6/6
ecnerwala::fft::engines::ntt<mod_goldilocks>::transform(std::span<mod_goldilocks const, 18446744073709551615ul>, int):
✓ Branch 4 → 5 taken 96 times.
✓ Branch 16 → 17 taken 4141 times.
ecnerwala::fft::engines::ntt<modnum<2013265921> >::transform(std::span<modnum<2013265921> const, 18446744073709551615ul>, int):
✓ Branch 4 → 5 taken 96 times.
✓ Branch 16 → 17 taken 2827 times.
ecnerwala::fft::engines::ntt<modnum<998244353> >::transform(std::span<modnum<998244353> const, 18446744073709551615ul>, int):
✓ Branch 4 → 5 taken 2644709 times.
✓ Branch 16 → 17 taken 5067 times.
 2668971 r.v.assign(n, num(0));
31 2656936 int lo = min(sz(a), n);
32
3/3
ecnerwala::fft::engines::ntt<mod_goldilocks>::transform(std::span<mod_goldilocks const, 18446744073709551615ul>, int):
✓ Branch 42 → 43 taken 4141 times.
ecnerwala::fft::engines::ntt<modnum<2013265921> >::transform(std::span<modnum<2013265921> const, 18446744073709551615ul>, int):
✓ Branch 42 → 43 taken 2827 times.
ecnerwala::fft::engines::ntt<modnum<998244353> >::transform(std::span<modnum<998244353> const, 18446744073709551615ul>, int):
✓ Branch 42 → 43 taken 5067 times.
 2693041 std::copy(a.begin(), a.begin() + lo, r.v.begin());
33
12/12
ecnerwala::fft::engines::ntt<mod_goldilocks>::transform(std::span<mod_goldilocks const, 18446744073709551615ul>, int):
✓ Branch 8 → 7 taken 4 times.
✓ Branch 8 → 9 taken 96 times.
✓ Branch 74 → 65 taken 170 times.
✓ Branch 74 → 75 taken 4141 times.
ecnerwala::fft::engines::ntt<modnum<2013265921> >::transform(std::span<modnum<2013265921> const, 18446744073709551615ul>, int):
✓ Branch 9 → 7 taken 4 times.
✓ Branch 9 → 10 taken 96 times.
✓ Branch 74 → 65 taken 139 times.
✓ Branch 74 → 75 taken 2827 times.
ecnerwala::fft::engines::ntt<modnum<998244353> >::transform(std::span<modnum<998244353> const, 18446744073709551615ul>, int):
✓ Branch 9 → 7 taken 14 times.
✓ Branch 9 → 10 taken 2644709 times.
✓ Branch 74 → 65 taken 197 times.
✓ Branch 74 → 75 taken 5067 times.
 2657464 for (int i = n; i < sz(a); i++) r.v[i - n] += a[i];
34
9/12
ecnerwala::fft::engines::ntt<mod_goldilocks>::transform(std::span<mod_goldilocks const, 18446744073709551615ul>, int):
✗ Branch 9 → 10 not taken.
✓ Branch 9 → 11 taken 96 times.
✓ Branch 11 → 12 taken 96 times.
✓ Branch 78 → 79 taken 4141 times.
ecnerwala::fft::engines::ntt<modnum<2013265921> >::transform(std::span<modnum<2013265921> const, 18446744073709551615ul>, int):
✗ Branch 10 → 11 not taken.
✓ Branch 10 → 12 taken 96 times.
✓ Branch 12 → 13 taken 96 times.
✓ Branch 78 → 79 taken 2827 times.
ecnerwala::fft::engines::ntt<modnum<998244353> >::transform(std::span<modnum<998244353> const, 18446744073709551615ul>, int):
✗ Branch 10 → 11 not taken.
✓ Branch 10 → 12 taken 2644709 times.
✓ Branch 12 → 13 taken 2644709 times.
✓ Branch 78 → 79 taken 5067 times.
 2656936 core::forward(std::span<num>(r.v));
35 2656936 return r;
36 }
37 7896509 static void extend_to(transformed& t, int m, std::span<const num> coeffs) {
38 7896509 assert(!(m & (m-1)) && sz(coeffs) <= 2 * m);
39
9/12
ecnerwala::fft::engines::ntt<mod_goldilocks>::extend_to(ecnerwala::fft::engines::ntt<mod_goldilocks>::transformed&, int, std::span<mod_goldilocks const, 18446744073709551615ul>):
✓ Branch 5 → 6 taken 96 times.
✗ Branch 5 → 17 not taken.
✓ Branch 11 → 12 taken 3356 times.
✓ Branch 11 → 77 taken 1000 times.
ecnerwala::fft::engines::ntt<modnum<2013265921> >::extend_to(ecnerwala::fft::engines::ntt<modnum<2013265921> >::transformed&, int, std::span<modnum<2013265921> const, 18446744073709551615ul>):
✓ Branch 5 → 6 taken 96 times.
✗ Branch 5 → 17 not taken.
✓ Branch 11 → 12 taken 1939 times.
✗ Branch 11 → 77 not taken.
ecnerwala::fft::engines::ntt<modnum<998244353> >::extend_to(ecnerwala::fft::engines::ntt<modnum<998244353> >::transformed&, int, std::span<modnum<998244353> const, 18446744073709551615ul>):
✓ Branch 5 → 6 taken 4606885 times.
✓ Branch 5 → 17 taken 3277021 times.
✓ Branch 11 → 12 taken 3814 times.
✓ Branch 11 → 77 taken 2302 times.
 7908920 if (t.size() >= m) return;
40
13/15
ecnerwala::fft::engines::ntt<mod_goldilocks>::extend_to(ecnerwala::fft::engines::ntt<mod_goldilocks>::transformed&, int, std::span<mod_goldilocks const, 18446744073709551615ul>):
✓ Branch 6 → 7 taken 96 times.
✗ Branch 6 → 16 not taken.
✓ Branch 17 → 18 taken 3084 times.
✓ Branch 17 → 71 taken 272 times.
✓ Branch 19 → 20 taken 3084 times.
ecnerwala::fft::engines::ntt<modnum<2013265921> >::extend_to(ecnerwala::fft::engines::ntt<modnum<2013265921> >::transformed&, int, std::span<modnum<2013265921> const, 18446744073709551615ul>):
✓ Branch 6 → 7 taken 96 times.
✗ Branch 6 → 16 not taken.
✓ Branch 17 → 18 taken 1932 times.
✓ Branch 17 → 71 taken 7 times.
✓ Branch 19 → 20 taken 1932 times.
ecnerwala::fft::engines::ntt<modnum<998244353> >::extend_to(ecnerwala::fft::engines::ntt<modnum<998244353> >::transformed&, int, std::span<modnum<998244353> const, 18446744073709551615ul>):
✓ Branch 6 → 7 taken 2635703 times.
✓ Branch 6 → 16 taken 1971182 times.
✓ Branch 17 → 18 taken 3365 times.
✓ Branch 17 → 71 taken 449 times.
✓ Branch 19 → 20 taken 3365 times.
 7277952 if (t.size() == 0) { t = transform(coeffs, m); return; }
41
8/12
ecnerwala::fft::engines::ntt<mod_goldilocks>::extend_to(ecnerwala::fft::engines::ntt<mod_goldilocks>::transformed&, int, std::span<mod_goldilocks const, 18446744073709551615ul>):
✗ Branch 16 → 11 not taken.
✗ Branch 16 → 17 not taken.
✓ Branch 76 → 46 taken 280 times.
✓ Branch 76 → 77 taken 272 times.
ecnerwala::fft::engines::ntt<modnum<2013265921> >::extend_to(ecnerwala::fft::engines::ntt<modnum<2013265921> >::transformed&, int, std::span<modnum<2013265921> const, 18446744073709551615ul>):
✗ Branch 16 → 11 not taken.
✗ Branch 16 → 17 not taken.
✓ Branch 76 → 46 taken 10 times.
✓ Branch 76 → 77 taken 7 times.
ecnerwala::fft::engines::ntt<modnum<998244353> >::extend_to(ecnerwala::fft::engines::ntt<modnum<998244353> >::transformed&, int, std::span<modnum<998244353> const, 18446744073709551615ul>):
✓ Branch 16 → 11 taken 2293280 times.
✓ Branch 16 → 17 taken 1971182 times.
✓ Branch 76 → 46 taken 497 times.
✓ Branch 76 → 77 taken 449 times.
 4267492 while (t.size() < m) {
42 2294067 int s = t.size();
43 2294067 t.v.resize(2 * s);
44 // coeffs past 2s are zero: they didn't fit in the transform we're a prefix of
45
4/9
ecnerwala::fft::engines::ntt<mod_goldilocks>::extend_to(ecnerwala::fft::engines::ntt<mod_goldilocks>::transformed&, int, std::span<mod_goldilocks const, 18446744073709551615ul>):
✗ Branch 12 → 13 not taken.
✗ Branch 12 → 14 not taken.
✓ Branch 67 → 68 taken 280 times.
ecnerwala::fft::engines::ntt<modnum<2013265921> >::extend_to(ecnerwala::fft::engines::ntt<modnum<2013265921> >::transformed&, int, std::span<modnum<2013265921> const, 18446744073709551615ul>):
✗ Branch 12 → 13 not taken.
✗ Branch 12 → 14 not taken.
✓ Branch 67 → 68 taken 10 times.
ecnerwala::fft::engines::ntt<modnum<998244353> >::extend_to(ecnerwala::fft::engines::ntt<modnum<998244353> >::transformed&, int, std::span<modnum<998244353> const, 18446744073709551615ul>):
✗ Branch 12 → 13 not taken.
✓ Branch 12 → 14 taken 2293280 times.
✓ Branch 67 → 68 taken 497 times.
 2294067 core::extend(std::span<num>(t.v), coeffs.first(size_t(min(sz(coeffs), 2 * s))));
46 }
47 }
48 3019 static transformed downsample(const transformed& t, int n, bool odd) {
49
4/4
ecnerwala::fft::engines::ntt<mod_goldilocks>::downsample(ecnerwala::fft::engines::ntt<mod_goldilocks>::transformed const&, int, bool):
✓ Branch 8 → 9 taken 588 times.
ecnerwala::fft::engines::ntt<modnum<2013265921> >::downsample(ecnerwala::fft::engines::ntt<modnum<2013265921> >::transformed const&, int, bool):
✓ Branch 8 → 9 taken 294 times.
ecnerwala::fft::engines::ntt<modnum<998244353> >::downsample(ecnerwala::fft::engines::ntt<modnum<998244353> >::transformed const&, int, bool):
✓ Branch 2 → 3 taken 1826 times.
✓ Branch 8 → 9 taken 311 times.
 3019 transformed r; r.v.resize(n);
50
14/16
ecnerwala::fft::engines::ntt<mod_goldilocks>::downsample(ecnerwala::fft::engines::ntt<mod_goldilocks>::transformed const&, int, bool):
✓ Branch 9 → 10 taken 198 times.
✓ Branch 9 → 21 taken 390 times.
✓ Branch 18 → 19 taken 198 times.
ecnerwala::fft::engines::ntt<modnum<2013265921> >::downsample(ecnerwala::fft::engines::ntt<modnum<2013265921> >::transformed const&, int, bool):
✓ Branch 9 → 10 taken 99 times.
✓ Branch 9 → 21 taken 195 times.
✓ Branch 18 → 19 taken 99 times.
ecnerwala::fft::engines::ntt<modnum<998244353> >::downsample(ecnerwala::fft::engines::ntt<modnum<998244353> >::transformed const&, int, bool):
✓ Branch 3 → 4 taken 306 times.
✓ Branch 3 → 10 taken 1520 times.
✗ Branch 4 → 5 not taken.
✓ Branch 4 → 6 taken 306 times.
✗ Branch 6 → 7 not taken.
✓ Branch 6 → 8 taken 306 times.
✓ Branch 8 → 9 taken 306 times.
✓ Branch 9 → 10 taken 99 times.
✓ Branch 9 → 21 taken 212 times.
✓ Branch 18 → 19 taken 99 times.
 3019 if (odd) core::odd_half(std::span<const num>(t.v), std::span<num>(r.v));
51
2/4
✗ Branch 10 → 11 not taken.
✓ Branch 10 → 12 taken 1520 times.
✗ Branch 12 → 13 not taken.
✓ Branch 12 → 14 taken 1520 times.
 2317 else core::even_half(std::span<const num>(t.v), std::span<num>(r.v));
52 3019 return r;
53 }
54 1891 static transformed negate_arg(const transformed& t, int n) {
55 2564 assert(n >= 2 && t.size() >= n);
56
4/4
ecnerwala::fft::engines::ntt<mod_goldilocks>::negate_arg(ecnerwala::fft::engines::ntt<mod_goldilocks>::transformed const&, int):
✓ Branch 16 → 29 taken 328 times.
ecnerwala::fft::engines::ntt<modnum<2013265921> >::negate_arg(ecnerwala::fft::engines::ntt<modnum<2013265921> >::transformed const&, int):
✓ Branch 16 → 29 taken 164 times.
ecnerwala::fft::engines::ntt<modnum<998244353> >::negate_arg(ecnerwala::fft::engines::ntt<modnum<998244353> >::transformed const&, int):
✓ Branch 5 → 7 taken 1218 times.
✓ Branch 16 → 29 taken 181 times.
 1891 transformed r; r.v.resize(n);
57
8/8
ecnerwala::fft::engines::ntt<mod_goldilocks>::negate_arg(ecnerwala::fft::engines::ntt<mod_goldilocks>::transformed const&, int):
✓ Branch 29 → 17 taken 7052 times.
✓ Branch 29 → 30 taken 328 times.
ecnerwala::fft::engines::ntt<modnum<2013265921> >::negate_arg(ecnerwala::fft::engines::ntt<modnum<2013265921> >::transformed const&, int):
✓ Branch 29 → 17 taken 3526 times.
✓ Branch 29 → 30 taken 164 times.
ecnerwala::fft::engines::ntt<modnum<998244353> >::negate_arg(ecnerwala::fft::engines::ntt<modnum<998244353> >::transformed const&, int):
✓ Branch 7 → 6 taken 239557132 times.
✓ Branch 7 → 8 taken 1218 times.
✓ Branch 29 → 17 taken 5838 times.
✓ Branch 29 → 30 taken 181 times.
 239575439 for (int j = 0; j < n; j++) r.v[j] = t.v[j ^ 1];
58 1891 return r;
59 }
60 2668465 static product mul(const transformed& a, const transformed& b, int n) {
61 2683915 assert(a.size() >= n && b.size() >= n);
62
6/6
ecnerwala::fft::engines::ntt<mod_goldilocks>::mul(ecnerwala::fft::engines::ntt<mod_goldilocks>::transformed const&, ecnerwala::fft::engines::ntt<mod_goldilocks>::transformed const&, int):
✓ Branch 5 → 7 taken 48 times.
✓ Branch 21 → 42 taken 2574 times.
ecnerwala::fft::engines::ntt<modnum<2013265921> >::mul(ecnerwala::fft::engines::ntt<modnum<2013265921> >::transformed const&, ecnerwala::fft::engines::ntt<modnum<2013265921> >::transformed const&, int):
✓ Branch 5 → 7 taken 48 times.
✓ Branch 21 → 42 taken 1812 times.
ecnerwala::fft::engines::ntt<modnum<998244353> >::mul(ecnerwala::fft::engines::ntt<modnum<998244353> >::transformed const&, ecnerwala::fft::engines::ntt<modnum<998244353> >::transformed const&, int):
✓ Branch 5 → 7 taken 2660644 times.
✓ Branch 21 → 42 taken 3339 times.
 2668465 product p; p.v.resize(n);
63
12/12
ecnerwala::fft::engines::ntt<mod_goldilocks>::mul(ecnerwala::fft::engines::ntt<mod_goldilocks>::transformed const&, ecnerwala::fft::engines::ntt<mod_goldilocks>::transformed const&, int):
✓ Branch 7 → 6 taken 24699142 times.
✓ Branch 7 → 8 taken 48 times.
✓ Branch 42 → 22 taken 57399 times.
✓ Branch 42 → 43 taken 2574 times.
ecnerwala::fft::engines::ntt<modnum<2013265921> >::mul(ecnerwala::fft::engines::ntt<modnum<2013265921> >::transformed const&, ecnerwala::fft::engines::ntt<modnum<2013265921> >::transformed const&, int):
✓ Branch 7 → 6 taken 24699142 times.
✓ Branch 7 → 8 taken 48 times.
✓ Branch 42 → 22 taken 41418 times.
✓ Branch 42 → 43 taken 1812 times.
ecnerwala::fft::engines::ntt<modnum<998244353> >::mul(ecnerwala::fft::engines::ntt<modnum<998244353> >::transformed const&, ecnerwala::fft::engines::ntt<modnum<998244353> >::transformed const&, int):
✓ Branch 7 → 6 taken 802879241 times.
✓ Branch 7 → 8 taken 2660644 times.
✓ Branch 42 → 22 taken 82494 times.
✓ Branch 42 → 43 taken 3339 times.
 855127301 for (int i = 0; i < n; i++) p.v[i] = a.v[i] * b.v[i];
64 2668465 return p;
65 }
66
1/1
✓ Branch 5 → 6 taken 537 times.
 657 static product sq(const transformed& a, int n) { return mul(a, a, n); }
67 651482 static product mul2(
68 const transformed& a1, const transformed& b1,
69 const transformed& a2, const transformed& b2,
70 int n
71 ) {
72 681206 assert(a1.size() >= n && b1.size() >= n && a2.size() >= n && b2.size() >= n);
73
4/4
ecnerwala::fft::engines::ntt<mod_goldilocks>::mul2(ecnerwala::fft::engines::ntt<mod_goldilocks>::transformed const&, ecnerwala::fft::engines::ntt<mod_goldilocks>::transformed const&, ecnerwala::fft::engines::ntt<mod_goldilocks>::transformed const&, ecnerwala::fft::engines::ntt<mod_goldilocks>::transformed const&, int):
✓ Branch 33 → 72 taken 2091 times.
ecnerwala::fft::engines::ntt<modnum<2013265921> >::mul2(ecnerwala::fft::engines::ntt<modnum<2013265921> >::transformed const&, ecnerwala::fft::engines::ntt<modnum<2013265921> >::transformed const&, ecnerwala::fft::engines::ntt<modnum<2013265921> >::transformed const&, ecnerwala::fft::engines::ntt<modnum<2013265921> >::transformed const&, int):
✓ Branch 33 → 72 taken 1761 times.
ecnerwala::fft::engines::ntt<modnum<998244353> >::mul2(ecnerwala::fft::engines::ntt<modnum<998244353> >::transformed const&, ecnerwala::fft::engines::ntt<modnum<998244353> >::transformed const&, ecnerwala::fft::engines::ntt<modnum<998244353> >::transformed const&, ecnerwala::fft::engines::ntt<modnum<998244353> >::transformed const&, int):
✓ Branch 7 → 12 taken 644051 times.
✓ Branch 33 → 72 taken 3579 times.
 651482 product p; p.v.resize(n);
74
10/10
ecnerwala::fft::engines::ntt<mod_goldilocks>::mul2(ecnerwala::fft::engines::ntt<mod_goldilocks>::transformed const&, ecnerwala::fft::engines::ntt<mod_goldilocks>::transformed const&, ecnerwala::fft::engines::ntt<mod_goldilocks>::transformed const&, ecnerwala::fft::engines::ntt<mod_goldilocks>::transformed const&, int):
✓ Branch 72 → 34 taken 6703 times.
✓ Branch 72 → 73 taken 2091 times.
ecnerwala::fft::engines::ntt<modnum<2013265921> >::mul2(ecnerwala::fft::engines::ntt<modnum<2013265921> >::transformed const&, ecnerwala::fft::engines::ntt<modnum<2013265921> >::transformed const&, ecnerwala::fft::engines::ntt<modnum<2013265921> >::transformed const&, ecnerwala::fft::engines::ntt<modnum<2013265921> >::transformed const&, int):
✓ Branch 72 → 34 taken 5228 times.
✓ Branch 72 → 73 taken 1761 times.
ecnerwala::fft::engines::ntt<modnum<998244353> >::mul2(ecnerwala::fft::engines::ntt<modnum<998244353> >::transformed const&, ecnerwala::fft::engines::ntt<modnum<998244353> >::transformed const&, ecnerwala::fft::engines::ntt<modnum<998244353> >::transformed const&, ecnerwala::fft::engines::ntt<modnum<998244353> >::transformed const&, int):
✓ Branch 8 → 9 taken 5332038 times.
✓ Branch 8 → 10 taken 5332656 times.
✓ Branch 12 → 8 taken 10664694 times.
✓ Branch 12 → 13 taken 644051 times.
✓ Branch 72 → 34 taken 10459 times.
✓ Branch 72 → 73 taken 3579 times.
 11338566 for (int i = 0; i < n; i++) p.v[i] = a1.v[i] * b1.v[i] + a2.v[i] * b2.v[i];
75 651482 return p;
76 }
77 1702 static product add(product&& a, const product& b) {
78 5106 assert(a.size() == b.size());
79
6/6
ecnerwala::fft::engines::ntt<mod_goldilocks>::add(ecnerwala::fft::engines::ntt<mod_goldilocks>::transformed&&, ecnerwala::fft::engines::ntt<mod_goldilocks>::transformed const&):
✓ Branch 32 → 15 taken 2875 times.
✓ Branch 32 → 33 taken 110 times.
ecnerwala::fft::engines::ntt<modnum<2013265921> >::add(ecnerwala::fft::engines::ntt<modnum<2013265921> >::transformed&&, ecnerwala::fft::engines::ntt<modnum<2013265921> >::transformed const&):
✓ Branch 32 → 15 taken 2793 times.
✓ Branch 32 → 33 taken 107 times.
ecnerwala::fft::engines::ntt<modnum<998244353> >::add(ecnerwala::fft::engines::ntt<modnum<998244353> >::transformed&&, ecnerwala::fft::engines::ntt<modnum<998244353> >::transformed const&):
✓ Branch 32 → 15 taken 15109 times.
✓ Branch 32 → 33 taken 1485 times.
 24181 for (int i = 0; i < a.size(); i++) a.v[i] += b.v[i];
80 1702 return std::move(a);
81 }
82 3318281 template <typename Op = assign_op> static void finish(product&& p, std::span<num> out, Op op = {}) {
83 3318281 int n = p.size();
84 3318281 assert(sz(out) <= n);
85
21/29
void ecnerwala::fft::engines::ntt<mod_goldilocks>::finish<ecnerwala::fft::add_twice_op>(ecnerwala::fft::engines::ntt<mod_goldilocks>::transformed&&, std::span<mod_goldilocks, 18446744073709551615ul>, ecnerwala::fft::add_twice_op):
✓ Branch 14 → 15 taken 238 times.
void ecnerwala::fft::engines::ntt<mod_goldilocks>::finish<ecnerwala::fft::add_op>(ecnerwala::fft::engines::ntt<mod_goldilocks>::transformed&&, std::span<mod_goldilocks, 18446744073709551615ul>, ecnerwala::fft::add_op):
✓ Branch 14 → 15 taken 268 times.
void ecnerwala::fft::engines::ntt<mod_goldilocks>::finish<ecnerwala::fft::detail::cut_op<mod_goldilocks, ecnerwala::fft::add_twice_op> >(ecnerwala::fft::engines::ntt<mod_goldilocks>::transformed&&, std::span<mod_goldilocks, 18446744073709551615ul>, ecnerwala::fft::detail::cut_op<mod_goldilocks, ecnerwala::fft::add_twice_op>):
✓ Branch 14 → 15 taken 84 times.
void ecnerwala::fft::engines::ntt<mod_goldilocks>::finish<ecnerwala::fft::detail::cut_op<mod_goldilocks, ecnerwala::fft::add_op> >(ecnerwala::fft::engines::ntt<mod_goldilocks>::transformed&&, std::span<mod_goldilocks, 18446744073709551615ul>, ecnerwala::fft::detail::cut_op<mod_goldilocks, ecnerwala::fft::add_op>):
✓ Branch 14 → 15 taken 90 times.
void ecnerwala::fft::engines::ntt<mod_goldilocks>::finish<ecnerwala::fft::detail::cut_op<mod_goldilocks, ecnerwala::fft::assign_op> >(ecnerwala::fft::engines::ntt<mod_goldilocks>::transformed&&, std::span<mod_goldilocks, 18446744073709551615ul>, ecnerwala::fft::detail::cut_op<mod_goldilocks, ecnerwala::fft::assign_op>):
✓ Branch 14 → 15 taken 17 times.
void ecnerwala::fft::engines::ntt<mod_goldilocks>::finish<ecnerwala::fft::assign_op>(ecnerwala::fft::engines::ntt<mod_goldilocks>::transformed&&, std::span<mod_goldilocks, 18446744073709551615ul>, ecnerwala::fft::assign_op):
✗ Branch 4 → 5 not taken.
✓ Branch 4 → 6 taken 48 times.
✗ Branch 7 → 8 not taken.
✓ Branch 7 → 9 taken 48 times.
✓ Branch 14 → 15 taken 3876 times.
void ecnerwala::fft::engines::ntt<modnum<2013265921> >::finish<ecnerwala::fft::assign_op>(ecnerwala::fft::engines::ntt<modnum<2013265921> >::transformed&&, std::span<modnum<2013265921>, 18446744073709551615ul>, ecnerwala::fft::assign_op):
✗ Branch 4 → 5 not taken.
✓ Branch 4 → 6 taken 48 times.
✗ Branch 7 → 8 not taken.
✓ Branch 7 → 9 taken 48 times.
✓ Branch 14 → 15 taken 3475 times.
void ecnerwala::fft::engines::ntt<modnum<998244353> >::finish<ecnerwala::fft::add_twice_op>(ecnerwala::fft::engines::ntt<modnum<998244353> >::transformed&&, std::span<modnum<998244353>, 18446744073709551615ul>, ecnerwala::fft::add_twice_op):
✓ Branch 14 → 15 taken 238 times.
void ecnerwala::fft::engines::ntt<modnum<998244353> >::finish<ecnerwala::fft::add_op>(ecnerwala::fft::engines::ntt<modnum<998244353> >::transformed&&, std::span<modnum<998244353>, 18446744073709551615ul>, ecnerwala::fft::add_op):
✓ Branch 14 → 15 taken 2003 times.
void ecnerwala::fft::engines::ntt<modnum<998244353> >::finish<ecnerwala::fft::detail::cut_op<modnum<998244353>, ecnerwala::fft::add_twice_op> >(ecnerwala::fft::engines::ntt<modnum<998244353> >::transformed&&, std::span<modnum<998244353>, 18446744073709551615ul>, ecnerwala::fft::detail::cut_op<modnum<998244353>, ecnerwala::fft::add_twice_op>):
✓ Branch 14 → 15 taken 84 times.
void ecnerwala::fft::engines::ntt<modnum<998244353> >::finish<ecnerwala::fft::detail::cut_op<modnum<998244353>, ecnerwala::fft::add_op> >(ecnerwala::fft::engines::ntt<modnum<998244353> >::transformed&&, std::span<modnum<998244353>, 18446744073709551615ul>, ecnerwala::fft::detail::cut_op<modnum<998244353>, ecnerwala::fft::add_op>):
✓ Branch 14 → 15 taken 177 times.
void ecnerwala::fft::engines::ntt<modnum<998244353> >::finish<ecnerwala::fft::detail::cut_op<modnum<998244353>, ecnerwala::fft::assign_op> >(ecnerwala::fft::engines::ntt<modnum<998244353> >::transformed&&, std::span<modnum<998244353>, 18446744073709551615ul>, ecnerwala::fft::detail::cut_op<modnum<998244353>, ecnerwala::fft::assign_op>):
✗ Branch 4 → 5 not taken.
✓ Branch 4 → 6 taken 1647987 times.
✗ Branch 7 → 8 not taken.
✓ Branch 7 → 9 taken 1647987 times.
✓ Branch 14 → 15 taken 260 times.
void ecnerwala::fft::engines::ntt<modnum<998244353> >::finish<ecnerwala::fft::assign_op>(ecnerwala::fft::engines::ntt<modnum<998244353> >::transformed&&, std::span<modnum<998244353>, 18446744073709551615ul>, ecnerwala::fft::assign_op):
✗ Branch 4 → 5 not taken.
✓ Branch 4 → 6 taken 1656708 times.
✗ Branch 7 → 8 not taken.
✓ Branch 7 → 9 taken 1656708 times.
✓ Branch 14 → 15 taken 2680 times.
 3318281 core::inverse(std::span<num>(p.v));
86 3331771 num d = inv(num(n));
87
34/34
void ecnerwala::fft::engines::ntt<mod_goldilocks>::finish<ecnerwala::fft::add_twice_op>(ecnerwala::fft::engines::ntt<mod_goldilocks>::transformed&&, std::span<mod_goldilocks, 18446744073709551615ul>, ecnerwala::fft::add_twice_op):
✓ Branch 38 → 28 taken 938 times.
✓ Branch 38 → 39 taken 238 times.
void ecnerwala::fft::engines::ntt<mod_goldilocks>::finish<ecnerwala::fft::add_op>(ecnerwala::fft::engines::ntt<mod_goldilocks>::transformed&&, std::span<mod_goldilocks, 18446744073709551615ul>, ecnerwala::fft::add_op):
✓ Branch 40 → 28 taken 1456 times.
✓ Branch 40 → 41 taken 268 times.
void ecnerwala::fft::engines::ntt<mod_goldilocks>::finish<ecnerwala::fft::detail::cut_op<mod_goldilocks, ecnerwala::fft::add_twice_op> >(ecnerwala::fft::engines::ntt<mod_goldilocks>::transformed&&, std::span<mod_goldilocks, 18446744073709551615ul>, ecnerwala::fft::detail::cut_op<mod_goldilocks, ecnerwala::fft::add_twice_op>):
✓ Branch 38 → 28 taken 168 times.
✓ Branch 38 → 39 taken 84 times.
void ecnerwala::fft::engines::ntt<mod_goldilocks>::finish<ecnerwala::fft::detail::cut_op<mod_goldilocks, ecnerwala::fft::add_op> >(ecnerwala::fft::engines::ntt<mod_goldilocks>::transformed&&, std::span<mod_goldilocks, 18446744073709551615ul>, ecnerwala::fft::detail::cut_op<mod_goldilocks, ecnerwala::fft::add_op>):
✓ Branch 38 → 28 taken 180 times.
✓ Branch 38 → 39 taken 90 times.
void ecnerwala::fft::engines::ntt<mod_goldilocks>::finish<ecnerwala::fft::detail::cut_op<mod_goldilocks, ecnerwala::fft::assign_op> >(ecnerwala::fft::engines::ntt<mod_goldilocks>::transformed&&, std::span<mod_goldilocks, 18446744073709551615ul>, ecnerwala::fft::detail::cut_op<mod_goldilocks, ecnerwala::fft::assign_op>):
✓ Branch 38 → 28 taken 250 times.
✓ Branch 38 → 39 taken 17 times.
void ecnerwala::fft::engines::ntt<mod_goldilocks>::finish<ecnerwala::fft::assign_op>(ecnerwala::fft::engines::ntt<mod_goldilocks>::transformed&&, std::span<mod_goldilocks, 18446744073709551615ul>, ecnerwala::fft::assign_op):
✓ Branch 13 → 12 taken 22077513 times.
✓ Branch 13 → 14 taken 48 times.
✓ Branch 39 → 28 taken 48514 times.
✓ Branch 39 → 40 taken 3876 times.
void ecnerwala::fft::engines::ntt<modnum<2013265921> >::finish<ecnerwala::fft::assign_op>(ecnerwala::fft::engines::ntt<modnum<2013265921> >::transformed&&, std::span<modnum<2013265921>, 18446744073709551615ul>, ecnerwala::fft::assign_op):
✓ Branch 13 → 12 taken 22077513 times.
✓ Branch 13 → 14 taken 48 times.
✓ Branch 39 → 28 taken 38844 times.
✓ Branch 39 → 40 taken 3475 times.
void ecnerwala::fft::engines::ntt<modnum<998244353> >::finish<ecnerwala::fft::add_twice_op>(ecnerwala::fft::engines::ntt<modnum<998244353> >::transformed&&, std::span<modnum<998244353>, 18446744073709551615ul>, ecnerwala::fft::add_twice_op):
✓ Branch 38 → 28 taken 938 times.
✓ Branch 38 → 39 taken 238 times.
void ecnerwala::fft::engines::ntt<modnum<998244353> >::finish<ecnerwala::fft::add_op>(ecnerwala::fft::engines::ntt<modnum<998244353> >::transformed&&, std::span<modnum<998244353>, 18446744073709551615ul>, ecnerwala::fft::add_op):
✓ Branch 40 → 28 taken 17482 times.
✓ Branch 40 → 41 taken 2003 times.
void ecnerwala::fft::engines::ntt<modnum<998244353> >::finish<ecnerwala::fft::detail::cut_op<modnum<998244353>, ecnerwala::fft::add_twice_op> >(ecnerwala::fft::engines::ntt<modnum<998244353> >::transformed&&, std::span<modnum<998244353>, 18446744073709551615ul>, ecnerwala::fft::detail::cut_op<modnum<998244353>, ecnerwala::fft::add_twice_op>):
✓ Branch 38 → 28 taken 168 times.
✓ Branch 38 → 39 taken 84 times.
void ecnerwala::fft::engines::ntt<modnum<998244353> >::finish<ecnerwala::fft::detail::cut_op<modnum<998244353>, ecnerwala::fft::add_op> >(ecnerwala::fft::engines::ntt<modnum<998244353> >::transformed&&, std::span<modnum<998244353>, 18446744073709551615ul>, ecnerwala::fft::detail::cut_op<modnum<998244353>, ecnerwala::fft::add_op>):
✓ Branch 38 → 28 taken 354 times.
✓ Branch 38 → 39 taken 177 times.
void ecnerwala::fft::engines::ntt<modnum<998244353> >::finish<ecnerwala::fft::detail::cut_op<modnum<998244353>, ecnerwala::fft::assign_op> >(ecnerwala::fft::engines::ntt<modnum<998244353> >::transformed&&, std::span<modnum<998244353>, 18446744073709551615ul>, ecnerwala::fft::detail::cut_op<modnum<998244353>, ecnerwala::fft::assign_op>):
✓ Branch 14 → 12 taken 22153567 times.
✓ Branch 14 → 15 taken 1647987 times.
✓ Branch 38 → 28 taken 2214 times.
✓ Branch 38 → 39 taken 260 times.
void ecnerwala::fft::engines::ntt<modnum<998244353> >::finish<ecnerwala::fft::assign_op>(ecnerwala::fft::engines::ntt<modnum<998244353> >::transformed&&, std::span<modnum<998244353>, 18446744073709551615ul>, ecnerwala::fft::assign_op):
✓ Branch 13 → 12 taken 543549690 times.
✓ Branch 13 → 14 taken 1656708 times.
✓ Branch 39 → 28 taken 42300 times.
✓ Branch 39 → 40 taken 2680 times.
 613330370 for (int i = 0; i < sz(out); i++) op(out[i], p.v[i] * d);
88 3318281 }
89 };
90
91 /* namespace ecnerwala::fft::engines */ }
92