fft/series_core.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include <algorithm> | ||
| 4 | #include <cassert> | ||
| 5 | #include <concepts> | ||
| 6 | #include <cstddef> | ||
| 7 | #include <functional> | ||
| 8 | #include <optional> | ||
| 9 | #include <span> | ||
| 10 | #include <utility> | ||
| 11 | #include <vector> | ||
| 12 | |||
| 13 | #include "fft/multiply.hpp" | ||
| 14 | |||
| 15 | // ==== value types ==== | ||
| 16 | |||
| 17 | namespace wala::series { | ||
| 18 | |||
| 19 | // A series is either exact (a finite series, R[x] sitting inside R[[x]]: the | ||
| 20 | // length is just the support bound) or trunc (a known prefix of an infinite | ||
| 21 | // series: the length is the precision, and products truncate to it). | ||
| 22 | |||
| 23 | // Non-owning view of power series coefficients: the span pattern (contiguous | ||
| 24 | // window + series semantics), borrowed from an owning series-like type. | ||
| 25 | template <fft::engine E, bool exact_> | ||
| 26 | struct span { | ||
| 27 | using T = typename E::value_type; | ||
| 28 | using engine_t = E; | ||
| 29 | static constexpr bool exact_v = exact_; | ||
| 30 | |||
| 31 | ✗ | span() = default; | |
| 32 | 10549409 | explicit span(std::span<const T> s_) : s(s_) {} | |
| 33 | // exact -> trunc is implicit, trunc -> exact is explicit | ||
| 34 | template <bool oe> requires (oe != exact_) | ||
| 35 | ✗ | explicit(oe < exact_) span(span<E, oe> o) : s(o.coeffs()) {} | |
| 36 | |||
| 37 |
9/12✗ Branch 4 → 5 not taken.
✓ Branch 4 → 6 taken 60 times.
✗ Branch 6 → 7 not taken.
✓ Branch 6 → 8 taken 59 times.
✓ Branch 8 → 9 taken 55 times.
✓ Branch 8 → 10 taken 4 times.
✓ Branch 12 → 13 taken 3971680 times.
✓ Branch 12 → 15 taken 2 times.
✗ Branch 34 → 35 not taken.
✓ Branch 34 → 36 taken 17 times.
✓ Branch 61 → 12 taken 578 times.
✓ Branch 61 → 62 taken 43 times.
|
6628996 | int len() const { return sz(s); } |
| 38 |
4/6✗ Branch 4 → 5 not taken.
✓ Branch 4 → 6 taken 42 times.
✗ Branch 6 → 7 not taken.
✓ Branch 6 → 8 taken 60 times.
✓ Branch 13 → 14 taken 3971648 times.
✓ Branch 13 → 15 taken 32 times.
|
3971946 | const T& operator[](int i) const { return s[size_t(i)]; } |
| 39 |
3/3✓ Branch 12 → 13 taken 2245 times.
✓ Branch 17 → 18 taken 59 times.
✓ Branch 27 → 28 taken 578 times.
|
5330 | auto begin() const { return s.begin(); } |
| 40 |
2/2✓ Branch 12 → 13 taken 1667 times.
✓ Branch 17 → 18 taken 59 times.
|
3856 | auto end() const { return s.end(); } |
| 41 | // engine primitives borrow through std::span's range constructor | ||
| 42 |
1/1✓ Branch 32 → 33 taken 6 times.
|
4625389 | std::span<const T> coeffs() const { return s; } |
| 43 | // the first n coefficients; requires n <= len(). | ||
| 44 | // Widening past len() is explicit: see with_len. | ||
| 45 | 5546 | span first(int n) const { | |
| 46 | 6466 | assert(n <= len()); | |
| 47 | 5546 | return span(s.first(size_t(n))); | |
| 48 | } | ||
| 49 | |||
| 50 | private: | ||
| 51 | std::span<const T> s; | ||
| 52 | }; | ||
| 53 | |||
| 54 | // `vec` represents both exact (finite) power series (R[x]) and prefixes of infinite power series (R[[x]]), depending on the flag. | ||
| 55 | // `exact` and `trunc` are aliases. | ||
| 56 | // | ||
| 57 | // Operators here are typically permissive: they will accept combinations of unequal types and lengths. | ||
| 58 | template <fft::engine E, bool exact_> | ||
| 59 |
30/30✓ Branch 9 → 10 taken 38 times.
✓ Branch 11 → 16 taken 9 times.
✓ Branch 14 → 15 taken 20 times.
✓ Branch 15 → 16 taken 6 times.
✓ Branch 15 → 17 taken 578 times.
✓ Branch 25 → 26 taken 578 times.
✓ Branch 28 → 29 taken 10 times.
✓ Branch 31 → 32 taken 578 times.
✓ Branch 41 → 42 taken 6 times.
✓ Branch 43 → 44 taken 1 time.
✓ Branch 48 → 59 taken 6 times.
✓ Branch 117 → 118 taken 5 times.
✓ Branch 126 → 127 taken 6 times.
✓ Branch 151 → 152 taken 1 time.
✓ Branch 171 → 172 taken 1 time.
✓ Branch 211 → 212 taken 6 times.
✓ Branch 306 → 307 taken 1 time.
✓ Branch 316 → 317 taken 6 times.
✓ Branch 332 → 333 taken 6 times.
✓ Branch 349 → 350 taken 1 time.
✓ Branch 393 → 394 taken 1 time.
✓ Branch 407 → 408 taken 1 time.
✓ Branch 453 → 454 taken 6 times.
✓ Branch 507 → 508 taken 1 time.
✓ Branch 621 → 622 taken 1 time.
✓ Branch 624 → 625 taken 1 time.
✓ Branch 733 → 734 taken 1 time.
✓ Branch 775 → 776 taken 1 time.
✓ Branch 1041 → 1042 taken 1 time.
✓ Branch 1073 → 1074 taken 1 time.
|
1980412 | struct vec : public std::vector<typename E::value_type> { |
| 60 | using T = typename E::value_type; | ||
| 61 | using engine_t = E; | ||
| 62 | static constexpr bool exact_v = exact_; | ||
| 63 |
52/56✓ Branch 9 → 10 taken 59 times.
✓ Branch 10 → 11 taken 220 times.
✓ Branch 11 → 12 taken 21 times.
✓ Branch 12 → 13 taken 791 times.
✓ Branch 16 → 17 taken 115 times.
✓ Branch 17 → 18 taken 61 times.
✓ Branch 18 → 19 taken 45 times.
✓ Branch 20 → 21 taken 50 times.
✓ Branch 21 → 22 taken 59 times.
✓ Branch 24 → 25 taken 6 times.
✓ Branch 27 → 28 taken 578 times.
✓ Branch 31 → 32 taken 11 times.
✓ Branch 33 → 34 taken 37 times.
✓ Branch 34 → 35 taken 11 times.
✓ Branch 40 → 57 taken 20 times.
✓ Branch 41 → 42 taken 537 times.
✓ Branch 42 → 59 taken 4 times.
✗ Branch 48 → 53 not taken.
✗ Branch 48 → 55 not taken.
✗ Branch 48 → 65 not taken.
✓ Branch 52 → 53 taken 11 times.
✗ Branch 54 → 59 not taken.
✓ Branch 56 → 57 taken 59 times.
✓ Branch 56 → 59 taken 80 times.
✓ Branch 58 → 61 taken 229 times.
✓ Branch 64 → 67 taken 10 times.
✓ Branch 66 → 67 taken 17 times.
✓ Branch 72 → 73 taken 2 times.
✓ Branch 73 → 74 taken 6 times.
✓ Branch 93 → 94 taken 1 time.
✓ Branch 103 → 104 taken 34 times.
✓ Branch 103 → 119 taken 6 times.
✓ Branch 112 → 113 taken 20 times.
✓ Branch 115 → 116 taken 20 times.
✓ Branch 116 → 117 taken 1 time.
✓ Branch 131 → 132 taken 6 times.
✓ Branch 142 → 143 taken 20 times.
✓ Branch 145 → 146 taken 26 times.
✓ Branch 157 → 158 taken 6 times.
✓ Branch 158 → 159 taken 1 time.
✓ Branch 222 → 223 taken 34 times.
✓ Branch 228 → 229 taken 1 time.
✓ Branch 260 → 261 taken 1 time.
✓ Branch 266 → 267 taken 1 time.
✓ Branch 277 → 278 taken 1 time.
✓ Branch 354 → 355 taken 25 times.
✓ Branch 374 → 375 taken 2 times.
✓ Branch 380 → 381 taken 1 time.
✓ Branch 397 → 398 taken 6 times.
✓ Branch 454 → 455 taken 1 time.
✓ Branch 608 → 609 taken 1 time.
✓ Branch 797 → 798 taken 1 time.
✓ Branch 880 → 881 taken 7 times.
✓ Branch 905 → 906 taken 1 time.
✓ Branch 1007 → 1008 taken 1 time.
✓ Branch 1078 → 1079 taken 1 time.
|
1975757 | using std::vector<T>::vector; |
| 64 | |||
| 65 | // a free const borrow of the coefficients: implicit | ||
| 66 |
2/4✗ Branch 2 → 3 not taken.
✓ Branch 2 → 4 taken 1974 times.
✗ Branch 4 → 5 not taken.
✓ Branch 4 → 6 taken 59 times.
|
10537001 | operator span<E, exact_>() const { |
| 67 |
2/4✗ Branch 4 → 5 not taken.
✓ Branch 4 → 6 taken 198 times.
✗ Branch 6 → 7 not taken.
✓ Branch 6 → 8 taken 59 times.
|
10538199 | return span<E, exact_>(std::span<const T>(*this)); |
| 68 | } | ||
| 69 | |||
| 70 | // exact -> trunc is implicit, trunc -> exact is explicit | ||
| 71 | template <bool oe> requires (oe != exact_) | ||
| 72 |
2/2✓ Branch 726 → 727 taken 1 time.
✓ Branch 819 → 820 taken 1 time.
|
2 | explicit(oe < exact_) vec(const vec<E, oe>& p) : std::vector<T>(p) {} |
| 73 | template <bool oe> requires (oe != exact_) | ||
| 74 | 217 | explicit(oe < exact_) vec(vec<E, oe>&& p) : std::vector<T>(std::move(p)) {} | |
| 75 | |||
| 76 | // adopt a plain coefficient vector | ||
| 77 | 2652532 | explicit vec(std::vector<T> v) : std::vector<T>(std::move(v)) {} | |
| 78 | // materialize an owned copy of any borrowed series, of either exactness | ||
| 79 |
1/1✓ Branch 13 → 14 taken 6 times.
|
29 | explicit vec(span<E, exact_> s) : std::vector<T>(s.begin(), s.end()) {} |
| 80 |
1/1✓ Branch 13 → 14 taken 12 times.
|
56 | explicit vec(span<E, !exact_> s) : std::vector<T>(s.begin(), s.end()) {} |
| 81 | |||
| 82 |
1/2✗ Branch 2 → 3 not taken.
✓ Branch 2 → 4 taken 1667 times.
|
1831 | span<E, exact_> first(int n) const { return span<E, exact_>(*this).first(n); } |
| 83 | |||
| 84 |
2/4✗ Branch 5 → 6 not taken.
✓ Branch 5 → 7 taken 2651880 times.
✗ Branch 37 → 38 not taken.
✓ Branch 37 → 39 taken 537 times.
|
42296691 | int len() const { |
| 85 |
50/68✗ Branch 2 → 3 not taken.
✓ Branch 2 → 4 taken 69 times.
✓ Branch 4 → 5 taken 20 times.
✓ Branch 4 → 6 taken 11 times.
✗ Branch 5 → 6 not taken.
✓ Branch 5 → 7 taken 20 times.
✗ Branch 7 → 8 not taken.
✓ Branch 7 → 9 taken 14420522 times.
✗ Branch 8 → 9 not taken.
✓ Branch 8 → 10 taken 12812345 times.
✓ Branch 9 → 3 taken 14420406 times.
✓ Branch 9 → 10 taken 276 times.
✓ Branch 9 → 11 taken 40 times.
✗ Branch 9 → 22 not taken.
✓ Branch 10 → 11 taken 14 times.
✓ Branch 10 → 12 taken 46415355 times.
✗ Branch 10 → 38 not taken.
✓ Branch 12 → 6 taken 46413579 times.
✓ Branch 12 → 13 taken 2357 times.
✓ Branch 12 → 14 taken 30167014 times.
✗ Branch 12 → 37 not taken.
✗ Branch 12 → 68 not taken.
✗ Branch 12 → 78 not taken.
✓ Branch 14 → 8 taken 10144438 times.
✓ Branch 14 → 15 taken 42 times.
✓ Branch 14 → 16 taken 7210241 times.
✓ Branch 16 → 17 taken 7210241 times.
✗ Branch 20 → 21 not taken.
✓ Branch 20 → 22 taken 644060 times.
✓ Branch 22 → 23 taken 644061 times.
✓ Branch 22 → 44 taken 1 time.
✓ Branch 24 → 7 taken 268 times.
✓ Branch 24 → 25 taken 32 times.
✓ Branch 27 → 7 taken 268 times.
✓ Branch 27 → 28 taken 32 times.
✗ Branch 29 → 30 not taken.
✗ Branch 29 → 260 not taken.
✓ Branch 31 → 32 taken 20 times.
✓ Branch 31 → 37 taken 80 times.
✗ Branch 32 → 33 not taken.
✓ Branch 32 → 34 taken 17 times.
✗ Branch 34 → 35 not taken.
✓ Branch 34 → 36 taken 595 times.
✓ Branch 36 → 19 taken 938 times.
✓ Branch 36 → 37 taken 616 times.
✓ Branch 36 → 56 taken 41 times.
✗ Branch 37 → 38 not taken.
✓ Branch 37 → 39 taken 537 times.
✓ Branch 38 → 39 taken 20 times.
✓ Branch 38 → 40 taken 100 times.
✓ Branch 38 → 44 taken 80 times.
✗ Branch 39 → 40 not taken.
✓ Branch 39 → 41 taken 537 times.
✓ Branch 41 → 23 taken 249 times.
✓ Branch 41 → 42 taken 571 times.
✓ Branch 47 → 48 taken 6 times.
✓ Branch 55 → 35 taken 60 times.
✓ Branch 55 → 56 taken 2 times.
✓ Branch 56 → 38 taken 249 times.
✓ Branch 56 → 57 taken 11 times.
✗ Branch 59 → 60 not taken.
✓ Branch 59 → 61 taken 621 times.
✓ Branch 60 → 32 taken 88 times.
✓ Branch 60 → 61 taken 3 times.
✓ Branch 61 → 12 taken 578 times.
✓ Branch 61 → 62 taken 43 times.
✗ Branch 336 → 337 not taken.
✓ Branch 336 → 338 taken 25 times.
|
111681800 | return int(this->size()); |
| 86 | } | ||
| 87 | ✗ | int degree() const requires (exact_) { | |
| 88 | ✗ | return len() - 1; | |
| 89 | } | ||
| 90 | ✗ | void extend(int sz) { | |
| 91 | ✗ | assert(sz >= len()); | |
| 92 | ✗ | this->resize(sz); | |
| 93 | } | ||
| 94 |
1/2✗ Branch 2 → 3 not taken.
✓ Branch 2 → 4 taken 9 times.
|
15 | void shrink(int sz) { |
| 95 | 21 | assert(sz <= len()); | |
| 96 | 15 | this->resize(sz); | |
| 97 | 15 | } | |
| 98 | // multiply by x^n within the fixed precision window | ||
| 99 | ✗ | void shift_trunc(int n = 1) requires (!exact_) { | |
| 100 | ✗ | assert(n >= 0 && n <= len()); | |
| 101 | ✗ | std::rotate(this->begin(), this->end()-n, this->end()); | |
| 102 | ✗ | std::fill(this->begin(), this->begin()+n, T(0)); | |
| 103 | } | ||
| 104 | // divide by x^n and 0-pad within the fixed precision window | ||
| 105 | ✗ | void unshift_trunc(int n = 1) requires (!exact_) { | |
| 106 | ✗ | assert(n >= 0 && n <= len()); | |
| 107 | ✗ | std::fill(this->begin(), this->begin()+n, T(0)); | |
| 108 | ✗ | std::rotate(this->begin(), this->begin()+n, this->end()); | |
| 109 | } | ||
| 110 | |||
| 111 | // in-place forms require that the result's exactness/length must equal this operand's | ||
| 112 | template <bool oe> requires (exact_ <= oe) | ||
| 113 | ✗ | vec& operator += (const vec<E, oe>& o) { | |
| 114 | ✗ | if constexpr (exact_) { if (o.len() > len()) this->resize(o.len()); } | |
| 115 | ✗ | else if constexpr (!oe) { if (o.len() < len()) this->resize(o.len()); } | |
| 116 | ✗ | for (int i = 0; i < std::min(len(), o.len()); i++) { | |
| 117 | ✗ | (*this)[i] += o[i]; | |
| 118 | } | ||
| 119 | ✗ | return *this; | |
| 120 | } | ||
| 121 | template <bool oe> requires (exact_ <= oe) | ||
| 122 |
1/2✗ Branch 2 → 3 not taken.
✓ Branch 2 → 4 taken 578 times.
|
612 | vec& operator -= (const vec<E, oe>& o) { |
| 123 | if constexpr (exact_) { if (o.len() > len()) this->resize(o.len()); } | ||
| 124 |
3/6✗ Branch 4 → 5 not taken.
✓ Branch 4 → 6 taken 578 times.
✗ Branch 6 → 7 not taken.
✓ Branch 6 → 12 taken 578 times.
✗ Branch 16 → 17 not taken.
✓ Branch 16 → 39 taken 34 times.
|
680 | else if constexpr (!oe) { if (o.len() < len()) this->resize(o.len()); } |
| 125 |
6/8✗ Branch 13 → 14 not taken.
✓ Branch 13 → 15 taken 10645015 times.
✗ Branch 15 → 16 not taken.
✓ Branch 15 → 17 taken 10645015 times.
✓ Branch 17 → 8 taken 10644437 times.
✓ Branch 17 → 18 taken 578 times.
✓ Branch 63 → 27 taken 249 times.
✓ Branch 63 → 64 taken 34 times.
|
10645864 | for (int i = 0; i < std::min(len(), o.len()); i++) { |
| 126 |
2/2✓ Branch 8 → 9 taken 4673577 times.
✓ Branch 8 → 10 taken 5970860 times.
|
10644686 | (*this)[i] -= o[i]; |
| 127 | } | ||
| 128 | 612 | return *this; | |
| 129 | } | ||
| 130 | |||
| 131 | 69 | vec& operator *= (const T& n) { | |
| 132 |
8/8None:
✓ Branch 11 → 10 taken 4745532 times.
✓ Branch 11 → 12 taken 17 times.
✓ Branch 23 → 22 taken 4745532 times.
✓ Branch 23 → 24 taken 17 times.
✓ Branch 30 → 29 taken 4745532 times.
✓ Branch 30 → 31 taken 17 times.
wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false>::operator*=(wala::modnum<998244353> const&):
✓ Branch 22 → 9 taken 411 times.
✓ Branch 22 → 23 taken 18 times.
|
14237112 | for (auto& v : *this) v *= n; |
| 133 | 18 | return *this; | |
| 134 | } | ||
| 135 | ✗ | friend vec operator * (const vec& a, const T& n) { | |
| 136 | ✗ | vec r(a.size()); | |
| 137 | ✗ | for (int i = 0; i < a.len(); i++) { | |
| 138 | ✗ | r[i] = a[i] * n; | |
| 139 | } | ||
| 140 | ✗ | return r; | |
| 141 | } | ||
| 142 | ✗ | friend vec operator * (const T& n, const vec& a) { | |
| 143 | ✗ | vec r(a.size()); | |
| 144 | ✗ | for (int i = 0; i < a.len(); i++) { | |
| 145 | ✗ | r[i] = n * a[i]; | |
| 146 | } | ||
| 147 | ✗ | return r; | |
| 148 | } | ||
| 149 | |||
| 150 | 1373 | vec& operator *= (const vec& o) { | |
| 151 |
1/1✓ Branch 4 → 5 taken 158 times.
|
2904 | return *this = (*this) * o; |
| 152 | } | ||
| 153 | }; | ||
| 154 | |||
| 155 | template <fft::engine E> using exact = vec<E, true>; | ||
| 156 | template <fft::engine E> using trunc = vec<E, false>; | ||
| 157 | |||
| 158 | // Series-like concepts: the binary operators below are written once as constrained | ||
| 159 | // templates and dispatch on which memoized transforms an operand carries. | ||
| 160 | // A series-like type exposes its engine/exactness and its coefficients as a | ||
| 161 | // span borrow of exactly len() coefficients; cached wrappers additionally | ||
| 162 | // expose their transform caches (filling them is logically const). | ||
| 163 | template <typename S> | ||
| 164 | concept like = fft::engine<typename S::engine_t> && requires(const S& s, int i) { | ||
| 165 | { S::exact_v } -> std::convertible_to<bool>; | ||
| 166 | { s.len() } -> std::same_as<int>; | ||
| 167 | { s[i] } -> std::convertible_to<const typename S::engine_t::value_type&>; | ||
| 168 | // borrows straight into the engine primitives | ||
| 169 | { std::span<const typename S::engine_t::value_type>(s) }; | ||
| 170 | // and into the series layer's own span, keeping the exactness tag | ||
| 171 | requires std::convertible_to<const S&, span<typename S::engine_t, S::exact_v>>; | ||
| 172 | // first(n): the first n coefficients, borrowed; requires n <= len(). | ||
| 173 | // The result is itself like (concepts can't self-reference). | ||
| 174 | // Cached types keep a cache in the result only when it still serves the whole borrow. | ||
| 175 | { s.first(i) } -> std::convertible_to<span<typename S::engine_t, S::exact_v>>; | ||
| 176 | }; | ||
| 177 | template <typename S> | ||
| 178 | concept exact_like = like<S> && S::exact_v; | ||
| 179 | template <typename S> | ||
| 180 | concept trunc_like = like<S> && !S::exact_v; | ||
| 181 | |||
| 182 | // carries one extendable transform of the whole coefficient sequence | ||
| 183 | template <typename S> | ||
| 184 | concept has_cache = like<S> && requires(const S& s) { | ||
| 185 | { s.cache() } -> std::same_as<fft::transformed<typename S::engine_t>&>; | ||
| 186 | }; | ||
| 187 | |||
| 188 | template <fft::engine E, bool exact_> | ||
| 189 | struct maybe_cached; | ||
| 190 | |||
| 191 | // A borrowed series paired with the transform serving it: the | ||
| 192 | // normalized operand form fed to the cached fft:: entry points. Models has_cache. | ||
| 193 | template <fft::engine E, bool exact_> | ||
| 194 | struct cached_span { | ||
| 195 | using engine_t = E; | ||
| 196 | static constexpr bool exact_v = exact_; | ||
| 197 | |||
| 198 | span<E, exact_> s; | ||
| 199 | std::reference_wrapper<fft::transformed<E>> f; | ||
| 200 | |||
| 201 | 2654829 | cached_span(span<E, exact_> s_, fft::transformed<E>& f_) : s(s_), f(f_) {} | |
| 202 | // exact -> trunc is implicit, trunc -> exact is explicit | ||
| 203 | template <bool oe> requires (oe != exact_) | ||
| 204 | ✗ | explicit(oe < exact_) cached_span(cached_span<E, oe> o) : s(span<E, exact_>(o.s)), f(o.f) {} | |
| 205 | |||
| 206 |
3/6✓ Branch 2 → 3 taken 20 times.
✗ Branch 2 → 4 not taken.
✗ Branch 9 → 10 not taken.
✓ Branch 9 → 11 taken 20 times.
✓ Branch 10 → 11 taken 100 times.
✗ Branch 10 → 29 not taken.
|
740 | int len() const { return s.len(); } |
| 207 |
1/2✗ Branch 3 → 4 not taken.
✓ Branch 3 → 5 taken 20 times.
|
220 | const typename E::value_type& operator[](int i) const { return s[i]; } |
| 208 |
1/1✓ Branch 14 → 15 taken 20 times.
|
4625363 | operator std::span<const typename E::value_type>() const { return s.coeffs(); } |
| 209 | 2655940 | operator span<E, exact_>() const { return s; } | |
| 210 | maybe_cached<E, exact_> first(int n) const; | ||
| 211 | 7284203 | fft::transformed<E>& cache() const { return f; } | |
| 212 | }; | ||
| 213 | |||
| 214 | // carries a whole-sequence cache only sometimes, decided at runtime | ||
| 215 | template <typename S> | ||
| 216 | concept has_cache_opt = like<S> && requires(const S& s) { | ||
| 217 | { s.cache_opt() } -> std::same_as<std::optional<std::reference_wrapper<fft::transformed<typename S::engine_t>>>>; | ||
| 218 | }; | ||
| 219 | |||
| 220 | namespace detail { | ||
| 221 | // the operand's whole cache, if it carries one | ||
| 222 | template <like S> | ||
| 223 | 13192960 | std::optional<std::reference_wrapper<fft::transformed<typename S::engine_t>>> cache_of(const S& s) { | |
| 224 | 13193388 | if constexpr (has_cache<S>) return s.cache(); | |
| 225 | 20 | else if constexpr (has_cache_opt<S>) return s.cache_opt(); | |
| 226 | 3982 | else return std::nullopt; | |
| 227 | } | ||
| 228 | } // namespace detail | ||
| 229 | |||
| 230 | // A borrowed series which may carry the transform serving it: the runtime | ||
| 231 | // counterpart of cached_span in the borrow hierarchy | ||
| 232 | // prefix_cached/cached -> maybe_cached/cached_span -> span. | ||
| 233 | template <fft::engine E, bool exact_> | ||
| 234 | struct maybe_cached { | ||
| 235 | using T = typename E::value_type; | ||
| 236 | using engine_t = E; | ||
| 237 | static constexpr bool exact_v = exact_; | ||
| 238 | |||
| 239 | span<E, exact_> s; | ||
| 240 | std::optional<std::reference_wrapper<fft::transformed<E>>> f; | ||
| 241 | |||
| 242 | ✗ | explicit maybe_cached(span<E, exact_> s_) : s(s_) {} | |
| 243 | 23 | maybe_cached(span<E, exact_> s_, fft::transformed<E>& f_) : s(s_), f(f_) {} | |
| 244 | ✗ | maybe_cached(cached_span<E, exact_> c) : s(c.s), f(c.f) {} | |
| 245 | // borrow any like operand whole, taking along whatever cache it carries | ||
| 246 | template <like S> requires std::same_as<typename S::engine_t, E> && (S::exact_v == exact_) | ||
| 247 | ✗ | maybe_cached(const S& o) : s(o), f(detail::cache_of(o)) {} | |
| 248 | |||
| 249 | 6 | int len() const { return s.len(); } | |
| 250 | 6 | const T& operator[](int i) const { return s[i]; } | |
| 251 | ✗ | operator std::span<const T>() const { return s.coeffs(); } | |
| 252 | 20 | operator span<E, exact_>() const { return s; } | |
| 253 | ✗ | maybe_cached first(int n) const { | |
| 254 | ✗ | return n == len() ? *this : maybe_cached(s.first(n)); | |
| 255 | } | ||
| 256 | 20 | std::optional<std::reference_wrapper<fft::transformed<E>>> cache_opt() const { return f; } | |
| 257 | }; | ||
| 258 | |||
| 259 | template <fft::engine E, bool exact_> | ||
| 260 | ✗ | maybe_cached<E, exact_> cached_span<E, exact_>::first(int n) const { | |
| 261 | ✗ | return maybe_cached<E, exact_>(*this).first(n); | |
| 262 | } | ||
| 263 | |||
| 264 | // An owned series copy at an adjusted logical length: the result of with_len. | ||
| 265 | // Carries a reference to a source cache when it still serves the copied | ||
| 266 | // coefficients (a zero tail doesn't change the transform), so the source | ||
| 267 | // must outlive the result. | ||
| 268 | template <fft::engine E> | ||
| 269 | struct resized { | ||
| 270 | using T = typename E::value_type; | ||
| 271 | using engine_t = E; | ||
| 272 | static constexpr bool exact_v = false; | ||
| 273 | |||
| 274 | trunc<E> s; | ||
| 275 | std::optional<std::reference_wrapper<fft::transformed<E>>> f; | ||
| 276 | |||
| 277 | ✗ | int len() const { return s.len(); } | |
| 278 | ✗ | const T& operator[](int i) const { return s[size_t(i)]; } | |
| 279 | ✗ | operator std::span<const T>() const { return std::span<const T>(s); } | |
| 280 | ✗ | operator span<E, false>() const { return s; } | |
| 281 | ✗ | maybe_cached<E, false> first(int n) const { | |
| 282 | ✗ | span<E, false> v = s; | |
| 283 | ✗ | if (n == len() && f) return {v, f->get()}; | |
| 284 | ✗ | return maybe_cached<E, false>(v.first(n)); | |
| 285 | } | ||
| 286 | ✗ | std::optional<std::reference_wrapper<fft::transformed<E>>> cache_opt() const { return f; } | |
| 287 | }; | ||
| 288 | |||
| 289 | // copy any operand to logical length n: extending zero-fills, shrinking truncates | ||
| 290 | template <like S> | ||
| 291 | ✗ | resized<typename S::engine_t> with_len(const S& s, int n) { | |
| 292 | using E = typename S::engine_t; | ||
| 293 | using T = typename E::value_type; | ||
| 294 | ✗ | auto p = s.first(std::min(n, s.len())); | |
| 295 | ✗ | resized<E> r; | |
| 296 | ✗ | r.s.assign(size_t(n), T{}); | |
| 297 | ✗ | std::span<const T> pc(p); | |
| 298 | ✗ | std::copy(pc.begin(), pc.end(), r.s.begin()); | |
| 299 | ✗ | r.f = detail::cache_of(p); | |
| 300 | ✗ | return r; | |
| 301 | } | ||
| 302 | |||
| 303 | // carries memoized transforms of power-of-two prefixes (see prefix_cached): | ||
| 304 | // product operands truncate to a covered scale to reuse them. | ||
| 305 | // Trunc-only: an exact operand participates whole, so has_cache covers it. | ||
| 306 | template <typename S> | ||
| 307 | concept has_prefix_cache = like<S> && !S::exact_v && requires(const S& s, int n) { | ||
| 308 | { s.prefix_cache(n) } -> std::same_as<fft::transformed<typename S::engine_t>&>; | ||
| 309 | }; | ||
| 310 | |||
| 311 | // Wrapper around vec which caches the transform of the whole series. | ||
| 312 | // Ops exploit the cache whenever the whole span participates; a trunc series' | ||
| 313 | // whole-sequence transform is still useful for middle products and repeated | ||
| 314 | // full-precision use. | ||
| 315 | template <fft::engine E, bool exact_> | ||
| 316 |
2/2✓ Branch 13 → 14 taken 1325940 times.
✓ Branch 17 → 18 taken 11 times.
|
19131946 | struct cached { |
| 317 | using T = typename E::value_type; | ||
| 318 | using engine_t = E; | ||
| 319 | static constexpr bool exact_v = exact_; | ||
| 320 | |||
| 321 | 6593380 | cached() = default; | |
| 322 | // moving coefficients in or out is free: implicit on rvalues, explicit copy otherwise | ||
| 323 | 4624051 | cached(vec<E, exact_>&& s_) : s(std::move(s_)) {} | |
| 324 | 43 | explicit cached(const vec<E, exact_>& s_) : s(s_) {} | |
| 325 | 182 | operator vec<E, exact_>() && { return std::move(s); } | |
| 326 | |||
| 327 |
22/33✗ Branch 2 → 3 not taken.
✓ Branch 2 → 4 taken 2651900 times.
✓ Branch 4 → 5 taken 2651880 times.
✓ Branch 4 → 6 taken 31 times.
✗ Branch 4 → 8 not taken.
✗ Branch 5 → 6 not taken.
✓ Branch 5 → 7 taken 2651891 times.
✗ Branch 6 → 7 not taken.
✓ Branch 6 → 8 taken 11 times.
✓ Branch 7 → 8 taken 8 times.
✓ Branch 7 → 9 taken 2651880 times.
✓ Branch 7 → 10 taken 3 times.
✓ Branch 8 → 9 taken 8 times.
✗ Branch 9 → 10 not taken.
✓ Branch 9 → 11 taken 11 times.
✓ Branch 11 → 12 taken 11 times.
✓ Branch 15 → 16 taken 260 times.
✗ Branch 15 → 43 not taken.
✗ Branch 22 → 23 not taken.
✓ Branch 22 → 24 taken 7 times.
✓ Branch 24 → 25 taken 6 times.
✗ Branch 24 → 91 not taken.
✗ Branch 25 → 26 not taken.
✓ Branch 25 → 27 taken 3 times.
✗ Branch 28 → 29 not taken.
✓ Branch 28 → 30 taken 1 time.
✓ Branch 30 → 31 taken 1 time.
✗ Branch 36 → 37 not taken.
✓ Branch 36 → 38 taken 1 time.
✓ Branch 42 → 43 taken 7 times.
✓ Branch 42 → 44 taken 260 times.
✓ Branch 66 → 35 taken 39 times.
✓ Branch 66 → 67 taken 1 time.
|
2654584 | int len() const { return s.len(); } |
| 328 | // unwrap to the owned coefficients | ||
| 329 | ✗ | const vec<E, exact_>& uncached() const { return s; } | |
| 330 | 1327576 | const T& operator[](int i) const { return s[size_t(i)]; } | |
| 331 | 8 | auto begin() const { return s.cbegin(); } | |
| 332 | 6 | auto end() const { return s.cend(); } | |
| 333 |
5/7✗ Branch 2 → 3 not taken.
✓ Branch 2 → 4 taken 11 times.
✗ Branch 5 → 6 not taken.
✓ Branch 5 → 7 taken 11 times.
✓ Branch 7 → 8 taken 11 times.
✓ Branch 7 → 9 taken 9 times.
✓ Branch 9 → 10 taken 9 times.
|
1119 | operator span<E, exact_>() const { return s; } |
| 334 | ✗ | maybe_cached<E, exact_> first(int n) const { | |
| 335 | ✗ | return n == len() ? maybe_cached<E, exact_>(s, f) : maybe_cached<E, exact_>(s.first(n)); | |
| 336 | } | ||
| 337 | // the transform of the coefficients, fed to the cached fft:: entry points alongside them | ||
| 338 | 10533209 | fft::transformed<E>& cache() const { return f; } | |
| 339 | |||
| 340 | template <like S> | ||
| 341 | 10 | friend bool operator==(const cached& a, const S& b) { | |
| 342 | 10 | span<E, S::exact_v> bs = b; | |
| 343 |
10/18bool wala::series::operator==<wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, true> >(wala::series::cached<wala::fft::engines::ntt<wala::modnum<998244353> >, true> const&, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, true> const&):
✓ Branch 19 → 20 taken 3 times.
✗ Branch 19 → 41 not taken.
✓ Branch 30 → 31 taken 3 times.
✓ Branch 41 → 42 taken 3 times.
✗ Branch 41 → 43 not taken.
✓ Branch 43 → 44 taken 3 times.
✗ Branch 43 → 54 not taken.
✓ Branch 54 → 55 taken 3 times.
✗ Branch 54 → 56 not taken.
bool wala::series::operator==<wala::series::cached<wala::fft::engines::ntt<wala::modnum<998244353> >, true> >(wala::series::cached<wala::fft::engines::ntt<wala::modnum<998244353> >, true> const&, wala::series::cached<wala::fft::engines::ntt<wala::modnum<998244353> >, true> const&):
✓ Branch 22 → 23 taken 7 times.
✗ Branch 22 → 44 not taken.
✓ Branch 33 → 34 taken 7 times.
✓ Branch 44 → 45 taken 7 times.
✗ Branch 44 → 46 not taken.
✓ Branch 46 → 47 taken 7 times.
✗ Branch 46 → 57 not taken.
✓ Branch 57 → 58 taken 7 times.
✗ Branch 57 → 59 not taken.
|
70 | return a.len() == bs.len() && std::equal(a.s.begin(), a.s.end(), bs.begin()); |
| 344 | } | ||
| 345 | |||
| 346 | private: | ||
| 347 | vec<E, exact_> s; | ||
| 348 | mutable fft::transformed<E> f; // memoized transform: filling it is logically const | ||
| 349 | }; | ||
| 350 | |||
| 351 | template <fft::engine E> using cached_exact = cached<E, true>; | ||
| 352 | template <fft::engine E> using cached_trunc = cached<E, false>; | ||
| 353 | |||
| 354 | namespace detail { | ||
| 355 | // Normalize a whole-span operand to a cached_span: the coefficients borrowed | ||
| 356 | // together with the cache serving them (the operand's own, or tmp otherwise). | ||
| 357 | // The whole-span multiply/square/middle_product paths run entirely on this form. | ||
| 358 | template <like S> | ||
| 359 | 10536760 | cached_span<typename S::engine_t, S::exact_v> as_cached_span(const S& s, fft::transformed<typename S::engine_t>& tmp) { | |
| 360 |
2/4wala::series::cached_span<wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, true>::engine_t, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, true>::exact_v> wala::series::detail::as_cached_span<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>::engine_t::transformed&):
✗ Branch 2 → 3 not taken.
✓ Branch 2 → 4 taken 20 times.
wala::series::cached_span<wala::series::cached<wala::fft::engines::ntt<wala::modnum<998244353> >, true>::engine_t, wala::series::cached<wala::fft::engines::ntt<wala::modnum<998244353> >, true>::exact_v> wala::series::detail::as_cached_span<wala::series::cached<wala::fft::engines::ntt<wala::modnum<998244353> >, true> >(wala::series::cached<wala::fft::engines::ntt<wala::modnum<998244353> >, true> const&, wala::series::cached<wala::fft::engines::ntt<wala::modnum<998244353> >, true>::engine_t::transformed&):
✗ Branch 2 → 3 not taken.
✓ Branch 2 → 4 taken 7879964 times.
|
10536760 | auto co = cache_of(s); |
| 361 |
21/42wala::series::cached_span<wala::series::cached_span<wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >, false>::engine_t, wala::series::cached_span<wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >, false>::exact_v> wala::series::detail::as_cached_span<wala::series::cached_span<wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >, false> >(wala::series::cached_span<wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >, false> const&, wala::series::cached_span<wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >, false>::engine_t::transformed&):
✓ Branch 13 → 14 taken 20 times.
✗ Branch 13 → 18 not taken.
wala::series::cached_span<wala::series::cached_span<wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >, true>::engine_t, wala::series::cached_span<wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >, true>::exact_v> wala::series::detail::as_cached_span<wala::series::cached_span<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> const&, wala::series::cached_span<wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >, true>::engine_t::transformed&):
✓ Branch 2 → 3 taken 96 times.
✗ Branch 2 → 4 not taken.
✓ Branch 13 → 14 taken 20 times.
✗ Branch 13 → 18 not taken.
wala::series::cached_span<wala::series::cached_span<wala::fft::engines::ntt<wala::mod_goldilocks>, false>::engine_t, wala::series::cached_span<wala::fft::engines::ntt<wala::mod_goldilocks>, false>::exact_v> wala::series::detail::as_cached_span<wala::series::cached_span<wala::fft::engines::ntt<wala::mod_goldilocks>, false> >(wala::series::cached_span<wala::fft::engines::ntt<wala::mod_goldilocks>, false> const&, wala::series::cached_span<wala::fft::engines::ntt<wala::mod_goldilocks>, false>::engine_t::transformed&):
✓ Branch 13 → 14 taken 20 times.
✗ Branch 13 → 18 not taken.
wala::series::cached_span<wala::series::cached_span<wala::fft::engines::ntt<wala::mod_goldilocks>, true>::engine_t, wala::series::cached_span<wala::fft::engines::ntt<wala::mod_goldilocks>, true>::exact_v> wala::series::detail::as_cached_span<wala::series::cached_span<wala::fft::engines::ntt<wala::mod_goldilocks>, true> >(wala::series::cached_span<wala::fft::engines::ntt<wala::mod_goldilocks>, true> const&, wala::series::cached_span<wala::fft::engines::ntt<wala::mod_goldilocks>, true>::engine_t::transformed&):
✓ Branch 13 → 14 taken 20 times.
✗ Branch 13 → 18 not taken.
wala::series::cached_span<wala::series::cached_span<wala::fft::engines::ntt<wala::modnum<998244353> >, false>::engine_t, wala::series::cached_span<wala::fft::engines::ntt<wala::modnum<998244353> >, false>::exact_v> wala::series::detail::as_cached_span<wala::series::cached_span<wala::fft::engines::ntt<wala::modnum<998244353> >, false> >(wala::series::cached_span<wala::fft::engines::ntt<wala::modnum<998244353> >, false> const&, wala::series::cached_span<wala::fft::engines::ntt<wala::modnum<998244353> >, false>::engine_t::transformed&):
✓ Branch 2 → 3 taken 2601 times.
✗ Branch 2 → 4 not taken.
✓ Branch 13 → 14 taken 483 times.
✗ Branch 13 → 18 not taken.
wala::series::cached_span<wala::series::cached_span<wala::fft::engines::ntt<wala::modnum<998244353> >, true>::engine_t, wala::series::cached_span<wala::fft::engines::ntt<wala::modnum<998244353> >, true>::exact_v> wala::series::detail::as_cached_span<wala::series::cached_span<wala::fft::engines::ntt<wala::modnum<998244353> >, true> >(wala::series::cached_span<wala::fft::engines::ntt<wala::modnum<998244353> >, true> const&, wala::series::cached_span<wala::fft::engines::ntt<wala::modnum<998244353> >, true>::engine_t::transformed&):
✓ Branch 2 → 3 taken 2652055 times.
✗ Branch 2 → 4 not taken.
✓ Branch 13 → 14 taken 389 times.
✗ Branch 13 → 18 not taken.
wala::series::cached_span<wala::series::cached_span<wala::fft::engines::split<wala::modnum<1000000007> >, false>::engine_t, wala::series::cached_span<wala::fft::engines::split<wala::modnum<1000000007> >, false>::exact_v> wala::series::detail::as_cached_span<wala::series::cached_span<wala::fft::engines::split<wala::modnum<1000000007> >, false> >(wala::series::cached_span<wala::fft::engines::split<wala::modnum<1000000007> >, false> const&, wala::series::cached_span<wala::fft::engines::split<wala::modnum<1000000007> >, false>::engine_t::transformed&):
✓ Branch 13 → 14 taken 20 times.
✗ Branch 13 → 18 not taken.
wala::series::cached_span<wala::series::cached_span<wala::fft::engines::split<wala::modnum<1000000007> >, true>::engine_t, wala::series::cached_span<wala::fft::engines::split<wala::modnum<1000000007> >, true>::exact_v> wala::series::detail::as_cached_span<wala::series::cached_span<wala::fft::engines::split<wala::modnum<1000000007> >, true> >(wala::series::cached_span<wala::fft::engines::split<wala::modnum<1000000007> >, true> const&, wala::series::cached_span<wala::fft::engines::split<wala::modnum<1000000007> >, true>::engine_t::transformed&):
✓ Branch 2 → 3 taken 96 times.
✗ Branch 2 → 4 not taken.
✓ Branch 13 → 14 taken 20 times.
✗ Branch 13 → 18 not taken.
wala::series::cached_span<wala::series::maybe_cached<wala::fft::engines::ntt<wala::modnum<998244353> >, false>::engine_t, wala::series::maybe_cached<wala::fft::engines::ntt<wala::modnum<998244353> >, false>::exact_v> wala::series::detail::as_cached_span<wala::series::maybe_cached<wala::fft::engines::ntt<wala::modnum<998244353> >, false> >(wala::series::maybe_cached<wala::fft::engines::ntt<wala::modnum<998244353> >, false> const&, wala::series::maybe_cached<wala::fft::engines::ntt<wala::modnum<998244353> >, false>::engine_t::transformed&):
✓ Branch 13 → 14 taken 20 times.
✗ Branch 13 → 18 not taken.
wala::series::cached_span<wala::series::vec<wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >, true>::engine_t, wala::series::vec<wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >, true>::exact_v> wala::series::detail::as_cached_span<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>::engine_t::transformed&):
✗ Branch 12 → 13 not taken.
✓ Branch 12 → 17 taken 25 times.
wala::series::cached_span<wala::series::vec<wala::fft::engines::ntt<wala::mod_goldilocks>, true>::engine_t, wala::series::vec<wala::fft::engines::ntt<wala::mod_goldilocks>, true>::exact_v> wala::series::detail::as_cached_span<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>::engine_t::transformed&):
✗ Branch 12 → 13 not taken.
✓ Branch 12 → 17 taken 25 times.
wala::series::cached_span<wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false>::engine_t, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false>::exact_v> wala::series::detail::as_cached_span<wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> >(wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> const&, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false>::engine_t::transformed&):
✗ Branch 12 → 13 not taken.
✓ Branch 12 → 17 taken 24 times.
wala::series::cached_span<wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, true>::engine_t, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, true>::exact_v> wala::series::detail::as_cached_span<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>::engine_t::transformed&):
✗ Branch 4 → 5 not taken.
✓ Branch 4 → 6 taken 20 times.
✗ Branch 12 → 13 not taken.
✓ Branch 12 → 17 taken 30 times.
wala::series::cached_span<wala::series::vec<wala::fft::engines::split<wala::modnum<1000000007> >, true>::engine_t, wala::series::vec<wala::fft::engines::split<wala::modnum<1000000007> >, true>::exact_v> wala::series::detail::as_cached_span<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>::engine_t::transformed&):
✗ Branch 12 → 13 not taken.
✓ Branch 12 → 17 taken 25 times.
wala::series::cached_span<wala::series::cached<wala::fft::engines::ntt<wala::modnum<998244353> >, true>::engine_t, wala::series::cached<wala::fft::engines::ntt<wala::modnum<998244353> >, true>::exact_v> wala::series::detail::as_cached_span<wala::series::cached<wala::fft::engines::ntt<wala::modnum<998244353> >, true> >(wala::series::cached<wala::fft::engines::ntt<wala::modnum<998244353> >, true> const&, wala::series::cached<wala::fft::engines::ntt<wala::modnum<998244353> >, true>::engine_t::transformed&):
✓ Branch 4 → 5 taken 7879964 times.
✗ Branch 4 → 6 not taken.
✓ Branch 15 → 16 taken 787 times.
✗ Branch 15 → 20 not taken.
|
10540487 | return {s, co ? co->get() : tmp}; |
| 362 | } | ||
| 363 | } // namespace detail | ||
| 364 | |||
| 365 | // Newton inversion: 1/a mod x^a.len(). Generic over any engine; per doubling step | ||
| 366 | // n -> m = 2n this is 5 transforms of size m, reusing b's transform for both circular | ||
| 367 | // products; in each product the wraparound only contaminates coefficients [0, n) | ||
| 368 | // which are already known. | ||
| 369 | // | ||
| 370 | // This is correct for non-commutative rings. | ||
| 371 | // TODO: reuse/populate the operand's whole/prefix transform caches | ||
| 372 | template <trunc_like S> | ||
| 373 |
1/2✗ Branch 2 → 3 not taken.
✓ Branch 2 → 4 taken 146 times.
|
180 | trunc<typename S::engine_t> ps_inv(const S& a) { |
| 374 | using E = typename S::engine_t; | ||
| 375 | using T = typename E::value_type; | ||
| 376 | 180 | int N = a.len(); | |
| 377 |
1/2✓ Branch 5 → 6 taken 146 times.
✗ Branch 5 → 46 not taken.
|
248 | trunc<E> r(size_t(N), T{}); |
| 378 |
5/10wala::series::vec<wala::series::vec<wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >, false>::engine_t, false> wala::series::ps_inv<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> >, false> const&):
✓ Branch 21 → 22 taken 1 time.
✗ Branch 21 → 238 not taken.
wala::series::vec<wala::series::vec<wala::fft::engines::ntt<wala::mod_goldilocks>, false>::engine_t, false> wala::series::ps_inv<wala::series::vec<wala::fft::engines::ntt<wala::mod_goldilocks>, false> >(wala::series::vec<wala::fft::engines::ntt<wala::mod_goldilocks>, false> const&):
✓ Branch 21 → 22 taken 1 time.
✗ Branch 21 → 318 not taken.
wala::series::vec<wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false>::engine_t, false> wala::series::ps_inv<wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> >(wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> const&):
✓ Branch 5 → 6 taken 146 times.
✗ Branch 5 → 46 not taken.
✓ Branch 21 → 22 taken 31 times.
✗ Branch 21 → 318 not taken.
wala::series::vec<wala::series::vec<wala::fft::engines::split<wala::modnum<1000000007> >, false>::engine_t, false> wala::series::ps_inv<wala::series::vec<wala::fft::engines::split<wala::modnum<1000000007> >, false> >(wala::series::vec<wala::fft::engines::split<wala::modnum<1000000007> >, false> const&):
✓ Branch 21 → 22 taken 1 time.
✗ Branch 21 → 286 not taken.
|
180 | if (N == 0) return r; |
| 379 |
2/2✓ Branch 6 → 7 taken 137 times.
✓ Branch 6 → 8 taken 9 times.
|
180 | int s = nextPow2(N); |
| 380 |
5/5wala::series::vec<wala::series::vec<wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >, false>::engine_t, false> wala::series::ps_inv<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> >, false> const&):
✓ Branch 30 → 31 taken 1 time.
wala::series::vec<wala::series::vec<wala::fft::engines::ntt<wala::mod_goldilocks>, false>::engine_t, false> wala::series::ps_inv<wala::series::vec<wala::fft::engines::ntt<wala::mod_goldilocks>, false> >(wala::series::vec<wala::fft::engines::ntt<wala::mod_goldilocks>, false> const&):
✓ Branch 30 → 31 taken 1 time.
wala::series::vec<wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false>::engine_t, false> wala::series::ps_inv<wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> >(wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> const&):
✓ Branch 8 → 9 taken 146 times.
✓ Branch 30 → 31 taken 31 times.
wala::series::vec<wala::series::vec<wala::fft::engines::split<wala::modnum<1000000007> >, false>::engine_t, false> wala::series::ps_inv<wala::series::vec<wala::fft::engines::split<wala::modnum<1000000007> >, false> >(wala::series::vec<wala::fft::engines::split<wala::modnum<1000000007> >, false> const&):
✓ Branch 30 → 31 taken 1 time.
|
214 | std::vector<T> b(size_t(s), T{}); |
| 381 | 214 | b[0] = inv(a[0]); | |
| 382 |
10/10wala::series::vec<wala::series::vec<wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >, false>::engine_t, false> wala::series::ps_inv<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> >, false> const&):
✓ Branch 159 → 50 taken 9 times.
✓ Branch 159 → 160 taken 1 time.
wala::series::vec<wala::series::vec<wala::fft::engines::ntt<wala::mod_goldilocks>, false>::engine_t, false> wala::series::ps_inv<wala::series::vec<wala::fft::engines::ntt<wala::mod_goldilocks>, false> >(wala::series::vec<wala::fft::engines::ntt<wala::mod_goldilocks>, false> const&):
✓ Branch 239 → 50 taken 9 times.
✓ Branch 239 → 240 taken 1 time.
wala::series::vec<wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false>::engine_t, false> wala::series::ps_inv<wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> >(wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> const&):
✓ Branch 42 → 11 taken 1667 times.
✓ Branch 42 → 43 taken 146 times.
✓ Branch 239 → 50 taken 106 times.
✓ Branch 239 → 240 taken 31 times.
wala::series::vec<wala::series::vec<wala::fft::engines::split<wala::modnum<1000000007> >, false>::engine_t, false> wala::series::ps_inv<wala::series::vec<wala::fft::engines::split<wala::modnum<1000000007> >, false> >(wala::series::vec<wala::fft::engines::split<wala::modnum<1000000007> >, false> const&):
✓ Branch 207 → 50 taken 9 times.
✓ Branch 207 → 208 taken 1 time.
|
2485 | for (int n = 1; n < N; n *= 2) { |
| 383 | 1800 | int m = 2 * n; | |
| 384 |
5/5wala::series::vec<wala::series::vec<wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >, false>::engine_t, false> wala::series::ps_inv<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> >, false> const&):
✓ Branch 61 → 62 taken 9 times.
wala::series::vec<wala::series::vec<wala::fft::engines::ntt<wala::mod_goldilocks>, false>::engine_t, false> wala::series::ps_inv<wala::series::vec<wala::fft::engines::ntt<wala::mod_goldilocks>, false> >(wala::series::vec<wala::fft::engines::ntt<wala::mod_goldilocks>, false> const&):
✓ Branch 61 → 62 taken 9 times.
wala::series::vec<wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false>::engine_t, false> wala::series::ps_inv<wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> >(wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> const&):
✓ Branch 12 → 13 taken 1667 times.
✓ Branch 61 → 62 taken 106 times.
wala::series::vec<wala::series::vec<wala::fft::engines::split<wala::modnum<1000000007> >, false>::engine_t, false> wala::series::ps_inv<wala::series::vec<wala::fft::engines::split<wala::modnum<1000000007> >, false> >(wala::series::vec<wala::fft::engines::split<wala::modnum<1000000007> >, false> const&):
✓ Branch 61 → 62 taken 9 times.
|
1800 | auto ta = E::transform(a.first(std::min(N, m)), m); |
| 385 |
6/7wala::series::vec<wala::series::vec<wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >, false>::engine_t, false> wala::series::ps_inv<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> >, false> const&):
✓ Branch 69 → 70 taken 9 times.
wala::series::vec<wala::series::vec<wala::fft::engines::ntt<wala::mod_goldilocks>, false>::engine_t, false> wala::series::ps_inv<wala::series::vec<wala::fft::engines::ntt<wala::mod_goldilocks>, false> >(wala::series::vec<wala::fft::engines::ntt<wala::mod_goldilocks>, false> const&):
✓ Branch 69 → 70 taken 9 times.
wala::series::vec<wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false>::engine_t, false> wala::series::ps_inv<wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> >(wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> const&):
✗ Branch 13 → 14 not taken.
✓ Branch 13 → 15 taken 1667 times.
✓ Branch 15 → 16 taken 1667 times.
✓ Branch 69 → 70 taken 106 times.
wala::series::vec<wala::series::vec<wala::fft::engines::split<wala::modnum<1000000007> >, false>::engine_t, false> wala::series::ps_inv<wala::series::vec<wala::fft::engines::split<wala::modnum<1000000007> >, false> >(wala::series::vec<wala::fft::engines::split<wala::modnum<1000000007> >, false> const&):
✓ Branch 69 → 70 taken 9 times.
|
1800 | auto tb = E::transform(std::span<const T>(b).first(n), m); |
| 386 | // e = a*b mod x^m; only e[n..m) is needed (and is wraparound-free). | ||
| 387 |
6/7wala::series::vec<wala::series::vec<wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >, false>::engine_t, false> wala::series::ps_inv<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> >, false> const&):
✓ Branch 72 → 73 taken 9 times.
wala::series::vec<wala::series::vec<wala::fft::engines::ntt<wala::mod_goldilocks>, false>::engine_t, false> wala::series::ps_inv<wala::series::vec<wala::fft::engines::ntt<wala::mod_goldilocks>, false> >(wala::series::vec<wala::fft::engines::ntt<wala::mod_goldilocks>, false> const&):
✓ Branch 72 → 73 taken 9 times.
wala::series::vec<wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false>::engine_t, false> wala::series::ps_inv<wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> >(wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> const&):
✓ Branch 16 → 17 taken 1667 times.
✗ Branch 17 → 18 not taken.
✓ Branch 17 → 19 taken 1667 times.
✓ Branch 72 → 73 taken 106 times.
wala::series::vec<wala::series::vec<wala::fft::engines::split<wala::modnum<1000000007> >, false>::engine_t, false> wala::series::ps_inv<wala::series::vec<wala::fft::engines::split<wala::modnum<1000000007> >, false> >(wala::series::vec<wala::fft::engines::split<wala::modnum<1000000007> >, false> const&):
✓ Branch 72 → 73 taken 9 times.
|
1800 | auto e = fft::buffer_pool<T>::get(m); |
| 388 |
10/10wala::series::vec<wala::series::vec<wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >, false>::engine_t, false> wala::series::ps_inv<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> >, false> const&):
✓ Branch 79 → 80 taken 9 times.
✓ Branch 81 → 82 taken 9 times.
wala::series::vec<wala::series::vec<wala::fft::engines::ntt<wala::mod_goldilocks>, false>::engine_t, false> wala::series::ps_inv<wala::series::vec<wala::fft::engines::ntt<wala::mod_goldilocks>, false> >(wala::series::vec<wala::fft::engines::ntt<wala::mod_goldilocks>, false> const&):
✓ Branch 79 → 80 taken 9 times.
✓ Branch 81 → 82 taken 9 times.
wala::series::vec<wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false>::engine_t, false> wala::series::ps_inv<wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> >(wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> const&):
✓ Branch 19 → 20 taken 1667 times.
✓ Branch 20 → 21 taken 1667 times.
✓ Branch 79 → 80 taken 106 times.
✓ Branch 81 → 82 taken 106 times.
wala::series::vec<wala::series::vec<wala::fft::engines::split<wala::modnum<1000000007> >, false>::engine_t, false> wala::series::ps_inv<wala::series::vec<wala::fft::engines::split<wala::modnum<1000000007> >, false> >(wala::series::vec<wala::fft::engines::split<wala::modnum<1000000007> >, false> const&):
✓ Branch 79 → 80 taken 9 times.
✓ Branch 81 → 82 taken 9 times.
|
1800 | E::finish(E::mul(ta, tb, m), e.span()); |
| 389 |
10/10wala::series::vec<wala::series::vec<wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >, false>::engine_t, false> wala::series::ps_inv<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> >, false> const&):
✓ Branch 99 → 85 taken 511 times.
✓ Branch 99 → 100 taken 9 times.
wala::series::vec<wala::series::vec<wala::fft::engines::ntt<wala::mod_goldilocks>, false>::engine_t, false> wala::series::ps_inv<wala::series::vec<wala::fft::engines::ntt<wala::mod_goldilocks>, false> >(wala::series::vec<wala::fft::engines::ntt<wala::mod_goldilocks>, false> const&):
✓ Branch 115 → 101 taken 511 times.
✓ Branch 115 → 116 taken 9 times.
wala::series::vec<wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false>::engine_t, false> wala::series::ps_inv<wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> >(wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> const&):
✓ Branch 24 → 23 taken 22233283 times.
✓ Branch 24 → 25 taken 1667 times.
✓ Branch 115 → 101 taken 1309 times.
✓ Branch 115 → 116 taken 106 times.
wala::series::vec<wala::series::vec<wala::fft::engines::split<wala::modnum<1000000007> >, false>::engine_t, false> wala::series::ps_inv<wala::series::vec<wala::fft::engines::split<wala::modnum<1000000007> >, false> >(wala::series::vec<wala::fft::engines::split<wala::modnum<1000000007> >, false> const&):
✓ Branch 99 → 85 taken 511 times.
✓ Branch 99 → 100 taken 9 times.
|
22240767 | for (int i = 0; i < n; i++) e[i] = T{}; |
| 390 |
5/5wala::series::vec<wala::series::vec<wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >, false>::engine_t, false> wala::series::ps_inv<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> >, false> const&):
✓ Branch 110 → 111 taken 9 times.
wala::series::vec<wala::series::vec<wala::fft::engines::ntt<wala::mod_goldilocks>, false>::engine_t, false> wala::series::ps_inv<wala::series::vec<wala::fft::engines::ntt<wala::mod_goldilocks>, false> >(wala::series::vec<wala::fft::engines::ntt<wala::mod_goldilocks>, false> const&):
✓ Branch 126 → 127 taken 9 times.
wala::series::vec<wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false>::engine_t, false> wala::series::ps_inv<wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> >(wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> const&):
✓ Branch 25 → 26 taken 1667 times.
✓ Branch 126 → 127 taken 106 times.
wala::series::vec<wala::series::vec<wala::fft::engines::split<wala::modnum<1000000007> >, false>::engine_t, false> wala::series::ps_inv<wala::series::vec<wala::fft::engines::split<wala::modnum<1000000007> >, false> >(wala::series::vec<wala::fft::engines::split<wala::modnum<1000000007> >, false> const&):
✓ Branch 110 → 111 taken 9 times.
|
1933 | auto te = E::transform(std::span<const T>(e.span()), m); |
| 391 |
6/7wala::series::vec<wala::series::vec<wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >, false>::engine_t, false> wala::series::ps_inv<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> >, false> const&):
✓ Branch 114 → 115 taken 9 times.
wala::series::vec<wala::series::vec<wala::fft::engines::ntt<wala::mod_goldilocks>, false>::engine_t, false> wala::series::ps_inv<wala::series::vec<wala::fft::engines::ntt<wala::mod_goldilocks>, false> >(wala::series::vec<wala::fft::engines::ntt<wala::mod_goldilocks>, false> const&):
✓ Branch 130 → 131 taken 9 times.
wala::series::vec<wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false>::engine_t, false> wala::series::ps_inv<wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> >(wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> const&):
✓ Branch 26 → 27 taken 1667 times.
✗ Branch 27 → 28 not taken.
✓ Branch 27 → 29 taken 1667 times.
✓ Branch 130 → 131 taken 106 times.
wala::series::vec<wala::series::vec<wala::fft::engines::split<wala::modnum<1000000007> >, false>::engine_t, false> wala::series::ps_inv<wala::series::vec<wala::fft::engines::split<wala::modnum<1000000007> >, false> >(wala::series::vec<wala::fft::engines::split<wala::modnum<1000000007> >, false> const&):
✓ Branch 114 → 115 taken 9 times.
|
1800 | auto c = fft::buffer_pool<T>::get(m); |
| 392 | // b' = 2b - b*(a*b): keep b on the left of e = a*b | ||
| 393 |
10/10wala::series::vec<wala::series::vec<wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >, false>::engine_t, false> wala::series::ps_inv<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> >, false> const&):
✓ Branch 121 → 122 taken 9 times.
✓ Branch 123 → 124 taken 9 times.
wala::series::vec<wala::series::vec<wala::fft::engines::ntt<wala::mod_goldilocks>, false>::engine_t, false> wala::series::ps_inv<wala::series::vec<wala::fft::engines::ntt<wala::mod_goldilocks>, false> >(wala::series::vec<wala::fft::engines::ntt<wala::mod_goldilocks>, false> const&):
✓ Branch 137 → 138 taken 9 times.
✓ Branch 139 → 140 taken 9 times.
wala::series::vec<wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false>::engine_t, false> wala::series::ps_inv<wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> >(wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> const&):
✓ Branch 29 → 30 taken 1667 times.
✓ Branch 30 → 31 taken 1667 times.
✓ Branch 137 → 138 taken 106 times.
✓ Branch 139 → 140 taken 106 times.
wala::series::vec<wala::series::vec<wala::fft::engines::split<wala::modnum<1000000007> >, false>::engine_t, false> wala::series::ps_inv<wala::series::vec<wala::fft::engines::split<wala::modnum<1000000007> >, false> >(wala::series::vec<wala::fft::engines::split<wala::modnum<1000000007> >, false> const&):
✓ Branch 121 → 122 taken 9 times.
✓ Branch 123 → 124 taken 9 times.
|
1800 | E::finish(E::mul(tb, te, m), c.span()); |
| 394 |
10/10wala::series::vec<wala::series::vec<wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >, false>::engine_t, false> wala::series::ps_inv<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> >, false> const&):
✓ Branch 147 → 127 taken 297 times.
✓ Branch 147 → 148 taken 9 times.
wala::series::vec<wala::series::vec<wala::fft::engines::ntt<wala::mod_goldilocks>, false>::engine_t, false> wala::series::ps_inv<wala::series::vec<wala::fft::engines::ntt<wala::mod_goldilocks>, false> >(wala::series::vec<wala::fft::engines::ntt<wala::mod_goldilocks>, false> const&):
✓ Branch 179 → 159 taken 297 times.
✓ Branch 179 → 180 taken 9 times.
wala::series::vec<wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false>::engine_t, false> wala::series::ps_inv<wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> >(wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> const&):
✓ Branch 35 → 33 taken 18840532 times.
✓ Branch 35 → 36 taken 1667 times.
✓ Branch 179 → 159 taken 848 times.
✓ Branch 179 → 180 taken 106 times.
wala::series::vec<wala::series::vec<wala::fft::engines::split<wala::modnum<1000000007> >, false>::engine_t, false> wala::series::ps_inv<wala::series::vec<wala::fft::engines::split<wala::modnum<1000000007> >, false> >(wala::series::vec<wala::fft::engines::split<wala::modnum<1000000007> >, false> const&):
✓ Branch 147 → 127 taken 297 times.
✓ Branch 147 → 148 taken 9 times.
|
18845810 | for (int i = n; i < std::min(m, N); i++) b[i] = -c[i]; |
| 395 | } | ||
| 396 |
4/4wala::series::vec<wala::series::vec<wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >, false>::engine_t, false> wala::series::ps_inv<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> >, false> const&):
✓ Branch 171 → 172 taken 1 time.
wala::series::vec<wala::series::vec<wala::fft::engines::ntt<wala::mod_goldilocks>, false>::engine_t, false> wala::series::ps_inv<wala::series::vec<wala::fft::engines::ntt<wala::mod_goldilocks>, false> >(wala::series::vec<wala::fft::engines::ntt<wala::mod_goldilocks>, false> const&):
✓ Branch 251 → 252 taken 1 time.
wala::series::vec<wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false>::engine_t, false> wala::series::ps_inv<wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> >(wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> const&):
✓ Branch 251 → 252 taken 31 times.
wala::series::vec<wala::series::vec<wala::fft::engines::split<wala::modnum<1000000007> >, false>::engine_t, false> wala::series::ps_inv<wala::series::vec<wala::fft::engines::split<wala::modnum<1000000007> >, false> >(wala::series::vec<wala::fft::engines::split<wala::modnum<1000000007> >, false> const&):
✓ Branch 219 → 220 taken 1 time.
|
350 | std::copy(b.begin(), b.begin() + N, r.begin()); |
| 397 | 180 | return r; | |
| 398 | 180 | } | |
| 399 | // TODO: operator / can be done slightly faster than ps_inv: | ||
| 400 | // we only need the n/2 terms of ps_inv(), and can do the last Newton step directly on the quotient | ||
| 401 | |||
| 402 | // Both consume whole-sequence transforms by nature (the full span always | ||
| 403 | // participates), so only whole caches apply, never prefix caches. | ||
| 404 | template <like A> | ||
| 405 | 30 | auto square(const A& a) { | |
| 406 | using E = typename A::engine_t; | ||
| 407 | using T = typename E::value_type; | ||
| 408 | 30 | fft::transformed<E> ta_; | |
| 409 | 30 | auto av = detail::as_cached_span(a, ta_); | |
| 410 | if constexpr (A::exact_v) { | ||
| 411 | // like operator*, an exact square returns has_cache, adopting the | ||
| 412 | // pointwise product as the result's transform when the engine supports it | ||
| 413 | 6 | std::vector<T> coeffs; | |
| 414 | 6 | fft::transformed<E> f; | |
| 415 |
2/2auto wala::series::square<wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, true> >(wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, true> const&):
✓ Branch 16 → 17 taken 4 times.
auto wala::series::square<wala::series::cached<wala::fft::engines::ntt<wala::modnum<998244353> >, true> >(wala::series::cached<wala::fft::engines::ntt<wala::modnum<998244353> >, true> const&):
✓ Branch 16 → 17 taken 2 times.
|
6 | fft::square_cached<E>(av, av.cache(), coeffs, f); |
| 416 | 30 | cached<E, true> w(exact<E>(std::move(coeffs))); | |
| 417 | 12 | w.cache() = std::move(f); | |
| 418 | 6 | return w; | |
| 419 | 12 | } else { | |
| 420 | 96 | trunc<E> r(size_t(a.len()), T{}); | |
| 421 |
1/1✓ Branch 34 → 35 taken 24 times.
|
48 | fft::square<E>(av, av.cache(), std::span<T>(r)); |
| 422 | 24 | return r; | |
| 423 | } | ||
| 424 | 30 | } | |
| 425 | |||
| 426 | // a*b + c*d, all exact; returns has_cache, adopting the summed pointwise | ||
| 427 | // product as the result's transform when the engine supports it. Reuses each | ||
| 428 | // operand's whole cache. Requires a*b and c*d to have equal length. | ||
| 429 | template <like A, like B, like C, like D> | ||
| 430 | requires fft::same_engine<A, B> && fft::same_engine<A, C> && fft::same_engine<A, D> | ||
| 431 | && A::exact_v && B::exact_v && C::exact_v && D::exact_v | ||
| 432 | 644116 | cached<typename A::engine_t, true> multiply_add2( | |
| 433 | const A& a, const B& b, const C& c, const D& d) { | ||
| 434 | using E = typename A::engine_t; | ||
| 435 | using T = typename E::value_type; | ||
| 436 | 644116 | fft::transformed<E> ta_, tb_, tc_, td_; | |
| 437 | 644116 | auto av = detail::as_cached_span(a, ta_), bv = detail::as_cached_span(b, tb_); | |
| 438 | 644116 | auto cv = detail::as_cached_span(c, tc_), dv = detail::as_cached_span(d, td_); | |
| 439 | 644116 | std::vector<T> coeffs; | |
| 440 |
1/1✓ Branch 2 → 3 taken 644051 times.
|
644116 | fft::transformed<E> f; |
| 441 |
2/2✓ Branch 2 → 3 taken 644051 times.
✓ Branch 52 → 53 taken 65 times.
|
644311 | fft::multiply_add2_cached<E>( |
| 442 | av, av.cache(), | ||
| 443 | bv, bv.cache(), | ||
| 444 | cv, cv.cache(), | ||
| 445 | dv, dv.cache(), | ||
| 446 | coeffs, f | ||
| 447 | ); | ||
| 448 | 644376 | cached<E, true> w(exact<E>(std::move(coeffs))); | |
| 449 | 644116 | w.cache() = std::move(f); | |
| 450 | 644181 | return w; | |
| 451 | 644441 | } | |
| 452 | |||
| 453 | // coefficients [b.len()-1, a.len()) of a*b; requires a.len() >= b.len() > 0. | ||
| 454 | // The kernel b participates whole, so it must be exact; the result mirrors a's kind. | ||
| 455 | template <like A, exact_like B> requires fft::same_engine<A, B> | ||
| 456 | 2652143 | vec<typename A::engine_t, A::exact_v> middle_product(const A& a, const B& b) { | |
| 457 | using E = typename A::engine_t; | ||
| 458 | 2652143 | fft::transformed<E> ta_, tb_; | |
| 459 | 2652143 | auto av = detail::as_cached_span(a, ta_); | |
| 460 |
1/1✓ Branch 2 → 3 taken 2651880 times.
|
2652143 | auto bv = detail::as_cached_span(b, tb_); |
| 461 |
3/3wala::series::vec<wala::series::cached<wala::fft::engines::ntt<wala::modnum<998244353> >, true>::engine_t, wala::series::cached<wala::fft::engines::ntt<wala::modnum<998244353> >, true>::exact_v> wala::series::middle_product<wala::series::cached<wala::fft::engines::ntt<wala::modnum<998244353> >, true>, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, true> >(wala::series::cached<wala::fft::engines::ntt<wala::modnum<998244353> >, true> const&, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, true> const&):
✓ Branch 27 → 28 taken 1 time.
wala::series::vec<wala::series::cached<wala::fft::engines::ntt<wala::modnum<998244353> >, true>::engine_t, wala::series::cached<wala::fft::engines::ntt<wala::modnum<998244353> >, true>::exact_v> wala::series::middle_product<wala::series::cached<wala::fft::engines::ntt<wala::modnum<998244353> >, true>, wala::series::cached<wala::fft::engines::ntt<wala::modnum<998244353> >, true> >(wala::series::cached<wala::fft::engines::ntt<wala::modnum<998244353> >, true> const&, wala::series::cached<wala::fft::engines::ntt<wala::modnum<998244353> >, true> const&):
✓ Branch 2 → 3 taken 2651880 times.
✓ Branch 27 → 28 taken 262 times.
|
5304549 | return vec<E, A::exact_v>(fft::middle_product<E>( |
| 462 | av, av.cache(), | ||
| 463 | bv, bv.cache() | ||
| 464 | 2652669 | )); | |
| 465 | 2652406 | } | |
| 466 | |||
| 467 | namespace detail { | ||
| 468 | 1327954 | template <bool ea, bool eb> int product_prec(int la, int lb) { | |
| 469 |
2/4✓ Branch 2 → 3 taken 1326258 times.
✗ Branch 2 → 5 not taken.
✓ Branch 3 → 4 taken 1326258 times.
✗ Branch 3 → 5 not taken.
|
1326258 | if constexpr (ea && eb) return la > 0 && lb > 0 ? la + lb - 1 : 0; |
| 470 | 1696 | else return ea ? lb : eb ? la : std::min(la, lb); | |
| 471 | } | ||
| 472 | |||
| 473 | // Normalize a product operand at the given precision to a borrowed series + the | ||
| 474 | // whole cache serving it: a prefix cache at scale nextPow2(prec), or the whole | ||
| 475 | // span with the operand's own cache, or a truncated span with the caller's | ||
| 476 | // throwaway cache. | ||
| 477 | // A whole cache of an over-length operand (len > prec, which pins the other, | ||
| 478 | // necessarily trunc, operand's span at exactly prec) is only worth using when | ||
| 479 | // the untruncated span doesn't grow the transform size: a 2x'd inverse | ||
| 480 | // transform costs more than the saved forward transform. | ||
| 481 | template <like S> | ||
| 482 |
5/10auto wala::series::detail::product_operand<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&, int, wala::series::vec<wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >, true>::engine_t::transformed&):
✗ Branch 2 → 3 not taken.
✓ Branch 2 → 4 taken 96 times.
auto wala::series::detail::product_operand<wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> >(wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> const&, int, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false>::engine_t::transformed&):
✗ Branch 2 → 3 not taken.
✓ Branch 2 → 4 taken 2581 times.
auto wala::series::detail::product_operand<wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, true> >(wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, true> const&, int, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, true>::engine_t::transformed&):
✗ Branch 2 → 3 not taken.
✓ Branch 2 → 4 taken 144 times.
auto wala::series::detail::product_operand<wala::series::vec<wala::fft::engines::split<wala::modnum<1000000007> >, true> >(wala::series::vec<wala::fft::engines::split<wala::modnum<1000000007> >, true> const&, int, wala::series::vec<wala::fft::engines::split<wala::modnum<1000000007> >, true>::engine_t::transformed&):
✗ Branch 2 → 3 not taken.
✓ Branch 2 → 4 taken 96 times.
auto wala::series::detail::product_operand<wala::series::cached<wala::fft::engines::ntt<wala::modnum<998244353> >, true> >(wala::series::cached<wala::fft::engines::ntt<wala::modnum<998244353> >, true> const&, int, wala::series::cached<wala::fft::engines::ntt<wala::modnum<998244353> >, true>::engine_t::transformed&):
✗ Branch 2 → 3 not taken.
✓ Branch 2 → 4 taken 2651891 times.
|
2655860 | auto product_operand(const S& s, int prec, fft::transformed<typename S::engine_t>& tmp) { |
| 483 | using E = typename S::engine_t; | ||
| 484 | if constexpr (has_prefix_cache<S>) { | ||
| 485 |
1/1✓ Branch 21 → 22 taken 20 times.
|
40 | return s.first(std::min(s.len(), nextPow2(prec))); |
| 486 | } else { | ||
| 487 | 2655840 | span<E, S::exact_v> v = s; | |
| 488 |
7/14auto wala::series::detail::product_operand<wala::series::cached_span<wala::fft::engines::ntt<wala::modnum<998244353> >, true> >(wala::series::cached_span<wala::fft::engines::ntt<wala::modnum<998244353> >, true> const&, int, wala::series::cached_span<wala::fft::engines::ntt<wala::modnum<998244353> >, true>::engine_t::transformed&):
✓ Branch 2 → 3 taken 20 times.
✗ Branch 2 → 6 not taken.
auto wala::series::detail::product_operand<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&, int, wala::series::vec<wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >, true>::engine_t::transformed&):
✗ Branch 4 → 5 not taken.
✓ Branch 4 → 8 taken 96 times.
auto wala::series::detail::product_operand<wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> >(wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> const&, int, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false>::engine_t::transformed&):
✗ Branch 4 → 5 not taken.
✓ Branch 4 → 8 taken 2581 times.
auto wala::series::detail::product_operand<wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, true> >(wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, true> const&, int, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, true>::engine_t::transformed&):
✗ Branch 4 → 5 not taken.
✓ Branch 4 → 8 taken 144 times.
auto wala::series::detail::product_operand<wala::series::vec<wala::fft::engines::split<wala::modnum<1000000007> >, true> >(wala::series::vec<wala::fft::engines::split<wala::modnum<1000000007> >, true> const&, int, wala::series::vec<wala::fft::engines::split<wala::modnum<1000000007> >, true>::engine_t::transformed&):
✗ Branch 4 → 5 not taken.
✓ Branch 4 → 8 taken 96 times.
auto wala::series::detail::product_operand<wala::series::span<wala::fft::engines::ntt<wala::modnum<998244353> >, false> >(wala::series::span<wala::fft::engines::ntt<wala::modnum<998244353> >, false> const&, int, wala::series::span<wala::fft::engines::ntt<wala::modnum<998244353> >, false>::engine_t::transformed&):
✗ Branch 2 → 3 not taken.
✓ Branch 2 → 6 taken 20 times.
auto wala::series::detail::product_operand<wala::series::cached<wala::fft::engines::ntt<wala::modnum<998244353> >, true> >(wala::series::cached<wala::fft::engines::ntt<wala::modnum<998244353> >, true> const&, int, wala::series::cached<wala::fft::engines::ntt<wala::modnum<998244353> >, true>::engine_t::transformed&):
✓ Branch 4 → 5 taken 2651891 times.
✗ Branch 4 → 8 not taken.
|
2656832 | int used = std::min(v.len(), prec); |
| 489 |
19/38auto wala::series::detail::product_operand<wala::series::cached_span<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> const&, int, wala::series::cached_span<wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >, true>::engine_t::transformed&):
✓ Branch 24 → 25 taken 20 times.
✗ Branch 24 → 51 not taken.
auto wala::series::detail::product_operand<wala::series::cached_span<wala::fft::engines::ntt<wala::mod_goldilocks>, true> >(wala::series::cached_span<wala::fft::engines::ntt<wala::mod_goldilocks>, true> const&, int, wala::series::cached_span<wala::fft::engines::ntt<wala::mod_goldilocks>, true>::engine_t::transformed&):
✓ Branch 24 → 25 taken 20 times.
✗ Branch 24 → 51 not taken.
auto wala::series::detail::product_operand<wala::series::cached_span<wala::fft::engines::ntt<wala::modnum<998244353> >, true> >(wala::series::cached_span<wala::fft::engines::ntt<wala::modnum<998244353> >, true> const&, int, wala::series::cached_span<wala::fft::engines::ntt<wala::modnum<998244353> >, true>::engine_t::transformed&):
✓ Branch 2 → 3 taken 20 times.
✗ Branch 2 → 6 not taken.
✓ Branch 24 → 25 taken 20 times.
✗ Branch 24 → 51 not taken.
auto wala::series::detail::product_operand<wala::series::cached_span<wala::fft::engines::split<wala::modnum<1000000007> >, true> >(wala::series::cached_span<wala::fft::engines::split<wala::modnum<1000000007> >, true> const&, int, wala::series::cached_span<wala::fft::engines::split<wala::modnum<1000000007> >, true>::engine_t::transformed&):
✓ Branch 24 → 25 taken 20 times.
✗ Branch 24 → 51 not taken.
auto wala::series::detail::product_operand<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&, int, wala::series::vec<wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >, true>::engine_t::transformed&):
✗ Branch 4 → 5 not taken.
✓ Branch 4 → 8 taken 96 times.
auto wala::series::detail::product_operand<wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> >(wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> const&, int, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false>::engine_t::transformed&):
✗ Branch 4 → 5 not taken.
✓ Branch 4 → 8 taken 2581 times.
✗ Branch 23 → 24 not taken.
✓ Branch 23 → 48 taken 460 times.
auto wala::series::detail::product_operand<wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, true> >(wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, true> const&, int, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, true>::engine_t::transformed&):
✗ Branch 4 → 5 not taken.
✓ Branch 4 → 8 taken 144 times.
✗ Branch 23 → 24 not taken.
✓ Branch 23 → 48 taken 96 times.
auto wala::series::detail::product_operand<wala::series::vec<wala::fft::engines::split<wala::modnum<1000000007> >, true> >(wala::series::vec<wala::fft::engines::split<wala::modnum<1000000007> >, true> const&, int, wala::series::vec<wala::fft::engines::split<wala::modnum<1000000007> >, true>::engine_t::transformed&):
✗ Branch 4 → 5 not taken.
✓ Branch 4 → 8 taken 96 times.
auto wala::series::detail::product_operand<wala::series::span<wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >, false> >(wala::series::span<wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >, false> const&, int, wala::series::span<wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >, false>::engine_t::transformed&):
✗ Branch 23 → 24 not taken.
✓ Branch 23 → 44 taken 20 times.
auto wala::series::detail::product_operand<wala::series::span<wala::fft::engines::ntt<wala::mod_goldilocks>, false> >(wala::series::span<wala::fft::engines::ntt<wala::mod_goldilocks>, false> const&, int, wala::series::span<wala::fft::engines::ntt<wala::mod_goldilocks>, false>::engine_t::transformed&):
✗ Branch 23 → 24 not taken.
✓ Branch 23 → 44 taken 20 times.
auto wala::series::detail::product_operand<wala::series::span<wala::fft::engines::ntt<wala::modnum<998244353> >, false> >(wala::series::span<wala::fft::engines::ntt<wala::modnum<998244353> >, false> const&, int, wala::series::span<wala::fft::engines::ntt<wala::modnum<998244353> >, false>::engine_t::transformed&):
✗ Branch 2 → 3 not taken.
✓ Branch 2 → 6 taken 20 times.
✗ Branch 23 → 24 not taken.
✓ Branch 23 → 44 taken 20 times.
auto wala::series::detail::product_operand<wala::series::span<wala::fft::engines::split<wala::modnum<1000000007> >, false> >(wala::series::span<wala::fft::engines::split<wala::modnum<1000000007> >, false> const&, int, wala::series::span<wala::fft::engines::split<wala::modnum<1000000007> >, false>::engine_t::transformed&):
✗ Branch 23 → 24 not taken.
✓ Branch 23 → 44 taken 20 times.
auto wala::series::detail::product_operand<wala::series::cached<wala::fft::engines::ntt<wala::modnum<998244353> >, false> >(wala::series::cached<wala::fft::engines::ntt<wala::modnum<998244353> >, false> const&, int, wala::series::cached<wala::fft::engines::ntt<wala::modnum<998244353> >, false>::engine_t::transformed&):
✓ Branch 26 → 27 taken 3 times.
✗ Branch 26 → 57 not taken.
auto wala::series::detail::product_operand<wala::series::cached<wala::fft::engines::ntt<wala::modnum<998244353> >, true> >(wala::series::cached<wala::fft::engines::ntt<wala::modnum<998244353> >, true> const&, int, wala::series::cached<wala::fft::engines::ntt<wala::modnum<998244353> >, true>::engine_t::transformed&):
✓ Branch 4 → 5 taken 2651891 times.
✗ Branch 4 → 8 not taken.
✓ Branch 26 → 27 taken 273 times.
✗ Branch 26 → 57 not taken.
|
2656832 | if (auto co = cache_of(s)) { |
| 490 |
9/38auto wala::series::detail::product_operand<wala::series::cached_span<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> const&, int, wala::series::cached_span<wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >, true>::engine_t::transformed&):
✓ Branch 33 → 34 taken 20 times.
✗ Branch 33 → 45 not taken.
auto wala::series::detail::product_operand<wala::series::cached_span<wala::fft::engines::ntt<wala::mod_goldilocks>, true> >(wala::series::cached_span<wala::fft::engines::ntt<wala::mod_goldilocks>, true> const&, int, wala::series::cached_span<wala::fft::engines::ntt<wala::mod_goldilocks>, true>::engine_t::transformed&):
✓ Branch 33 → 34 taken 20 times.
✗ Branch 33 → 45 not taken.
auto wala::series::detail::product_operand<wala::series::cached_span<wala::fft::engines::ntt<wala::modnum<998244353> >, true> >(wala::series::cached_span<wala::fft::engines::ntt<wala::modnum<998244353> >, true> const&, int, wala::series::cached_span<wala::fft::engines::ntt<wala::modnum<998244353> >, true>::engine_t::transformed&):
✓ Branch 3 → 4 taken 20 times.
✗ Branch 3 → 5 not taken.
✓ Branch 33 → 34 taken 20 times.
✗ Branch 33 → 45 not taken.
auto wala::series::detail::product_operand<wala::series::cached_span<wala::fft::engines::split<wala::modnum<1000000007> >, true> >(wala::series::cached_span<wala::fft::engines::split<wala::modnum<1000000007> >, true> const&, int, wala::series::cached_span<wala::fft::engines::split<wala::modnum<1000000007> >, true>::engine_t::transformed&):
✓ Branch 33 → 34 taken 20 times.
✗ Branch 33 → 45 not taken.
auto wala::series::detail::product_operand<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&, int, wala::series::vec<wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >, true>::engine_t::transformed&):
✗ Branch 5 → 6 not taken.
✗ Branch 5 → 7 not taken.
auto wala::series::detail::product_operand<wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> >(wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> const&, int, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false>::engine_t::transformed&):
✗ Branch 5 → 6 not taken.
✗ Branch 5 → 7 not taken.
✗ Branch 31 → 32 not taken.
✗ Branch 31 → 42 not taken.
auto wala::series::detail::product_operand<wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, true> >(wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, true> const&, int, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, true>::engine_t::transformed&):
✗ Branch 5 → 6 not taken.
✗ Branch 5 → 7 not taken.
✗ Branch 31 → 32 not taken.
✗ Branch 31 → 42 not taken.
auto wala::series::detail::product_operand<wala::series::vec<wala::fft::engines::split<wala::modnum<1000000007> >, true> >(wala::series::vec<wala::fft::engines::split<wala::modnum<1000000007> >, true> const&, int, wala::series::vec<wala::fft::engines::split<wala::modnum<1000000007> >, true>::engine_t::transformed&):
✗ Branch 5 → 6 not taken.
✗ Branch 5 → 7 not taken.
auto wala::series::detail::product_operand<wala::series::span<wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >, false> >(wala::series::span<wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >, false> const&, int, wala::series::span<wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >, false>::engine_t::transformed&):
✗ Branch 29 → 30 not taken.
✗ Branch 29 → 38 not taken.
auto wala::series::detail::product_operand<wala::series::span<wala::fft::engines::ntt<wala::mod_goldilocks>, false> >(wala::series::span<wala::fft::engines::ntt<wala::mod_goldilocks>, false> const&, int, wala::series::span<wala::fft::engines::ntt<wala::mod_goldilocks>, false>::engine_t::transformed&):
✗ Branch 29 → 30 not taken.
✗ Branch 29 → 38 not taken.
auto wala::series::detail::product_operand<wala::series::span<wala::fft::engines::ntt<wala::modnum<998244353> >, false> >(wala::series::span<wala::fft::engines::ntt<wala::modnum<998244353> >, false> const&, int, wala::series::span<wala::fft::engines::ntt<wala::modnum<998244353> >, false>::engine_t::transformed&):
✗ Branch 3 → 4 not taken.
✗ Branch 3 → 5 not taken.
✗ Branch 29 → 30 not taken.
✗ Branch 29 → 38 not taken.
auto wala::series::detail::product_operand<wala::series::span<wala::fft::engines::split<wala::modnum<1000000007> >, false> >(wala::series::span<wala::fft::engines::split<wala::modnum<1000000007> >, false> const&, int, wala::series::span<wala::fft::engines::split<wala::modnum<1000000007> >, false>::engine_t::transformed&):
✗ Branch 29 → 30 not taken.
✗ Branch 29 → 38 not taken.
auto wala::series::detail::product_operand<wala::series::cached<wala::fft::engines::ntt<wala::modnum<998244353> >, false> >(wala::series::cached<wala::fft::engines::ntt<wala::modnum<998244353> >, false> const&, int, wala::series::cached<wala::fft::engines::ntt<wala::modnum<998244353> >, false>::engine_t::transformed&):
✓ Branch 37 → 38 taken 1 time.
✓ Branch 37 → 51 taken 2 times.
auto wala::series::detail::product_operand<wala::series::cached<wala::fft::engines::ntt<wala::modnum<998244353> >, true> >(wala::series::cached<wala::fft::engines::ntt<wala::modnum<998244353> >, true> const&, int, wala::series::cached<wala::fft::engines::ntt<wala::modnum<998244353> >, true>::engine_t::transformed&):
✗ Branch 5 → 6 not taken.
✓ Branch 5 → 7 taken 2651891 times.
✗ Branch 37 → 38 not taken.
✓ Branch 37 → 51 taken 273 times.
|
2652704 | if (s.len() <= prec || fft::detail::conv_size_for(s.len() + prec - 1).n |
| 491 |
11/38auto wala::series::detail::product_operand<wala::series::cached_span<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> const&, int, wala::series::cached_span<wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >, true>::engine_t::transformed&):
✓ Branch 44 → 45 taken 15 times.
✓ Branch 44 → 51 taken 5 times.
auto wala::series::detail::product_operand<wala::series::cached_span<wala::fft::engines::ntt<wala::mod_goldilocks>, true> >(wala::series::cached_span<wala::fft::engines::ntt<wala::mod_goldilocks>, true> const&, int, wala::series::cached_span<wala::fft::engines::ntt<wala::mod_goldilocks>, true>::engine_t::transformed&):
✓ Branch 44 → 45 taken 15 times.
✓ Branch 44 → 51 taken 5 times.
auto wala::series::detail::product_operand<wala::series::cached_span<wala::fft::engines::ntt<wala::modnum<998244353> >, true> >(wala::series::cached_span<wala::fft::engines::ntt<wala::modnum<998244353> >, true> const&, int, wala::series::cached_span<wala::fft::engines::ntt<wala::modnum<998244353> >, true>::engine_t::transformed&):
✓ Branch 4 → 5 taken 18 times.
✓ Branch 4 → 6 taken 2 times.
✓ Branch 44 → 45 taken 15 times.
✓ Branch 44 → 51 taken 5 times.
auto wala::series::detail::product_operand<wala::series::cached_span<wala::fft::engines::split<wala::modnum<1000000007> >, true> >(wala::series::cached_span<wala::fft::engines::split<wala::modnum<1000000007> >, true> const&, int, wala::series::cached_span<wala::fft::engines::split<wala::modnum<1000000007> >, true>::engine_t::transformed&):
✓ Branch 44 → 45 taken 15 times.
✓ Branch 44 → 51 taken 5 times.
auto wala::series::detail::product_operand<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&, int, wala::series::vec<wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >, true>::engine_t::transformed&):
✗ Branch 6 → 7 not taken.
✗ Branch 6 → 8 not taken.
auto wala::series::detail::product_operand<wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> >(wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> const&, int, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false>::engine_t::transformed&):
✗ Branch 6 → 7 not taken.
✗ Branch 6 → 8 not taken.
✗ Branch 41 → 42 not taken.
✗ Branch 41 → 48 not taken.
auto wala::series::detail::product_operand<wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, true> >(wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, true> const&, int, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, true>::engine_t::transformed&):
✗ Branch 6 → 7 not taken.
✗ Branch 6 → 8 not taken.
✗ Branch 41 → 42 not taken.
✗ Branch 41 → 48 not taken.
auto wala::series::detail::product_operand<wala::series::vec<wala::fft::engines::split<wala::modnum<1000000007> >, true> >(wala::series::vec<wala::fft::engines::split<wala::modnum<1000000007> >, true> const&, int, wala::series::vec<wala::fft::engines::split<wala::modnum<1000000007> >, true>::engine_t::transformed&):
✗ Branch 6 → 7 not taken.
✗ Branch 6 → 8 not taken.
auto wala::series::detail::product_operand<wala::series::span<wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >, false> >(wala::series::span<wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >, false> const&, int, wala::series::span<wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >, false>::engine_t::transformed&):
✗ Branch 37 → 38 not taken.
✗ Branch 37 → 44 not taken.
auto wala::series::detail::product_operand<wala::series::span<wala::fft::engines::ntt<wala::mod_goldilocks>, false> >(wala::series::span<wala::fft::engines::ntt<wala::mod_goldilocks>, false> const&, int, wala::series::span<wala::fft::engines::ntt<wala::mod_goldilocks>, false>::engine_t::transformed&):
✗ Branch 37 → 38 not taken.
✗ Branch 37 → 44 not taken.
auto wala::series::detail::product_operand<wala::series::span<wala::fft::engines::ntt<wala::modnum<998244353> >, false> >(wala::series::span<wala::fft::engines::ntt<wala::modnum<998244353> >, false> const&, int, wala::series::span<wala::fft::engines::ntt<wala::modnum<998244353> >, false>::engine_t::transformed&):
✗ Branch 4 → 5 not taken.
✗ Branch 4 → 6 not taken.
✗ Branch 37 → 38 not taken.
✗ Branch 37 → 44 not taken.
auto wala::series::detail::product_operand<wala::series::span<wala::fft::engines::split<wala::modnum<1000000007> >, false> >(wala::series::span<wala::fft::engines::split<wala::modnum<1000000007> >, false> const&, int, wala::series::span<wala::fft::engines::split<wala::modnum<1000000007> >, false>::engine_t::transformed&):
✗ Branch 37 → 38 not taken.
✗ Branch 37 → 44 not taken.
auto wala::series::detail::product_operand<wala::series::cached<wala::fft::engines::ntt<wala::modnum<998244353> >, false> >(wala::series::cached<wala::fft::engines::ntt<wala::modnum<998244353> >, false> const&, int, wala::series::cached<wala::fft::engines::ntt<wala::modnum<998244353> >, false>::engine_t::transformed&):
✓ Branch 50 → 51 taken 1 time.
✗ Branch 50 → 57 not taken.
auto wala::series::detail::product_operand<wala::series::cached<wala::fft::engines::ntt<wala::modnum<998244353> >, true> >(wala::series::cached<wala::fft::engines::ntt<wala::modnum<998244353> >, true> const&, int, wala::series::cached<wala::fft::engines::ntt<wala::modnum<998244353> >, true>::engine_t::transformed&):
✗ Branch 6 → 7 not taken.
✗ Branch 6 → 8 not taken.
✗ Branch 50 → 51 not taken.
✗ Branch 50 → 57 not taken.
|
101 | == fft::detail::conv_size_for(2 * prec - 1).n) { |
| 492 | 2652245 | return cached_span<E, S::exact_v>{v, co->get()}; | |
| 493 | } | ||
| 494 | } | ||
| 495 | 3595 | return cached_span<E, S::exact_v>{v.first(used), tmp}; | |
| 496 | } | ||
| 497 | } | ||
| 498 | } // namespace detail | ||
| 499 | |||
| 500 | template <like A, like B> requires fft::same_engine<A, B> | ||
| 501 | 3 | vec<typename A::engine_t, A::exact_v && B::exact_v> operator + (const A& a, const B& b) { | |
| 502 | using T = typename A::engine_t::value_type; | ||
| 503 | 5 | int n = (A::exact_v && B::exact_v) ? std::max(a.len(), b.len()) | |
| 504 | 4 | : A::exact_v ? b.len() : B::exact_v ? a.len() : std::min(a.len(), b.len()); | |
| 505 | 9 | vec<typename A::engine_t, A::exact_v && B::exact_v> r(size_t(n), T(0)); | |
| 506 |
6/6wala::series::vec<wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false>::engine_t, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false>::exact_v&&wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false>::exact_v> wala::series::operator+<wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false>, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> >(wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> const&, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> const&):
✓ Branch 91 → 37 taken 23 times.
✓ Branch 91 → 92 taken 1 time.
wala::series::vec<wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, true>::engine_t, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, true>::exact_v&&wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false>::exact_v> wala::series::operator+<wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, true>, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> >(wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, true> const&, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> const&):
✓ Branch 75 → 21 taken 23 times.
✓ Branch 75 → 76 taken 1 time.
wala::series::vec<wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, true>::engine_t, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, true>::exact_v&&wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, true>::exact_v> wala::series::operator+<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&):
✓ Branch 91 → 37 taken 37 times.
✓ Branch 91 → 92 taken 1 time.
|
86 | for (int i = 0; i < n; i++) { |
| 507 |
7/12wala::series::vec<wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false>::engine_t, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false>::exact_v&&wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false>::exact_v> wala::series::operator+<wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false>, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> >(wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> const&, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> const&):
✓ Branch 46 → 47 taken 23 times.
✗ Branch 46 → 55 not taken.
✓ Branch 67 → 68 taken 23 times.
✗ Branch 67 → 76 not taken.
wala::series::vec<wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, true>::engine_t, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, true>::exact_v&&wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false>::exact_v> wala::series::operator+<wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, true>, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> >(wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, true> const&, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> const&):
✓ Branch 30 → 31 taken 23 times.
✗ Branch 30 → 39 not taken.
✓ Branch 51 → 52 taken 23 times.
✗ Branch 51 → 60 not taken.
wala::series::vec<wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, true>::engine_t, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, true>::exact_v&&wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, true>::exact_v> wala::series::operator+<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&):
✓ Branch 46 → 47 taken 23 times.
✓ Branch 46 → 55 taken 14 times.
✓ Branch 67 → 68 taken 37 times.
✗ Branch 67 → 76 not taken.
|
263 | r[i] = (i < a.len() ? a[i] : T(0)) + (i < b.len() ? b[i] : T(0)); |
| 508 | } | ||
| 509 | 3 | return r; | |
| 510 | } | ||
| 511 | template <like A, like B> requires fft::same_engine<A, B> | ||
| 512 |
1/2✗ Branch 2 → 3 not taken.
✓ Branch 2 → 4 taken 578 times.
|
614 | vec<typename A::engine_t, A::exact_v && B::exact_v> operator - (const A& a, const B& b) { |
| 513 | using T = typename A::engine_t::value_type; | ||
| 514 | 38 | int n = (A::exact_v && B::exact_v) ? std::max(a.len(), b.len()) | |
| 515 |
1/2✗ Branch 4 → 5 not taken.
✓ Branch 4 → 6 taken 578 times.
|
714 | : A::exact_v ? b.len() : B::exact_v ? a.len() : std::min(a.len(), b.len()); |
| 516 | 686 | vec<typename A::engine_t, A::exact_v && B::exact_v> r(size_t(n), T(0)); | |
| 517 |
8/8wala::series::vec<wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false>::engine_t, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false>::exact_v&&wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, true>::exact_v> wala::series::operator-<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&):
✓ Branch 75 → 21 taken 23 times.
✓ Branch 75 → 76 taken 1 time.
wala::series::vec<wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false>::engine_t, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false>::exact_v&&wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false>::exact_v> wala::series::operator-<wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false>, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> >(wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> const&, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> const&):
✓ Branch 20 → 8 taken 12812331 times.
✓ Branch 20 → 21 taken 578 times.
✓ Branch 91 → 37 taken 339 times.
✓ Branch 91 → 92 taken 34 times.
wala::series::vec<wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, true>::engine_t, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, true>::exact_v&&wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, true>::exact_v> wala::series::operator-<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&):
✓ Branch 91 → 37 taken 37 times.
✓ Branch 91 → 92 taken 1 time.
|
12813344 | for (int i = 0; i < n; i++) { |
| 518 |
9/16wala::series::vec<wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false>::engine_t, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false>::exact_v&&wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, true>::exact_v> wala::series::operator-<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&):
✓ Branch 30 → 31 taken 23 times.
✗ Branch 30 → 39 not taken.
✓ Branch 51 → 52 taken 23 times.
✗ Branch 51 → 60 not taken.
wala::series::vec<wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false>::engine_t, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false>::exact_v&&wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false>::exact_v> wala::series::operator-<wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false>, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> >(wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> const&, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> const&):
✓ Branch 10 → 11 taken 12812331 times.
✗ Branch 10 → 12 not taken.
✓ Branch 14 → 15 taken 12812331 times.
✗ Branch 14 → 16 not taken.
✓ Branch 46 → 47 taken 339 times.
✗ Branch 46 → 55 not taken.
✓ Branch 67 → 68 taken 339 times.
✗ Branch 67 → 76 not taken.
wala::series::vec<wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, true>::engine_t, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, true>::exact_v&&wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, true>::exact_v> wala::series::operator-<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&):
✓ Branch 46 → 47 taken 23 times.
✓ Branch 46 → 55 taken 14 times.
✓ Branch 67 → 68 taken 37 times.
✗ Branch 67 → 76 not taken.
|
38438204 | r[i] = (i < a.len() ? a[i] : T(0)) - (i < b.len() ? b[i] : T(0)); |
| 519 | } | ||
| 520 | 614 | return r; | |
| 521 | } | ||
| 522 | |||
| 523 | // The single multiplication operator: each operand is normalized to a borrowed | ||
| 524 | // series + whole cache (see detail::product_operand), then multiplied once. | ||
| 525 | // An exact x exact product returns a has_cache result, going through | ||
| 526 | // fft::multiply_cached so the pointwise product is adopted as the result's | ||
| 527 | // transform whenever the engine supports it. | ||
| 528 | template <like A, like B> requires fft::same_engine<A, B> | ||
| 529 | 1327954 | auto operator * (const A& a, const B& b) { | |
| 530 | using E = typename A::engine_t; | ||
| 531 | using T = typename E::value_type; | ||
| 532 |
7/14auto wala::series::operator*<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&):
✗ Branch 2 → 3 not taken.
✓ Branch 2 → 4 taken 48 times.
auto wala::series::operator*<wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false>, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> >(wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> const&, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> const&):
✗ Branch 2 → 3 not taken.
✓ Branch 2 → 4 taken 1266 times.
auto wala::series::operator*<wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, true>, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> >(wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, true> const&, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> const&):
✗ Branch 2 → 3 not taken.
✓ Branch 2 → 4 taken 38 times.
auto wala::series::operator*<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&):
✗ Branch 2 → 3 not taken.
✓ Branch 2 → 4 taken 53 times.
auto wala::series::operator*<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&):
✗ Branch 2 → 3 not taken.
✓ Branch 2 → 4 taken 48 times.
auto wala::series::operator*<wala::series::cached<wala::fft::engines::ntt<wala::modnum<998244353> >, true>, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> >(wala::series::cached<wala::fft::engines::ntt<wala::modnum<998244353> >, true> const&, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> const&):
✗ Branch 2 → 3 not taken.
✓ Branch 2 → 4 taken 11 times.
auto wala::series::operator*<wala::series::cached<wala::fft::engines::ntt<wala::modnum<998244353> >, true>, wala::series::cached<wala::fft::engines::ntt<wala::modnum<998244353> >, true> >(wala::series::cached<wala::fft::engines::ntt<wala::modnum<998244353> >, true> const&, wala::series::cached<wala::fft::engines::ntt<wala::modnum<998244353> >, true> const&):
✗ Branch 2 → 3 not taken.
✓ Branch 2 → 4 taken 1325940 times.
|
1327954 | constexpr bool ea = A::exact_v, eb = B::exact_v; |
| 533 |
7/14auto wala::series::operator*<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&):
✗ Branch 4 → 5 not taken.
✓ Branch 4 → 6 taken 48 times.
auto wala::series::operator*<wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false>, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> >(wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> const&, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> const&):
✗ Branch 4 → 5 not taken.
✓ Branch 4 → 6 taken 1266 times.
auto wala::series::operator*<wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, true>, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> >(wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, true> const&, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> const&):
✗ Branch 4 → 5 not taken.
✓ Branch 4 → 6 taken 38 times.
auto wala::series::operator*<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&):
✗ Branch 4 → 5 not taken.
✓ Branch 4 → 6 taken 53 times.
auto wala::series::operator*<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&):
✗ Branch 4 → 5 not taken.
✓ Branch 4 → 6 taken 48 times.
auto wala::series::operator*<wala::series::cached<wala::fft::engines::ntt<wala::modnum<998244353> >, true>, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> >(wala::series::cached<wala::fft::engines::ntt<wala::modnum<998244353> >, true> const&, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> const&):
✗ Branch 4 → 5 not taken.
✓ Branch 4 → 6 taken 11 times.
auto wala::series::operator*<wala::series::cached<wala::fft::engines::ntt<wala::modnum<998244353> >, true>, wala::series::cached<wala::fft::engines::ntt<wala::modnum<998244353> >, true> >(wala::series::cached<wala::fft::engines::ntt<wala::modnum<998244353> >, true> const&, wala::series::cached<wala::fft::engines::ntt<wala::modnum<998244353> >, true> const&):
✗ Branch 4 → 5 not taken.
✓ Branch 4 → 6 taken 1325940 times.
|
1328833 | int prec = detail::product_prec<ea, eb>(a.len(), b.len()); |
| 534 |
73/136auto wala::series::operator*<wala::series::prefix_cached<wala::fft::engines::ntt<wala::modnum<998244353> > >, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> >(wala::series::prefix_cached<wala::fft::engines::ntt<wala::modnum<998244353> > > const&, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> const&):
✓ Branch 20 → 21 taken 8 times.
✗ Branch 20 → 40 not taken.
✗ Branch 39 → 40 not taken.
✓ Branch 39 → 49 taken 8 times.
auto wala::series::operator*<wala::series::prefix_cached<wala::fft::engines::ntt<wala::modnum<998244353> > >, wala::series::prefix_cached<wala::fft::engines::ntt<wala::modnum<998244353> > > >(wala::series::prefix_cached<wala::fft::engines::ntt<wala::modnum<998244353> > > const&, wala::series::prefix_cached<wala::fft::engines::ntt<wala::modnum<998244353> > > const&):
✓ Branch 23 → 24 taken 2 times.
✗ Branch 23 → 46 not taken.
auto wala::series::operator*<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&):
✓ Branch 6 → 7 taken 48 times.
✗ Branch 6 → 9 not taken.
✓ Branch 7 → 8 taken 48 times.
✗ Branch 7 → 9 not taken.
✗ Branch 8 → 9 not taken.
✓ Branch 8 → 10 taken 48 times.
auto wala::series::operator*<wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false>, wala::series::prefix_cached<wala::fft::engines::ntt<wala::modnum<998244353> > > >(wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> const&, wala::series::prefix_cached<wala::fft::engines::ntt<wala::modnum<998244353> > > const&):
✓ Branch 20 → 21 taken 8 times.
✗ Branch 20 → 40 not taken.
✓ Branch 28 → 29 taken 8 times.
✗ Branch 28 → 40 not taken.
auto wala::series::operator*<wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false>, wala::series::cached<wala::fft::engines::ntt<wala::modnum<998244353> >, false> >(wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> const&, wala::series::cached<wala::fft::engines::ntt<wala::modnum<998244353> >, false> const&):
✓ Branch 20 → 21 taken 1 time.
✗ Branch 20 → 40 not taken.
✓ Branch 28 → 29 taken 1 time.
✗ Branch 28 → 40 not taken.
✗ Branch 39 → 40 not taken.
✓ Branch 39 → 49 taken 1 time.
auto wala::series::operator*<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&):
✓ Branch 17 → 18 taken 1 time.
✗ Branch 17 → 34 not taken.
✓ Branch 25 → 26 taken 1 time.
✗ Branch 25 → 34 not taken.
✗ Branch 33 → 34 not taken.
✓ Branch 33 → 43 taken 1 time.
auto wala::series::operator*<wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false>, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> >(wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> const&, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> const&):
✓ Branch 6 → 7 taken 1266 times.
✗ Branch 6 → 9 not taken.
✓ Branch 7 → 8 taken 1266 times.
✗ Branch 7 → 9 not taken.
✗ Branch 8 → 9 not taken.
✓ Branch 8 → 11 taken 1266 times.
✓ Branch 17 → 18 taken 205 times.
✗ Branch 17 → 34 not taken.
✓ Branch 25 → 26 taken 205 times.
✗ Branch 25 → 34 not taken.
✗ Branch 33 → 34 not taken.
✓ Branch 33 → 43 taken 205 times.
auto wala::series::operator*<wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, true>, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> >(wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, true> const&, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> const&):
✓ Branch 6 → 7 taken 38 times.
✗ Branch 6 → 9 not taken.
✓ Branch 7 → 8 taken 38 times.
✗ Branch 7 → 9 not taken.
✗ Branch 8 → 9 not taken.
✓ Branch 8 → 11 taken 38 times.
✓ Branch 17 → 18 taken 23 times.
✓ Branch 17 → 34 taken 4 times.
✓ Branch 25 → 26 taken 23 times.
✗ Branch 25 → 34 not taken.
✗ Branch 33 → 34 not taken.
✓ Branch 33 → 43 taken 23 times.
auto wala::series::operator*<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&):
✓ Branch 6 → 7 taken 53 times.
✗ Branch 6 → 9 not taken.
✓ Branch 7 → 8 taken 53 times.
✗ Branch 7 → 9 not taken.
✗ Branch 8 → 9 not taken.
✓ Branch 8 → 10 taken 53 times.
✓ Branch 16 → 17 taken 35 times.
✗ Branch 16 → 33 not taken.
✓ Branch 24 → 25 taken 35 times.
✗ Branch 24 → 33 not taken.
✗ Branch 32 → 33 not taken.
✓ Branch 32 → 42 taken 35 times.
auto wala::series::operator*<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&):
✓ Branch 6 → 7 taken 48 times.
✗ Branch 6 → 9 not taken.
✓ Branch 7 → 8 taken 48 times.
✗ Branch 7 → 9 not taken.
✗ Branch 8 → 9 not taken.
✓ Branch 8 → 10 taken 48 times.
auto wala::series::operator*<wala::series::span<wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >, false>, wala::series::cached_span<wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >, true> >(wala::series::span<wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >, false> const&, wala::series::cached_span<wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >, true> const&):
✓ Branch 16 → 17 taken 20 times.
✓ Branch 16 → 32 taken 5 times.
✓ Branch 22 → 23 taken 20 times.
✗ Branch 22 → 32 not taken.
✗ Branch 31 → 32 not taken.
✓ Branch 31 → 41 taken 20 times.
auto wala::series::operator*<wala::series::span<wala::fft::engines::ntt<wala::mod_goldilocks>, false>, wala::series::cached_span<wala::fft::engines::ntt<wala::mod_goldilocks>, true> >(wala::series::span<wala::fft::engines::ntt<wala::mod_goldilocks>, false> const&, wala::series::cached_span<wala::fft::engines::ntt<wala::mod_goldilocks>, true> const&):
✓ Branch 16 → 17 taken 20 times.
✓ Branch 16 → 32 taken 5 times.
✓ Branch 22 → 23 taken 20 times.
✗ Branch 22 → 32 not taken.
✗ Branch 31 → 32 not taken.
✓ Branch 31 → 41 taken 20 times.
auto wala::series::operator*<wala::series::span<wala::fft::engines::ntt<wala::modnum<998244353> >, false>, wala::series::cached_span<wala::fft::engines::ntt<wala::modnum<998244353> >, true> >(wala::series::span<wala::fft::engines::ntt<wala::modnum<998244353> >, false> const&, wala::series::cached_span<wala::fft::engines::ntt<wala::modnum<998244353> >, true> const&):
✓ Branch 2 → 3 taken 20 times.
✗ Branch 2 → 5 not taken.
✓ Branch 3 → 4 taken 20 times.
✗ Branch 3 → 5 not taken.
✗ Branch 4 → 5 not taken.
✓ Branch 4 → 7 taken 20 times.
✓ Branch 16 → 17 taken 20 times.
✓ Branch 16 → 32 taken 5 times.
✓ Branch 22 → 23 taken 20 times.
✗ Branch 22 → 32 not taken.
✗ Branch 31 → 32 not taken.
✓ Branch 31 → 41 taken 20 times.
auto wala::series::operator*<wala::series::span<wala::fft::engines::split<wala::modnum<1000000007> >, false>, wala::series::cached_span<wala::fft::engines::split<wala::modnum<1000000007> >, true> >(wala::series::span<wala::fft::engines::split<wala::modnum<1000000007> >, false> const&, wala::series::cached_span<wala::fft::engines::split<wala::modnum<1000000007> >, true> const&):
✓ Branch 16 → 17 taken 20 times.
✓ Branch 16 → 32 taken 5 times.
✓ Branch 22 → 23 taken 20 times.
✗ Branch 22 → 32 not taken.
✗ Branch 31 → 32 not taken.
✓ Branch 31 → 41 taken 20 times.
auto wala::series::operator*<wala::series::cached<wala::fft::engines::ntt<wala::modnum<998244353> >, false>, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> >(wala::series::cached<wala::fft::engines::ntt<wala::modnum<998244353> >, false> const&, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> const&):
✓ Branch 20 → 21 taken 2 times.
✗ Branch 20 → 40 not taken.
✓ Branch 31 → 32 taken 2 times.
✗ Branch 31 → 40 not taken.
✗ Branch 39 → 40 not taken.
✓ Branch 39 → 49 taken 2 times.
auto wala::series::operator*<wala::series::cached<wala::fft::engines::ntt<wala::modnum<998244353> >, true>, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> >(wala::series::cached<wala::fft::engines::ntt<wala::modnum<998244353> >, true> const&, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> const&):
✓ Branch 6 → 7 taken 11 times.
✗ Branch 6 → 9 not taken.
✓ Branch 7 → 8 taken 11 times.
✗ Branch 7 → 9 not taken.
✗ Branch 8 → 9 not taken.
✓ Branch 8 → 11 taken 11 times.
✓ Branch 20 → 21 taken 7 times.
✗ Branch 20 → 40 not taken.
✓ Branch 31 → 32 taken 7 times.
✗ Branch 31 → 40 not taken.
✗ Branch 39 → 40 not taken.
✓ Branch 39 → 49 taken 7 times.
auto wala::series::operator*<wala::series::cached<wala::fft::engines::ntt<wala::modnum<998244353> >, true>, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, true> >(wala::series::cached<wala::fft::engines::ntt<wala::modnum<998244353> >, true> const&, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, true> const&):
✓ Branch 19 → 20 taken 2 times.
✗ Branch 19 → 39 not taken.
✓ Branch 30 → 31 taken 2 times.
✗ Branch 30 → 39 not taken.
✗ Branch 38 → 39 not taken.
✓ Branch 38 → 48 taken 2 times.
auto wala::series::operator*<wala::series::cached<wala::fft::engines::ntt<wala::modnum<998244353> >, true>, wala::series::cached<wala::fft::engines::ntt<wala::modnum<998244353> >, true> >(wala::series::cached<wala::fft::engines::ntt<wala::modnum<998244353> >, true> const&, wala::series::cached<wala::fft::engines::ntt<wala::modnum<998244353> >, true> const&):
✓ Branch 6 → 7 taken 1325940 times.
✗ Branch 6 → 9 not taken.
✓ Branch 7 → 8 taken 1325940 times.
✗ Branch 7 → 9 not taken.
✗ Branch 8 → 9 not taken.
✓ Branch 8 → 10 taken 1325940 times.
✓ Branch 22 → 23 taken 132 times.
✗ Branch 22 → 45 not taken.
✓ Branch 33 → 34 taken 132 times.
✗ Branch 33 → 45 not taken.
✗ Branch 44 → 45 not taken.
✓ Branch 44 → 54 taken 132 times.
|
1328956 | if (prec == 0 || a.len() == 0 || b.len() == 0) { |
| 535 | ✗ | if constexpr (ea && eb) return cached<E, true>{}; | |
| 536 | 72 | else return trunc<E>(size_t(prec), T(0)); | |
| 537 | } | ||
| 538 | 1327930 | fft::transformed<E> ta_, tb_; | |
| 539 |
2/2auto wala::series::operator*<wala::series::prefix_cached<wala::fft::engines::ntt<wala::modnum<998244353> > >, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> >(wala::series::prefix_cached<wala::fft::engines::ntt<wala::modnum<998244353> > > const&, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> const&):
✓ Branch 52 → 55 taken 8 times.
auto wala::series::operator*<wala::series::prefix_cached<wala::fft::engines::ntt<wala::modnum<998244353> > >, wala::series::prefix_cached<wala::fft::engines::ntt<wala::modnum<998244353> > > >(wala::series::prefix_cached<wala::fft::engines::ntt<wala::modnum<998244353> > > const&, wala::series::prefix_cached<wala::fft::engines::ntt<wala::modnum<998244353> > > const&):
✓ Branch 58 → 61 taken 2 times.
|
1327930 | auto va = detail::product_operand(a, prec, ta_); |
| 540 |
6/6auto wala::series::operator*<wala::series::prefix_cached<wala::fft::engines::ntt<wala::modnum<998244353> > >, wala::series::prefix_cached<wala::fft::engines::ntt<wala::modnum<998244353> > > >(wala::series::prefix_cached<wala::fft::engines::ntt<wala::modnum<998244353> > > const&, wala::series::prefix_cached<wala::fft::engines::ntt<wala::modnum<998244353> > > const&):
✓ Branch 62 → 63 taken 2 times.
auto wala::series::operator*<wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false>, wala::series::prefix_cached<wala::fft::engines::ntt<wala::modnum<998244353> > > >(wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> const&, wala::series::prefix_cached<wala::fft::engines::ntt<wala::modnum<998244353> > > const&):
✓ Branch 54 → 57 taken 8 times.
auto wala::series::operator*<wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false>, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> >(wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> const&, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> const&):
✓ Branch 13 → 14 taken 1266 times.
auto wala::series::operator*<wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, true>, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> >(wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, true> const&, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> const&):
✓ Branch 13 → 14 taken 38 times.
auto wala::series::operator*<wala::series::span<wala::fft::engines::ntt<wala::modnum<998244353> >, false>, wala::series::cached_span<wala::fft::engines::ntt<wala::modnum<998244353> >, true> >(wala::series::span<wala::fft::engines::ntt<wala::modnum<998244353> >, false> const&, wala::series::cached_span<wala::fft::engines::ntt<wala::modnum<998244353> >, true> const&):
✓ Branch 9 → 10 taken 20 times.
auto wala::series::operator*<wala::series::cached<wala::fft::engines::ntt<wala::modnum<998244353> >, true>, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> >(wala::series::cached<wala::fft::engines::ntt<wala::modnum<998244353> >, true> const&, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> const&):
✓ Branch 13 → 14 taken 11 times.
|
1327930 | auto vb = detail::product_operand(b, prec, tb_); |
| 541 | if constexpr (ea && eb) { | ||
| 542 | 1326258 | std::vector<T> coeffs; | |
| 543 | 1326258 | fft::transformed<E> f; | |
| 544 |
4/4auto wala::series::operator*<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&):
✓ Branch 12 → 13 taken 48 times.
auto wala::series::operator*<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&):
✓ Branch 12 → 13 taken 53 times.
auto wala::series::operator*<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&):
✓ Branch 12 → 13 taken 48 times.
auto wala::series::operator*<wala::series::cached<wala::fft::engines::ntt<wala::modnum<998244353> >, true>, wala::series::cached<wala::fft::engines::ntt<wala::modnum<998244353> >, true> >(wala::series::cached<wala::fft::engines::ntt<wala::modnum<998244353> >, true> const&, wala::series::cached<wala::fft::engines::ntt<wala::modnum<998244353> >, true> const&):
✓ Branch 12 → 13 taken 1325940 times.
|
1326258 | auto ca = detail::as_cached_span(va, ta_), cb = detail::as_cached_span(vb, tb_); |
| 545 |
7/7auto wala::series::operator*<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&):
✓ Branch 12 → 13 taken 48 times.
auto wala::series::operator*<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&):
✓ Branch 12 → 13 taken 53 times.
✓ Branch 72 → 73 taken 35 times.
auto wala::series::operator*<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&):
✓ Branch 12 → 13 taken 48 times.
auto wala::series::operator*<wala::series::cached<wala::fft::engines::ntt<wala::modnum<998244353> >, true>, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, true> >(wala::series::cached<wala::fft::engines::ntt<wala::modnum<998244353> >, true> const&, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, true> const&):
✓ Branch 78 → 79 taken 2 times.
auto wala::series::operator*<wala::series::cached<wala::fft::engines::ntt<wala::modnum<998244353> >, true>, wala::series::cached<wala::fft::engines::ntt<wala::modnum<998244353> >, true> >(wala::series::cached<wala::fft::engines::ntt<wala::modnum<998244353> >, true> const&, wala::series::cached<wala::fft::engines::ntt<wala::modnum<998244353> >, true> const&):
✓ Branch 12 → 13 taken 1325940 times.
✓ Branch 84 → 85 taken 132 times.
|
1326427 | fft::multiply_cached<E>( |
| 546 | ca, ca.cache(), | ||
| 547 | cb, cb.cache(), | ||
| 548 | coeffs, f | ||
| 549 | ); | ||
| 550 | 1326934 | cached<E, true> w(exact<E>(std::move(coeffs))); | |
| 551 | 1326258 | w.cache() = std::move(f); | |
| 552 | 1326258 | return w; | |
| 553 | 1326644 | } else { | |
| 554 |
8/12auto wala::series::operator*<wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false>, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> >(wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> const&, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> const&):
✓ Branch 13 → 14 taken 1266 times.
✗ Branch 14 → 15 not taken.
✓ Branch 14 → 16 taken 1266 times.
auto wala::series::operator*<wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, true>, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> >(wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, true> const&, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> const&):
✓ Branch 13 → 14 taken 38 times.
✗ Branch 14 → 15 not taken.
✓ Branch 14 → 16 taken 38 times.
auto wala::series::operator*<wala::series::span<wala::fft::engines::ntt<wala::modnum<998244353> >, false>, wala::series::cached_span<wala::fft::engines::ntt<wala::modnum<998244353> >, true> >(wala::series::span<wala::fft::engines::ntt<wala::modnum<998244353> >, false> const&, wala::series::cached_span<wala::fft::engines::ntt<wala::modnum<998244353> >, true> const&):
✓ Branch 9 → 10 taken 20 times.
✗ Branch 10 → 11 not taken.
✓ Branch 10 → 12 taken 20 times.
auto wala::series::operator*<wala::series::cached<wala::fft::engines::ntt<wala::modnum<998244353> >, true>, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> >(wala::series::cached<wala::fft::engines::ntt<wala::modnum<998244353> >, true> const&, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> const&):
✓ Branch 13 → 14 taken 11 times.
✗ Branch 14 → 15 not taken.
✓ Branch 14 → 16 taken 11 times.
|
2346 | trunc<E> r(size_t(prec), T(0)); |
| 555 |
4/8auto wala::series::operator*<wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false>, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> >(wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> const&, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> const&):
✗ Branch 14 → 15 not taken.
✓ Branch 14 → 16 taken 1266 times.
auto wala::series::operator*<wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, true>, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> >(wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, true> const&, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> const&):
✗ Branch 14 → 15 not taken.
✓ Branch 14 → 16 taken 38 times.
auto wala::series::operator*<wala::series::span<wala::fft::engines::ntt<wala::modnum<998244353> >, false>, wala::series::cached_span<wala::fft::engines::ntt<wala::modnum<998244353> >, true> >(wala::series::span<wala::fft::engines::ntt<wala::modnum<998244353> >, false> const&, wala::series::cached_span<wala::fft::engines::ntt<wala::modnum<998244353> >, true> const&):
✗ Branch 10 → 11 not taken.
✓ Branch 10 → 12 taken 20 times.
auto wala::series::operator*<wala::series::cached<wala::fft::engines::ntt<wala::modnum<998244353> >, true>, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> >(wala::series::cached<wala::fft::engines::ntt<wala::modnum<998244353> >, true> const&, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> const&):
✗ Branch 14 → 15 not taken.
✓ Branch 14 → 16 taken 11 times.
|
1672 | auto ca = detail::as_cached_span(va, ta_), cb = detail::as_cached_span(vb, tb_); |
| 556 |
17/17auto wala::series::operator*<wala::series::prefix_cached<wala::fft::engines::ntt<wala::modnum<998244353> > >, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> >(wala::series::prefix_cached<wala::fft::engines::ntt<wala::modnum<998244353> > > const&, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> const&):
✓ Branch 93 → 94 taken 8 times.
auto wala::series::operator*<wala::series::prefix_cached<wala::fft::engines::ntt<wala::modnum<998244353> > >, wala::series::prefix_cached<wala::fft::engines::ntt<wala::modnum<998244353> > > >(wala::series::prefix_cached<wala::fft::engines::ntt<wala::modnum<998244353> > > const&, wala::series::prefix_cached<wala::fft::engines::ntt<wala::modnum<998244353> > > const&):
✓ Branch 99 → 100 taken 2 times.
auto wala::series::operator*<wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false>, wala::series::prefix_cached<wala::fft::engines::ntt<wala::modnum<998244353> > > >(wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> const&, wala::series::prefix_cached<wala::fft::engines::ntt<wala::modnum<998244353> > > const&):
✓ Branch 93 → 94 taken 8 times.
auto wala::series::operator*<wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false>, wala::series::cached<wala::fft::engines::ntt<wala::modnum<998244353> >, false> >(wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> const&, wala::series::cached<wala::fft::engines::ntt<wala::modnum<998244353> >, false> const&):
✓ Branch 93 → 94 taken 1 time.
auto wala::series::operator*<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&):
✓ Branch 87 → 88 taken 1 time.
auto wala::series::operator*<wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false>, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> >(wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> const&, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> const&):
✓ Branch 16 → 17 taken 1266 times.
✓ Branch 87 → 88 taken 205 times.
auto wala::series::operator*<wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, true>, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> >(wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, true> const&, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> const&):
✓ Branch 16 → 17 taken 38 times.
✓ Branch 87 → 88 taken 23 times.
auto wala::series::operator*<wala::series::span<wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >, false>, wala::series::cached_span<wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >, true> >(wala::series::span<wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >, false> const&, wala::series::cached_span<wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >, true> const&):
✓ Branch 85 → 86 taken 20 times.
auto wala::series::operator*<wala::series::span<wala::fft::engines::ntt<wala::mod_goldilocks>, false>, wala::series::cached_span<wala::fft::engines::ntt<wala::mod_goldilocks>, true> >(wala::series::span<wala::fft::engines::ntt<wala::mod_goldilocks>, false> const&, wala::series::cached_span<wala::fft::engines::ntt<wala::mod_goldilocks>, true> const&):
✓ Branch 85 → 86 taken 20 times.
auto wala::series::operator*<wala::series::span<wala::fft::engines::ntt<wala::modnum<998244353> >, false>, wala::series::cached_span<wala::fft::engines::ntt<wala::modnum<998244353> >, true> >(wala::series::span<wala::fft::engines::ntt<wala::modnum<998244353> >, false> const&, wala::series::cached_span<wala::fft::engines::ntt<wala::modnum<998244353> >, true> const&):
✓ Branch 12 → 13 taken 20 times.
✓ Branch 85 → 86 taken 20 times.
auto wala::series::operator*<wala::series::span<wala::fft::engines::split<wala::modnum<1000000007> >, false>, wala::series::cached_span<wala::fft::engines::split<wala::modnum<1000000007> >, true> >(wala::series::span<wala::fft::engines::split<wala::modnum<1000000007> >, false> const&, wala::series::cached_span<wala::fft::engines::split<wala::modnum<1000000007> >, true> const&):
✓ Branch 85 → 86 taken 20 times.
auto wala::series::operator*<wala::series::cached<wala::fft::engines::ntt<wala::modnum<998244353> >, false>, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> >(wala::series::cached<wala::fft::engines::ntt<wala::modnum<998244353> >, false> const&, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> const&):
✓ Branch 93 → 94 taken 2 times.
auto wala::series::operator*<wala::series::cached<wala::fft::engines::ntt<wala::modnum<998244353> >, true>, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> >(wala::series::cached<wala::fft::engines::ntt<wala::modnum<998244353> >, true> const&, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> const&):
✓ Branch 16 → 17 taken 11 times.
✓ Branch 93 → 94 taken 7 times.
|
2346 | fft::multiply<E>( |
| 557 | ca, ca.cache(), | ||
| 558 | cb, cb.cache(), | ||
| 559 |
4/4auto wala::series::operator*<wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false>, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> >(wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> const&, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> const&):
✓ Branch 16 → 17 taken 1266 times.
auto wala::series::operator*<wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, true>, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> >(wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, true> const&, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> const&):
✓ Branch 16 → 17 taken 38 times.
auto wala::series::operator*<wala::series::span<wala::fft::engines::ntt<wala::modnum<998244353> >, false>, wala::series::cached_span<wala::fft::engines::ntt<wala::modnum<998244353> >, true> >(wala::series::span<wala::fft::engines::ntt<wala::modnum<998244353> >, false> const&, wala::series::cached_span<wala::fft::engines::ntt<wala::modnum<998244353> >, true> const&):
✓ Branch 12 → 13 taken 20 times.
auto wala::series::operator*<wala::series::cached<wala::fft::engines::ntt<wala::modnum<998244353> >, true>, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> >(wala::series::cached<wala::fft::engines::ntt<wala::modnum<998244353> >, true> const&, wala::series::vec<wala::fft::engines::ntt<wala::modnum<998244353> >, false> const&):
✓ Branch 16 → 17 taken 11 times.
|
1672 | std::span<T>(r) |
| 560 | ); | ||
| 561 | 1672 | return r; | |
| 562 | 1672 | } | |
| 563 | 1328464 | } | |
| 564 | |||
| 565 | // Wrapper around trunc which caches transform(s[:2^k]) for all k, | ||
| 566 | // matching the doubling shape of ps_inv/exp so they can populate the caches. | ||
| 567 | // TODO: make ps_inv/exp populate these | ||
| 568 | template <fft::engine E> | ||
| 569 | struct prefix_cached { | ||
| 570 | using T = typename E::value_type; | ||
| 571 | |||
| 572 | using engine_t = E; | ||
| 573 | static constexpr bool exact_v = false; | ||
| 574 | |||
| 575 | ✗ | prefix_cached() = default; | |
| 576 | // moving coefficients in or out is free: implicit on rvalues, explicit copy otherwise | ||
| 577 | ✗ | prefix_cached(trunc<E>&& s_) : s(std::move(s_)) {} | |
| 578 | 4 | explicit prefix_cached(const trunc<E>& s_) : s(s_) {} | |
| 579 | ✗ | operator trunc<E>() && { return std::move(s); } | |
| 580 | |||
| 581 |
4/8✓ Branch 31 → 32 taken 8 times.
✗ Branch 31 → 40 not taken.
✓ Branch 34 → 35 taken 2 times.
✗ Branch 34 → 46 not taken.
✗ Branch 39 → 40 not taken.
✓ Branch 39 → 49 taken 8 times.
✗ Branch 45 → 46 not taken.
✓ Branch 45 → 55 taken 2 times.
|
199 | int len() const { return s.len(); } |
| 582 | // unwrap to the owned coefficients | ||
| 583 | ✗ | const trunc<E>& uncached() const { return s; } | |
| 584 | ✗ | const T& operator[](int i) const { return s[size_t(i)]; } | |
| 585 | ✗ | auto begin() const { return s.cbegin(); } | |
| 586 | ✗ | auto end() const { return s.cend(); } | |
| 587 | ✗ | operator span<E, false>() const { return s; } | |
| 588 | |||
| 589 | // extend precision: appends coefficients, keeping all covering caches valid | ||
| 590 | 1 | void append(std::span<const T> tail) { | |
| 591 |
1/1✓ Branch 22 → 23 taken 1 time.
|
5 | s.insert(s.end(), tail.begin(), tail.end()); |
| 592 | 1 | } | |
| 593 | |||
| 594 | // The first k coefficients, with the covering prefix cache when one lines | ||
| 595 | // up with k (k a power of two, or k == len()); uncached otherwise. | ||
| 596 | 23 | maybe_cached<E, false> first(int k) const { | |
| 597 | 46 | assert(k <= len()); | |
| 598 | 23 | span<E, false> v = s.first(k); | |
| 599 | 23 | int n = nextPow2(k); | |
| 600 |
2/3✓ Branch 37 → 38 taken 23 times.
✗ Branch 37 → 41 not taken.
✓ Branch 39 → 40 taken 23 times.
|
46 | if (std::min(n, len()) == k) return {v, prefix_cache(n)}; |
| 601 | ✗ | return maybe_cached<E, false>(v); | |
| 602 | } | ||
| 603 | // the whole-sequence transform: the prefix cache covering all of len() | ||
| 604 | ✗ | fft::transformed<E>& cache() const { return prefix_cache(nextPow2(len())); } | |
| 605 | // cache over the prefix of length min(n, len()); n a power of two | ||
| 606 | 23 | fft::transformed<E>& prefix_cache(int n) const { | |
| 607 | 23 | assert(n > 0 && !(n & (n-1))); | |
| 608 |
1/2✗ Branch 5 → 6 not taken.
✓ Branch 5 → 7 taken 23 times.
|
23 | int k = __builtin_ctz(unsigned(n)); |
| 609 |
2/2✓ Branch 11 → 12 taken 3 times.
✓ Branch 11 → 16 taken 20 times.
|
23 | if (k >= sz(caches)) caches.resize(size_t(k) + 1); |
| 610 | 23 | auto& c = caches[k]; | |
| 611 | 46 | int e = std::min(n, len()); | |
| 612 |
2/2✓ Branch 40 → 41 taken 8 times.
✓ Branch 40 → 84 taken 15 times.
|
23 | if (c.len != e) { |
| 613 |
1/1✓ Branch 50 → 51 taken 8 times.
|
24 | c.t = E::transform(s.first(e), 2 * n); |
| 614 | 8 | c.len = e; | |
| 615 | } | ||
| 616 | 23 | return c.t; | |
| 617 | } | ||
| 618 | |||
| 619 | private: | ||
| 620 | trunc<E> s; | ||
| 621 | // memoized transforms: logically const; len tracks how much of s each covers | ||
| 622 | 38 | struct entry { fft::transformed<E> t; int len = 0; }; | |
| 623 | mutable std::vector<entry> caches; | ||
| 624 | }; | ||
| 625 | |||
| 626 | } // namespace wala::series | ||
| 627 |