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 "num/modnum.hpp" | ||
| 11 | |||
| 12 | namespace wala::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.
|
125597079 | cplx(dbl x_ = 0, dbl y_ = 0) : x(x_), y(y_) { } |
| 20 | 22585041 | 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.
|
25161075 | friend cplx operator-(cplx a, cplx b) { return cplx(a.x - b.x, a.y - b.y); } |
| 22 | 309 | friend cplx operator-(cplx a) { return cplx(-a.x, -a.y); } | |
| 23 | 25366316 | 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); } | |
| 24 |
1/2✗ Branch 8 → 9 not taken.
✓ Branch 8 → 10 taken 24699142 times.
|
24823091 | friend cplx conj(cplx a) { return cplx(a.x, -a.y); } |
| 25 | 1318 | friend cplx inv(cplx a) { dbl n = (a.x*a.x+a.y*a.y); return cplx(a.x/n,-a.y/n); } | |
| 26 | }; | ||
| 27 | |||
| 28 | // getRoot implementations | ||
| 29 | template <typename num> struct getRoot { | ||
| 30 | ✗ | static num f(int k) = delete; | |
| 31 | }; | ||
| 32 | template <typename dbl> struct getRoot<cplx<dbl>> { | ||
| 33 | 718 | static cplx<dbl> f(int k) { | |
| 34 | #ifndef M_PI | ||
| 35 | #define M_PI 3.14159265358979323846 | ||
| 36 | #endif | ||
| 37 | 718 | dbl a=2*M_PI/k; | |
| 38 | 718 | return cplx<dbl>(cos(a),sin(a)); | |
| 39 | } | ||
| 40 | }; | ||
| 41 | template <int MOD> struct primitive_root { | ||
| 42 | static const int value; | ||
| 43 | }; | ||
| 44 | // 998244353 = (119 << 23) + 1 = 2^30 - 2^26 - 2^23 + 1 | ||
| 45 | template <> struct primitive_root<998244353> { | ||
| 46 | static const int value = 3; | ||
| 47 | }; | ||
| 48 | // babybear prime | ||
| 49 | template <> struct primitive_root<(15 << 27) + 1> { | ||
| 50 | static const int value = 31; | ||
| 51 | }; | ||
| 52 | // koalabear prime | ||
| 53 | template <> struct primitive_root<(127 << 24) + 1> { | ||
| 54 | static const int value = 3; | ||
| 55 | }; | ||
| 56 | template <> struct primitive_root<(7 << 26) + 1> { | ||
| 57 | static const int value = 3; | ||
| 58 | }; | ||
| 59 | template <> struct primitive_root<(5 << 25) + 1> { | ||
| 60 | static const int value = 3; | ||
| 61 | }; | ||
| 62 | template <int MOD> struct getRoot<modnum<MOD>> { | ||
| 63 | 4448 | static modnum<MOD> f(int k) { | |
| 64 | 4448 | assert((MOD-1)%k == 0); | |
| 65 | 4770 | return power(modnum<MOD>(primitive_root<MOD>::value), (MOD-1)/k); | |
| 66 | } | ||
| 67 | }; | ||
| 68 | template <> struct getRoot<mod_goldilocks> { | ||
| 69 | 747 | static mod_goldilocks f(int k) { | |
| 70 | 747 | assert((mod_goldilocks::MOD-1)%k == 0); | |
| 71 |
0/2✗ Branch 4 → 5 not taken.
✗ Branch 5 → 6 not taken.
|
962 | return power(mod_goldilocks(mod_goldilocks::PRIMITIVE_ROOT), (mod_goldilocks::MOD-1)/k); |
| 72 | } | ||
| 73 | }; | ||
| 74 | |||
| 75 | // We take the bit-reverse convention: the coefficient of a[i] -> b[j] is omega^{i * bit_reverse(j)}. | ||
| 76 | // This means that the size 2^{k-1} transform is the prefix of the size 2^k transform (wrapping the input). | ||
| 77 | // | ||
| 78 | // We mostly work with spans here: | ||
| 79 | // spans of transforms are expected to have length exactly 2^k | ||
| 80 | // spans of inputs/outputs are expected to have length [0, 2^{k+1}) | ||
| 81 | // | ||
| 82 | // Inputs/outputs are treated mod x^{2^k} - 1. | ||
| 83 | // 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. | ||
| 84 | // 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. | ||
| 85 | template <typename num> struct fft_core { | ||
| 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 | 9279063 | static void init(int n) { | |
| 92 |
16/16wala::fft::fft_core<wala::fft::cplx<double> >::init(int):
✓ Branch 2 → 3 taken 48 times.
✓ Branch 2 → 23 taken 176 times.
✓ Branch 3 → 4 taken 156 times.
✓ Branch 3 → 84 taken 12114 times.
wala::fft::fft_core<wala::mod_goldilocks>::init(int):
✓ Branch 2 → 3 taken 44 times.
✓ Branch 2 → 25 taken 88 times.
✓ Branch 3 → 4 taken 154 times.
✓ Branch 3 → 87 taken 6113 times.
wala::fft::fft_core<wala::modnum<2013265921> >::init(int):
✓ Branch 2 → 3 taken 44 times.
✓ Branch 2 → 25 taken 88 times.
✓ Branch 3 → 4 taken 78 times.
✓ Branch 3 → 87 taken 4076 times.
wala::fft::fft_core<wala::modnum<998244353> >::init(int):
✓ Branch 2 → 3 taken 1599 times.
✓ Branch 2 → 25 taken 9246172 times.
✓ Branch 3 → 4 taken 151 times.
✓ Branch 3 → 87 taken 7962 times.
|
9279063 | if (n <= sz(rt)) return; |
| 93 | 2274 | rev.resize(n); | |
| 94 |
16/16wala::fft::fft_core<wala::fft::cplx<double> >::init(int):
✓ Branch 6 → 5 taken 24699142 times.
✓ Branch 6 → 7 taken 48 times.
✓ Branch 13 → 6 taken 8031 times.
✓ Branch 13 → 14 taken 156 times.
wala::fft::fft_core<wala::mod_goldilocks>::init(int):
✓ Branch 6 → 5 taken 24699138 times.
✓ Branch 6 → 7 taken 44 times.
✓ Branch 13 → 6 taken 8890 times.
✓ Branch 13 → 14 taken 154 times.
wala::fft::fft_core<wala::modnum<2013265921> >::init(int):
✓ Branch 6 → 5 taken 24699138 times.
✓ Branch 6 → 7 taken 44 times.
✓ Branch 13 → 6 taken 4514 times.
✓ Branch 13 → 14 taken 78 times.
wala::fft::fft_core<wala::modnum<998244353> >::init(int):
✓ Branch 6 → 5 taken 144766564 times.
✓ Branch 6 → 7 taken 1599 times.
✓ Branch 13 → 6 taken 8556 times.
✓ Branch 13 → 14 taken 151 times.
|
218896247 | for (int i = 0; i < n; i++) { |
| 95 | 218893973 | rev[i] = (rev[i>>1] | ((i&1)*n)) >> 1; | |
| 96 | } | ||
| 97 | 2274 | rt.reserve(n); inv_rt.reserve(n); | |
| 98 |
26/32wala::fft::fft_core<wala::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 73 times.
✓ Branch 25 → 33 taken 147 times.
✓ Branch 27 → 28 taken 64 times.
✓ Branch 27 → 33 taken 9 times.
wala::fft::fft_core<wala::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 74 times.
✓ Branch 27 → 37 taken 154 times.
✓ Branch 29 → 30 taken 74 times.
✗ Branch 29 → 37 not taken.
wala::fft::fft_core<wala::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 38 times.
✓ Branch 27 → 37 taken 78 times.
✓ Branch 29 → 30 taken 38 times.
✗ Branch 29 → 37 not taken.
wala::fft::fft_core<wala::modnum<998244353> >::init(int):
✓ Branch 10 → 11 taken 1599 times.
✓ Branch 10 → 12 taken 590 times.
✗ Branch 12 → 11 not taken.
✓ Branch 12 → 13 taken 590 times.
✓ Branch 27 → 28 taken 72 times.
✓ Branch 27 → 37 taken 151 times.
✓ Branch 29 → 30 taken 72 times.
✗ Branch 29 → 37 not taken.
|
3996 | while (sz(rt) < 2 && sz(rt) < n) { rt.push_back(num(1)); inv_rt.push_back(num(1)); } |
| 99 |
16/16wala::fft::fft_core<wala::fft::cplx<double> >::init(int):
✓ Branch 22 → 16 taken 532 times.
✓ Branch 22 → 23 taken 48 times.
✓ Branch 83 → 34 taken 186 times.
✓ Branch 83 → 84 taken 156 times.
wala::fft::fft_core<wala::mod_goldilocks>::init(int):
✓ Branch 24 → 16 taken 532 times.
✓ Branch 24 → 25 taken 44 times.
✓ Branch 86 → 38 taken 215 times.
✓ Branch 86 → 87 taken 154 times.
wala::fft::fft_core<wala::modnum<2013265921> >::init(int):
✓ Branch 24 → 16 taken 532 times.
✓ Branch 24 → 25 taken 44 times.
✓ Branch 86 → 38 taken 110 times.
✓ Branch 86 → 87 taken 78 times.
wala::fft::fft_core<wala::modnum<998244353> >::init(int):
✓ Branch 24 → 16 taken 3594 times.
✓ Branch 24 → 25 taken 1599 times.
✓ Branch 86 → 38 taken 212 times.
✓ Branch 86 → 87 taken 151 times.
|
8187 | for (int k = sz(rt); k < n; k *= 2) { |
| 100 |
8/8wala::fft::fft_core<wala::fft::cplx<double> >::init(int):
✓ Branch 34 → 35 taken 186 times.
✓ Branch 35 → 36 taken 186 times.
wala::fft::fft_core<wala::mod_goldilocks>::init(int):
✓ Branch 38 → 39 taken 215 times.
✓ Branch 39 → 40 taken 215 times.
wala::fft::fft_core<wala::modnum<2013265921> >::init(int):
✓ Branch 38 → 39 taken 110 times.
✓ Branch 39 → 40 taken 110 times.
wala::fft::fft_core<wala::modnum<998244353> >::init(int):
✓ Branch 38 → 39 taken 212 times.
✓ Branch 39 → 40 taken 212 times.
|
5913 | rt.resize(2*k); inv_rt.resize(2*k); |
| 101 | 5913 | num z = getRoot<num>::f(2*k); | |
| 102 | 5913 | num iz = inv(z); | |
| 103 |
16/16wala::fft::fft_core<wala::fft::cplx<double> >::init(int):
✓ Branch 20 → 19 taken 12349525 times.
✓ Branch 20 → 21 taken 532 times.
✓ Branch 80 → 41 taken 2336 times.
✓ Branch 80 → 81 taken 186 times.
wala::fft::fft_core<wala::mod_goldilocks>::init(int):
✓ Branch 22 → 21 taken 12349525 times.
✓ Branch 22 → 23 taken 532 times.
✓ Branch 83 → 48 taken 2747 times.
✓ Branch 83 → 84 taken 215 times.
wala::fft::fft_core<wala::modnum<2013265921> >::init(int):
✓ Branch 22 → 21 taken 12349525 times.
✓ Branch 22 → 23 taken 532 times.
✓ Branch 83 → 48 taken 1389 times.
✓ Branch 83 → 84 taken 110 times.
wala::fft::fft_core<wala::modnum<998244353> >::init(int):
✓ Branch 22 → 21 taken 52099586 times.
✓ Branch 22 → 23 taken 3594 times.
✓ Branch 83 → 48 taken 2636 times.
✓ Branch 83 → 84 taken 212 times.
|
89163182 | for (int i = k/2; i < k; i++) { |
| 104 | 89157269 | rt[2*i] = rt[i], rt[2*i+1] = rt[i]*z; | |
| 105 | 89157269 | 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 | 24296060 | static int brev(int i, int n) { | |
| 112 |
8/16wala::fft::fft_core<wala::fft::cplx<double> >::brev(int, int):
✗ Branch 3 → 4 not taken.
✓ Branch 3 → 5 taken 7078 times.
✗ Branch 5 → 6 not taken.
✓ Branch 5 → 7 taken 7078 times.
wala::fft::fft_core<wala::mod_goldilocks>::brev(int, int):
✗ Branch 3 → 4 not taken.
✓ Branch 3 → 5 taken 2884 times.
✗ Branch 5 → 6 not taken.
✓ Branch 5 → 7 taken 2884 times.
wala::fft::fft_core<wala::modnum<2013265921> >::brev(int, int):
✗ Branch 3 → 4 not taken.
✓ Branch 3 → 5 taken 1442 times.
✗ Branch 5 → 6 not taken.
✓ Branch 5 → 7 taken 1442 times.
wala::fft::fft_core<wala::modnum<998244353> >::brev(int, int):
✗ Branch 3 → 4 not taken.
✓ Branch 3 → 5 taken 1516 times.
✗ Branch 5 → 6 not taken.
✓ Branch 5 → 7 taken 1516 times.
|
24296060 | int s = __builtin_ctz(unsigned(sz(rev)/n)); |
| 113 |
4/8wala::fft::fft_core<wala::fft::cplx<double> >::brev(int, int):
✗ Branch 10 → 11 not taken.
✓ Branch 10 → 12 taken 7078 times.
wala::fft::fft_core<wala::mod_goldilocks>::brev(int, int):
✗ Branch 10 → 11 not taken.
✓ Branch 10 → 12 taken 2884 times.
wala::fft::fft_core<wala::modnum<2013265921> >::brev(int, int):
✗ Branch 10 → 11 not taken.
✓ Branch 10 → 12 taken 1442 times.
wala::fft::fft_core<wala::modnum<998244353> >::brev(int, int):
✗ Branch 10 → 11 not taken.
✓ Branch 10 → 12 taken 1516 times.
|
24296060 | return rev[i] >> s; |
| 114 | } | ||
| 115 | // index of the conjugate evaluation point, in the returned bit-reversed order | ||
| 116 | 24771331 | static int conj_index(int j) { | |
| 117 |
14/18None:
✓ Branch 6 → 7 taken 24699094 times.
✓ Branch 6 → 8 taken 48 times.
wala::fft::fft_core<wala::fft::cplx<double> >::conj_index(int):
✓ Branch 2 → 3 taken 64907 times.
✓ Branch 2 → 6 taken 6064 times.
✗ Branch 3 → 4 not taken.
✓ Branch 3 → 5 taken 64907 times.
wala::fft::fft_core<wala::mod_goldilocks>::conj_index(int):
✓ Branch 2 → 3 taken 574 times.
✓ Branch 2 → 6 taken 35 times.
✗ Branch 3 → 4 not taken.
✓ Branch 3 → 5 taken 574 times.
wala::fft::fft_core<wala::modnum<2013265921> >::conj_index(int):
✓ Branch 2 → 3 taken 246 times.
✓ Branch 2 → 6 taken 15 times.
✗ Branch 3 → 4 not taken.
✓ Branch 3 → 5 taken 246 times.
wala::fft::fft_core<wala::modnum<998244353> >::conj_index(int):
✓ Branch 2 → 3 taken 328 times.
✓ Branch 2 → 6 taken 20 times.
✗ Branch 3 → 4 not taken.
✓ Branch 3 → 5 taken 328 times.
|
24771331 | return j == 0 ? 0 : j ^ ((1 << (31 - __builtin_clz(unsigned(j)))) - 1); |
| 118 | } | ||
| 119 | |||
| 120 | 4954710 | static void forward(std::span<num> a) { | |
| 121 | 4954710 | int n = sz(a); | |
| 122 |
16/16wala::fft::fft_core<wala::fft::cplx<double> >::forward(std::span<wala::fft::cplx<double>, 18446744073709551615ul>):
✓ Branch 2 → 3 taken 88 times.
✓ Branch 2 → 11 taken 8 times.
✓ Branch 3 → 4 taken 2147 times.
✓ Branch 3 → 45 taken 1017 times.
wala::fft::fft_core<wala::mod_goldilocks>::forward(std::span<wala::mod_goldilocks, 18446744073709551615ul>):
✓ Branch 2 → 3 taken 88 times.
✓ Branch 2 → 11 taken 8 times.
✓ Branch 3 → 4 taken 2955 times.
✓ Branch 3 → 46 taken 1613 times.
wala::fft::fft_core<wala::modnum<2013265921> >::forward(std::span<wala::modnum<2013265921>, 18446744073709551615ul>):
✓ Branch 2 → 3 taken 88 times.
✓ Branch 2 → 17 taken 8 times.
✓ Branch 3 → 4 taken 1932 times.
✓ Branch 3 → 46 taken 971 times.
wala::fft::fft_core<wala::modnum<998244353> >::forward(std::span<wala::modnum<998244353>, 18446744073709551615ul>):
✓ Branch 2 → 3 taken 3971660 times.
✓ Branch 2 → 17 taken 966405 times.
✓ Branch 3 → 4 taken 3972 times.
✓ Branch 3 → 46 taken 1750 times.
|
4954710 | if (n <= 1) return; |
| 123 | 3982930 | init(n); | |
| 124 |
16/16wala::fft::fft_core<wala::fft::cplx<double> >::forward(std::span<wala::fft::cplx<double>, 18446744073709551615ul>):
✓ Branch 10 → 8 taken 1152 times.
✓ Branch 10 → 11 taken 88 times.
✓ Branch 44 → 42 taken 7339 times.
✓ Branch 44 → 45 taken 2147 times.
wala::fft::fft_core<wala::mod_goldilocks>::forward(std::span<wala::mod_goldilocks, 18446744073709551615ul>):
✓ Branch 10 → 8 taken 1152 times.
✓ Branch 10 → 11 taken 88 times.
✓ Branch 45 → 43 taken 9604 times.
✓ Branch 45 → 46 taken 2955 times.
wala::fft::fft_core<wala::modnum<2013265921> >::forward(std::span<wala::modnum<2013265921>, 18446744073709551615ul>):
✓ Branch 16 → 14 taken 1152 times.
✓ Branch 16 → 17 taken 88 times.
✓ Branch 45 → 43 taken 6497 times.
✓ Branch 45 → 46 taken 1932 times.
wala::fft::fft_core<wala::modnum<998244353> >::forward(std::span<wala::modnum<998244353>, 18446744073709551615ul>):
✓ Branch 16 → 14 taken 7386837 times.
✓ Branch 16 → 17 taken 3971660 times.
✓ Branch 45 → 43 taken 13152 times.
✓ Branch 45 → 46 taken 3972 times.
|
11409815 | for (int k = n/2; k >= 1; k /= 2) { |
| 125 |
16/16wala::fft::fft_core<wala::fft::cplx<double> >::forward(std::span<wala::fft::cplx<double>, 18446744073709551615ul>):
✓ Branch 8 → 6 taken 49398188 times.
✓ Branch 8 → 9 taken 1152 times.
✓ Branch 42 → 40 taken 51261 times.
✓ Branch 42 → 43 taken 7339 times.
wala::fft::fft_core<wala::mod_goldilocks>::forward(std::span<wala::mod_goldilocks, 18446744073709551615ul>):
✓ Branch 8 → 6 taken 49398188 times.
✓ Branch 8 → 9 taken 1152 times.
✓ Branch 43 → 41 taken 68237 times.
✓ Branch 43 → 44 taken 9604 times.
wala::fft::fft_core<wala::modnum<2013265921> >::forward(std::span<wala::modnum<2013265921>, 18446744073709551615ul>):
✓ Branch 14 → 12 taken 49398188 times.
✓ Branch 14 → 15 taken 1152 times.
✓ Branch 43 → 41 taken 44954 times.
✓ Branch 43 → 44 taken 6497 times.
wala::fft::fft_core<wala::modnum<998244353> >::forward(std::span<wala::modnum<998244353>, 18446744073709551615ul>):
✓ Branch 14 → 12 taken 851840068 times.
✓ Branch 14 → 15 taken 7386837 times.
✓ Branch 43 → 41 taken 92592 times.
✓ Branch 43 → 44 taken 13152 times.
|
1007718561 | for (int i = 0; i < n; i += 2*k) { |
| 126 |
16/16wala::fft::fft_core<wala::fft::cplx<double> >::forward(std::span<wala::fft::cplx<double>, 18446744073709551615ul>):
✓ Branch 6 → 5 taken 493102494 times.
✓ Branch 6 → 7 taken 49398188 times.
✓ Branch 40 → 6 taken 152044 times.
✓ Branch 40 → 41 taken 51261 times.
wala::fft::fft_core<wala::mod_goldilocks>::forward(std::span<wala::mod_goldilocks, 18446744073709551615ul>):
✓ Branch 6 → 5 taken 493102494 times.
✓ Branch 6 → 7 taken 49398188 times.
✓ Branch 41 → 6 taken 207114 times.
✓ Branch 41 → 42 taken 68237 times.
wala::fft::fft_core<wala::modnum<2013265921> >::forward(std::span<wala::modnum<2013265921>, 18446744073709551615ul>):
✓ Branch 12 → 5 taken 493102494 times.
✓ Branch 12 → 13 taken 49398188 times.
✓ Branch 41 → 6 taken 133295 times.
✓ Branch 41 → 42 taken 44954 times.
wala::fft::fft_core<wala::modnum<998244353> >::forward(std::span<wala::modnum<998244353>, 18446744073709551615ul>):
✓ Branch 12 → 5 taken 7483865674 times.
✓ Branch 12 → 13 taken 851840068 times.
✓ Branch 41 → 6 taken 274884 times.
✓ Branch 41 → 42 taken 92592 times.
|
9964232169 | for (int j = 0; j < k; j++) { |
| 127 |
4/4wala::fft::fft_core<wala::modnum<2013265921> >::forward(std::span<wala::modnum<2013265921>, 18446744073709551615ul>):
✓ Branch 5 → 6 taken 287392187 times.
✓ Branch 5 → 7 taken 205710307 times.
wala::fft::fft_core<wala::modnum<998244353> >::forward(std::span<wala::modnum<998244353>, 18446744073709551615ul>):
✓ Branch 5 → 6 taken 4484325180 times.
✓ Branch 5 → 7 taken 2999540494 times.
|
8963940493 | num u = a[i+j], v = a[i+j+k]; |
| 128 | 8963940493 | a[i+j] = u + v; | |
| 129 |
4/4wala::fft::fft_core<wala::modnum<2013265921> >::forward(std::span<wala::modnum<2013265921>, 18446744073709551615ul>):
✓ Branch 8 → 9 taken 202208976 times.
✓ Branch 8 → 10 taken 290893518 times.
wala::fft::fft_core<wala::modnum<998244353> >::forward(std::span<wala::modnum<998244353>, 18446744073709551615ul>):
✓ Branch 8 → 9 taken 3046558443 times.
✓ Branch 8 → 10 taken 4437307231 times.
|
16940908661 | a[i+j+k] = (u - v) * rt[j+k]; |
| 130 | } | ||
| 131 | } | ||
| 132 | } | ||
| 133 | } | ||
| 134 | |||
| 135 | 3325879 | static void inverse(std::span<num> a) { | |
| 136 | 3325879 | int n = sz(a); | |
| 137 |
16/16wala::fft::fft_core<wala::fft::cplx<double> >::inverse(std::span<wala::fft::cplx<double>, 18446744073709551615ul>):
✓ Branch 2 → 3 taken 88 times.
✓ Branch 2 → 11 taken 8 times.
✓ Branch 3 → 4 taken 4328 times.
✓ Branch 3 → 47 taken 2882 times.
wala::fft::fft_core<wala::mod_goldilocks>::inverse(std::span<wala::mod_goldilocks, 18446744073709551615ul>):
✓ Branch 2 → 3 taken 44 times.
✓ Branch 2 → 11 taken 4 times.
✓ Branch 3 → 4 taken 2810 times.
✓ Branch 3 → 39 taken 1876 times.
wala::fft::fft_core<wala::modnum<2013265921> >::inverse(std::span<wala::modnum<2013265921>, 18446744073709551615ul>):
✓ Branch 2 → 3 taken 44 times.
✓ Branch 2 → 17 taken 4 times.
✓ Branch 3 → 4 taken 2101 times.
✓ Branch 3 → 39 taken 1428 times.
wala::fft::fft_core<wala::modnum<998244353> >::inverse(std::span<wala::modnum<998244353>, 18446744073709551615ul>):
✓ Branch 2 → 3 taken 2982525 times.
✓ Branch 2 → 17 taken 322208 times.
✓ Branch 3 → 4 taken 3522 times.
✓ Branch 3 → 39 taken 2007 times.
|
3325879 | if (n <= 1) return; |
| 138 | 2995462 | init(n); | |
| 139 |
16/16wala::fft::fft_core<wala::fft::cplx<double> >::inverse(std::span<wala::fft::cplx<double>, 18446744073709551615ul>):
✓ Branch 10 → 8 taken 1152 times.
✓ Branch 10 → 11 taken 88 times.
✓ Branch 46 → 44 taken 13654 times.
✓ Branch 46 → 47 taken 4328 times.
wala::fft::fft_core<wala::mod_goldilocks>::inverse(std::span<wala::mod_goldilocks, 18446744073709551615ul>):
✓ Branch 10 → 8 taken 576 times.
✓ Branch 10 → 11 taken 44 times.
✓ Branch 38 → 36 taken 8697 times.
✓ Branch 38 → 39 taken 2810 times.
wala::fft::fft_core<wala::modnum<2013265921> >::inverse(std::span<wala::modnum<2013265921>, 18446744073709551615ul>):
✓ Branch 16 → 14 taken 576 times.
✓ Branch 16 → 17 taken 44 times.
✓ Branch 38 → 36 taken 6574 times.
✓ Branch 38 → 39 taken 2101 times.
wala::fft::fft_core<wala::modnum<998244353> >::inverse(std::span<wala::modnum<998244353>, 18446744073709551615ul>):
✓ Branch 16 → 14 taken 7689138 times.
✓ Branch 16 → 17 taken 2982525 times.
✓ Branch 38 → 36 taken 11143 times.
✓ Branch 38 → 39 taken 3522 times.
|
10726972 | for (int k = 1; k < n; k *= 2) { |
| 140 |
16/16wala::fft::fft_core<wala::fft::cplx<double> >::inverse(std::span<wala::fft::cplx<double>, 18446744073709551615ul>):
✓ Branch 8 → 6 taken 49398188 times.
✓ Branch 8 → 9 taken 1152 times.
✓ Branch 44 → 42 taken 82520 times.
✓ Branch 44 → 45 taken 13654 times.
wala::fft::fft_core<wala::mod_goldilocks>::inverse(std::span<wala::mod_goldilocks, 18446744073709551615ul>):
✓ Branch 8 → 6 taken 24699094 times.
✓ Branch 8 → 9 taken 576 times.
✓ Branch 36 → 34 taken 54566 times.
✓ Branch 36 → 37 taken 8697 times.
wala::fft::fft_core<wala::modnum<2013265921> >::inverse(std::span<wala::modnum<2013265921>, 18446744073709551615ul>):
✓ Branch 14 → 12 taken 24699094 times.
✓ Branch 14 → 15 taken 576 times.
✓ Branch 36 → 34 taken 39293 times.
✓ Branch 36 → 37 taken 6574 times.
wala::fft::fft_core<wala::modnum<998244353> >::inverse(std::span<wala::modnum<998244353>, 18446744073709551615ul>):
✓ Branch 14 → 12 taken 653261465 times.
✓ Branch 14 → 15 taken 7689138 times.
✓ Branch 36 → 34 taken 71282 times.
✓ Branch 36 → 37 taken 11143 times.
|
760037012 | for (int i = 0; i < n; i += 2*k) { |
| 141 |
16/16wala::fft::fft_core<wala::fft::cplx<double> >::inverse(std::span<wala::fft::cplx<double>, 18446744073709551615ul>):
✓ Branch 6 → 5 taken 493102494 times.
✓ Branch 6 → 7 taken 49398188 times.
✓ Branch 42 → 6 taken 233234 times.
✓ Branch 42 → 43 taken 82520 times.
wala::fft::fft_core<wala::mod_goldilocks>::inverse(std::span<wala::mod_goldilocks, 18446744073709551615ul>):
✓ Branch 6 → 5 taken 246551247 times.
✓ Branch 6 → 7 taken 24699094 times.
✓ Branch 34 → 6 taken 158732 times.
✓ Branch 34 → 35 taken 54566 times.
wala::fft::fft_core<wala::modnum<2013265921> >::inverse(std::span<wala::modnum<2013265921>, 18446744073709551615ul>):
✓ Branch 12 → 5 taken 246551247 times.
✓ Branch 12 → 13 taken 24699094 times.
✓ Branch 34 → 6 taken 110705 times.
✓ Branch 34 → 35 taken 39293 times.
wala::fft::fft_core<wala::modnum<998244353> >::inverse(std::span<wala::modnum<998244353>, 18446744073709551615ul>):
✓ Branch 12 → 5 taken 5576156571 times.
✓ Branch 12 → 13 taken 653261465 times.
✓ Branch 34 → 6 taken 205910 times.
✓ Branch 34 → 35 taken 71282 times.
|
7315375642 | for (int j = 0; j < k; j++) { |
| 142 |
4/4wala::fft::fft_core<wala::modnum<2013265921> >::inverse(std::span<wala::modnum<2013265921>, 18446744073709551615ul>):
✓ Branch 5 → 6 taken 111992701 times.
✓ Branch 5 → 7 taken 134558546 times.
wala::fft::fft_core<wala::modnum<998244353> >::inverse(std::span<wala::modnum<998244353>, 18446744073709551615ul>):
✓ Branch 5 → 6 taken 2522586409 times.
✓ Branch 5 → 7 taken 3053570162 times.
|
6563070140 | num t = inv_rt[j+k] * a[i+j+k]; |
| 143 |
4/4wala::fft::fft_core<wala::modnum<2013265921> >::inverse(std::span<wala::modnum<2013265921>, 18446744073709551615ul>):
✓ Branch 5 → 6 taken 111992701 times.
✓ Branch 5 → 7 taken 134558546 times.
wala::fft::fft_core<wala::modnum<998244353> >::inverse(std::span<wala::modnum<998244353>, 18446744073709551615ul>):
✓ Branch 5 → 6 taken 2522586409 times.
✓ Branch 5 → 7 taken 3053570162 times.
|
6563070140 | a[i+j+k] = a[i+j] - t; |
| 144 |
4/4wala::fft::fft_core<wala::modnum<2013265921> >::inverse(std::span<wala::modnum<2013265921>, 18446744073709551615ul>):
✓ Branch 8 → 9 taken 133348118 times.
✓ Branch 8 → 10 taken 113203129 times.
wala::fft::fft_core<wala::modnum<998244353> >::inverse(std::span<wala::modnum<998244353>, 18446744073709551615ul>):
✓ Branch 8 → 9 taken 3013307863 times.
✓ Branch 8 → 10 taken 2562848708 times.
|
12385777958 | 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/4wala::fft::fft_core<wala::fft::cplx<double> >::extend(std::span<wala::fft::cplx<double>, 18446744073709551615ul>, std::span<wala::fft::cplx<double> const, 18446744073709551615ul>):
✓ Branch 8 → 9 taken 19 times.
wala::fft::fft_core<wala::mod_goldilocks>::extend(std::span<wala::mod_goldilocks, 18446744073709551615ul>, std::span<wala::mod_goldilocks const, 18446744073709551615ul>):
✓ Branch 8 → 9 taken 280 times.
wala::fft::fft_core<wala::modnum<2013265921> >::extend(std::span<wala::modnum<2013265921>, 18446744073709551615ul>, std::span<wala::modnum<2013265921> const, 18446744073709551615ul>):
✓ Branch 8 → 9 taken 10 times.
wala::fft::fft_core<wala::modnum<998244353> >::extend(std::span<wala::modnum<998244353>, 18446744073709551615ul>, std::span<wala::modnum<998244353> const, 18446744073709551615ul>):
✓ Branch 8 → 9 taken 505 times.
|
2294094 | init(sz(t)); |
| 156 |
1/8wala::fft::fft_core<wala::fft::cplx<double> >::extend(std::span<wala::fft::cplx<double>, 18446744073709551615ul>, std::span<wala::fft::cplx<double> const, 18446744073709551615ul>):
✗ Branch 5 → 6 not taken.
✗ Branch 5 → 7 not taken.
wala::fft::fft_core<wala::mod_goldilocks>::extend(std::span<wala::mod_goldilocks, 18446744073709551615ul>, std::span<wala::mod_goldilocks const, 18446744073709551615ul>):
✗ Branch 5 → 6 not taken.
✗ Branch 5 → 7 not taken.
wala::fft::fft_core<wala::modnum<2013265921> >::extend(std::span<wala::modnum<2013265921>, 18446744073709551615ul>, std::span<wala::modnum<2013265921> const, 18446744073709551615ul>):
✗ Branch 5 → 6 not taken.
✗ Branch 5 → 7 not taken.
wala::fft::fft_core<wala::modnum<998244353> >::extend(std::span<wala::modnum<998244353>, 18446744073709551615ul>, std::span<wala::modnum<998244353> const, 18446744073709551615ul>):
✗ Branch 5 → 6 not taken.
✓ Branch 5 → 7 taken 2293280 times.
|
2294094 | auto b = t.subspan(n, n); |
| 157 | 2294094 | int lo = min(sz(coeffs), n); | |
| 158 |
10/16wala::fft::fft_core<wala::fft::cplx<double> >::extend(std::span<wala::fft::cplx<double>, 18446744073709551615ul>, std::span<wala::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.
wala::fft::fft_core<wala::mod_goldilocks>::extend(std::span<wala::mod_goldilocks, 18446744073709551615ul>, std::span<wala::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.
wala::fft::fft_core<wala::modnum<2013265921> >::extend(std::span<wala::modnum<2013265921>, 18446744073709551615ul>, std::span<wala::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.
wala::fft::fft_core<wala::modnum<998244353> >::extend(std::span<wala::modnum<998244353>, 18446744073709551615ul>, std::span<wala::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.
|
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/16wala::fft::fft_core<wala::fft::cplx<double> >::extend(std::span<wala::fft::cplx<double>, 18446744073709551615ul>, std::span<wala::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.
wala::fft::fft_core<wala::mod_goldilocks>::extend(std::span<wala::mod_goldilocks, 18446744073709551615ul>, std::span<wala::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.
wala::fft::fft_core<wala::modnum<2013265921> >::extend(std::span<wala::modnum<2013265921>, 18446744073709551615ul>, std::span<wala::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.
wala::fft::fft_core<wala::modnum<998244353> >::extend(std::span<wala::modnum<998244353>, 18446744073709551615ul>, std::span<wala::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.
|
3942335 | for (int i = n; i < sz(coeffs); i++) { |
| 164 |
2/4wala::fft::fft_core<wala::modnum<2013265921> >::extend(std::span<wala::modnum<2013265921>, 18446744073709551615ul>, std::span<wala::modnum<2013265921> const, 18446744073709551615ul>):
✗ Branch 13 → 14 not taken.
✗ Branch 13 → 15 not taken.
wala::fft::fft_core<wala::modnum<998244353> >::extend(std::span<wala::modnum<998244353>, 18446744073709551615ul>, std::span<wala::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/4wala::fft::fft_core<wala::fft::cplx<double> >::extend(std::span<wala::fft::cplx<double>, 18446744073709551615ul>, std::span<wala::fft::cplx<double> const, 18446744073709551615ul>):
✓ Branch 100 → 101 taken 19 times.
wala::fft::fft_core<wala::mod_goldilocks>::extend(std::span<wala::mod_goldilocks, 18446744073709551615ul>, std::span<wala::mod_goldilocks const, 18446744073709551615ul>):
✓ Branch 95 → 96 taken 280 times.
wala::fft::fft_core<wala::modnum<2013265921> >::extend(std::span<wala::modnum<2013265921>, 18446744073709551615ul>, std::span<wala::modnum<2013265921> const, 18446744073709551615ul>):
✓ Branch 95 → 96 taken 10 times.
wala::fft::fft_core<wala::modnum<998244353> >::extend(std::span<wala::modnum<998244353>, 18446744073709551615ul>, std::span<wala::modnum<998244353> const, 18446744073709551615ul>):
✓ Branch 95 → 96 taken 505 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 | 2740 | static void even_half(std::span<const num> t, std::span<num> out) { | |
| 172 | 2740 | int n = sz(out); | |
| 173 | 2740 | assert(sz(t) >= 2*n); | |
| 174 | 3564 | num half = inv(num(2)); | |
| 175 |
12/12wala::fft::fft_core<wala::fft::cplx<double> >::even_half(std::span<wala::fft::cplx<double> const, 18446744073709551615ul>, std::span<wala::fft::cplx<double>, 18446744073709551615ul>):
✓ Branch 30 → 12 taken 4456 times.
✓ Branch 30 → 31 taken 396 times.
wala::fft::fft_core<wala::mod_goldilocks>::even_half(std::span<wala::mod_goldilocks const, 18446744073709551615ul>, std::span<wala::mod_goldilocks, 18446744073709551615ul>):
✓ Branch 35 → 18 taken 4620 times.
✓ Branch 35 → 36 taken 402 times.
wala::fft::fft_core<wala::modnum<2013265921> >::even_half(std::span<wala::modnum<2013265921> const, 18446744073709551615ul>, std::span<wala::modnum<2013265921>, 18446744073709551615ul>):
✓ Branch 35 → 18 taken 2310 times.
✓ Branch 35 → 36 taken 201 times.
wala::fft::fft_core<wala::modnum<998244353> >::even_half(std::span<wala::modnum<998244353> const, 18446744073709551615ul>, std::span<wala::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 3540 times.
✓ Branch 35 → 36 taken 221 times.
|
147568776 | for (int j = 0; j < n; j++) out[j] = (t[2*j] + t[2*j+1]) * half; |
| 176 | 2740 | } | |
| 177 | 933 | static void odd_half(std::span<const num> t, std::span<num> out) { | |
| 178 | 933 | int n = sz(out); | |
| 179 | 933 | assert(sz(t) >= 2*n); | |
| 180 |
4/4wala::fft::fft_core<wala::fft::cplx<double> >::odd_half(std::span<wala::fft::cplx<double> const, 18446744073709551615ul>, std::span<wala::fft::cplx<double>, 18446744073709551615ul>):
✓ Branch 6 → 7 taken 204 times.
wala::fft::fft_core<wala::mod_goldilocks>::odd_half(std::span<wala::mod_goldilocks const, 18446744073709551615ul>, std::span<wala::mod_goldilocks, 18446744073709551615ul>):
✓ Branch 6 → 7 taken 210 times.
wala::fft::fft_core<wala::modnum<2013265921> >::odd_half(std::span<wala::modnum<2013265921> const, 18446744073709551615ul>, std::span<wala::modnum<2013265921>, 18446744073709551615ul>):
✓ Branch 6 → 7 taken 105 times.
wala::fft::fft_core<wala::modnum<998244353> >::odd_half(std::span<wala::modnum<998244353> const, 18446744073709551615ul>, std::span<wala::modnum<998244353>, 18446744073709551615ul>):
✓ Branch 6 → 7 taken 108 times.
|
933 | init(2*n); |
| 181 | 1356 | num half = inv(num(2)); | |
| 182 |
10/10wala::fft::fft_core<wala::fft::cplx<double> >::odd_half(std::span<wala::fft::cplx<double> const, 18446744073709551615ul>, std::span<wala::fft::cplx<double>, 18446744073709551615ul>):
✓ Branch 37 → 13 taken 2392 times.
✓ Branch 37 → 38 taken 204 times.
wala::fft::fft_core<wala::mod_goldilocks>::odd_half(std::span<wala::mod_goldilocks const, 18446744073709551615ul>, std::span<wala::mod_goldilocks, 18446744073709551615ul>):
✓ Branch 43 → 19 taken 2556 times.
✓ Branch 43 → 44 taken 210 times.
wala::fft::fft_core<wala::modnum<2013265921> >::odd_half(std::span<wala::modnum<2013265921> const, 18446744073709551615ul>, std::span<wala::modnum<2013265921>, 18446744073709551615ul>):
✓ Branch 43 → 19 taken 1278 times.
✓ Branch 43 → 44 taken 105 times.
wala::fft::fft_core<wala::modnum<998244353> >::odd_half(std::span<wala::modnum<998244353> const, 18446744073709551615ul>, std::span<wala::modnum<998244353>, 18446744073709551615ul>):
✓ Branch 11 → 7 taken 24283140 times.
✓ Branch 11 → 12 taken 306 times.
✓ Branch 43 → 19 taken 1352 times.
✓ Branch 43 → 44 taken 108 times.
|
24291651 | 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.
|
48573858 | out[j] = (t[2*j] - t[2*j+1]) * half * inv_rt[n + brev(j, n)]; |
| 185 | } | ||
| 186 | 933 | } | |
| 187 | 3667 | static void downsample(std::span<const num> t, std::span<num> out, bool odd) { | |
| 188 |
8/8wala::fft::fft_core<wala::fft::cplx<double> >::downsample(std::span<wala::fft::cplx<double> const, 18446744073709551615ul>, std::span<wala::fft::cplx<double>, 18446744073709551615ul>, bool):
✓ Branch 2 → 3 taken 204 times.
✓ Branch 2 → 4 taken 396 times.
wala::fft::fft_core<wala::mod_goldilocks>::downsample(std::span<wala::mod_goldilocks const, 18446744073709551615ul>, std::span<wala::mod_goldilocks, 18446744073709551615ul>, bool):
✓ Branch 2 → 3 taken 210 times.
✓ Branch 2 → 4 taken 402 times.
wala::fft::fft_core<wala::modnum<2013265921> >::downsample(std::span<wala::modnum<2013265921> const, 18446744073709551615ul>, std::span<wala::modnum<2013265921>, 18446744073709551615ul>, bool):
✓ Branch 2 → 3 taken 105 times.
✓ Branch 2 → 4 taken 201 times.
wala::fft::fft_core<wala::modnum<998244353> >::downsample(std::span<wala::modnum<998244353> const, 18446744073709551615ul>, std::span<wala::modnum<998244353>, 18446744073709551615ul>, bool):
✓ Branch 2 → 3 taken 411 times.
✓ Branch 2 → 4 taken 1738 times.
|
3667 | if (odd) odd_half(t, out); |
| 189 | 2737 | else even_half(t, out); | |
| 190 | 3667 | } | |
| 191 | |||
| 192 | 640 | static void upsample_as_evens(std::span<const num> t, std::span<num> out) { | |
| 193 | 640 | int n = sz(out); | |
| 194 | 640 | assert(2 * sz(t) >= n); | |
| 195 |
10/10wala::fft::fft_core<wala::fft::cplx<double> >::upsample_as_evens(std::span<wala::fft::cplx<double> const, 18446744073709551615ul>, std::span<wala::fft::cplx<double>, 18446744073709551615ul>):
✓ Branch 14 → 6 taken 492 times.
✓ Branch 14 → 15 taken 9 times.
wala::fft::fft_core<wala::mod_goldilocks>::upsample_as_evens(std::span<wala::mod_goldilocks const, 18446744073709551615ul>, std::span<wala::mod_goldilocks, 18446744073709551615ul>):
✓ Branch 14 → 6 taken 656 times.
✓ Branch 14 → 15 taken 12 times.
wala::fft::fft_core<wala::modnum<2013265921> >::upsample_as_evens(std::span<wala::modnum<2013265921> const, 18446744073709551615ul>, std::span<wala::modnum<2013265921>, 18446744073709551615ul>):
✓ Branch 14 → 6 taken 328 times.
✓ Branch 14 → 15 taken 6 times.
wala::fft::fft_core<wala::modnum<998244353> >::upsample_as_evens(std::span<wala::modnum<998244353> const, 18446744073709551615ul>, std::span<wala::modnum<998244353>, 18446744073709551615ul>):
✓ Branch 5 → 4 taken 133662464 times.
✓ Branch 5 → 6 taken 590 times.
✓ Branch 14 → 6 taken 2640 times.
✓ Branch 14 → 15 taken 23 times.
|
133667220 | for (int j = 0; j < n; j++) out[j] = t[j>>1]; |
| 196 | 640 | } | |
| 197 | // TODO: We could just implement a generic "cyclic-shift" primitive; at least we should make it not involve brev | ||
| 198 | 33 | static void upsample_as_odds(std::span<const num> t, std::span<num> out) { | |
| 199 | 33 | int n = sz(out); | |
| 200 | 33 | assert(n >= 2); | |
| 201 | 33 | assert(sz(t) >= n / 2); | |
| 202 | 33 | init(n); | |
| 203 |
8/10wala::fft::fft_core<wala::fft::cplx<double> >::upsample_as_odds(std::span<wala::fft::cplx<double> const, 18446744073709551615ul>, std::span<wala::fft::cplx<double>, 18446744073709551615ul>):
✓ Branch 34 → 10 taken 246 times.
✓ Branch 34 → 35 taken 9 times.
wala::fft::fft_core<wala::mod_goldilocks>::upsample_as_odds(std::span<wala::mod_goldilocks const, 18446744073709551615ul>, std::span<wala::mod_goldilocks, 18446744073709551615ul>):
✓ Branch 33 → 10 taken 328 times.
✓ Branch 33 → 34 taken 12 times.
wala::fft::fft_core<wala::modnum<2013265921> >::upsample_as_odds(std::span<wala::modnum<2013265921> const, 18446744073709551615ul>, std::span<wala::modnum<2013265921>, 18446744073709551615ul>):
✓ Branch 33 → 10 taken 164 times.
✓ Branch 33 → 34 taken 6 times.
wala::fft::fft_core<wala::modnum<998244353> >::upsample_as_odds(std::span<wala::modnum<998244353> const, 18446744073709551615ul>, std::span<wala::modnum<998244353>, 18446744073709551615ul>):
✗ Branch 10 → 8 not taken.
✗ Branch 10 → 11 not taken.
✓ Branch 33 → 10 taken 164 times.
✓ Branch 33 → 34 taken 6 times.
|
935 | for (int j = 0; j < n/2; j++) { |
| 204 | 902 | num v = t[j] * rt[n/2 + brev(j, n/2)]; | |
| 205 | 902 | out[2*j+0] = v; | |
| 206 | 1558 | out[2*j+1] = -v; | |
| 207 | } | ||
| 208 | 33 | } | |
| 209 | 673 | static void upsample(std::span<const num> t, std::span<num> out, bool odd) { | |
| 210 |
8/8wala::fft::fft_core<wala::fft::cplx<double> >::upsample(std::span<wala::fft::cplx<double> const, 18446744073709551615ul>, std::span<wala::fft::cplx<double>, 18446744073709551615ul>, bool):
✓ Branch 2 → 3 taken 9 times.
✓ Branch 2 → 4 taken 9 times.
wala::fft::fft_core<wala::mod_goldilocks>::upsample(std::span<wala::mod_goldilocks const, 18446744073709551615ul>, std::span<wala::mod_goldilocks, 18446744073709551615ul>, bool):
✓ Branch 2 → 3 taken 12 times.
✓ Branch 2 → 4 taken 12 times.
wala::fft::fft_core<wala::modnum<2013265921> >::upsample(std::span<wala::modnum<2013265921> const, 18446744073709551615ul>, std::span<wala::modnum<2013265921>, 18446744073709551615ul>, bool):
✓ Branch 2 → 3 taken 6 times.
✓ Branch 2 → 4 taken 6 times.
wala::fft::fft_core<wala::modnum<998244353> >::upsample(std::span<wala::modnum<998244353> const, 18446744073709551615ul>, std::span<wala::modnum<998244353>, 18446744073709551615ul>, bool):
✓ Branch 2 → 3 taken 6 times.
✓ Branch 2 → 4 taken 613 times.
|
673 | if (odd) upsample_as_odds(t, out); |
| 211 | 640 | else upsample_as_evens(t, out); | |
| 212 | 673 | } | |
| 213 | }; | ||
| 214 | |||
| 215 | } // namespace wala::fft | ||
| 216 |