GCC Code Coverage Report

Directory: src/
Coverage: low: ≥ 0% medium: ≥ 75.0% high: ≥ 90.0%
Coverage Exec / Excl / Total
Lines: 99.6% 284 / 0 / 285
Functions: 100.0% 39 / 0 / 39
Branches: 87.6% 326 / 48 / 420
fft/core.hpp
Line Branch Exec Source
1 #pragma once
2
3 #include <algorithm>
4 #include <cassert>
5 #include <cmath>
6 #include <span>
7 #include <vector>
8
9 #include "fft/common.hpp"
10 #include "modnum.hpp"
11
12 namespace ecnerwala::fft {
13
14 // ==== core: roots, buffers, raw transforms ====
15
16 // Complex
17 template <typename dbl> struct cplx { /// start-hash
18 dbl x, y;
19
2/4
✓ Branch 4 → 5 taken 96 times.
✗ Branch 6 → 7 not taken.
✗ Branch 8 → 9 not taken.
✓ Branch 8 → 10 taken 24699142 times.
 125469362 cplx(dbl x_ = 0, dbl y_ = 0) : x(x_), y(y_) { }
20 22554317 friend cplx operator+(cplx a, cplx b) { return cplx(a.x + b.x, a.y + b.y); }
21
1/2
✗ Branch 8 → 9 not taken.
✓ Branch 8 → 10 taken 24699142 times.
 25133194 friend cplx operator-(cplx a, cplx b) { return cplx(a.x - b.x, a.y - b.y); }
22 25325526 friend cplx operator*(cplx a, cplx b) { return cplx(a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x); }
23
1/2
✗ Branch 8 → 9 not taken.
✓ Branch 8 → 10 taken 24699142 times.
 24816037 friend cplx conj(cplx a) { return cplx(a.x, -a.y); }
24 1268 friend cplx inv(cplx a) { dbl n = (a.x*a.x+a.y*a.y); return cplx(a.x/n,-a.y/n); }
25 };
26
27 // getRoot implementations
28 template <typename num> struct getRoot {
29 ✗ static num f(int k) = delete;
30 };
31 template <typename dbl> struct getRoot<cplx<dbl>> {
32 680 static cplx<dbl> f(int k) {
33 #ifndef M_PI
34 #define M_PI 3.14159265358979323846
35 #endif
36 680 dbl a=2*M_PI/k;
37 680 return cplx<dbl>(cos(a),sin(a));
38 }
39 };
40 template <int MOD> struct primitive_root {
41 static const int value;
42 };
43 // 998244353 = (119 << 23) + 1 = 2^30 - 2^26 - 2^23 + 1
44 template <> struct primitive_root<998244353> {
45 static const int value = 3;
46 };
47 // babybear prime
48 template <> struct primitive_root<(15 << 27) + 1> {
49 static const int value = 31;
50 };
51 // koalabear prime
52 template <> struct primitive_root<(127 << 24) + 1> {
53 static const int value = 3;
54 };
55 template <> struct primitive_root<(7 << 26) + 1> {
56 static const int value = 3;
57 };
58 template <> struct primitive_root<(5 << 25) + 1> {
59 static const int value = 3;
60 };
61 template <int MOD> struct getRoot<modnum<MOD>> {
62 4015 static modnum<MOD> f(int k) {
63 4015 assert((MOD-1)%k == 0);
64 4292 return power(modnum<MOD>(primitive_root<MOD>::value), (MOD-1)/k);
65 }
66 };
67 template <> struct getRoot<mod_goldilocks> {
68 708 static mod_goldilocks f(int k) {
69 708 assert((mod_goldilocks::MOD-1)%k == 0);
70
0/2
✗ Branch 4 → 5 not taken.
✗ Branch 5 → 6 not taken.
 884 return power(mod_goldilocks(mod_goldilocks::PRIMITIVE_ROOT), (mod_goldilocks::MOD-1)/k);
71 }
72 };
73
74 // We take the bit-reverse convention: the coefficient of a[i] -> b[j] is omega^{i * bit_reverse(j)}.
75 // This means that the size 2^{k-1} transform is the prefix of the size 2^k transform (wrapping the input).
76 //
77 // We mostly work with spans here:
78 // spans of transforms are expected to have length exactly 2^k
79 // spans of inputs/outputs are expected to have length [0, 2^{k+1})
80 //
81 // Inputs/outputs are treated mod x^{2^k} - 1.
82 // Their length is allowed to be bigger than 2^k mostly to perform ops on sequences of size n+1 with only transforms of size n.
83 // The upper bound of 2^{k+1} is arbitrary: we could tighten it to 2^k + 1 or loosen it to infinity, this is just a "defensive" choice.
84 template <typename num> struct fft_core {
85
86 static inline vector<int> rev;
87 // rt[2^k + i] = 1^{i / 2^(k+1)}
88 // TODO: can we get rid of inv_rt; alternatively, should we store inv_rt in bit-reverse order?
89 static inline vector<num> rt, inv_rt;
90
91 9277963 static void init(int n) {
92
16/16
ecnerwala::fft::fft_core<mod_goldilocks>::init(int):
✓ Branch 2 → 3 taken 44 times.
✓ Branch 2 → 25 taken 88 times.
✓ Branch 3 → 4 taken 118 times.
✓ Branch 3 → 87 taken 5887 times.
ecnerwala::fft::fft_core<modnum<2013265921> >::init(int):
✓ Branch 2 → 3 taken 44 times.
✓ Branch 2 → 25 taken 88 times.
✓ Branch 3 → 4 taken 62 times.
✓ Branch 3 → 87 taken 3969 times.
ecnerwala::fft::fft_core<modnum<998244353> >::init(int):
✓ Branch 2 → 3 taken 1562 times.
✓ Branch 2 → 25 taken 9246098 times.
✓ Branch 3 → 4 taken 127 times.
✓ Branch 3 → 87 taken 7793 times.
ecnerwala::fft::fft_core<ecnerwala::fft::cplx<double> >::init(int):
✓ Branch 2 → 3 taken 48 times.
✓ Branch 2 → 23 taken 176 times.
✓ Branch 3 → 4 taken 115 times.
✓ Branch 3 → 84 taken 11744 times.
 9277963 if (n <= sz(rt)) return;
93 2120 rev.resize(n);
94
16/16
ecnerwala::fft::fft_core<mod_goldilocks>::init(int):
✓ Branch 6 → 5 taken 24699138 times.
✓ Branch 6 → 7 taken 44 times.
✓ Branch 13 → 6 taken 7648 times.
✓ Branch 13 → 14 taken 118 times.
ecnerwala::fft::fft_core<modnum<2013265921> >::init(int):
✓ Branch 6 → 5 taken 24699138 times.
✓ Branch 6 → 7 taken 44 times.
✓ Branch 13 → 6 taken 3936 times.
✓ Branch 13 → 14 taken 62 times.
ecnerwala::fft::fft_core<modnum<998244353> >::init(int):
✓ Branch 6 → 5 taken 129910052 times.
✓ Branch 6 → 7 taken 1562 times.
✓ Branch 13 → 6 taken 7742 times.
✓ Branch 13 → 14 taken 127 times.
ecnerwala::fft::fft_core<ecnerwala::fft::cplx<double> >::init(int):
✓ Branch 6 → 5 taken 24699142 times.
✓ Branch 6 → 7 taken 48 times.
✓ Branch 13 → 6 taken 6824 times.
✓ Branch 13 → 14 taken 115 times.
 204035740 for (int i = 0; i < n; i++) {
95 204033620 rev[i] = (rev[i>>1] | ((i&1)*n)) >> 1;
96 }
97 2120 rt.reserve(n); inv_rt.reserve(n);
98
26/32
ecnerwala::fft::fft_core<mod_goldilocks>::init(int):
✓ Branch 10 → 11 taken 44 times.
✓ Branch 10 → 12 taken 88 times.
✗ Branch 12 → 11 not taken.
✓ Branch 12 → 13 taken 88 times.
✓ Branch 27 → 28 taken 60 times.
✓ Branch 27 → 37 taken 118 times.
✓ Branch 29 → 30 taken 60 times.
✗ Branch 29 → 37 not taken.
ecnerwala::fft::fft_core<modnum<2013265921> >::init(int):
✓ Branch 10 → 11 taken 44 times.
✓ Branch 10 → 12 taken 88 times.
✗ Branch 12 → 11 not taken.
✓ Branch 12 → 13 taken 88 times.
✓ Branch 27 → 28 taken 32 times.
✓ Branch 27 → 37 taken 62 times.
✓ Branch 29 → 30 taken 32 times.
✗ Branch 29 → 37 not taken.
ecnerwala::fft::fft_core<modnum<998244353> >::init(int):
✓ Branch 10 → 11 taken 1562 times.
✓ Branch 10 → 12 taken 516 times.
✗ Branch 12 → 11 not taken.
✓ Branch 12 → 13 taken 516 times.
✓ Branch 27 → 28 taken 62 times.
✓ Branch 27 → 37 taken 127 times.
✓ Branch 29 → 30 taken 62 times.
✗ Branch 29 → 37 not taken.
ecnerwala::fft::fft_core<ecnerwala::fft::cplx<double> >::init(int):
✓ Branch 10 → 11 taken 44 times.
✓ Branch 10 → 12 taken 96 times.
✓ Branch 12 → 11 taken 4 times.
✓ Branch 12 → 13 taken 92 times.
✓ Branch 25 → 26 taken 58 times.
✓ Branch 25 → 33 taken 107 times.
✓ Branch 27 → 28 taken 50 times.
✓ Branch 27 → 33 taken 8 times.
 3620 while (sz(rt) < 2 && sz(rt) < n) { rt.push_back(num(1)); inv_rt.push_back(num(1)); }
99
16/16
ecnerwala::fft::fft_core<mod_goldilocks>::init(int):
✓ Branch 24 → 16 taken 532 times.
✓ Branch 24 → 25 taken 44 times.
✓ Branch 86 → 38 taken 176 times.
✓ Branch 86 → 87 taken 118 times.
ecnerwala::fft::fft_core<modnum<2013265921> >::init(int):
✓ Branch 24 → 16 taken 532 times.
✓ Branch 24 → 25 taken 44 times.
✓ Branch 86 → 38 taken 93 times.
✓ Branch 86 → 87 taken 62 times.
ecnerwala::fft::fft_core<modnum<998244353> >::init(int):
✓ Branch 24 → 16 taken 3206 times.
✓ Branch 24 → 25 taken 1562 times.
✓ Branch 86 → 38 taken 184 times.
✓ Branch 86 → 87 taken 127 times.
ecnerwala::fft::fft_core<ecnerwala::fft::cplx<double> >::init(int):
✓ Branch 22 → 16 taken 532 times.
✓ Branch 22 → 23 taken 48 times.
✓ Branch 83 → 34 taken 148 times.
✓ Branch 83 → 84 taken 115 times.
 7523 for (int k = sz(rt); k < n; k *= 2) {
100
8/8
ecnerwala::fft::fft_core<mod_goldilocks>::init(int):
✓ Branch 38 → 39 taken 176 times.
✓ Branch 39 → 40 taken 176 times.
ecnerwala::fft::fft_core<modnum<2013265921> >::init(int):
✓ Branch 38 → 39 taken 93 times.
✓ Branch 39 → 40 taken 93 times.
ecnerwala::fft::fft_core<modnum<998244353> >::init(int):
✓ Branch 38 → 39 taken 184 times.
✓ Branch 39 → 40 taken 184 times.
ecnerwala::fft::fft_core<ecnerwala::fft::cplx<double> >::init(int):
✓ Branch 34 → 35 taken 148 times.
✓ Branch 35 → 36 taken 148 times.
 5403 rt.resize(2*k); inv_rt.resize(2*k);
101 5403 num z = getRoot<num>::f(2*k);
102 5403 num iz = inv(z);
103
16/16
ecnerwala::fft::fft_core<mod_goldilocks>::init(int):
✓ Branch 22 → 21 taken 12349525 times.
✓ Branch 22 → 23 taken 532 times.
✓ Branch 83 → 48 taken 2402 times.
✓ Branch 83 → 84 taken 176 times.
ecnerwala::fft::fft_core<modnum<2013265921> >::init(int):
✓ Branch 22 → 21 taken 12349525 times.
✓ Branch 22 → 23 taken 532 times.
✓ Branch 83 → 48 taken 1232 times.
✓ Branch 83 → 84 taken 93 times.
ecnerwala::fft::fft_core<modnum<998244353> >::init(int):
✓ Branch 22 → 21 taken 44671367 times.
✓ Branch 22 → 23 taken 3206 times.
✓ Branch 83 → 48 taken 2385 times.
✓ Branch 83 → 84 taken 184 times.
ecnerwala::fft::fft_core<ecnerwala::fft::cplx<double> >::init(int):
✓ Branch 20 → 19 taken 12349525 times.
✓ Branch 20 → 21 taken 532 times.
✓ Branch 80 → 41 taken 2023 times.
✓ Branch 80 → 81 taken 148 times.
 81733387 for (int i = k/2; i < k; i++) {
104 81727984 rt[2*i] = rt[i], rt[2*i+1] = rt[i]*z;
105 81727984 inv_rt[2*i] = inv_rt[i], inv_rt[2*i+1] = inv_rt[i]*iz;
106 }
107 }
108 }
109
110 // bit-reversal of i as a log2(n)-bit number
111 24293093 static int brev(int i, int n) {
112
8/16
ecnerwala::fft::fft_core<mod_goldilocks>::brev(int, int):
✗ Branch 3 → 4 not taken.
✓ Branch 3 → 5 taken 2228 times.
✗ Branch 5 → 6 not taken.
✓ Branch 5 → 7 taken 2228 times.
ecnerwala::fft::fft_core<modnum<2013265921> >::brev(int, int):
✗ Branch 3 → 4 not taken.
✓ Branch 3 → 5 taken 1114 times.
✗ Branch 5 → 6 not taken.
✓ Branch 5 → 7 taken 1114 times.
ecnerwala::fft::fft_core<modnum<998244353> >::brev(int, int):
✗ Branch 3 → 4 not taken.
✓ Branch 3 → 5 taken 1188 times.
✗ Branch 5 → 6 not taken.
✓ Branch 5 → 7 taken 1188 times.
ecnerwala::fft::fft_core<ecnerwala::fft::cplx<double> >::brev(int, int):
✗ Branch 3 → 4 not taken.
✓ Branch 3 → 5 taken 5423 times.
✗ Branch 5 → 6 not taken.
✓ Branch 5 → 7 taken 5423 times.
 24293093 int s = __builtin_ctz(unsigned(sz(rev)/n));
113
4/8
ecnerwala::fft::fft_core<mod_goldilocks>::brev(int, int):
✗ Branch 10 → 11 not taken.
✓ Branch 10 → 12 taken 2228 times.
ecnerwala::fft::fft_core<modnum<2013265921> >::brev(int, int):
✗ Branch 10 → 11 not taken.
✓ Branch 10 → 12 taken 1114 times.
ecnerwala::fft::fft_core<modnum<998244353> >::brev(int, int):
✗ Branch 10 → 11 not taken.
✓ Branch 10 → 12 taken 1188 times.
ecnerwala::fft::fft_core<ecnerwala::fft::cplx<double> >::brev(int, int):
✗ Branch 10 → 11 not taken.
✓ Branch 10 → 12 taken 5423 times.
 24293093 return rev[i] >> s;
114 }
115 // index of the conjugate evaluation point, in the returned bit-reversed order
116 24764163 static int conj_index(int j) {
117
5/6
None:
✓ Branch 6 → 7 taken 24699094 times.
✓ Branch 6 → 8 taken 48 times.
ecnerwala::fft::fft_core<ecnerwala::fft::cplx<double> >::conj_index(int):
✓ Branch 2 → 3 taken 59295 times.
✓ Branch 2 → 6 taken 5726 times.
✗ Branch 3 → 4 not taken.
✓ Branch 3 → 5 taken 59295 times.
 24764163 return j == 0 ? 0 : j ^ ((1 << (31 - __builtin_clz(unsigned(j)))) - 1);
118 }
119
120 4954149 static void forward(std::span<num> a) {
121 4954149 int n = sz(a);
122
16/16
ecnerwala::fft::fft_core<mod_goldilocks>::forward(std::span<mod_goldilocks, 18446744073709551615ul>):
✓ Branch 2 → 3 taken 88 times.
✓ Branch 2 → 11 taken 8 times.
✓ Branch 3 → 4 taken 2823 times.
✓ Branch 3 → 46 taken 1598 times.
ecnerwala::fft::fft_core<modnum<2013265921> >::forward(std::span<modnum<2013265921>, 18446744073709551615ul>):
✓ Branch 2 → 3 taken 88 times.
✓ Branch 2 → 17 taken 8 times.
✓ Branch 3 → 4 taken 1872 times.
✓ Branch 3 → 46 taken 965 times.
ecnerwala::fft::fft_core<modnum<998244353> >::forward(std::span<modnum<998244353>, 18446744073709551615ul>):
✓ Branch 2 → 3 taken 3971586 times.
✓ Branch 2 → 17 taken 966403 times.
✓ Branch 3 → 4 taken 3864 times.
✓ Branch 3 → 46 taken 1733 times.
ecnerwala::fft::fft_core<ecnerwala::fft::cplx<double> >::forward(std::span<ecnerwala::fft::cplx<double>, 18446744073709551615ul>):
✓ Branch 2 → 3 taken 88 times.
✓ Branch 2 → 11 taken 8 times.
✓ Branch 3 → 4 taken 2031 times.
✓ Branch 3 → 45 taken 986 times.
 4954149 if (n <= 1) return;
123 3982440 init(n);
124
16/16
ecnerwala::fft::fft_core<mod_goldilocks>::forward(std::span<mod_goldilocks, 18446744073709551615ul>):
✓ Branch 10 → 8 taken 1152 times.
✓ Branch 10 → 11 taken 88 times.
✓ Branch 45 → 43 taken 9115 times.
✓ Branch 45 → 46 taken 2823 times.
ecnerwala::fft::fft_core<modnum<2013265921> >::forward(std::span<modnum<2013265921>, 18446744073709551615ul>):
✓ Branch 16 → 14 taken 1152 times.
✓ Branch 16 → 17 taken 88 times.
✓ Branch 45 → 43 taken 6272 times.
✓ Branch 45 → 46 taken 1872 times.
ecnerwala::fft::fft_core<modnum<998244353> >::forward(std::span<modnum<998244353>, 18446744073709551615ul>):
✓ Branch 16 → 14 taken 7386577 times.
✓ Branch 16 → 17 taken 3971586 times.
✓ Branch 45 → 43 taken 12769 times.
✓ Branch 45 → 46 taken 3864 times.
ecnerwala::fft::fft_core<ecnerwala::fft::cplx<double> >::forward(std::span<ecnerwala::fft::cplx<double>, 18446744073709551615ul>):
✓ Branch 10 → 8 taken 1152 times.
✓ Branch 10 → 11 taken 88 times.
✓ Branch 44 → 42 taken 6922 times.
✓ Branch 44 → 45 taken 2031 times.
 11407551 for (int k = n/2; k >= 1; k /= 2) {
125
16/16
ecnerwala::fft::fft_core<mod_goldilocks>::forward(std::span<mod_goldilocks, 18446744073709551615ul>):
✓ Branch 8 → 6 taken 49398188 times.
✓ Branch 8 → 9 taken 1152 times.
✓ Branch 43 → 41 taken 64291 times.
✓ Branch 43 → 44 taken 9115 times.
ecnerwala::fft::fft_core<modnum<2013265921> >::forward(std::span<modnum<2013265921>, 18446744073709551615ul>):
✓ Branch 14 → 12 taken 49398188 times.
✓ Branch 14 → 15 taken 1152 times.
✓ Branch 43 → 41 taken 43104 times.
✓ Branch 43 → 44 taken 6272 times.
ecnerwala::fft::fft_core<modnum<998244353> >::forward(std::span<modnum<998244353>, 18446744073709551615ul>):
✓ Branch 14 → 12 taken 888958350 times.
✓ Branch 14 → 15 taken 7386577 times.
✓ Branch 43 → 41 taken 90232 times.
✓ Branch 43 → 44 taken 12769 times.
ecnerwala::fft::fft_core<ecnerwala::fft::cplx<double> >::forward(std::span<ecnerwala::fft::cplx<double>, 18446744073709551615ul>):
✓ Branch 8 → 6 taken 49398188 times.
✓ Branch 8 → 9 taken 1152 times.
✓ Branch 42 → 40 taken 48399 times.
✓ Branch 42 → 43 taken 6922 times.
 1044824051 for (int i = 0; i < n; i += 2*k) {
126
16/16
ecnerwala::fft::fft_core<mod_goldilocks>::forward(std::span<mod_goldilocks, 18446744073709551615ul>):
✓ Branch 6 → 5 taken 493102494 times.
✓ Branch 6 → 7 taken 49398188 times.
✓ Branch 41 → 6 taken 195209 times.
✓ Branch 41 → 42 taken 64291 times.
ecnerwala::fft::fft_core<modnum<2013265921> >::forward(std::span<modnum<2013265921>, 18446744073709551615ul>):
✓ Branch 12 → 5 taken 493102494 times.
✓ Branch 12 → 13 taken 49398188 times.
✓ Branch 41 → 6 taken 127686 times.
✓ Branch 41 → 42 taken 43104 times.
ecnerwala::fft::fft_core<modnum<998244353> >::forward(std::span<modnum<998244353>, 18446744073709551615ul>):
✓ Branch 12 → 5 taken 7844364150 times.
✓ Branch 12 → 13 taken 888958350 times.
✓ Branch 41 → 6 taken 268868 times.
✓ Branch 41 → 42 taken 90232 times.
ecnerwala::fft::fft_core<ecnerwala::fft::cplx<double> >::forward(std::span<ecnerwala::fft::cplx<double>, 18446744073709551615ul>):
✓ Branch 6 → 5 taken 493102494 times.
✓ Branch 6 → 7 taken 49398188 times.
✓ Branch 40 → 6 taken 143829 times.
✓ Branch 40 → 41 taken 48399 times.
 10361806164 for (int j = 0; j < k; j++) {
127
4/4
ecnerwala::fft::fft_core<modnum<2013265921> >::forward(std::span<modnum<2013265921>, 18446744073709551615ul>):
✓ Branch 5 → 6 taken 287392187 times.
✓ Branch 5 → 7 taken 205710307 times.
ecnerwala::fft::fft_core<modnum<998244353> >::forward(std::span<modnum<998244353>, 18446744073709551615ul>):
✓ Branch 5 → 6 taken 4985163574 times.
✓ Branch 5 → 7 taken 2859200576 times.
 9324407224 num u = a[i+j], v = a[i+j+k];
128 9324407224 a[i+j] = u + v;
129
4/4
ecnerwala::fft::fft_core<modnum<2013265921> >::forward(std::span<modnum<2013265921>, 18446744073709551615ul>):
✓ Branch 8 → 9 taken 202208976 times.
✓ Branch 8 → 10 taken 290893518 times.
ecnerwala::fft::fft_core<modnum<998244353> >::forward(std::span<modnum<998244353>, 18446744073709551615ul>):
✓ Branch 8 → 9 taken 2906246901 times.
✓ Branch 8 → 10 taken 4938117249 times.
 12557009448 a[i+j+k] = (u - v) * rt[j+k];
130 }
131 }
132 }
133 }
134
135 3325426 static void inverse(std::span<num> a) {
136 3325426 int n = sz(a);
137
16/16
ecnerwala::fft::fft_core<mod_goldilocks>::inverse(std::span<mod_goldilocks, 18446744073709551615ul>):
✓ Branch 2 → 3 taken 44 times.
✓ Branch 2 → 11 taken 4 times.
✓ Branch 3 → 4 taken 2704 times.
✓ Branch 3 → 39 taken 1869 times.
ecnerwala::fft::fft_core<modnum<2013265921> >::inverse(std::span<modnum<2013265921>, 18446744073709551615ul>):
✓ Branch 2 → 3 taken 44 times.
✓ Branch 2 → 17 taken 4 times.
✓ Branch 3 → 4 taken 2050 times.
✓ Branch 3 → 39 taken 1425 times.
ecnerwala::fft::fft_core<modnum<998244353> >::inverse(std::span<modnum<998244353>, 18446744073709551615ul>):
✓ Branch 2 → 3 taken 2982488 times.
✓ Branch 2 → 17 taken 322207 times.
✓ Branch 3 → 4 taken 3449 times.
✓ Branch 3 → 39 taken 1999 times.
ecnerwala::fft::fft_core<ecnerwala::fft::cplx<double> >::inverse(std::span<ecnerwala::fft::cplx<double>, 18446744073709551615ul>):
✓ Branch 2 → 3 taken 88 times.
✓ Branch 2 → 11 taken 8 times.
✓ Branch 3 → 4 taken 4182 times.
✓ Branch 3 → 47 taken 2861 times.
 3325426 if (n <= 1) return;
138 2995049 init(n);
139
16/16
ecnerwala::fft::fft_core<mod_goldilocks>::inverse(std::span<mod_goldilocks, 18446744073709551615ul>):
✓ Branch 10 → 8 taken 576 times.
✓ Branch 10 → 11 taken 44 times.
✓ Branch 38 → 36 taken 8284 times.
✓ Branch 38 → 39 taken 2704 times.
ecnerwala::fft::fft_core<modnum<2013265921> >::inverse(std::span<modnum<2013265921>, 18446744073709551615ul>):
✓ Branch 16 → 14 taken 576 times.
✓ Branch 16 → 17 taken 44 times.
✓ Branch 38 → 36 taken 6374 times.
✓ Branch 38 → 39 taken 2050 times.
ecnerwala::fft::fft_core<modnum<998244353> >::inverse(std::span<modnum<998244353>, 18446744073709551615ul>):
✓ Branch 16 → 14 taken 7688713 times.
✓ Branch 16 → 17 taken 2982488 times.
✓ Branch 38 → 36 taken 10862 times.
✓ Branch 38 → 39 taken 3449 times.
ecnerwala::fft::fft_core<ecnerwala::fft::cplx<double> >::inverse(std::span<ecnerwala::fft::cplx<double>, 18446744073709551615ul>):
✓ Branch 10 → 8 taken 1152 times.
✓ Branch 10 → 11 taken 88 times.
✓ Branch 46 → 44 taken 13096 times.
✓ Branch 46 → 47 taken 4182 times.
 10724682 for (int k = 1; k < n; k *= 2) {
140
16/16
ecnerwala::fft::fft_core<mod_goldilocks>::inverse(std::span<mod_goldilocks, 18446744073709551615ul>):
✓ Branch 8 → 6 taken 24699094 times.
✓ Branch 8 → 9 taken 576 times.
✓ Branch 36 → 34 taken 50954 times.
✓ Branch 36 → 37 taken 8284 times.
ecnerwala::fft::fft_core<modnum<2013265921> >::inverse(std::span<modnum<2013265921>, 18446744073709551615ul>):
✓ Branch 14 → 12 taken 24699094 times.
✓ Branch 14 → 15 taken 576 times.
✓ Branch 36 → 34 taken 37528 times.
✓ Branch 36 → 37 taken 6374 times.
ecnerwala::fft::fft_core<modnum<998244353> >::inverse(std::span<modnum<998244353>, 18446744073709551615ul>):
✓ Branch 14 → 12 taken 638404990 times.
✓ Branch 14 → 15 taken 7688713 times.
✓ Branch 36 → 34 taken 68725 times.
✓ Branch 36 → 37 taken 10862 times.
ecnerwala::fft::fft_core<ecnerwala::fft::cplx<double> >::inverse(std::span<ecnerwala::fft::cplx<double>, 18446744073709551615ul>):
✓ Branch 8 → 6 taken 49398188 times.
✓ Branch 8 → 9 taken 1152 times.
✓ Branch 44 → 42 taken 78094 times.
✓ Branch 44 → 45 taken 13096 times.
 745166300 for (int i = 0; i < n; i += 2*k) {
141
16/16
ecnerwala::fft::fft_core<mod_goldilocks>::inverse(std::span<mod_goldilocks, 18446744073709551615ul>):
✓ Branch 6 → 5 taken 246551247 times.
✓ Branch 6 → 7 taken 24699094 times.
✓ Branch 34 → 6 taken 147595 times.
✓ Branch 34 → 35 taken 50954 times.
ecnerwala::fft::fft_core<modnum<2013265921> >::inverse(std::span<modnum<2013265921>, 18446744073709551615ul>):
✓ Branch 12 → 5 taken 246551247 times.
✓ Branch 12 → 13 taken 24699094 times.
✓ Branch 34 → 6 taken 105251 times.
✓ Branch 34 → 35 taken 37528 times.
ecnerwala::fft::fft_core<modnum<998244353> >::inverse(std::span<modnum<998244353>, 18446744073709551615ul>):
✓ Branch 12 → 5 taken 5427937985 times.
✓ Branch 12 → 13 taken 638404990 times.
✓ Branch 34 → 6 taken 197903 times.
✓ Branch 34 → 35 taken 68725 times.
ecnerwala::fft::fft_core<ecnerwala::fft::cplx<double> >::inverse(std::span<ecnerwala::fft::cplx<double>, 18446744073709551615ul>):
✓ Branch 6 → 5 taken 493102494 times.
✓ Branch 6 → 7 taken 49398188 times.
✓ Branch 42 → 6 taken 219960 times.
✓ Branch 42 → 43 taken 78094 times.
 7152250349 for (int j = 0; j < k; j++) {
142
4/4
ecnerwala::fft::fft_core<modnum<2013265921> >::inverse(std::span<modnum<2013265921>, 18446744073709551615ul>):
✓ Branch 5 → 6 taken 111992701 times.
✓ Branch 5 → 7 taken 134558546 times.
ecnerwala::fft::fft_core<modnum<998244353> >::inverse(std::span<modnum<998244353>, 18446744073709551615ul>):
✓ Branch 5 → 6 taken 2448700578 times.
✓ Branch 5 → 7 taken 2979237407 times.
 6414813682 num t = inv_rt[j+k] * a[i+j+k];
143
4/4
ecnerwala::fft::fft_core<modnum<2013265921> >::inverse(std::span<modnum<2013265921>, 18446744073709551615ul>):
✓ Branch 5 → 6 taken 111992701 times.
✓ Branch 5 → 7 taken 134558546 times.
ecnerwala::fft::fft_core<modnum<998244353> >::inverse(std::span<modnum<998244353>, 18446744073709551615ul>):
✓ Branch 5 → 6 taken 2448700578 times.
✓ Branch 5 → 7 taken 2979237407 times.
 6414813682 a[i+j+k] = a[i+j] - t;
144
4/4
ecnerwala::fft::fft_core<modnum<2013265921> >::inverse(std::span<modnum<2013265921>, 18446744073709551615ul>):
✓ Branch 8 → 9 taken 133348118 times.
✓ Branch 8 → 10 taken 113203129 times.
ecnerwala::fft::fft_core<modnum<998244353> >::inverse(std::span<modnum<998244353>, 18446744073709551615ul>):
✓ Branch 8 → 9 taken 2939192253 times.
✓ Branch 8 → 10 taken 2488745732 times.
 12089302914 a[i+j] = a[i+j] + t;
145 }
146 }
147 }
148 }
149
150 // Extend a size 2^{k-1} transform to size 2^k; we need the coefficients.
151 // t must have size 2^k, and coeffs must have size at most 2^{k+1}.
152 2294094 static void extend(std::span<num> t, std::span<const num> coeffs) {
153 2294094 int n = sz(t) / 2;
154 2294094 assert(sz(coeffs) <= 2 * n);
155
4/4
ecnerwala::fft::fft_core<mod_goldilocks>::extend(std::span<mod_goldilocks, 18446744073709551615ul>, std::span<mod_goldilocks const, 18446744073709551615ul>):
✓ Branch 8 → 9 taken 280 times.
ecnerwala::fft::fft_core<modnum<2013265921> >::extend(std::span<modnum<2013265921>, 18446744073709551615ul>, std::span<modnum<2013265921> const, 18446744073709551615ul>):
✓ Branch 8 → 9 taken 10 times.
ecnerwala::fft::fft_core<modnum<998244353> >::extend(std::span<modnum<998244353>, 18446744073709551615ul>, std::span<modnum<998244353> const, 18446744073709551615ul>):
✓ Branch 8 → 9 taken 505 times.
ecnerwala::fft::fft_core<ecnerwala::fft::cplx<double> >::extend(std::span<ecnerwala::fft::cplx<double>, 18446744073709551615ul>, std::span<ecnerwala::fft::cplx<double> const, 18446744073709551615ul>):
✓ Branch 8 → 9 taken 19 times.
 2294094 init(sz(t));
156
1/8
ecnerwala::fft::fft_core<mod_goldilocks>::extend(std::span<mod_goldilocks, 18446744073709551615ul>, std::span<mod_goldilocks const, 18446744073709551615ul>):
✗ Branch 5 → 6 not taken.
✗ Branch 5 → 7 not taken.
ecnerwala::fft::fft_core<modnum<2013265921> >::extend(std::span<modnum<2013265921>, 18446744073709551615ul>, std::span<modnum<2013265921> const, 18446744073709551615ul>):
✗ Branch 5 → 6 not taken.
✗ Branch 5 → 7 not taken.
ecnerwala::fft::fft_core<modnum<998244353> >::extend(std::span<modnum<998244353>, 18446744073709551615ul>, std::span<modnum<998244353> const, 18446744073709551615ul>):
✗ Branch 5 → 6 not taken.
✓ Branch 5 → 7 taken 2293280 times.
ecnerwala::fft::fft_core<ecnerwala::fft::cplx<double> >::extend(std::span<ecnerwala::fft::cplx<double>, 18446744073709551615ul>, std::span<ecnerwala::fft::cplx<double> const, 18446744073709551615ul>):
✗ Branch 5 → 6 not taken.
✗ Branch 5 → 7 not taken.
 2294094 auto b = t.subspan(n, n);
157 2294094 int lo = min(sz(coeffs), n);
158
10/16
ecnerwala::fft::fft_core<mod_goldilocks>::extend(std::span<mod_goldilocks, 18446744073709551615ul>, std::span<mod_goldilocks const, 18446744073709551615ul>):
✗ Branch 9 → 8 not taken.
✗ Branch 9 → 10 not taken.
✓ Branch 32 → 19 taken 2521 times.
✓ Branch 32 → 33 taken 280 times.
ecnerwala::fft::fft_core<modnum<2013265921> >::extend(std::span<modnum<2013265921>, 18446744073709551615ul>, std::span<modnum<2013265921> const, 18446744073709551615ul>):
✗ Branch 9 → 8 not taken.
✗ Branch 9 → 10 not taken.
✓ Branch 32 → 19 taken 177 times.
✓ Branch 32 → 33 taken 10 times.
ecnerwala::fft::fft_core<modnum<998244353> >::extend(std::span<modnum<998244353>, 18446744073709551615ul>, std::span<modnum<998244353> const, 18446744073709551615ul>):
✓ Branch 9 → 8 taken 106687013 times.
✓ Branch 9 → 10 taken 2293280 times.
✓ Branch 32 → 19 taken 3530 times.
✓ Branch 32 → 33 taken 505 times.
ecnerwala::fft::fft_core<ecnerwala::fft::cplx<double> >::extend(std::span<ecnerwala::fft::cplx<double>, 18446744073709551615ul>, std::span<ecnerwala::fft::cplx<double> const, 18446744073709551615ul>):
✗ Branch 9 → 8 not taken.
✗ Branch 9 → 10 not taken.
✓ Branch 36 → 19 taken 390 times.
✓ Branch 36 → 37 taken 19 times.
 108987725 for (int i = 0; i < lo; i++) {
159 // rt[n + i] = w_{2n}^i
160 106693631 b[i] = coeffs[i] * rt[n + i];
161 }
162 2296517 std::fill(b.begin() + lo, b.end(), num(0));
163
10/16
ecnerwala::fft::fft_core<mod_goldilocks>::extend(std::span<mod_goldilocks, 18446744073709551615ul>, std::span<mod_goldilocks const, 18446744073709551615ul>):
✗ Branch 14 → 13 not taken.
✗ Branch 14 → 15 not taken.
✓ Branch 94 → 74 taken 77 times.
✓ Branch 94 → 95 taken 280 times.
ecnerwala::fft::fft_core<modnum<2013265921> >::extend(std::span<modnum<2013265921>, 18446744073709551615ul>, std::span<modnum<2013265921> const, 18446744073709551615ul>):
✗ Branch 17 → 13 not taken.
✗ Branch 17 → 18 not taken.
✓ Branch 94 → 74 taken 6 times.
✓ Branch 94 → 95 taken 10 times.
ecnerwala::fft::fft_core<modnum<998244353> >::extend(std::span<modnum<998244353>, 18446744073709551615ul>, std::span<modnum<998244353> const, 18446744073709551615ul>):
✓ Branch 17 → 13 taken 1647931 times.
✓ Branch 17 → 18 taken 2293280 times.
✓ Branch 94 → 74 taken 219 times.
✓ Branch 94 → 95 taken 505 times.
ecnerwala::fft::fft_core<ecnerwala::fft::cplx<double> >::extend(std::span<ecnerwala::fft::cplx<double>, 18446744073709551615ul>, std::span<ecnerwala::fft::cplx<double> const, 18446744073709551615ul>):
✗ Branch 14 → 13 not taken.
✗ Branch 14 → 15 not taken.
✓ Branch 99 → 76 taken 8 times.
✓ Branch 99 → 100 taken 19 times.
 3942335 for (int i = n; i < sz(coeffs); i++) {
164
2/4
ecnerwala::fft::fft_core<modnum<2013265921> >::extend(std::span<modnum<2013265921>, 18446744073709551615ul>, std::span<modnum<2013265921> const, 18446744073709551615ul>):
✗ Branch 13 → 14 not taken.
✗ Branch 13 → 15 not taken.
ecnerwala::fft::fft_core<modnum<998244353> >::extend(std::span<modnum<998244353>, 18446744073709551615ul>, std::span<modnum<998244353> const, 18446744073709551615ul>):
✓ Branch 13 → 14 taken 1487405 times.
✓ Branch 13 → 15 taken 160526 times.
 3296172 b[i - n] = b[i - n] - coeffs[i] * rt[i];
165 }
166
4/4
ecnerwala::fft::fft_core<mod_goldilocks>::extend(std::span<mod_goldilocks, 18446744073709551615ul>, std::span<mod_goldilocks const, 18446744073709551615ul>):
✓ Branch 95 → 96 taken 280 times.
ecnerwala::fft::fft_core<modnum<2013265921> >::extend(std::span<modnum<2013265921>, 18446744073709551615ul>, std::span<modnum<2013265921> const, 18446744073709551615ul>):
✓ Branch 95 → 96 taken 10 times.
ecnerwala::fft::fft_core<modnum<998244353> >::extend(std::span<modnum<998244353>, 18446744073709551615ul>, std::span<modnum<998244353> const, 18446744073709551615ul>):
✓ Branch 95 → 96 taken 505 times.
ecnerwala::fft::fft_core<ecnerwala::fft::cplx<double> >::extend(std::span<ecnerwala::fft::cplx<double>, 18446744073709551615ul>, std::span<ecnerwala::fft::cplx<double> const, 18446744073709551615ul>):
✓ Branch 100 → 101 taken 19 times.
 2294094 forward(b);
167 2294094 }
168
169 // Consider t = transform(P) and P(x) = E(x^2) + O(x^2) * x
170 // `even_half` and `odd_half` extract a size 2^{k-1} transform of E/O, respectively.
171 2710 static void even_half(std::span<const num> t, std::span<num> out) {
172 2710 int n = sz(out);
173 2710 assert(sz(t) >= 2*n);
174 3510 num half = inv(num(2));
175
12/12
ecnerwala::fft::fft_core<mod_goldilocks>::even_half(std::span<mod_goldilocks const, 18446744073709551615ul>, std::span<mod_goldilocks, 18446744073709551615ul>):
✓ Branch 35 → 18 taken 4292 times.
✓ Branch 35 → 36 taken 390 times.
ecnerwala::fft::fft_core<modnum<2013265921> >::even_half(std::span<modnum<2013265921> const, 18446744073709551615ul>, std::span<modnum<2013265921>, 18446744073709551615ul>):
✓ Branch 35 → 18 taken 2146 times.
✓ Branch 35 → 36 taken 195 times.
ecnerwala::fft::fft_core<modnum<998244353> >::even_half(std::span<modnum<998244353> const, 18446744073709551615ul>, std::span<modnum<998244353>, 18446744073709551615ul>):
✓ Branch 6 → 7 taken 74053960 times.
✓ Branch 6 → 8 taken 73497150 times.
✓ Branch 10 → 6 taken 147551110 times.
✓ Branch 10 → 11 taken 1520 times.
✓ Branch 35 → 18 taken 3376 times.
✓ Branch 35 → 36 taken 215 times.
ecnerwala::fft::fft_core<ecnerwala::fft::cplx<double> >::even_half(std::span<ecnerwala::fft::cplx<double> const, 18446744073709551615ul>, std::span<ecnerwala::fft::cplx<double>, 18446744073709551615ul>):
✓ Branch 30 → 12 taken 4292 times.
✓ Branch 30 → 31 taken 390 times.
 147567926 for (int j = 0; j < n; j++) out[j] = (t[2*j] + t[2*j+1]) * half;
176 2710 }
177 903 static void odd_half(std::span<const num> t, std::span<num> out) {
178 903 int n = sz(out);
179 903 assert(sz(t) >= 2*n);
180
4/4
ecnerwala::fft::fft_core<mod_goldilocks>::odd_half(std::span<mod_goldilocks const, 18446744073709551615ul>, std::span<mod_goldilocks, 18446744073709551615ul>):
✓ Branch 6 → 7 taken 198 times.
ecnerwala::fft::fft_core<modnum<2013265921> >::odd_half(std::span<modnum<2013265921> const, 18446744073709551615ul>, std::span<modnum<2013265921>, 18446744073709551615ul>):
✓ Branch 6 → 7 taken 99 times.
ecnerwala::fft::fft_core<modnum<998244353> >::odd_half(std::span<modnum<998244353> const, 18446744073709551615ul>, std::span<modnum<998244353>, 18446744073709551615ul>):
✓ Branch 6 → 7 taken 102 times.
ecnerwala::fft::fft_core<ecnerwala::fft::cplx<double> >::odd_half(std::span<ecnerwala::fft::cplx<double> const, 18446744073709551615ul>, std::span<ecnerwala::fft::cplx<double>, 18446744073709551615ul>):
✓ Branch 6 → 7 taken 198 times.
 903 init(2*n);
181 1302 num half = inv(num(2));
182
10/10
ecnerwala::fft::fft_core<mod_goldilocks>::odd_half(std::span<mod_goldilocks const, 18446744073709551615ul>, std::span<mod_goldilocks, 18446744073709551615ul>):
✓ Branch 43 → 19 taken 2228 times.
✓ Branch 43 → 44 taken 198 times.
ecnerwala::fft::fft_core<modnum<2013265921> >::odd_half(std::span<modnum<2013265921> const, 18446744073709551615ul>, std::span<modnum<2013265921>, 18446744073709551615ul>):
✓ Branch 43 → 19 taken 1114 times.
✓ Branch 43 → 44 taken 99 times.
ecnerwala::fft::fft_core<modnum<998244353> >::odd_half(std::span<modnum<998244353> const, 18446744073709551615ul>, std::span<modnum<998244353>, 18446744073709551615ul>):
✓ Branch 11 → 7 taken 24283140 times.
✓ Branch 11 → 12 taken 306 times.
✓ Branch 43 → 19 taken 1188 times.
✓ Branch 43 → 44 taken 102 times.
ecnerwala::fft::fft_core<ecnerwala::fft::cplx<double> >::odd_half(std::span<ecnerwala::fft::cplx<double> const, 18446744073709551615ul>, std::span<ecnerwala::fft::cplx<double>, 18446744073709551615ul>):
✓ Branch 37 → 13 taken 2228 times.
✓ Branch 37 → 38 taken 198 times.
 24290801 for (int j = 0; j < n; j++) {
183 // entry j of the size-2n transform pairs (w, -w) with w = w_{2n}^{brev(j, n)}
184
2/2
✓ Branch 7 → 8 taken 12141324 times.
✓ Branch 7 → 9 taken 12141816 times.
 48573038 out[j] = (t[2*j] - t[2*j+1]) * half * inv_rt[n + brev(j, n)];
185 }
186 903 }
187 };
188
189 /* namespace ecnerwala::fft */ }
190