fft/series.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include <algorithm> | ||
| 4 | #include <cassert> | ||
| 5 | #include <cstdint> | ||
| 6 | #include <span> | ||
| 7 | #include <utility> | ||
| 8 | #include <vector> | ||
| 9 | |||
| 10 | #include "fft/series_core.hpp" | ||
| 11 | |||
| 12 | // ==== analytic ops ==== | ||
| 13 | // Free functions over series-like operands; each borrows the operand's span | ||
| 14 | // and writes a fresh result. | ||
| 15 | // TODO: reuse/populate the operands' whole/prefix transform caches | ||
| 16 | |||
| 17 | namespace ecnerwala::series { | ||
| 18 | |||
| 19 | template <like S> | ||
| 20 | ✗ | vec<typename S::engine_t, S::exact_v> stretch(const S& a_, int n) { | |
| 21 | using E = typename S::engine_t; | ||
| 22 | ✗ | span<E, S::exact_v> a = a_; | |
| 23 | ✗ | vec<E, S::exact_v> r(size_t(a.len())); | |
| 24 | ✗ | for (int i = 0; i*n < a.len(); i++) { | |
| 25 | ✗ | r[i*n] = a[i]; | |
| 26 | } | ||
| 27 | ✗ | return r; | |
| 28 | } | ||
| 29 | template <like S> | ||
| 30 |
1/2✗ Branch 2 → 3 not taken.
✓ Branch 2 → 4 taken 1198 times.
|
1277 | vec<typename S::engine_t, S::exact_v> deriv_shift(const S& a_) { |
| 31 | using E = typename S::engine_t; | ||
| 32 | 79 | span<E, S::exact_v> a = a_; | |
| 33 | 1514 | vec<E, S::exact_v> r(a.begin(), a.end()); | |
| 34 |
5/6✗ Branch 10 → 11 not taken.
✓ Branch 10 → 12 taken 35770340 times.
✓ Branch 12 → 6 taken 35769142 times.
✓ Branch 12 → 13 taken 1198 times.
✓ Branch 36 → 19 taken 938 times.
✓ Branch 36 → 37 taken 79 times.
|
35772374 | for (int i = 0; i < r.len(); i++) { |
| 35 | 35771018 | r[i] *= i; | |
| 36 | } | ||
| 37 | 1277 | return r; | |
| 38 | } | ||
| 39 | template <like S> | ||
| 40 |
1/2✗ Branch 2 → 3 not taken.
✓ Branch 2 → 4 taken 42 times.
|
53 | vec<typename S::engine_t, S::exact_v> integ_shift(const S& a_) { |
| 41 | using E = typename S::engine_t; | ||
| 42 | using T = typename E::value_type; | ||
| 43 |
1/2✗ Branch 4 → 5 not taken.
✓ Branch 4 → 6 taken 42 times.
|
53 | span<E, S::exact_v> a = a_; |
| 44 | 75 | assert(a[0] == 0); | |
| 45 | 86 | vec<E, S::exact_v> r(a.begin(), a.end()); | |
| 46 | 53 | T f = 1; | |
| 47 |
5/6✗ Branch 12 → 13 not taken.
✓ Branch 12 → 14 taken 10144480 times.
✓ Branch 14 → 8 taken 10144438 times.
✓ Branch 14 → 15 taken 42 times.
✓ Branch 56 → 38 taken 249 times.
✓ Branch 56 → 57 taken 11 times.
|
10145000 | for (int i = 1; i < r.len(); i++) { |
| 48 |
1/2✗ Branch 8 → 9 not taken.
✓ Branch 8 → 10 taken 10144438 times.
|
10144687 | r[i] *= f; |
| 49 | 10144936 | f *= i; | |
| 50 | } | ||
| 51 | 64 | f = inv(f); | |
| 52 |
4/4✓ Branch 18 → 17 taken 10144438 times.
✓ Branch 18 → 19 taken 42 times.
✓ Branch 84 → 72 taken 249 times.
✓ Branch 84 → 85 taken 11 times.
|
10144740 | for (int i = r.len() - 1; i > 0; i--) { |
| 53 | 10144687 | r[i] *= f; | |
| 54 | 10144936 | f *= i; | |
| 55 | } | ||
| 56 | 53 | return r; | |
| 57 | } | ||
| 58 | template <like S> | ||
| 59 |
1/2✗ Branch 2 → 3 not taken.
✓ Branch 2 → 4 taken 578 times.
|
612 | vec<typename S::engine_t, S::exact_v> integ_shift_offset(const S& a_, int offset) { |
| 60 | using E = typename S::engine_t; | ||
| 61 | using T = typename E::value_type; | ||
| 62 | 612 | span<E, S::exact_v> a = a_; | |
| 63 | 748 | vec<E, S::exact_v> r(a.begin(), a.end()); | |
| 64 | 612 | T f = 1; | |
| 65 |
5/6✗ Branch 10 → 11 not taken.
✓ Branch 10 → 12 taken 10645015 times.
✓ Branch 12 → 6 taken 10644437 times.
✓ Branch 12 → 13 taken 578 times.
✓ Branch 41 → 23 taken 249 times.
✓ Branch 41 → 42 taken 34 times.
|
10645581 | for (int i = 0; i < r.len(); i++) { |
| 66 |
1/2✗ Branch 6 → 7 not taken.
✓ Branch 6 → 8 taken 10644437 times.
|
10644686 | r[i] *= f; |
| 67 |
1/2✗ Branch 6 → 7 not taken.
✓ Branch 6 → 8 taken 10644437 times.
|
21289372 | f *= i + offset; |
| 68 | } | ||
| 69 | 646 | assert(f != 0); | |
| 70 | 646 | f = inv(f); | |
| 71 |
4/4✓ Branch 21 → 17 taken 10644437 times.
✓ Branch 21 → 22 taken 578 times.
✓ Branch 78 → 66 taken 249 times.
✓ Branch 78 → 79 taken 34 times.
|
10645298 | for (int i = r.len() - 1; i >= 0; i--) { |
| 72 |
1/2✗ Branch 17 → 18 not taken.
✓ Branch 17 → 19 taken 10644437 times.
|
10644686 | r[i] *= f; |
| 73 |
1/2✗ Branch 17 → 18 not taken.
✓ Branch 17 → 19 taken 10644437 times.
|
21289372 | f *= i + offset; |
| 74 | } | ||
| 75 | 612 | return r; | |
| 76 | } | ||
| 77 | template <trunc_like S> | ||
| 78 | 53 | trunc<typename S::engine_t> deriv_shift_log(const S& a) { | |
| 79 |
4/4✓ Branch 3 → 4 taken 53 times.
✓ Branch 4 → 5 taken 42 times.
✓ Branch 6 → 7 taken 11 times.
✓ Branch 10 → 11 taken 11 times.
|
117 | return deriv_shift(a) * ps_inv(a); |
| 80 | } | ||
| 81 | template <trunc_like S> | ||
| 82 |
1/2✗ Branch 2 → 3 not taken.
✓ Branch 2 → 4 taken 42 times.
|
53 | trunc<typename S::engine_t> ps_log(const S& a) { |
| 83 | 64 | assert(a[0] == 1); | |
| 84 |
3/3✓ Branch 5 → 6 taken 42 times.
✓ Branch 17 → 18 taken 11 times.
✓ Branch 21 → 22 taken 11 times.
|
106 | return integ_shift(deriv_shift_log(a)); |
| 85 | } | ||
| 86 | template <trunc_like S> | ||
| 87 |
1/2✗ Branch 2 → 3 not taken.
✓ Branch 2 → 4 taken 43 times.
|
54 | trunc<typename S::engine_t> ps_exp(const S& a_) { |
| 88 | // See https://mathexp.eu/bostan/publications/BoSc09a.pdf for details | ||
| 89 | using E = typename S::engine_t; | ||
| 90 | using T = typename E::value_type; | ||
| 91 |
1/2✗ Branch 4 → 5 not taken.
✓ Branch 4 → 6 taken 43 times.
|
54 | span<E, false> a = a_; |
| 92 | 54 | assert(a.len() >= 1); | |
| 93 | 76 | assert(a[0] == 0); | |
| 94 |
2/2✓ Branch 9 → 10 taken 43 times.
✓ Branch 42 → 43 taken 11 times.
|
87 | trunc<E> r(1, T(1)); r.reserve(size_t(a.len())); |
| 95 |
3/3✓ Branch 10 → 11 taken 43 times.
✓ Branch 11 → 59 taken 43 times.
✓ Branch 59 → 449 taken 11 times.
|
87 | trunc<E> invR(1, T(1)); invR.reserve(size_t(a.len())); |
| 96 |
5/6✗ Branch 59 → 60 not taken.
✓ Branch 59 → 61 taken 621 times.
✓ Branch 61 → 12 taken 578 times.
✓ Branch 61 → 62 taken 43 times.
✓ Branch 459 → 60 taken 34 times.
✓ Branch 459 → 460 taken 11 times.
|
824 | while (r.len() < a.len()) { |
| 97 | 612 | int o_sz = r.len(); | |
| 98 |
1/1✓ Branch 12 → 13 taken 578 times.
|
646 | int n_sz = std::min(o_sz * 2, a.len()); |
| 99 |
4/5✓ Branch 12 → 13 taken 578 times.
✓ Branch 13 → 14 taken 578 times.
✗ Branch 15 → 16 not taken.
✓ Branch 15 → 17 taken 578 times.
✓ Branch 105 → 106 taken 34 times.
|
1360 | trunc<E> t = deriv_shift(trunc<E>(a.begin(), a.begin() + o_sz)); |
| 100 |
3/4✗ Branch 17 → 18 not taken.
✓ Branch 17 → 19 taken 578 times.
✓ Branch 19 → 20 taken 578 times.
✓ Branch 134 → 135 taken 34 times.
|
612 | fft::multiply_circular<E>(std::span<const T>(t), std::span<const T>(r).first(o_sz), std::span<T>(t), o_sz); |
| 101 |
4/4✓ Branch 20 → 21 taken 578 times.
✓ Branch 21 → 22 taken 578 times.
✓ Branch 140 → 141 taken 34 times.
✓ Branch 142 → 143 taken 34 times.
|
1292 | t = deriv_shift(r) - t; |
| 102 |
2/2✓ Branch 25 → 26 taken 578 times.
✓ Branch 186 → 187 taken 34 times.
|
612 | t *= invR; |
| 103 |
2/2✓ Branch 26 → 27 taken 578 times.
✓ Branch 187 → 188 taken 34 times.
|
612 | t.resize(size_t(n_sz - o_sz)); |
| 104 |
2/2✓ Branch 27 → 28 taken 578 times.
✓ Branch 28 → 29 taken 578 times.
|
782 | trunc<E> v(a.begin() + o_sz, a.begin() + n_sz); |
| 105 |
4/4✓ Branch 28 → 29 taken 578 times.
✓ Branch 29 → 30 taken 578 times.
✓ Branch 227 → 228 taken 34 times.
✓ Branch 229 → 230 taken 34 times.
|
646 | v -= integ_shift_offset(t, o_sz); |
| 106 |
2/2✓ Branch 31 → 32 taken 578 times.
✓ Branch 248 → 249 taken 34 times.
|
612 | v *= r; |
| 107 |
2/2✓ Branch 32 → 33 taken 578 times.
✓ Branch 250 → 251 taken 34 times.
|
612 | r.resize(size_t(n_sz)); |
| 108 |
2/3✗ Branch 34 → 35 not taken.
✓ Branch 34 → 36 taken 578 times.
✓ Branch 262 → 263 taken 34 times.
|
782 | std::copy(v.begin(), v.end(), r.begin() + o_sz); |
| 109 |
4/4✓ Branch 36 → 37 taken 537 times.
✓ Branch 36 → 56 taken 41 times.
✓ Branch 323 → 324 taken 25 times.
✓ Branch 323 → 413 taken 9 times.
|
646 | if (r.len() < a.len()) { |
| 110 | // double invR via a Newton step | ||
| 111 | 587 | assert(r.len() == 2 * invR.len()); | |
| 112 | 562 | int n = invR.len(); | |
| 113 | 562 | int nn = r.len(); | |
| 114 |
2/3✓ Branch 41 → 42 taken 537 times.
✗ Branch 42 → 43 not taken.
✓ Branch 42 → 44 taken 537 times.
|
587 | trunc<E> tmp(size_t(4) * n); |
| 115 |
4/6✗ Branch 44 → 45 not taken.
✓ Branch 44 → 46 taken 537 times.
✓ Branch 46 → 47 taken 537 times.
✗ Branch 47 → 48 not taken.
✓ Branch 47 → 49 taken 537 times.
✓ Branch 362 → 363 taken 25 times.
|
562 | fft::square<E>(std::span<const T>(invR).first(n), std::span<T>(tmp)); |
| 116 |
3/4✗ Branch 47 → 48 not taken.
✓ Branch 47 → 49 taken 537 times.
✓ Branch 49 → 50 taken 537 times.
✓ Branch 375 → 376 taken 25 times.
|
562 | fft::multiply<E>(std::span<const T>(tmp).first(nn), std::span<const T>(r).first(nn), std::span<T>(tmp)); |
| 117 |
2/2✓ Branch 50 → 53 taken 537 times.
✓ Branch 379 → 394 taken 25 times.
|
562 | invR.resize(size_t(nn)); |
| 118 |
4/4✓ Branch 53 → 51 taken 6406145 times.
✓ Branch 53 → 54 taken 537 times.
✓ Branch 394 → 380 taken 165 times.
✓ Branch 394 → 395 taken 25 times.
|
6406872 | for (int i = n; i < nn; i++) invR[i] = -tmp[i]; |
| 119 | 562 | } | |
| 120 | } | ||
| 121 | 65 | return r; | |
| 122 | 54 | } | |
| 123 | template <trunc_like S> | ||
| 124 |
1/2✗ Branch 2 → 3 not taken.
✓ Branch 2 → 4 taken 17 times.
|
23 | trunc<typename S::engine_t> ps_pow_monic(const S& a_, typename S::engine_t::value_type k) { |
| 125 | using E = typename S::engine_t; | ||
| 126 |
1/2✗ Branch 4 → 5 not taken.
✓ Branch 4 → 6 taken 17 times.
|
23 | span<E, false> a = a_; |
| 127 |
2/4✗ Branch 4 → 5 not taken.
✓ Branch 4 → 6 taken 17 times.
✗ Branch 9 → 10 not taken.
✓ Branch 9 → 16 taken 6 times.
|
23 | if (a.len() == 0) return {}; |
| 128 | 35 | assert(a[0] == 1); | |
| 129 |
1/1✓ Branch 32 → 33 taken 6 times.
|
23 | trunc<E> l = ps_log(a_); |
| 130 | 23 | l *= k; | |
| 131 |
2/2✓ Branch 12 → 13 taken 17 times.
✓ Branch 36 → 37 taken 6 times.
|
23 | return ps_exp(l); |
| 132 | 23 | } | |
| 133 | template <trunc_like S> | ||
| 134 |
1/2✗ Branch 2 → 3 not taken.
✓ Branch 2 → 4 taken 37 times.
|
44 | trunc<typename S::engine_t> ps_pow(const S& a_, int64_t k) { |
| 135 | using E = typename S::engine_t; | ||
| 136 | using T = typename E::value_type; | ||
| 137 | 44 | span<E, false> a = a_; | |
| 138 | 44 | assert(k >= 0); | |
| 139 |
3/4✓ Branch 6 → 7 taken 3 times.
✓ Branch 6 → 12 taken 34 times.
✗ Branch 7 → 8 not taken.
✓ Branch 7 → 42 taken 7 times.
|
44 | if (k == 0) { |
| 140 |
1/2✗ Branch 8 → 9 not taken.
✓ Branch 8 → 10 taken 3 times.
|
3 | trunc<E> r(size_t(a.len()), T(0)); |
| 141 |
1/4✓ Branch 10 → 11 taken 3 times.
✗ Branch 10 → 38 not taken.
✗ Branch 29 → 30 not taken.
✗ Branch 29 → 260 not taken.
|
3 | if (r.len() > 0) r[0] = T(1); |
| 142 | return r; | ||
| 143 | } | ||
| 144 | |||
| 145 | int st = 0; | ||
| 146 |
7/8✓ Branch 12 → 13 taken 3971680 times.
✓ Branch 12 → 15 taken 2 times.
✓ Branch 13 → 14 taken 3971648 times.
✓ Branch 13 → 15 taken 32 times.
✓ Branch 46 → 47 taken 13 times.
✗ Branch 46 → 60 not taken.
✓ Branch 60 → 41 taken 6 times.
✓ Branch 60 → 61 taken 7 times.
|
3971728 | while (st < a.len() && a[st] == 0) st++; |
| 147 | |||
| 148 |
9/10✓ Branch 15 → 16 taken 24 times.
✓ Branch 15 → 17 taken 10 times.
✓ Branch 16 → 17 taken 7 times.
✓ Branch 16 → 20 taken 17 times.
✓ Branch 61 → 62 taken 2 times.
✓ Branch 61 → 69 taken 5 times.
✗ Branch 66 → 67 not taken.
✓ Branch 66 → 68 taken 2 times.
✓ Branch 68 → 69 taken 1 time.
✓ Branch 68 → 104 taken 1 time.
|
43 | if (st > 0 && k > (a.len() - 1) / st) { |
| 149 | 21 | return trunc<E>(size_t(a.len()), T(0)); | |
| 150 | } | ||
| 151 | |||
| 152 | 53 | trunc<E> r(a.begin() + st, a.end() - (st * (k-1))); | |
| 153 | 23 | T leading_coeff = r[0]; | |
| 154 |
1/1✓ Branch 24 → 25 taken 17 times.
|
46 | r *= inv(leading_coeff); |
| 155 |
2/2✓ Branch 24 → 25 taken 17 times.
✓ Branch 140 → 141 taken 6 times.
|
58 | r = ps_pow_monic(r, T(k)); |
| 156 |
1/1✓ Branch 31 → 32 taken 17 times.
|
40 | r *= power(leading_coeff, k); |
| 157 |
3/4✓ Branch 31 → 32 taken 17 times.
✗ Branch 32 → 33 not taken.
✓ Branch 32 → 34 taken 17 times.
✓ Branch 193 → 194 taken 6 times.
|
53 | r.insert(r.begin(), size_t(st * k), T(0)); |
| 158 | 29 | assert(r.len() == a.len()); | |
| 159 | 23 | return r; | |
| 160 | 23 | } | |
| 161 | |||
| 162 | template <trunc_like S> | ||
| 163 | ✗ | trunc<typename S::engine_t> to_newton_sums(const S& a, int deg) { | |
| 164 | ✗ | auto r = deriv_shift_log(a); | |
| 165 | ✗ | r[0] = deg; | |
| 166 | ✗ | for (int i = 1; i < r.len(); i++) r[i] = -r[i]; | |
| 167 | ✗ | return r; | |
| 168 | } | ||
| 169 | template <trunc_like S> | ||
| 170 | ✗ | trunc<typename S::engine_t> from_newton_sums(const S& s_, int deg) { | |
| 171 | using E = typename S::engine_t; | ||
| 172 | ✗ | span<E, false> s = s_; | |
| 173 | ✗ | assert(s[0] == deg); | |
| 174 | ✗ | trunc<E> r(s.begin(), s.end()); | |
| 175 | ✗ | r[0] = 0; | |
| 176 | ✗ | for (int i = 1; i < r.len(); i++) r[i] = -r[i]; | |
| 177 | ✗ | return ps_exp(integ_shift(std::move(r))); | |
| 178 | } | ||
| 179 | |||
| 180 | // Calculates prod 1/(1-x^i)^{a[i]} | ||
| 181 | template <trunc_like S> | ||
| 182 | ✗ | trunc<typename S::engine_t> euler_transform(const S& a) { | |
| 183 | using E = typename S::engine_t; | ||
| 184 | ✗ | trunc<E> r = deriv_shift(a); | |
| 185 | ✗ | std::vector<bool> is_prime(size_t(r.len()), true); | |
| 186 | ✗ | for (int p = 2; p < r.len(); p++) { | |
| 187 | ✗ | if (!is_prime[p]) continue; | |
| 188 | ✗ | for (int i = 1; i*p < r.len(); i++) { | |
| 189 | ✗ | r[i*p] += r[i]; | |
| 190 | ✗ | is_prime[i*p] = false; | |
| 191 | } | ||
| 192 | } | ||
| 193 | ✗ | return ps_exp(integ_shift(r)); | |
| 194 | } | ||
| 195 | template <trunc_like S> | ||
| 196 | ✗ | trunc<typename S::engine_t> inverse_euler_transform(const S& a) { | |
| 197 | using E = typename S::engine_t; | ||
| 198 | ✗ | trunc<E> r = deriv_shift(ps_log(a)); | |
| 199 | ✗ | std::vector<bool> is_prime(size_t(r.len()), true); | |
| 200 | ✗ | for (int p = 2; p < r.len(); p++) { | |
| 201 | ✗ | if (!is_prime[p]) continue; | |
| 202 | ✗ | for (int i = (r.len()-1)/p; i >= 1; i--) { | |
| 203 | ✗ | r[i*p] -= r[i]; | |
| 204 | ✗ | is_prime[i*p] = false; | |
| 205 | } | ||
| 206 | } | ||
| 207 | ✗ | return integ_shift(r); | |
| 208 | } | ||
| 209 | |||
| 210 | // Helper packed bivariate buffer for Kinoshita-Li composition (arXiv:2404.05177). | ||
| 211 | // | ||
| 212 | // The motivation is performing Bostan-Mori (Graeffe root-squaring) to compute | ||
| 213 | // something like [x^n] P / Q_0(x, y) with deg_y(Q_0) = 1 and deg_x(Q_0) = n. | ||
| 214 | // | ||
| 215 | // In each step, we want to compute Q_{i+1}(x^2, y) = Q_i(x, y) * Q_i(-x, y). | ||
| 216 | // This doubles the degree of y and also lets us truncate x at half the previous | ||
| 217 | // degree, leaving the total size invariant. | ||
| 218 | // | ||
| 219 | // We will store Q as a packed buffer with x as the inner dimension to facilitate easy Q(-x) substitution. | ||
| 220 | // The inner span will be 2*deg(x), and the outer span will be 2*deg(y). | ||
| 221 | // As we advance, we will also return the cached transform of Q_i(-x, y) for the caller to use in the numerator. | ||
| 222 | 6 | template <fft::engine E> struct packed_bivariate { | |
| 223 | using T = typename E::value_type; | ||
| 224 | int L, l; | ||
| 225 | std::vector<T> c; | ||
| 226 | |||
| 227 | // Q_0 = 1 - y g(x), deg g < n <= 2^L | ||
| 228 |
2/3✗ Branch 13 → 14 not taken.
✓ Branch 13 → 15 taken 6 times.
✓ Branch 15 → 16 taken 6 times.
|
65 | packed_bivariate(int L_, std::span<const T> g) : L(L_), l(0), c(size_t(4) << L) { |
| 229 | 71 | c[0] = T(1); | |
| 230 |
5/6✓ Branch 6 → 4 taken 1878056 times.
✓ Branch 6 → 7 taken 59 times.
✗ Branch 44 → 45 not taken.
✓ Branch 44 → 46 taken 67 times.
✓ Branch 53 → 31 taken 67 times.
✓ Branch 53 → 54 taken 6 times.
|
1878188 | for (int i = 0; i < sz(g); i++) c[(2 << L) + i] = -g[i]; |
| 231 | 65 | } | |
| 232 | |||
| 233 | 607 | fft::transformed<E> advance() { | |
| 234 |
1/2✗ Branch 4 → 5 not taken.
✓ Branch 4 → 6 taken 17 times.
|
607 | int B = 4 << L; |
| 235 |
2/3✗ Branch 2 → 3 not taken.
✓ Branch 2 → 4 taken 590 times.
✓ Branch 12 → 13 taken 17 times.
|
607 | auto tq = E::transform(std::span<const T>(c), B); |
| 236 |
2/2✓ Branch 5 → 6 taken 590 times.
✓ Branch 16 → 17 taken 17 times.
|
607 | auto tn = E::negate_arg(tq, B); |
| 237 |
2/2✓ Branch 10 → 11 taken 590 times.
✓ Branch 30 → 31 taken 17 times.
|
607 | E::finish( |
| 238 |
4/4✓ Branch 8 → 9 taken 590 times.
✓ Branch 9 → 10 taken 590 times.
✓ Branch 26 → 27 taken 17 times.
✓ Branch 28 → 29 taken 17 times.
|
1231 | E::downsample(E::mul(tq, tn, B), B/2, false), |
| 239 |
2/3✗ Branch 6 → 7 not taken.
✓ Branch 6 → 8 taken 590 times.
✓ Branch 8 → 9 taken 590 times.
|
624 | std::span<T>(c).first(B/2) |
| 240 | ); | ||
| 241 | 607 | l++; | |
| 242 | // undo the circular wraparound using monicity in y | ||
| 243 |
5/6✓ Branch 15 → 14 taken 4030642 times.
✓ Branch 15 → 16 taken 590 times.
✗ Branch 111 → 112 not taken.
✓ Branch 111 → 113 taken 227 times.
✓ Branch 113 → 75 taken 210 times.
✓ Branch 113 → 114 taken 17 times.
|
4031459 | for (int i = 0; i < (2 << (L - l)); i++) { |
| 244 |
1/2✗ Branch 85 → 86 not taken.
✓ Branch 85 → 87 taken 210 times.
|
4030852 | c[(2 << L) + i] = c[i]; |
| 245 | 4031062 | c[i] = T(0); | |
| 246 | } | ||
| 247 |
2/4✗ Branch 16 → 17 not taken.
✓ Branch 16 → 18 taken 590 times.
✗ Branch 124 → 125 not taken.
✓ Branch 124 → 126 taken 17 times.
|
1214 | c[2 << L] -= T(1); |
| 248 | 624 | c[0] = T(1); | |
| 249 | // zero x coefficients beyond the level's truncation mod x^(2^(L-l)) | ||
| 250 |
2/4✗ Branch 159 → 160 not taken.
✓ Branch 159 → 161 taken 17 times.
✗ Branch 164 → 165 not taken.
✓ Branch 164 → 166 taken 17 times.
|
709 | std::fill(c.begin() + (2 << L) + (1 << (L - l)), c.end(), T(0)); |
| 251 |
5/6✓ Branch 25 → 23 taken 4030642 times.
✓ Branch 25 → 26 taken 590 times.
✗ Branch 269 → 270 not taken.
✓ Branch 269 → 271 taken 227 times.
✓ Branch 271 → 253 taken 210 times.
✓ Branch 271 → 272 taken 17 times.
|
4031459 | for (int i = 0; i < (2 << L); i += 2 << (L - l)) { |
| 252 |
5/6✓ Branch 23 → 22 taken 33415616 times.
✓ Branch 23 → 24 taken 4030642 times.
✗ Branch 258 → 259 not taken.
✓ Branch 258 → 260 taken 788 times.
✓ Branch 260 → 232 taken 578 times.
✓ Branch 260 → 261 taken 210 times.
|
37447046 | for (int j = 0; j < (1 << (L - l)); j++) { |
| 253 |
1/2✗ Branch 245 → 246 not taken.
✓ Branch 245 → 247 taken 578 times.
|
33416772 | c[i + (1 << (L - l)) + j] = T(0); |
| 254 | } | ||
| 255 | } | ||
| 256 | 624 | return tn; | |
| 257 | 607 | } | |
| 258 | }; | ||
| 259 | |||
| 260 | // Calculates f(g(x)) mod x^n where deg(g) == n | ||
| 261 | template <trunc_like SF, trunc_like SG> requires fft::same_engine<SF, SG> | ||
| 262 |
1/2✗ Branch 2 → 3 not taken.
✓ Branch 2 → 4 taken 59 times.
|
65 | trunc<typename SF::engine_t> ps_compose(const SF& f_, const SG& g_) { |
| 263 | using E = typename SF::engine_t; | ||
| 264 | using T = typename E::value_type; | ||
| 265 |
1/2✗ Branch 4 → 5 not taken.
✓ Branch 4 → 6 taken 59 times.
|
65 | span<E, false> f = f_; |
| 266 |
1/2✗ Branch 6 → 7 not taken.
✓ Branch 6 → 8 taken 59 times.
|
65 | span<E, false> g = g_; |
| 267 |
2/4✗ Branch 6 → 7 not taken.
✓ Branch 6 → 8 taken 59 times.
✗ Branch 12 → 13 not taken.
✓ Branch 12 → 19 taken 6 times.
|
65 | if (g.len() == 0) return {}; |
| 268 | |||
| 269 | 65 | int m = f.len(); | |
| 270 |
2/2✓ Branch 8 → 9 taken 55 times.
✓ Branch 8 → 10 taken 4 times.
|
65 | int n = g.len(); |
| 271 | |||
| 272 | // https://arxiv.org/pdf/2404.05177 | ||
| 273 | // Consider P(y) = f(1/y) has terms from y^{-(m-1)}...y^0 (Laurent series) | ||
| 274 | // We want [y^0] P(y) / (1 - y g(x)) | ||
| 275 | // Let Q_0 = 1 - yg(x) | ||
| 276 | // Q_{i+1}(x^2, y) = Q_i(x, y) * Q_i(-x, y) mod x^{ceil(n / 2^i)} | ||
| 277 | // deg_y(Q_i) = 2^i, deg_x(Q_i) = ceil(n / 2^i) - 1 | ||
| 278 | // | ||
| 279 | // [y^0] P(y) / Q_l(x^2^l, y) * Q_{l-1}(-x^2^{l-1}, y) * Q_{l-2}(-x^2^{l-2}, y) * ... * Q_0(-x, y) | ||
| 280 | // The total y deg of Q_{k-1} ... Q_0 is 2^k-1 | ||
| 281 |
1/2✗ Branch 28 → 29 not taken.
✓ Branch 28 → 30 taken 6 times.
|
65 | int L = __builtin_ctz(unsigned(nextPow2(n))); |
| 282 | 65 | int B = 4 << L; | |
| 283 |
1/1✓ Branch 32 → 33 taken 6 times.
|
65 | packed_bivariate<E> Q(L, g.coeffs()); |
| 284 | // tneg[l] is the transform of Q_l(-x, y), reused by the pushdown pass below | ||
| 285 | 65 | std::vector<fft::transformed<E>> tneg; | |
| 286 |
2/2✓ Branch 11 → 16 taken 59 times.
✓ Branch 34 → 59 taken 6 times.
|
65 | tneg.reserve(L); |
| 287 |
6/6✓ Branch 12 → 13 taken 590 times.
✓ Branch 16 → 12 taken 590 times.
✓ Branch 16 → 17 taken 59 times.
✓ Branch 36 → 37 taken 17 times.
✓ Branch 59 → 35 taken 17 times.
✓ Branch 59 → 60 taken 6 times.
|
689 | for (int l = 1; l <= L; l++) tneg.push_back(Q.advance()); |
| 288 |
1/1✓ Branch 17 → 18 taken 59 times.
|
65 | trunc<E> P; |
| 289 | { | ||
| 290 |
1/1✓ Branch 17 → 18 taken 59 times.
|
95 | P = trunc<E>(f.begin(), f.end()); |
| 291 |
1/1✓ Branch 104 → 105 taken 6 times.
|
77 | std::reverse(P.begin(), P.end()); |
| 292 |
2/3✓ Branch 21 → 22 taken 59 times.
✗ Branch 127 → 128 not taken.
✓ Branch 127 → 129 taken 6 times.
|
71 | trunc<E> QL((1 << L) + 1); |
| 293 |
4/4✓ Branch 24 → 23 taken 2015439 times.
✓ Branch 24 → 25 taken 59 times.
✓ Branch 142 → 134 taken 117 times.
✓ Branch 142 → 143 taken 6 times.
|
2015621 | for (int i = 0; i <= (1 << L); i++) { |
| 294 | 2015556 | QL[i] = Q.c[2 * i]; | |
| 295 | } | ||
| 296 |
2/2✓ Branch 25 → 26 taken 59 times.
✓ Branch 148 → 149 taken 6 times.
|
71 | QL.resize(size_t(m), T(0)); |
| 297 |
4/4✓ Branch 26 → 27 taken 59 times.
✓ Branch 27 → 28 taken 59 times.
✓ Branch 151 → 152 taken 6 times.
✓ Branch 153 → 154 taken 6 times.
|
130 | P *= ps_inv(QL); |
| 298 |
2/2✓ Branch 30 → 31 taken 59 times.
✓ Branch 176 → 177 taken 6 times.
|
77 | std::reverse(P.begin(), P.end()); |
| 299 |
3/4✓ Branch 30 → 31 taken 59 times.
✗ Branch 202 → 203 not taken.
✓ Branch 202 → 204 taken 6 times.
✓ Branch 204 → 205 taken 6 times.
|
71 | P.resize(size_t(1) << L, T(0)); |
| 300 |
2/2✓ Branch 32 → 33 taken 59 times.
✓ Branch 210 → 211 taken 6 times.
|
77 | std::reverse(P.begin(), P.end()); |
| 301 |
2/2✓ Branch 32 → 33 taken 59 times.
✓ Branch 236 → 237 taken 6 times.
|
71 | P.resize(size_t(B), T(0)); |
| 302 |
4/4✓ Branch 35 → 34 taken 2015321 times.
✓ Branch 35 → 36 taken 59 times.
✓ Branch 257 → 239 taken 105 times.
✓ Branch 257 → 258 taken 6 times.
|
2015491 | for (int i = (1 << L) - 1; i > 0; i--) { |
| 303 | 2015426 | P[2*i] = P[i]; | |
| 304 | 2015531 | P[i] = T(0); | |
| 305 | } | ||
| 306 | 6 | } | |
| 307 |
4/4✓ Branch 54 → 38 taken 590 times.
✓ Branch 54 → 55 taken 59 times.
✓ Branch 381 → 277 taken 17 times.
✓ Branch 381 → 382 taken 6 times.
|
672 | for (int l = L-1; l >= 0; l--) { |
| 308 | // Spread it out, clear the high terms | ||
| 309 |
4/4✓ Branch 42 → 39 taken 66830642 times.
✓ Branch 42 → 43 taken 590 times.
✓ Branch 309 → 278 taken 1139 times.
✓ Branch 309 → 310 taken 17 times.
|
66832388 | for (int i = (2 << L) - 1; i > 0; i--) { |
| 310 |
2/2✓ Branch 39 → 40 taken 33415026 times.
✓ Branch 39 → 41 taken 33415616 times.
|
66831781 | T v = P[i]; |
| 311 |
5/6✓ Branch 39 → 40 taken 33415026 times.
✓ Branch 39 → 41 taken 33415616 times.
✗ Branch 284 → 285 not taken.
✓ Branch 284 → 286 taken 1139 times.
✓ Branch 286 → 287 taken 578 times.
✓ Branch 286 → 290 taken 561 times.
|
100247385 | P[2*i] = ((2*i) & (1 << (L-l))) ? T(0) : v; |
| 312 | 66832920 | P[i] = T(0); | |
| 313 | } | ||
| 314 |
3/3✓ Branch 45 → 46 taken 590 times.
✓ Branch 46 → 47 taken 590 times.
✓ Branch 313 → 314 taken 17 times.
|
607 | auto tp = E::transform(std::span<const T>(P), B); |
| 315 |
4/4✓ Branch 46 → 47 taken 590 times.
✓ Branch 47 → 48 taken 590 times.
✓ Branch 320 → 321 taken 17 times.
✓ Branch 322 → 323 taken 17 times.
|
624 | E::finish(E::mul(tneg[l], tp, B), std::span<T>(P)); |
| 316 |
4/4✓ Branch 51 → 50 taken 66831232 times.
✓ Branch 51 → 52 taken 590 times.
✓ Branch 361 → 343 taken 1156 times.
✓ Branch 361 → 362 taken 17 times.
|
66832995 | for (int i = 0; i < (2 << L); i++) { |
| 317 | 66832388 | P[i] = P[(2 << L) + i]; | |
| 318 | 66833544 | P[(2 << L) + i] = T(0); | |
| 319 | } | ||
| 320 | } | ||
| 321 |
1/1✓ Branch 55 → 56 taken 59 times.
|
89 | return trunc<E>(P.begin(), P.begin() + n); |
| 322 | 77 | } | |
| 323 | |||
| 324 | // [x^k] p(x)/q(x) (Bostan-Mori) for an exact rational function. | ||
| 325 | template <exact_like P, exact_like Q> requires fft::same_engine<P, Q> | ||
| 326 |
1/2✓ Branch 2 → 3 taken 20 times.
✗ Branch 2 → 4 not taken.
|
220 | P::engine_t::value_type kth_term_of_rational_function( |
| 327 | const P& p, | ||
| 328 | const Q& q, | ||
| 329 | uint64_t k | ||
| 330 | ) { | ||
| 331 | using E = P::engine_t; | ||
| 332 | using T = E::value_type; | ||
| 333 | |||
| 334 | 720 | assert(q.len() > 0 && q[0] != T(0)); | |
| 335 | // Check this here so we avoid accessing p[0] | ||
| 336 |
17/18ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true>, ecnerwala::series::cached_span<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true> const&, ecnerwala::series::cached_span<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true> const&, unsigned long):
✓ Branch 38 → 39 taken 5 times.
✓ Branch 38 → 44 taken 20 times.
ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true>, ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true> const&, ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true> const&, unsigned long):
✓ Branch 31 → 32 taken 5 times.
✓ Branch 31 → 37 taken 20 times.
ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true>, ecnerwala::series::cached_span<ecnerwala::fft::engines::ntt<mod_goldilocks>, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true> const&, ecnerwala::series::cached_span<ecnerwala::fft::engines::ntt<mod_goldilocks>, true> const&, unsigned long):
✓ Branch 38 → 39 taken 5 times.
✓ Branch 38 → 44 taken 20 times.
ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true>, ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true> const&, ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true> const&, unsigned long):
✓ Branch 31 → 32 taken 5 times.
✓ Branch 31 → 37 taken 20 times.
ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true>, ecnerwala::series::cached_span<ecnerwala::fft::engines::ntt<modnum<998244353> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true> const&, ecnerwala::series::cached_span<ecnerwala::fft::engines::ntt<modnum<998244353> >, true> const&, unsigned long):
✗ Branch 7 → 8 not taken.
✓ Branch 7 → 9 taken 20 times.
✓ Branch 38 → 39 taken 5 times.
✓ Branch 38 → 44 taken 20 times.
ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true>, ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true> const&, ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true> const&, unsigned long):
✓ Branch 31 → 32 taken 5 times.
✓ Branch 31 → 37 taken 20 times.
ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true>, ecnerwala::series::cached_span<ecnerwala::fft::engines::split<modnum<1000000007> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true> const&, ecnerwala::series::cached_span<ecnerwala::fft::engines::split<modnum<1000000007> >, true> const&, unsigned long):
✓ Branch 38 → 39 taken 5 times.
✓ Branch 38 → 44 taken 20 times.
ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true>, ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true> const&, ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true> const&, unsigned long):
✓ Branch 31 → 32 taken 5 times.
✓ Branch 31 → 37 taken 20 times.
|
460 | if (p.len() == 0) return T(0); |
| 337 | |||
| 338 | // Size up in a pretty conservative way | ||
| 339 |
1/2✗ Branch 9 → 10 not taken.
✓ Branch 9 → 11 taken 20 times.
|
500 | int d = std::max(p.len() + 1, q.len()); |
| 340 | 180 | assert(d >= 2); | |
| 341 | |||
| 342 |
1/2✓ Branch 11 → 12 taken 20 times.
✗ Branch 11 → 13 not taken.
|
180 | int n = nextPow2((d-1) + d - 1); // >= d |
| 343 | |||
| 344 | // Seed the loop transforms from any whole caches; the buffers below hold the | ||
| 345 | // current p, q (zero-padded, which extend_to tolerates). | ||
| 346 | 180 | fft::transformed<E> tq, tp; | |
| 347 |
16/30ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true>, ecnerwala::series::cached_span<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true> const&, ecnerwala::series::cached_span<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true> const&, unsigned long):
✓ Branch 81 → 82 taken 20 times.
✗ Branch 81 → 94 not taken.
✓ Branch 88 → 89 taken 20 times.
✓ Branch 93 → 94 taken 20 times.
ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true>, ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true> const&, ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true> const&, unsigned long):
✗ Branch 73 → 74 not taken.
✓ Branch 73 → 87 taken 20 times.
✗ Branch 80 → 81 not taken.
✗ Branch 86 → 87 not taken.
ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true>, ecnerwala::series::cached_span<ecnerwala::fft::engines::ntt<mod_goldilocks>, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true> const&, ecnerwala::series::cached_span<ecnerwala::fft::engines::ntt<mod_goldilocks>, true> const&, unsigned long):
✓ Branch 81 → 82 taken 20 times.
✗ Branch 81 → 98 not taken.
✓ Branch 87 → 88 taken 20 times.
ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true>, ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true> const&, ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true> const&, unsigned long):
✗ Branch 73 → 74 not taken.
✓ Branch 73 → 91 taken 20 times.
✗ Branch 79 → 80 not taken.
ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true>, ecnerwala::series::cached_span<ecnerwala::fft::engines::ntt<modnum<998244353> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true> const&, ecnerwala::series::cached_span<ecnerwala::fft::engines::ntt<modnum<998244353> >, true> const&, unsigned long):
✓ Branch 13 → 14 taken 20 times.
✗ Branch 13 → 16 not taken.
✓ Branch 14 → 15 taken 20 times.
✓ Branch 15 → 16 taken 20 times.
✓ Branch 81 → 82 taken 20 times.
✗ Branch 81 → 98 not taken.
✓ Branch 87 → 88 taken 20 times.
ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true>, ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true> const&, ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true> const&, unsigned long):
✗ Branch 73 → 74 not taken.
✓ Branch 73 → 91 taken 20 times.
✗ Branch 79 → 80 not taken.
ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true>, ecnerwala::series::cached_span<ecnerwala::fft::engines::split<modnum<1000000007> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true> const&, ecnerwala::series::cached_span<ecnerwala::fft::engines::split<modnum<1000000007> >, true> const&, unsigned long):
✓ Branch 81 → 82 taken 20 times.
✗ Branch 81 → 99 not taken.
✓ Branch 88 → 89 taken 20 times.
ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true>, ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true> const&, ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true> const&, unsigned long):
✗ Branch 73 → 74 not taken.
✓ Branch 73 → 92 taken 20 times.
✗ Branch 80 → 81 not taken.
|
400 | if (auto cq = detail::cache_of(q)) { E::extend_to(cq->get(), n, q); tq = cq->get(); } |
| 348 |
10/31ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true>, ecnerwala::series::cached_span<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true> const&, ecnerwala::series::cached_span<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true> const&, unsigned long):
✗ Branch 103 → 104 not taken.
✓ Branch 103 → 117 taken 20 times.
✗ Branch 110 → 111 not taken.
✗ Branch 116 → 117 not taken.
ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true>, ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true> const&, ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true> const&, unsigned long):
✗ Branch 96 → 97 not taken.
✓ Branch 96 → 110 taken 20 times.
✗ Branch 103 → 104 not taken.
✗ Branch 109 → 110 not taken.
ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true>, ecnerwala::series::cached_span<ecnerwala::fft::engines::ntt<mod_goldilocks>, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true> const&, ecnerwala::series::cached_span<ecnerwala::fft::engines::ntt<mod_goldilocks>, true> const&, unsigned long):
✗ Branch 107 → 108 not taken.
✓ Branch 107 → 125 taken 20 times.
✗ Branch 113 → 114 not taken.
ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true>, ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true> const&, ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true> const&, unsigned long):
✗ Branch 100 → 101 not taken.
✓ Branch 100 → 118 taken 20 times.
✗ Branch 106 → 107 not taken.
ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true>, ecnerwala::series::cached_span<ecnerwala::fft::engines::ntt<modnum<998244353> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true> const&, ecnerwala::series::cached_span<ecnerwala::fft::engines::ntt<modnum<998244353> >, true> const&, unsigned long):
✗ Branch 16 → 17 not taken.
✓ Branch 16 → 21 taken 20 times.
✗ Branch 19 → 20 not taken.
✗ Branch 20 → 21 not taken.
✓ Branch 21 → 22 taken 20 times.
✗ Branch 107 → 108 not taken.
✓ Branch 107 → 125 taken 20 times.
✗ Branch 113 → 114 not taken.
ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true>, ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true> const&, ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true> const&, unsigned long):
✗ Branch 100 → 101 not taken.
✓ Branch 100 → 118 taken 20 times.
✗ Branch 106 → 107 not taken.
ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true>, ecnerwala::series::cached_span<ecnerwala::fft::engines::split<modnum<1000000007> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true> const&, ecnerwala::series::cached_span<ecnerwala::fft::engines::split<modnum<1000000007> >, true> const&, unsigned long):
✗ Branch 108 → 109 not taken.
✓ Branch 108 → 127 taken 20 times.
✗ Branch 115 → 116 not taken.
ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true>, ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true> const&, ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true> const&, unsigned long):
✗ Branch 101 → 102 not taken.
✓ Branch 101 → 120 taken 20 times.
✗ Branch 108 → 109 not taken.
|
340 | if (auto cp = detail::cache_of(p)) { E::extend_to(cp->get(), n, p); tp = cp->get(); } |
| 349 | |||
| 350 |
10/11ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true>, ecnerwala::series::cached_span<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true> const&, ecnerwala::series::cached_span<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true> const&, unsigned long):
✓ Branch 125 → 126 taken 20 times.
ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true>, ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true> const&, ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true> const&, unsigned long):
✓ Branch 118 → 119 taken 20 times.
ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true>, ecnerwala::series::cached_span<ecnerwala::fft::engines::ntt<mod_goldilocks>, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true> const&, ecnerwala::series::cached_span<ecnerwala::fft::engines::ntt<mod_goldilocks>, true> const&, unsigned long):
✓ Branch 133 → 134 taken 20 times.
ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true>, ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true> const&, ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true> const&, unsigned long):
✓ Branch 126 → 127 taken 20 times.
ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true>, ecnerwala::series::cached_span<ecnerwala::fft::engines::ntt<modnum<998244353> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true> const&, ecnerwala::series::cached_span<ecnerwala::fft::engines::ntt<modnum<998244353> >, true> const&, unsigned long):
✓ Branch 21 → 22 taken 20 times.
✗ Branch 22 → 23 not taken.
✓ Branch 22 → 24 taken 20 times.
✓ Branch 133 → 134 taken 20 times.
ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true>, ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true> const&, ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true> const&, unsigned long):
✓ Branch 126 → 127 taken 20 times.
ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true>, ecnerwala::series::cached_span<ecnerwala::fft::engines::split<modnum<1000000007> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true> const&, ecnerwala::series::cached_span<ecnerwala::fft::engines::split<modnum<1000000007> >, true> const&, unsigned long):
✓ Branch 135 → 136 taken 20 times.
ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true>, ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true> const&, ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true> const&, unsigned long):
✓ Branch 128 → 129 taken 20 times.
|
340 | std::vector<T> p_buf(d-1, T(0)); |
| 351 |
2/3✗ Branch 22 → 23 not taken.
✓ Branch 22 → 24 taken 20 times.
✓ Branch 25 → 26 taken 20 times.
|
500 | std::ranges::copy(std::span<const T>(p), p_buf.begin()); |
| 352 |
9/9ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true>, ecnerwala::series::cached_span<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true> const&, ecnerwala::series::cached_span<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true> const&, unsigned long):
✓ Branch 166 → 167 taken 20 times.
ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true>, ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true> const&, ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true> const&, unsigned long):
✓ Branch 159 → 160 taken 20 times.
ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true>, ecnerwala::series::cached_span<ecnerwala::fft::engines::ntt<mod_goldilocks>, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true> const&, ecnerwala::series::cached_span<ecnerwala::fft::engines::ntt<mod_goldilocks>, true> const&, unsigned long):
✓ Branch 174 → 175 taken 20 times.
ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true>, ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true> const&, ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true> const&, unsigned long):
✓ Branch 167 → 168 taken 20 times.
ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true>, ecnerwala::series::cached_span<ecnerwala::fft::engines::ntt<modnum<998244353> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true> const&, ecnerwala::series::cached_span<ecnerwala::fft::engines::ntt<modnum<998244353> >, true> const&, unsigned long):
✓ Branch 25 → 26 taken 20 times.
✓ Branch 174 → 175 taken 20 times.
ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true>, ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true> const&, ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true> const&, unsigned long):
✓ Branch 167 → 168 taken 20 times.
ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true>, ecnerwala::series::cached_span<ecnerwala::fft::engines::split<modnum<1000000007> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true> const&, ecnerwala::series::cached_span<ecnerwala::fft::engines::split<modnum<1000000007> >, true> const&, unsigned long):
✓ Branch 176 → 177 taken 20 times.
ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true>, ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true> const&, ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true> const&, unsigned long):
✓ Branch 169 → 170 taken 20 times.
|
340 | std::vector<T> q_buf(d, T(0)); |
| 353 | 500 | std::ranges::copy(std::span<const T>(q), q_buf.begin()); | |
| 354 | |||
| 355 |
17/18ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true>, ecnerwala::series::cached_span<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true> const&, ecnerwala::series::cached_span<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true> const&, unsigned long):
✓ Branch 301 → 202 taken 80 times.
✓ Branch 301 → 302 taken 4 times.
ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true>, ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true> const&, ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true> const&, unsigned long):
✓ Branch 293 → 194 taken 80 times.
✓ Branch 293 → 294 taken 4 times.
ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true>, ecnerwala::series::cached_span<ecnerwala::fft::engines::ntt<mod_goldilocks>, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true> const&, ecnerwala::series::cached_span<ecnerwala::fft::engines::ntt<mod_goldilocks>, true> const&, unsigned long):
✓ Branch 425 → 210 taken 80 times.
✓ Branch 425 → 426 taken 4 times.
ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true>, ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true> const&, ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true> const&, unsigned long):
✓ Branch 417 → 202 taken 80 times.
✓ Branch 417 → 418 taken 4 times.
ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true>, ecnerwala::series::cached_span<ecnerwala::fft::engines::ntt<modnum<998244353> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true> const&, ecnerwala::series::cached_span<ecnerwala::fft::engines::ntt<modnum<998244353> >, true> const&, unsigned long):
✓ Branch 64 → 28 taken 628 times.
✗ Branch 64 → 65 not taken.
✓ Branch 423 → 210 taken 80 times.
✓ Branch 423 → 424 taken 4 times.
ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true>, ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true> const&, ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true> const&, unsigned long):
✓ Branch 415 → 202 taken 80 times.
✓ Branch 415 → 416 taken 4 times.
ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true>, ecnerwala::series::cached_span<ecnerwala::fft::engines::split<modnum<1000000007> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true> const&, ecnerwala::series::cached_span<ecnerwala::fft::engines::split<modnum<1000000007> >, true> const&, unsigned long):
✓ Branch 385 → 212 taken 80 times.
✓ Branch 385 → 386 taken 4 times.
ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true>, ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true> const&, ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true> const&, unsigned long):
✓ Branch 377 → 204 taken 80 times.
✓ Branch 377 → 378 taken 4 times.
|
2696 | while (k > 0) { |
| 356 |
9/9ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true>, ecnerwala::series::cached_span<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true> const&, ecnerwala::series::cached_span<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true> const&, unsigned long):
✓ Branch 204 → 205 taken 80 times.
ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true>, ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true> const&, ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true> const&, unsigned long):
✓ Branch 196 → 197 taken 80 times.
ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true>, ecnerwala::series::cached_span<ecnerwala::fft::engines::ntt<mod_goldilocks>, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true> const&, ecnerwala::series::cached_span<ecnerwala::fft::engines::ntt<mod_goldilocks>, true> const&, unsigned long):
✓ Branch 212 → 213 taken 80 times.
ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true>, ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true> const&, ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true> const&, unsigned long):
✓ Branch 204 → 205 taken 80 times.
ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true>, ecnerwala::series::cached_span<ecnerwala::fft::engines::ntt<modnum<998244353> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true> const&, ecnerwala::series::cached_span<ecnerwala::fft::engines::ntt<modnum<998244353> >, true> const&, unsigned long):
✓ Branch 30 → 31 taken 628 times.
✓ Branch 212 → 213 taken 80 times.
ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true>, ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true> const&, ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true> const&, unsigned long):
✓ Branch 204 → 205 taken 80 times.
ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true>, ecnerwala::series::cached_span<ecnerwala::fft::engines::split<modnum<1000000007> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true> const&, ecnerwala::series::cached_span<ecnerwala::fft::engines::split<modnum<1000000007> >, true> const&, unsigned long):
✓ Branch 214 → 215 taken 80 times.
ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true>, ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true> const&, ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true> const&, unsigned long):
✓ Branch 206 → 207 taken 80 times.
|
1268 | E::extend_to(tq, n, q_buf); |
| 357 |
9/9ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true>, ecnerwala::series::cached_span<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true> const&, ecnerwala::series::cached_span<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true> const&, unsigned long):
✓ Branch 207 → 208 taken 80 times.
ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true>, ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true> const&, ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true> const&, unsigned long):
✓ Branch 199 → 200 taken 80 times.
ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true>, ecnerwala::series::cached_span<ecnerwala::fft::engines::ntt<mod_goldilocks>, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true> const&, ecnerwala::series::cached_span<ecnerwala::fft::engines::ntt<mod_goldilocks>, true> const&, unsigned long):
✓ Branch 215 → 216 taken 80 times.
ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true>, ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true> const&, ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true> const&, unsigned long):
✓ Branch 207 → 208 taken 80 times.
ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true>, ecnerwala::series::cached_span<ecnerwala::fft::engines::ntt<modnum<998244353> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true> const&, ecnerwala::series::cached_span<ecnerwala::fft::engines::ntt<modnum<998244353> >, true> const&, unsigned long):
✓ Branch 31 → 32 taken 628 times.
✓ Branch 215 → 216 taken 80 times.
ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true>, ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true> const&, ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true> const&, unsigned long):
✓ Branch 207 → 208 taken 80 times.
ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true>, ecnerwala::series::cached_span<ecnerwala::fft::engines::split<modnum<1000000007> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true> const&, ecnerwala::series::cached_span<ecnerwala::fft::engines::split<modnum<1000000007> >, true> const&, unsigned long):
✓ Branch 217 → 218 taken 80 times.
ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true>, ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true> const&, ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true> const&, unsigned long):
✓ Branch 209 → 210 taken 80 times.
|
1268 | auto tnq = E::negate_arg(tq, n); |
| 358 |
9/9ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true>, ecnerwala::series::cached_span<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true> const&, ecnerwala::series::cached_span<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true> const&, unsigned long):
✓ Branch 210 → 211 taken 80 times.
ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true>, ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true> const&, ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true> const&, unsigned long):
✓ Branch 202 → 203 taken 80 times.
ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true>, ecnerwala::series::cached_span<ecnerwala::fft::engines::ntt<mod_goldilocks>, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true> const&, ecnerwala::series::cached_span<ecnerwala::fft::engines::ntt<mod_goldilocks>, true> const&, unsigned long):
✓ Branch 218 → 219 taken 80 times.
ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true>, ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true> const&, ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true> const&, unsigned long):
✓ Branch 210 → 211 taken 80 times.
ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true>, ecnerwala::series::cached_span<ecnerwala::fft::engines::ntt<modnum<998244353> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true> const&, ecnerwala::series::cached_span<ecnerwala::fft::engines::ntt<modnum<998244353> >, true> const&, unsigned long):
✓ Branch 34 → 35 taken 628 times.
✓ Branch 218 → 219 taken 80 times.
ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true>, ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true> const&, ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true> const&, unsigned long):
✓ Branch 210 → 211 taken 80 times.
ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true>, ecnerwala::series::cached_span<ecnerwala::fft::engines::split<modnum<1000000007> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true> const&, ecnerwala::series::cached_span<ecnerwala::fft::engines::split<modnum<1000000007> >, true> const&, unsigned long):
✓ Branch 220 → 221 taken 80 times.
ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true>, ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true> const&, ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true> const&, unsigned long):
✓ Branch 212 → 213 taken 80 times.
|
1268 | E::extend_to(tp, n, p_buf); |
| 359 | |||
| 360 | // P <- downsample(P(x) * Q(-x)) | ||
| 361 |
19/20ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true>, ecnerwala::series::cached_span<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true> const&, ecnerwala::series::cached_span<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true> const&, unsigned long):
✓ Branch 214 → 215 taken 80 times.
✓ Branch 216 → 217 taken 80 times.
ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true>, ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true> const&, ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true> const&, unsigned long):
✓ Branch 206 → 207 taken 80 times.
✓ Branch 208 → 209 taken 80 times.
ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true>, ecnerwala::series::cached_span<ecnerwala::fft::engines::ntt<mod_goldilocks>, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true> const&, ecnerwala::series::cached_span<ecnerwala::fft::engines::ntt<mod_goldilocks>, true> const&, unsigned long):
✓ Branch 222 → 223 taken 80 times.
✓ Branch 224 → 225 taken 80 times.
ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true>, ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true> const&, ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true> const&, unsigned long):
✓ Branch 214 → 215 taken 80 times.
✓ Branch 216 → 217 taken 80 times.
ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true>, ecnerwala::series::cached_span<ecnerwala::fft::engines::ntt<modnum<998244353> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true> const&, ecnerwala::series::cached_span<ecnerwala::fft::engines::ntt<modnum<998244353> >, true> const&, unsigned long):
✓ Branch 35 → 36 taken 628 times.
✓ Branch 36 → 37 taken 628 times.
✗ Branch 38 → 39 not taken.
✓ Branch 38 → 40 taken 628 times.
✓ Branch 222 → 223 taken 80 times.
✓ Branch 224 → 225 taken 80 times.
ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true>, ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true> const&, ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true> const&, unsigned long):
✓ Branch 214 → 215 taken 80 times.
✓ Branch 216 → 217 taken 80 times.
ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true>, ecnerwala::series::cached_span<ecnerwala::fft::engines::split<modnum<1000000007> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true> const&, ecnerwala::series::cached_span<ecnerwala::fft::engines::split<modnum<1000000007> >, true> const&, unsigned long):
✓ Branch 224 → 225 taken 80 times.
✓ Branch 226 → 227 taken 80 times.
ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true>, ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true> const&, ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true> const&, unsigned long):
✓ Branch 216 → 217 taken 80 times.
✓ Branch 218 → 219 taken 80 times.
|
2216 | auto ntp = E::downsample(E::mul(tp, tnq, n), n/2, bool(k & 1)); |
| 362 | 1268 | assert(ntp.size() == n/2); | |
| 363 | if constexpr (std::same_as<typename E::product, typename E::transformed>) { | ||
| 364 |
1/1✓ Branch 41 → 42 taken 628 times.
|
948 | tp = ntp; |
| 365 | } else { | ||
| 366 | 640 | tp = {}; | |
| 367 | } | ||
| 368 |
9/9ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true>, ecnerwala::series::cached_span<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true> const&, ecnerwala::series::cached_span<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true> const&, unsigned long):
✓ Branch 232 → 233 taken 80 times.
ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true>, ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true> const&, ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true> const&, unsigned long):
✓ Branch 224 → 225 taken 80 times.
ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true>, ecnerwala::series::cached_span<ecnerwala::fft::engines::ntt<mod_goldilocks>, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true> const&, ecnerwala::series::cached_span<ecnerwala::fft::engines::ntt<mod_goldilocks>, true> const&, unsigned long):
✓ Branch 257 → 258 taken 80 times.
ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true>, ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true> const&, ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true> const&, unsigned long):
✓ Branch 249 → 250 taken 80 times.
ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true>, ecnerwala::series::cached_span<ecnerwala::fft::engines::ntt<modnum<998244353> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true> const&, ecnerwala::series::cached_span<ecnerwala::fft::engines::ntt<modnum<998244353> >, true> const&, unsigned long):
✓ Branch 41 → 42 taken 628 times.
✓ Branch 257 → 258 taken 80 times.
ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true>, ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true> const&, ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true> const&, unsigned long):
✓ Branch 249 → 250 taken 80 times.
ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true>, ecnerwala::series::cached_span<ecnerwala::fft::engines::split<modnum<1000000007> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true> const&, ecnerwala::series::cached_span<ecnerwala::fft::engines::split<modnum<1000000007> >, true> const&, unsigned long):
✓ Branch 263 → 264 taken 80 times.
ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true>, ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true> const&, ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true> const&, unsigned long):
✓ Branch 255 → 256 taken 80 times.
|
1268 | E::finish(std::move(ntp), std::span(p_buf)); |
| 369 | 1268 | k >>= 1; | |
| 370 | |||
| 371 | // Save the last iteration if we're done | ||
| 372 |
18/18ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true>, ecnerwala::series::cached_span<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true> const&, ecnerwala::series::cached_span<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true> const&, unsigned long):
✓ Branch 234 → 235 taken 16 times.
✓ Branch 234 → 245 taken 64 times.
ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true>, ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true> const&, ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true> const&, unsigned long):
✓ Branch 226 → 227 taken 16 times.
✓ Branch 226 → 237 taken 64 times.
ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true>, ecnerwala::series::cached_span<ecnerwala::fft::engines::ntt<mod_goldilocks>, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true> const&, ecnerwala::series::cached_span<ecnerwala::fft::engines::ntt<mod_goldilocks>, true> const&, unsigned long):
✓ Branch 259 → 260 taken 16 times.
✓ Branch 259 → 304 taken 64 times.
ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true>, ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true> const&, ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true> const&, unsigned long):
✓ Branch 251 → 252 taken 16 times.
✓ Branch 251 → 296 taken 64 times.
ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true>, ecnerwala::series::cached_span<ecnerwala::fft::engines::ntt<modnum<998244353> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true> const&, ecnerwala::series::cached_span<ecnerwala::fft::engines::ntt<modnum<998244353> >, true> const&, unsigned long):
✓ Branch 42 → 43 taken 20 times.
✓ Branch 42 → 46 taken 608 times.
✓ Branch 259 → 260 taken 16 times.
✓ Branch 259 → 302 taken 64 times.
ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true>, ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true> const&, ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true> const&, unsigned long):
✓ Branch 251 → 252 taken 16 times.
✓ Branch 251 → 294 taken 64 times.
ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true>, ecnerwala::series::cached_span<ecnerwala::fft::engines::split<modnum<1000000007> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true> const&, ecnerwala::series::cached_span<ecnerwala::fft::engines::split<modnum<1000000007> >, true> const&, unsigned long):
✓ Branch 265 → 266 taken 16 times.
✓ Branch 265 → 292 taken 64 times.
ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true>, ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true> const&, ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true> const&, unsigned long):
✓ Branch 257 → 258 taken 16 times.
✓ Branch 257 → 284 taken 64 times.
|
1268 | if (!k) { |
| 373 | // HACK: fix the constant coefficient of q only | ||
| 374 | 148 | q_buf[0] *= q_buf[0]; | |
| 375 | break; | ||
| 376 | } | ||
| 377 | |||
| 378 | // Q <- downsample(Q(x) * Q(-x)) | ||
| 379 |
19/20ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true>, ecnerwala::series::cached_span<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true> const&, ecnerwala::series::cached_span<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true> const&, unsigned long):
✓ Branch 247 → 248 taken 64 times.
✓ Branch 249 → 250 taken 64 times.
ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true>, ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true> const&, ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true> const&, unsigned long):
✓ Branch 239 → 240 taken 64 times.
✓ Branch 241 → 242 taken 64 times.
ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true>, ecnerwala::series::cached_span<ecnerwala::fft::engines::ntt<mod_goldilocks>, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true> const&, ecnerwala::series::cached_span<ecnerwala::fft::engines::ntt<mod_goldilocks>, true> const&, unsigned long):
✓ Branch 306 → 307 taken 64 times.
✓ Branch 308 → 309 taken 64 times.
ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true>, ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true> const&, ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true> const&, unsigned long):
✓ Branch 298 → 299 taken 64 times.
✓ Branch 300 → 301 taken 64 times.
ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true>, ecnerwala::series::cached_span<ecnerwala::fft::engines::ntt<modnum<998244353> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true> const&, ecnerwala::series::cached_span<ecnerwala::fft::engines::ntt<modnum<998244353> >, true> const&, unsigned long):
✓ Branch 46 → 47 taken 608 times.
✓ Branch 47 → 48 taken 608 times.
✗ Branch 49 → 50 not taken.
✓ Branch 49 → 51 taken 608 times.
✓ Branch 304 → 305 taken 64 times.
✓ Branch 306 → 307 taken 64 times.
ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true>, ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true> const&, ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true> const&, unsigned long):
✓ Branch 296 → 297 taken 64 times.
✓ Branch 298 → 299 taken 64 times.
ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true>, ecnerwala::series::cached_span<ecnerwala::fft::engines::split<modnum<1000000007> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true> const&, ecnerwala::series::cached_span<ecnerwala::fft::engines::split<modnum<1000000007> >, true> const&, unsigned long):
✓ Branch 294 → 295 taken 64 times.
✓ Branch 296 → 297 taken 64 times.
ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true>, ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true> const&, ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true> const&, unsigned long):
✓ Branch 286 → 287 taken 64 times.
✓ Branch 288 → 289 taken 64 times.
|
1984 | auto ntq = E::downsample(E::mul(tq, tnq, n), n/2, false); |
| 380 | 1120 | assert(ntq.size() == n/2); | |
| 381 | if constexpr (std::same_as<typename E::product, typename E::transformed>) { | ||
| 382 | 864 | tq = ntq; | |
| 383 | } else { | ||
| 384 | 512 | tq = {}; | |
| 385 | } | ||
| 386 |
18/18ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true>, ecnerwala::series::cached_span<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true> const&, ecnerwala::series::cached_span<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true> const&, unsigned long):
✓ Branch 263 → 264 taken 32 times.
✓ Branch 263 → 291 taken 32 times.
ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true>, ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true> const&, ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true> const&, unsigned long):
✓ Branch 255 → 256 taken 32 times.
✓ Branch 255 → 283 taken 32 times.
ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true>, ecnerwala::series::cached_span<ecnerwala::fft::engines::ntt<mod_goldilocks>, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true> const&, ecnerwala::series::cached_span<ecnerwala::fft::engines::ntt<mod_goldilocks>, true> const&, unsigned long):
✓ Branch 339 → 340 taken 32 times.
✓ Branch 339 → 367 taken 32 times.
ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true>, ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true> const&, ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true> const&, unsigned long):
✓ Branch 331 → 332 taken 32 times.
✓ Branch 331 → 359 taken 32 times.
ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true>, ecnerwala::series::cached_span<ecnerwala::fft::engines::ntt<modnum<998244353> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true> const&, ecnerwala::series::cached_span<ecnerwala::fft::engines::ntt<modnum<998244353> >, true> const&, unsigned long):
✓ Branch 52 → 53 taken 60 times.
✓ Branch 52 → 58 taken 548 times.
✓ Branch 337 → 338 taken 32 times.
✓ Branch 337 → 365 taken 32 times.
ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true>, ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true> const&, ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true> const&, unsigned long):
✓ Branch 329 → 330 taken 32 times.
✓ Branch 329 → 357 taken 32 times.
ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true>, ecnerwala::series::cached_span<ecnerwala::fft::engines::split<modnum<1000000007> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true> const&, ecnerwala::series::cached_span<ecnerwala::fft::engines::split<modnum<1000000007> >, true> const&, unsigned long):
✓ Branch 331 → 332 taken 32 times.
✓ Branch 331 → 359 taken 32 times.
ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true>, ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true> const&, ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true> const&, unsigned long):
✓ Branch 323 → 324 taken 32 times.
✓ Branch 323 → 351 taken 32 times.
|
1120 | if (n/2 == d-1) { |
| 387 | // Fix the wraparound | ||
| 388 |
1/1✓ Branch 53 → 54 taken 60 times.
|
316 | T v0 = q_buf[0] * q_buf[0]; |
| 389 |
9/9ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true>, ecnerwala::series::cached_span<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true> const&, ecnerwala::series::cached_span<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true> const&, unsigned long):
✓ Branch 274 → 275 taken 32 times.
ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true>, ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true> const&, ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true> const&, unsigned long):
✓ Branch 266 → 267 taken 32 times.
ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true>, ecnerwala::series::cached_span<ecnerwala::fft::engines::ntt<mod_goldilocks>, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true> const&, ecnerwala::series::cached_span<ecnerwala::fft::engines::ntt<mod_goldilocks>, true> const&, unsigned long):
✓ Branch 350 → 351 taken 32 times.
ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true>, ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true> const&, ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true> const&, unsigned long):
✓ Branch 342 → 343 taken 32 times.
ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true>, ecnerwala::series::cached_span<ecnerwala::fft::engines::ntt<modnum<998244353> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true> const&, ecnerwala::series::cached_span<ecnerwala::fft::engines::ntt<modnum<998244353> >, true> const&, unsigned long):
✓ Branch 53 → 54 taken 60 times.
✓ Branch 348 → 349 taken 32 times.
ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true>, ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true> const&, ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true> const&, unsigned long):
✓ Branch 340 → 341 taken 32 times.
ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true>, ecnerwala::series::cached_span<ecnerwala::fft::engines::split<modnum<1000000007> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true> const&, ecnerwala::series::cached_span<ecnerwala::fft::engines::split<modnum<1000000007> >, true> const&, unsigned long):
✓ Branch 342 → 343 taken 32 times.
ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true>, ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true> const&, ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true> const&, unsigned long):
✓ Branch 334 → 335 taken 32 times.
|
316 | E::finish(std::move(ntq), std::span(q_buf).first(d-1)); |
| 390 |
1/2✗ Branch 54 → 55 not taken.
✓ Branch 54 → 56 taken 60 times.
|
376 | q_buf[d-1] = std::exchange(q_buf[0], v0) - v0; |
| 391 | } else { | ||
| 392 |
9/9ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true>, ecnerwala::series::cached_span<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true> const&, ecnerwala::series::cached_span<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true> const&, unsigned long):
✓ Branch 293 → 294 taken 32 times.
ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true>, ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true> const&, ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true> const&, unsigned long):
✓ Branch 285 → 286 taken 32 times.
ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true>, ecnerwala::series::cached_span<ecnerwala::fft::engines::ntt<mod_goldilocks>, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true> const&, ecnerwala::series::cached_span<ecnerwala::fft::engines::ntt<mod_goldilocks>, true> const&, unsigned long):
✓ Branch 369 → 370 taken 32 times.
ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true>, ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true> const&, ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true> const&, unsigned long):
✓ Branch 361 → 362 taken 32 times.
ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true>, ecnerwala::series::cached_span<ecnerwala::fft::engines::ntt<modnum<998244353> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true> const&, ecnerwala::series::cached_span<ecnerwala::fft::engines::ntt<modnum<998244353> >, true> const&, unsigned long):
✓ Branch 58 → 59 taken 548 times.
✓ Branch 367 → 368 taken 32 times.
ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true>, ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true> const&, ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true> const&, unsigned long):
✓ Branch 359 → 360 taken 32 times.
ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true>, ecnerwala::series::cached_span<ecnerwala::fft::engines::split<modnum<1000000007> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true> const&, ecnerwala::series::cached_span<ecnerwala::fft::engines::split<modnum<1000000007> >, true> const&, unsigned long):
✓ Branch 361 → 362 taken 32 times.
ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true>::engine_t::value_type ecnerwala::series::kth_term_of_rational_function<ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true>, ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true> const&, ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true> const&, unsigned long):
✓ Branch 353 → 354 taken 32 times.
|
804 | E::finish(std::move(ntq), std::span(q_buf)); |
| 393 | } | ||
| 394 | } | ||
| 395 | 340 | return p_buf[0] * inv(q_buf[0]); | |
| 396 | 580 | } | |
| 397 | |||
| 398 | // Find the kth term of linearly recurrent sequence S with char poly Q and len(S) >= len(Q)-1 | ||
| 399 | template <trunc_like S, exact_like Q> requires fft::same_engine<S, Q> | ||
| 400 |
1/2✗ Branch 2 → 3 not taken.
✓ Branch 2 → 4 taken 20 times.
|
120 | S::engine_t::value_type kth_term_of_linear_recurrence( |
| 401 | const S& s, | ||
| 402 | const Q& q, | ||
| 403 | uint64_t k | ||
| 404 | ) { | ||
| 405 | using E = S::engine_t; | ||
| 406 | using T = E::value_type; | ||
| 407 | |||
| 408 | 320 | assert(q.len() > 0 && q[0] != T(0)); | |
| 409 | 320 | assert(s.len() >= q.len()-1); | |
| 410 | |||
| 411 | // Don't even bother with P so we don't have to do truncation checks | ||
| 412 | // TODO: Could use generic multiply for this whole part? | ||
| 413 | 120 | fft::transformed<E> tq; | |
| 414 | 120 | auto q_cached = detail::as_cached_span(q, tq); | |
| 415 | |||
| 416 | // Compute the prefix and then hard-cast it to exact | ||
| 417 | 120 | span<E, false> sv = s; | |
| 418 |
5/5ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, false>::engine_t::value_type ecnerwala::series::kth_term_of_linear_recurrence<ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, false>, ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, false> const&, ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true> const&, unsigned long):
✓ Branch 58 → 59 taken 25 times.
ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, false>::engine_t::value_type ecnerwala::series::kth_term_of_linear_recurrence<ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, false>, ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, false> const&, ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true> const&, unsigned long):
✓ Branch 58 → 59 taken 25 times.
ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, false>::engine_t::value_type ecnerwala::series::kth_term_of_linear_recurrence<ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, false>, ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, false> const&, ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true> const&, unsigned long):
✓ Branch 12 → 13 taken 20 times.
✓ Branch 58 → 59 taken 25 times.
ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, false>::engine_t::value_type ecnerwala::series::kth_term_of_linear_recurrence<ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, false>, ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, false> const&, ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true> const&, unsigned long):
✓ Branch 58 → 59 taken 25 times.
|
420 | auto p = exact<E>(sv.first(q.len()-1) * q_cached); |
| 419 |
5/5ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, false>::engine_t::value_type ecnerwala::series::kth_term_of_linear_recurrence<ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, false>, ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, false> const&, ecnerwala::series::vec<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, true> const&, unsigned long):
✓ Branch 85 → 86 taken 25 times.
ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, false>::engine_t::value_type ecnerwala::series::kth_term_of_linear_recurrence<ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, false>, ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, false> const&, ecnerwala::series::vec<ecnerwala::fft::engines::ntt<mod_goldilocks>, true> const&, unsigned long):
✓ Branch 85 → 86 taken 25 times.
ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, false>::engine_t::value_type ecnerwala::series::kth_term_of_linear_recurrence<ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, false>, ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, false> const&, ecnerwala::series::vec<ecnerwala::fft::engines::ntt<modnum<998244353> >, true> const&, unsigned long):
✓ Branch 14 → 15 taken 20 times.
✓ Branch 85 → 86 taken 25 times.
ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, false>::engine_t::value_type ecnerwala::series::kth_term_of_linear_recurrence<ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, false>, ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true> >(ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, false> const&, ecnerwala::series::vec<ecnerwala::fft::engines::split<modnum<1000000007> >, true> const&, unsigned long):
✓ Branch 85 → 86 taken 25 times.
|
220 | return kth_term_of_rational_function(p, q_cached, k); |
| 420 | 195 | } | |
| 421 | |||
| 422 | /* namespace ecnerwala::series */ } | ||
| 423 |