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