fft/online.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include <algorithm> | ||
| 4 | #include <cassert> | ||
| 5 | #include <span> | ||
| 6 | #include <vector> | ||
| 7 | |||
| 8 | #include "fft/multiply.hpp" | ||
| 9 | |||
| 10 | namespace ecnerwala { | ||
| 11 | |||
| 12 | // ==== online multiplication ==== | ||
| 13 | |||
| 14 | // Online (relaxed) multiplication: computes the first N terms of f*g given the terms one at a time. | ||
| 15 | template <fft::engine E> struct online_multiplier { | ||
| 16 | using T = typename E::value_type; | ||
| 17 | int N; int i; | ||
| 18 | std::vector<T> f, g; | ||
| 19 | std::vector<T> res; | ||
| 20 | std::vector<fft::transformed<E>> f_blocks, g_blocks; // level k: block [2^k, 2^{k+1}) | ||
| 21 | |||
| 22 |
12/12ecnerwala::online_multiplier<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> > >::online_multiplier(int):
✓ Branch 18 → 19 taken 6 times.
✓ Branch 32 → 33 taken 6 times.
✓ Branch 46 → 47 taken 6 times.
ecnerwala::online_multiplier<ecnerwala::fft::engines::ntt<mod_goldilocks> >::online_multiplier(int):
✓ Branch 18 → 19 taken 6 times.
✓ Branch 32 → 33 taken 6 times.
✓ Branch 46 → 47 taken 6 times.
ecnerwala::online_multiplier<ecnerwala::fft::engines::ntt<modnum<998244353> > >::online_multiplier(int):
✓ Branch 18 → 19 taken 6 times.
✓ Branch 32 → 33 taken 6 times.
✓ Branch 46 → 47 taken 6 times.
ecnerwala::online_multiplier<ecnerwala::fft::engines::split<modnum<1000000007> > >::online_multiplier(int):
✓ Branch 18 → 19 taken 6 times.
✓ Branch 32 → 33 taken 6 times.
✓ Branch 46 → 47 taken 6 times.
|
96 | online_multiplier(int N_) : N(N_), i(0), f(N, T{}), g(N, T{}), res(2*N+1, T{}) {} |
| 23 | |||
| 24 | ✗ | T peek() { | |
| 25 | ✗ | return res[i]; | |
| 26 | } | ||
| 27 | |||
| 28 | 748 | void push(T v_f, T v_g) { | |
| 29 | 748 | assert(i < N); | |
| 30 | 748 | f[i] = v_f; | |
| 31 | 748 | g[i] = v_g; | |
| 32 |
8/8ecnerwala::online_multiplier<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> > >::push(modnum<1000000007>, modnum<1000000007>):
✓ Branch 30 → 31 taken 6 times.
✓ Branch 30 → 42 taken 181 times.
ecnerwala::online_multiplier<ecnerwala::fft::engines::ntt<mod_goldilocks> >::push(mod_goldilocks, mod_goldilocks):
✓ Branch 30 → 31 taken 6 times.
✓ Branch 30 → 42 taken 181 times.
ecnerwala::online_multiplier<ecnerwala::fft::engines::ntt<modnum<998244353> > >::push(modnum<998244353>, modnum<998244353>):
✓ Branch 30 → 31 taken 6 times.
✓ Branch 30 → 42 taken 181 times.
ecnerwala::online_multiplier<ecnerwala::fft::engines::split<modnum<1000000007> > >::push(modnum<1000000007>, modnum<1000000007>):
✓ Branch 30 → 31 taken 6 times.
✓ Branch 30 → 42 taken 181 times.
|
748 | if (i == 0) { |
| 33 | 24 | res[0] += v_f * v_g; | |
| 34 | } else { | ||
| 35 | 724 | res[i] += v_f * g[0]; | |
| 36 | 724 | res[i] += f[0] * v_g; | |
| 37 |
8/8ecnerwala::online_multiplier<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> > >::push(modnum<1000000007>, modnum<1000000007>):
✓ Branch 179 → 80 taken 340 times.
✓ Branch 179 → 180 taken 163 times.
ecnerwala::online_multiplier<ecnerwala::fft::engines::ntt<mod_goldilocks> >::push(mod_goldilocks, mod_goldilocks):
✓ Branch 211 → 80 taken 340 times.
✓ Branch 211 → 212 taken 163 times.
ecnerwala::online_multiplier<ecnerwala::fft::engines::ntt<modnum<998244353> > >::push(modnum<998244353>, modnum<998244353>):
✓ Branch 211 → 80 taken 340 times.
✓ Branch 211 → 212 taken 163 times.
ecnerwala::online_multiplier<ecnerwala::fft::engines::split<modnum<1000000007> > >::push(modnum<1000000007>, modnum<1000000007>):
✓ Branch 211 → 80 taken 340 times.
✓ Branch 211 → 212 taken 163 times.
|
4266 | for (int p = 1, k = 0; (i & (p-1)) == (p-1); p <<= 1, k++) { |
| 38 | 1360 | int lo1 = p; | |
| 39 | 1360 | int lo2 = i + 1 - p; | |
| 40 | 1360 | int s = 2*p - 1; | |
| 41 | 1360 | auto fb = std::span<const T>(f).subspan(p, p); | |
| 42 | 1360 | auto gb = std::span<const T>(g).subspan(p, p); | |
| 43 | 1360 | auto out = std::span<T>(res).subspan(lo1 + lo2, s); | |
| 44 |
8/8ecnerwala::online_multiplier<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> > >::push(modnum<1000000007>, modnum<1000000007>):
✓ Branch 113 → 114 taken 18 times.
✓ Branch 113 → 133 taken 322 times.
ecnerwala::online_multiplier<ecnerwala::fft::engines::ntt<mod_goldilocks> >::push(mod_goldilocks, mod_goldilocks):
✓ Branch 113 → 114 taken 18 times.
✓ Branch 113 → 133 taken 322 times.
ecnerwala::online_multiplier<ecnerwala::fft::engines::ntt<modnum<998244353> > >::push(modnum<998244353>, modnum<998244353>):
✓ Branch 113 → 114 taken 18 times.
✓ Branch 113 → 133 taken 322 times.
ecnerwala::online_multiplier<ecnerwala::fft::engines::split<modnum<1000000007> > >::push(modnum<1000000007>, modnum<1000000007>):
✓ Branch 113 → 114 taken 18 times.
✓ Branch 113 → 133 taken 322 times.
|
1360 | if (i == 2*p-1) { |
| 45 |
4/4ecnerwala::online_multiplier<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> > >::push(modnum<1000000007>, modnum<1000000007>):
✓ Branch 117 → 118 taken 18 times.
ecnerwala::online_multiplier<ecnerwala::fft::engines::ntt<mod_goldilocks> >::push(mod_goldilocks, mod_goldilocks):
✓ Branch 117 → 118 taken 18 times.
ecnerwala::online_multiplier<ecnerwala::fft::engines::ntt<modnum<998244353> > >::push(modnum<998244353>, modnum<998244353>):
✓ Branch 117 → 118 taken 18 times.
ecnerwala::online_multiplier<ecnerwala::fft::engines::split<modnum<1000000007> > >::push(modnum<1000000007>, modnum<1000000007>):
✓ Branch 117 → 118 taken 18 times.
|
72 | f_blocks.emplace_back(); |
| 46 |
4/4ecnerwala::online_multiplier<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> > >::push(modnum<1000000007>, modnum<1000000007>):
✓ Branch 121 → 122 taken 18 times.
ecnerwala::online_multiplier<ecnerwala::fft::engines::ntt<mod_goldilocks> >::push(mod_goldilocks, mod_goldilocks):
✓ Branch 121 → 122 taken 18 times.
ecnerwala::online_multiplier<ecnerwala::fft::engines::ntt<modnum<998244353> > >::push(modnum<998244353>, modnum<998244353>):
✓ Branch 121 → 122 taken 18 times.
ecnerwala::online_multiplier<ecnerwala::fft::engines::split<modnum<1000000007> > >::push(modnum<1000000007>, modnum<1000000007>):
✓ Branch 121 → 122 taken 18 times.
|
72 | g_blocks.emplace_back(); |
| 47 |
4/4ecnerwala::online_multiplier<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> > >::push(modnum<1000000007>, modnum<1000000007>):
✓ Branch 132 → 170 taken 18 times.
ecnerwala::online_multiplier<ecnerwala::fft::engines::ntt<mod_goldilocks> >::push(mod_goldilocks, mod_goldilocks):
✓ Branch 132 → 202 taken 18 times.
ecnerwala::online_multiplier<ecnerwala::fft::engines::ntt<modnum<998244353> > >::push(modnum<998244353>, modnum<998244353>):
✓ Branch 132 → 202 taken 18 times.
ecnerwala::online_multiplier<ecnerwala::fft::engines::split<modnum<1000000007> > >::push(modnum<1000000007>, modnum<1000000007>):
✓ Branch 132 → 202 taken 18 times.
|
72 | fft::multiply<E>(fb, f_blocks[k], gb, g_blocks[k], out, fft::add_op{}); |
| 48 | 72 | break; | |
| 49 | } | ||
| 50 | // both products keep f on the left: f_hi * g_lo + f_lo * g_hi | ||
| 51 | 1288 | fft::transformed<E> cf, cg; | |
| 52 |
4/4ecnerwala::online_multiplier<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> > >::push(modnum<1000000007>, modnum<1000000007>):
✓ Branch 159 → 160 taken 322 times.
ecnerwala::online_multiplier<ecnerwala::fft::engines::ntt<mod_goldilocks> >::push(mod_goldilocks, mod_goldilocks):
✓ Branch 159 → 160 taken 322 times.
ecnerwala::online_multiplier<ecnerwala::fft::engines::ntt<modnum<998244353> > >::push(modnum<998244353>, modnum<998244353>):
✓ Branch 159 → 160 taken 322 times.
ecnerwala::online_multiplier<ecnerwala::fft::engines::split<modnum<1000000007> > >::push(modnum<1000000007>, modnum<1000000007>):
✓ Branch 159 → 160 taken 322 times.
|
5152 | fft::multiply_add2<E>( |
| 53 | 3864 | fb, f_blocks[k], std::span<const T>(g).subspan(lo2, p), cg, | |
| 54 | 3864 | std::span<const T>(f).subspan(lo2, p), cf, gb, g_blocks[k], | |
| 55 | out, fft::add_op{}); | ||
| 56 | } | ||
| 57 | } | ||
| 58 | 748 | i++; | |
| 59 | 748 | } | |
| 60 | |||
| 61 | 748 | T back() { | |
| 62 | 748 | return res[i-1]; | |
| 63 | } | ||
| 64 | }; | ||
| 65 | |||
| 66 | template <fft::engine E> struct online_squarer { | ||
| 67 | using T = typename E::value_type; | ||
| 68 | int N; int i; | ||
| 69 | std::vector<T> f; | ||
| 70 | std::vector<T> res; | ||
| 71 | std::vector<fft::transformed<E>> f_blocks; | ||
| 72 | |||
| 73 |
34/34ecnerwala::online_squarer<ecnerwala::fft::engines::matrix_stable<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, 3> >::online_squarer(int):
✓ Branch 20 → 12 taken 9 times.
✓ Branch 20 → 21 taken 1 time.
✓ Branch 25 → 26 taken 1 time.
✓ Branch 41 → 33 taken 9 times.
✓ Branch 41 → 42 taken 1 time.
✓ Branch 46 → 47 taken 1 time.
ecnerwala::online_squarer<ecnerwala::fft::engines::matrix_stable<ecnerwala::fft::engines::ntt<modnum<998244353> >, 3> >::online_squarer(int):
✓ Branch 20 → 12 taken 9 times.
✓ Branch 20 → 21 taken 1 time.
✓ Branch 25 → 26 taken 1 time.
✓ Branch 41 → 33 taken 9 times.
✓ Branch 41 → 42 taken 1 time.
✓ Branch 46 → 47 taken 1 time.
ecnerwala::online_squarer<ecnerwala::fft::engines::matrix_stable<ecnerwala::fft::engines::split<modnum<1000000007> >, 3> >::online_squarer(int):
✓ Branch 20 → 12 taken 9 times.
✓ Branch 20 → 21 taken 1 time.
✓ Branch 25 → 26 taken 1 time.
✓ Branch 41 → 33 taken 9 times.
✓ Branch 41 → 42 taken 1 time.
✓ Branch 46 → 47 taken 1 time.
ecnerwala::online_squarer<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> > >::online_squarer(int):
✓ Branch 18 → 19 taken 6 times.
✓ Branch 32 → 33 taken 6 times.
ecnerwala::online_squarer<ecnerwala::fft::engines::ntt<mod_goldilocks> >::online_squarer(int):
✓ Branch 18 → 19 taken 6 times.
✓ Branch 32 → 33 taken 6 times.
ecnerwala::online_squarer<ecnerwala::fft::engines::ntt<modnum<998244353> > >::online_squarer(int):
✓ Branch 18 → 19 taken 6 times.
✓ Branch 32 → 33 taken 6 times.
ecnerwala::online_squarer<ecnerwala::fft::engines::split<modnum<1000000007> > >::online_squarer(int):
✓ Branch 18 → 19 taken 6 times.
✓ Branch 32 → 33 taken 6 times.
ecnerwala::online_squarer<ecnerwala::fft::engines::matrix<ecnerwala::fft::engines::ntt<modnum<998244353> >, 3> >::online_squarer(int):
✓ Branch 20 → 12 taken 9 times.
✓ Branch 20 → 21 taken 1 time.
✓ Branch 25 → 26 taken 1 time.
✓ Branch 41 → 33 taken 9 times.
✓ Branch 41 → 42 taken 1 time.
✓ Branch 46 → 47 taken 1 time.
ecnerwala::online_squarer<ecnerwala::fft::nc_engine>::online_squarer(int):
✓ Branch 18 → 19 taken 6 times.
✓ Branch 32 → 33 taken 6 times.
|
166 | online_squarer(int N_) : N(N_), i(0), f(N, T{}), res(2*N+1, T{}) {} |
| 74 | |||
| 75 | ✗ | T peek() { | |
| 76 | ✗ | return res[i]; | |
| 77 | } | ||
| 78 | |||
| 79 | 1067 | void push(T v_f) { | |
| 80 | 1067 | assert(i < N); | |
| 81 | 1067 | f[i] = v_f; | |
| 82 |
18/18ecnerwala::online_squarer<ecnerwala::fft::engines::matrix_stable<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, 3> >::push(ecnerwala::fft::engines::mat<modnum<1000000007>, 3>):
✓ Branch 21 → 22 taken 1 time.
✓ Branch 21 → 32 taken 32 times.
ecnerwala::online_squarer<ecnerwala::fft::engines::matrix_stable<ecnerwala::fft::engines::ntt<modnum<998244353> >, 3> >::push(ecnerwala::fft::engines::mat<modnum<998244353>, 3>):
✓ Branch 21 → 22 taken 1 time.
✓ Branch 21 → 32 taken 32 times.
ecnerwala::online_squarer<ecnerwala::fft::engines::matrix_stable<ecnerwala::fft::engines::split<modnum<1000000007> >, 3> >::push(ecnerwala::fft::engines::mat<modnum<1000000007>, 3>):
✓ Branch 21 → 22 taken 1 time.
✓ Branch 21 → 32 taken 32 times.
ecnerwala::online_squarer<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> > >::push(modnum<1000000007>):
✓ Branch 21 → 22 taken 6 times.
✓ Branch 21 → 33 taken 181 times.
ecnerwala::online_squarer<ecnerwala::fft::engines::ntt<mod_goldilocks> >::push(mod_goldilocks):
✓ Branch 21 → 22 taken 6 times.
✓ Branch 21 → 33 taken 181 times.
ecnerwala::online_squarer<ecnerwala::fft::engines::ntt<modnum<998244353> > >::push(modnum<998244353>):
✓ Branch 21 → 22 taken 6 times.
✓ Branch 21 → 33 taken 181 times.
ecnerwala::online_squarer<ecnerwala::fft::engines::split<modnum<1000000007> > >::push(modnum<1000000007>):
✓ Branch 21 → 22 taken 6 times.
✓ Branch 21 → 33 taken 181 times.
ecnerwala::online_squarer<ecnerwala::fft::engines::matrix<ecnerwala::fft::engines::ntt<modnum<998244353> >, 3> >::push(ecnerwala::fft::engines::mat<modnum<998244353>, 3>):
✓ Branch 21 → 22 taken 1 time.
✓ Branch 21 → 32 taken 32 times.
ecnerwala::online_squarer<ecnerwala::fft::nc_engine>::push(modnum<998244353>):
✓ Branch 21 → 22 taken 6 times.
✓ Branch 21 → 33 taken 181 times.
|
1067 | if (i == 0) { |
| 83 | 34 | res[0] += v_f * v_f; | |
| 84 | } else { | ||
| 85 | 724 | if constexpr (E::commutative) res[i] += (v_f + v_f) * f[0]; | |
| 86 | 437 | else res[i] += v_f * f[0] + f[0] * v_f; | |
| 87 |
18/18ecnerwala::online_squarer<ecnerwala::fft::engines::matrix_stable<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, 3> >::push(ecnerwala::fft::engines::mat<modnum<1000000007>, 3>):
✓ Branch 139 → 60 taken 58 times.
✓ Branch 139 → 140 taken 27 times.
ecnerwala::online_squarer<ecnerwala::fft::engines::matrix_stable<ecnerwala::fft::engines::ntt<modnum<998244353> >, 3> >::push(ecnerwala::fft::engines::mat<modnum<998244353>, 3>):
✓ Branch 137 → 60 taken 58 times.
✓ Branch 137 → 138 taken 27 times.
ecnerwala::online_squarer<ecnerwala::fft::engines::matrix_stable<ecnerwala::fft::engines::split<modnum<1000000007> >, 3> >::push(ecnerwala::fft::engines::mat<modnum<1000000007>, 3>):
✓ Branch 137 → 60 taken 58 times.
✓ Branch 137 → 138 taken 27 times.
ecnerwala::online_squarer<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> > >::push(modnum<1000000007>):
✓ Branch 121 → 56 taken 340 times.
✓ Branch 121 → 122 taken 163 times.
ecnerwala::online_squarer<ecnerwala::fft::engines::ntt<mod_goldilocks> >::push(mod_goldilocks):
✓ Branch 137 → 56 taken 340 times.
✓ Branch 137 → 138 taken 163 times.
ecnerwala::online_squarer<ecnerwala::fft::engines::ntt<modnum<998244353> > >::push(modnum<998244353>):
✓ Branch 137 → 56 taken 340 times.
✓ Branch 137 → 138 taken 163 times.
ecnerwala::online_squarer<ecnerwala::fft::engines::split<modnum<1000000007> > >::push(modnum<1000000007>):
✓ Branch 137 → 56 taken 340 times.
✓ Branch 137 → 138 taken 163 times.
ecnerwala::online_squarer<ecnerwala::fft::engines::matrix<ecnerwala::fft::engines::ntt<modnum<998244353> >, 3> >::push(ecnerwala::fft::engines::mat<modnum<998244353>, 3>):
✓ Branch 137 → 60 taken 58 times.
✓ Branch 137 → 138 taken 27 times.
ecnerwala::online_squarer<ecnerwala::fft::nc_engine>::push(modnum<998244353>):
✓ Branch 151 → 65 taken 340 times.
✓ Branch 151 → 152 taken 163 times.
|
4677 | for (int p = 1, k = 0; (i & (p-1)) == (p-1); p <<= 1, k++) { |
| 88 | 1932 | int lo1 = p; | |
| 89 | 1932 | int lo2 = i + 1 - p; | |
| 90 | 1932 | int s = 2*p - 1; | |
| 91 | 1932 | auto fb = std::span<const T>(f).subspan(p, p); | |
| 92 | 1932 | auto fw = std::span<const T>(f).subspan(lo2, p); | |
| 93 | 1932 | auto out = std::span<T>(res).subspan(lo1 + lo2, s); | |
| 94 |
18/18ecnerwala::online_squarer<ecnerwala::fft::engines::matrix_stable<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, 3> >::push(ecnerwala::fft::engines::mat<modnum<1000000007>, 3>):
✓ Branch 93 → 94 taken 5 times.
✓ Branch 93 → 104 taken 53 times.
ecnerwala::online_squarer<ecnerwala::fft::engines::matrix_stable<ecnerwala::fft::engines::ntt<modnum<998244353> >, 3> >::push(ecnerwala::fft::engines::mat<modnum<998244353>, 3>):
✓ Branch 93 → 94 taken 5 times.
✓ Branch 93 → 104 taken 53 times.
ecnerwala::online_squarer<ecnerwala::fft::engines::matrix_stable<ecnerwala::fft::engines::split<modnum<1000000007> >, 3> >::push(ecnerwala::fft::engines::mat<modnum<1000000007>, 3>):
✓ Branch 93 → 94 taken 5 times.
✓ Branch 93 → 104 taken 53 times.
ecnerwala::online_squarer<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> > >::push(modnum<1000000007>):
✓ Branch 89 → 90 taken 18 times.
✓ Branch 89 → 100 taken 322 times.
ecnerwala::online_squarer<ecnerwala::fft::engines::ntt<mod_goldilocks> >::push(mod_goldilocks):
✓ Branch 89 → 90 taken 18 times.
✓ Branch 89 → 100 taken 322 times.
ecnerwala::online_squarer<ecnerwala::fft::engines::ntt<modnum<998244353> > >::push(modnum<998244353>):
✓ Branch 89 → 90 taken 18 times.
✓ Branch 89 → 100 taken 322 times.
ecnerwala::online_squarer<ecnerwala::fft::engines::split<modnum<1000000007> > >::push(modnum<1000000007>):
✓ Branch 89 → 90 taken 18 times.
✓ Branch 89 → 100 taken 322 times.
ecnerwala::online_squarer<ecnerwala::fft::engines::matrix<ecnerwala::fft::engines::ntt<modnum<998244353> >, 3> >::push(ecnerwala::fft::engines::mat<modnum<998244353>, 3>):
✓ Branch 93 → 94 taken 5 times.
✓ Branch 93 → 104 taken 53 times.
ecnerwala::online_squarer<ecnerwala::fft::nc_engine>::push(modnum<998244353>):
✓ Branch 98 → 99 taken 18 times.
✓ Branch 98 → 109 taken 322 times.
|
1932 | if (i == 2*p-1) { |
| 95 |
9/9ecnerwala::online_squarer<ecnerwala::fft::engines::matrix_stable<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, 3> >::push(ecnerwala::fft::engines::mat<modnum<1000000007>, 3>):
✓ Branch 97 → 98 taken 5 times.
ecnerwala::online_squarer<ecnerwala::fft::engines::matrix_stable<ecnerwala::fft::engines::ntt<modnum<998244353> >, 3> >::push(ecnerwala::fft::engines::mat<modnum<998244353>, 3>):
✓ Branch 97 → 98 taken 5 times.
ecnerwala::online_squarer<ecnerwala::fft::engines::matrix_stable<ecnerwala::fft::engines::split<modnum<1000000007> >, 3> >::push(ecnerwala::fft::engines::mat<modnum<1000000007>, 3>):
✓ Branch 97 → 98 taken 5 times.
ecnerwala::online_squarer<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> > >::push(modnum<1000000007>):
✓ Branch 93 → 94 taken 18 times.
ecnerwala::online_squarer<ecnerwala::fft::engines::ntt<mod_goldilocks> >::push(mod_goldilocks):
✓ Branch 93 → 94 taken 18 times.
ecnerwala::online_squarer<ecnerwala::fft::engines::ntt<modnum<998244353> > >::push(modnum<998244353>):
✓ Branch 93 → 94 taken 18 times.
ecnerwala::online_squarer<ecnerwala::fft::engines::split<modnum<1000000007> > >::push(modnum<1000000007>):
✓ Branch 93 → 94 taken 18 times.
ecnerwala::online_squarer<ecnerwala::fft::engines::matrix<ecnerwala::fft::engines::ntt<modnum<998244353> >, 3> >::push(ecnerwala::fft::engines::mat<modnum<998244353>, 3>):
✓ Branch 97 → 98 taken 5 times.
ecnerwala::online_squarer<ecnerwala::fft::nc_engine>::push(modnum<998244353>):
✓ Branch 102 → 103 taken 18 times.
|
110 | f_blocks.emplace_back(); |
| 96 |
9/9ecnerwala::online_squarer<ecnerwala::fft::engines::matrix_stable<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, 3> >::push(ecnerwala::fft::engines::mat<modnum<1000000007>, 3>):
✓ Branch 103 → 131 taken 5 times.
ecnerwala::online_squarer<ecnerwala::fft::engines::matrix_stable<ecnerwala::fft::engines::ntt<modnum<998244353> >, 3> >::push(ecnerwala::fft::engines::mat<modnum<998244353>, 3>):
✓ Branch 103 → 129 taken 5 times.
ecnerwala::online_squarer<ecnerwala::fft::engines::matrix_stable<ecnerwala::fft::engines::split<modnum<1000000007> >, 3> >::push(ecnerwala::fft::engines::mat<modnum<1000000007>, 3>):
✓ Branch 103 → 129 taken 5 times.
ecnerwala::online_squarer<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> > >::push(modnum<1000000007>):
✓ Branch 99 → 113 taken 18 times.
ecnerwala::online_squarer<ecnerwala::fft::engines::ntt<mod_goldilocks> >::push(mod_goldilocks):
✓ Branch 99 → 129 taken 18 times.
ecnerwala::online_squarer<ecnerwala::fft::engines::ntt<modnum<998244353> > >::push(modnum<998244353>):
✓ Branch 99 → 129 taken 18 times.
ecnerwala::online_squarer<ecnerwala::fft::engines::split<modnum<1000000007> > >::push(modnum<1000000007>):
✓ Branch 99 → 129 taken 18 times.
ecnerwala::online_squarer<ecnerwala::fft::engines::matrix<ecnerwala::fft::engines::ntt<modnum<998244353> >, 3> >::push(ecnerwala::fft::engines::mat<modnum<998244353>, 3>):
✓ Branch 103 → 129 taken 5 times.
ecnerwala::online_squarer<ecnerwala::fft::nc_engine>::push(modnum<998244353>):
✓ Branch 108 → 143 taken 18 times.
|
110 | fft::square<E>(fb, f_blocks[k], out, fft::add_op{}); |
| 97 | 110 | break; | |
| 98 | } | ||
| 99 |
8/8ecnerwala::online_squarer<ecnerwala::fft::engines::matrix_stable<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, 3> >::push(ecnerwala::fft::engines::mat<modnum<1000000007>, 3>):
✓ Branch 110 → 111 taken 371 times.
✓ Branch 110 → 112 taken 53 times.
ecnerwala::online_squarer<ecnerwala::fft::engines::matrix_stable<ecnerwala::fft::engines::ntt<modnum<998244353> >, 3> >::push(ecnerwala::fft::engines::mat<modnum<998244353>, 3>):
✓ Branch 108 → 109 taken 371 times.
✓ Branch 108 → 110 taken 53 times.
ecnerwala::online_squarer<ecnerwala::fft::engines::matrix_stable<ecnerwala::fft::engines::split<modnum<1000000007> >, 3> >::push(ecnerwala::fft::engines::mat<modnum<1000000007>, 3>):
✓ Branch 108 → 109 taken 371 times.
✓ Branch 108 → 110 taken 53 times.
ecnerwala::online_squarer<ecnerwala::fft::engines::matrix<ecnerwala::fft::engines::ntt<modnum<998244353> >, 3> >::push(ecnerwala::fft::engines::mat<modnum<998244353>, 3>):
✓ Branch 108 → 109 taken 371 times.
✓ Branch 108 → 110 taken 53 times.
|
3306 | fft::transformed<E> cw; |
| 100 | if constexpr (E::commutative) { | ||
| 101 |
4/4ecnerwala::online_squarer<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> > >::push(modnum<1000000007>):
✓ Branch 106 → 107 taken 322 times.
ecnerwala::online_squarer<ecnerwala::fft::engines::ntt<mod_goldilocks> >::push(mod_goldilocks):
✓ Branch 106 → 107 taken 322 times.
ecnerwala::online_squarer<ecnerwala::fft::engines::ntt<modnum<998244353> > >::push(modnum<998244353>):
✓ Branch 106 → 107 taken 322 times.
ecnerwala::online_squarer<ecnerwala::fft::engines::split<modnum<1000000007> > >::push(modnum<1000000007>):
✓ Branch 106 → 107 taken 322 times.
|
1288 | fft::multiply<E>(fb, f_blocks[k], fw, cw, out, fft::add_twice_op{}); |
| 102 | } else { | ||
| 103 | // f_hi * f_lo + f_lo * f_hi from the same two transforms | ||
| 104 |
5/5ecnerwala::online_squarer<ecnerwala::fft::engines::matrix_stable<ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >, 3> >::push(ecnerwala::fft::engines::mat<modnum<1000000007>, 3>):
✓ Branch 122 → 123 taken 53 times.
ecnerwala::online_squarer<ecnerwala::fft::engines::matrix_stable<ecnerwala::fft::engines::ntt<modnum<998244353> >, 3> >::push(ecnerwala::fft::engines::mat<modnum<998244353>, 3>):
✓ Branch 120 → 121 taken 53 times.
ecnerwala::online_squarer<ecnerwala::fft::engines::matrix_stable<ecnerwala::fft::engines::split<modnum<1000000007> >, 3> >::push(ecnerwala::fft::engines::mat<modnum<1000000007>, 3>):
✓ Branch 120 → 121 taken 53 times.
ecnerwala::online_squarer<ecnerwala::fft::engines::matrix<ecnerwala::fft::engines::ntt<modnum<998244353> >, 3> >::push(ecnerwala::fft::engines::mat<modnum<998244353>, 3>):
✓ Branch 120 → 121 taken 53 times.
ecnerwala::online_squarer<ecnerwala::fft::nc_engine>::push(modnum<998244353>):
✓ Branch 120 → 121 taken 322 times.
|
534 | fft::multiply_add2<E>(fb, f_blocks[k], fw, cw, |
| 105 | 534 | fw, cw, fb, f_blocks[k], out, fft::add_op{}); | |
| 106 | } | ||
| 107 | } | ||
| 108 | } | ||
| 109 | 1067 | i++; | |
| 110 | 1067 | } | |
| 111 | |||
| 112 | 1067 | T back() { | |
| 113 | 1067 | return res[i-1]; | |
| 114 | } | ||
| 115 | }; | ||
| 116 | |||
| 117 | /* namespace ecnerwala */ } | ||
| 118 |