fft/engines/ntt.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include <algorithm> | ||
| 4 | #include <cassert> | ||
| 5 | #include <span> | ||
| 6 | #include <utility> | ||
| 7 | #include <vector> | ||
| 8 | |||
| 9 | #include "fft/core.hpp" | ||
| 10 | #include "fft/engine.hpp" | ||
| 11 | |||
| 12 | namespace wala::fft::engines { | ||
| 13 | |||
| 14 | template <typename num> struct ntt { | ||
| 15 | using value_type = num; | ||
| 16 | static constexpr bool commutative = true; | ||
| 17 | using core = fft_core<num>; | ||
| 18 |
22/29✓ Branch 8 → 9 taken 1325993 times.
✗ Branch 8 → 20 not taken.
✓ Branch 9 → 10 taken 48 times.
✗ Branch 9 → 14 not taken.
✓ Branch 12 → 13 taken 1647972 times.
✓ Branch 12 → 14 taken 322072 times.
✓ Branch 15 → 16 taken 20 times.
✓ Branch 20 → 21 taken 644051 times.
✗ Branch 38 → 39 not taken.
✓ Branch 38 → 40 taken 628 times.
✓ Branch 40 → 41 taken 628 times.
✓ Branch 47 → 48 taken 590 times.
✗ Branch 49 → 50 not taken.
✓ Branch 49 → 51 taken 608 times.
✓ Branch 51 → 52 taken 608 times.
✓ Branch 64 → 65 taken 6 times.
✓ Branch 70 → 71 taken 173 times.
✓ Branch 84 → 85 taken 12 times.
✗ Branch 89 → 90 not taken.
✓ Branch 90 → 91 taken 65 times.
✓ Branch 96 → 97 taken 40 times.
✗ Branch 116 → 117 not taken.
✗ Branch 123 → 124 not taken.
✓ Branch 245 → 246 taken 160 times.
✓ Branch 253 → 254 taken 160 times.
✓ Branch 327 → 328 taken 64 times.
✓ Branch 329 → 330 taken 64 times.
✓ Branch 335 → 336 taken 64 times.
✓ Branch 337 → 338 taken 64 times.
|
43566296 | struct transformed { |
| 19 | vector<num> v; | ||
| 20 |
3/6✗ Branch 2 → 3 not taken.
✓ Branch 2 → 4 taken 96 times.
✗ Branch 38 → 39 not taken.
✓ Branch 38 → 40 taken 628 times.
✗ Branch 49 → 50 not taken.
✓ Branch 49 → 51 taken 608 times.
|
23463041 | int size() const { return sz(v); } |
| 21 | }; | ||
| 22 | using product = transformed; | ||
| 23 | static constexpr int unit_scale = 0; | ||
| 24 | template <int A = 0> using transformed_t = transformed; | ||
| 25 | template <int K = 0> using product_t = product; | ||
| 26 | |||
| 27 | 2657350 | static transformed transform(std::span<const num> a, int n) { | |
| 28 | 2657350 | assert(sz(a) <= 2 * n); | |
| 29 | 2657350 | transformed r; | |
| 30 |
6/6wala::fft::engines::ntt<wala::mod_goldilocks>::transform(std::span<wala::mod_goldilocks const, 18446744073709551615ul>, int):
✓ Branch 4 → 5 taken 96 times.
✓ Branch 16 → 17 taken 4288 times.
wala::fft::engines::ntt<wala::modnum<2013265921> >::transform(std::span<wala::modnum<2013265921> const, 18446744073709551615ul>, int):
✓ Branch 4 → 5 taken 96 times.
✓ Branch 16 → 17 taken 2893 times.
wala::fft::engines::ntt<wala::modnum<998244353> >::transform(std::span<wala::modnum<998244353> const, 18446744073709551615ul>, int):
✓ Branch 4 → 5 taken 2644785 times.
✓ Branch 16 → 17 taken 5192 times.
|
2669723 | r.v.assign(n, num(0)); |
| 31 | 2657350 | int lo = min(sz(a), n); | |
| 32 |
3/3wala::fft::engines::ntt<wala::mod_goldilocks>::transform(std::span<wala::mod_goldilocks const, 18446744073709551615ul>, int):
✓ Branch 42 → 43 taken 4288 times.
wala::fft::engines::ntt<wala::modnum<2013265921> >::transform(std::span<wala::modnum<2013265921> const, 18446744073709551615ul>, int):
✓ Branch 42 → 43 taken 2893 times.
wala::fft::engines::ntt<wala::modnum<998244353> >::transform(std::span<wala::modnum<998244353> const, 18446744073709551615ul>, int):
✓ Branch 42 → 43 taken 5192 times.
|
2694469 | std::copy(a.begin(), a.begin() + lo, r.v.begin()); |
| 33 |
12/12wala::fft::engines::ntt<wala::mod_goldilocks>::transform(std::span<wala::mod_goldilocks const, 18446744073709551615ul>, int):
✓ Branch 8 → 7 taken 4 times.
✓ Branch 8 → 9 taken 96 times.
✓ Branch 74 → 65 taken 359 times.
✓ Branch 74 → 75 taken 4288 times.
wala::fft::engines::ntt<wala::modnum<2013265921> >::transform(std::span<wala::modnum<2013265921> const, 18446744073709551615ul>, int):
✓ Branch 9 → 7 taken 4 times.
✓ Branch 9 → 10 taken 96 times.
✓ Branch 74 → 65 taken 231 times.
✓ Branch 74 → 75 taken 2893 times.
wala::fft::engines::ntt<wala::modnum<998244353> >::transform(std::span<wala::modnum<998244353> const, 18446744073709551615ul>, int):
✓ Branch 9 → 7 taken 14 times.
✓ Branch 9 → 10 taken 2644785 times.
✓ Branch 74 → 65 taken 294 times.
✓ Branch 74 → 75 taken 5192 times.
|
2658256 | for (int i = n; i < sz(a); i++) r.v[i - n] += a[i]; |
| 34 |
9/12wala::fft::engines::ntt<wala::mod_goldilocks>::transform(std::span<wala::mod_goldilocks const, 18446744073709551615ul>, int):
✗ Branch 9 → 10 not taken.
✓ Branch 9 → 11 taken 96 times.
✓ Branch 11 → 12 taken 96 times.
✓ Branch 78 → 79 taken 4288 times.
wala::fft::engines::ntt<wala::modnum<2013265921> >::transform(std::span<wala::modnum<2013265921> const, 18446744073709551615ul>, int):
✗ Branch 10 → 11 not taken.
✓ Branch 10 → 12 taken 96 times.
✓ Branch 12 → 13 taken 96 times.
✓ Branch 78 → 79 taken 2893 times.
wala::fft::engines::ntt<wala::modnum<998244353> >::transform(std::span<wala::modnum<998244353> const, 18446744073709551615ul>, int):
✗ Branch 10 → 11 not taken.
✓ Branch 10 → 12 taken 2644785 times.
✓ Branch 12 → 13 taken 2644785 times.
✓ Branch 78 → 79 taken 5192 times.
|
2657350 | core::forward(std::span<num>(r.v)); |
| 35 | 2657350 | return r; | |
| 36 | } | ||
| 37 | 7896629 | static void extend_to(transformed& t, int m, std::span<const num> coeffs) { | |
| 38 | 7896629 | assert(!(m & (m-1)) && sz(coeffs) <= 2 * m); | |
| 39 |
9/12wala::fft::engines::ntt<wala::mod_goldilocks>::extend_to(wala::fft::engines::ntt<wala::mod_goldilocks>::transformed&, int, std::span<wala::mod_goldilocks const, 18446744073709551615ul>):
✓ Branch 5 → 6 taken 96 times.
✗ Branch 5 → 17 not taken.
✓ Branch 11 → 12 taken 3356 times.
✓ Branch 11 → 77 taken 1000 times.
wala::fft::engines::ntt<wala::modnum<2013265921> >::extend_to(wala::fft::engines::ntt<wala::modnum<2013265921> >::transformed&, int, std::span<wala::modnum<2013265921> const, 18446744073709551615ul>):
✓ Branch 5 → 6 taken 96 times.
✗ Branch 5 → 17 not taken.
✓ Branch 11 → 12 taken 1939 times.
✗ Branch 11 → 77 not taken.
wala::fft::engines::ntt<wala::modnum<998244353> >::extend_to(wala::fft::engines::ntt<wala::modnum<998244353> >::transformed&, int, std::span<wala::modnum<998244353> const, 18446744073709551615ul>):
✓ Branch 5 → 6 taken 4606961 times.
✓ Branch 5 → 17 taken 3277021 times.
✓ Branch 11 → 12 taken 3858 times.
✓ Branch 11 → 77 taken 2302 times.
|
7909084 | if (t.size() >= m) return; |
| 40 |
13/15wala::fft::engines::ntt<wala::mod_goldilocks>::extend_to(wala::fft::engines::ntt<wala::mod_goldilocks>::transformed&, int, std::span<wala::mod_goldilocks const, 18446744073709551615ul>):
✓ Branch 6 → 7 taken 96 times.
✗ Branch 6 → 16 not taken.
✓ Branch 17 → 18 taken 3084 times.
✓ Branch 17 → 71 taken 272 times.
✓ Branch 19 → 20 taken 3084 times.
wala::fft::engines::ntt<wala::modnum<2013265921> >::extend_to(wala::fft::engines::ntt<wala::modnum<2013265921> >::transformed&, int, std::span<wala::modnum<2013265921> const, 18446744073709551615ul>):
✓ Branch 6 → 7 taken 96 times.
✗ Branch 6 → 16 not taken.
✓ Branch 17 → 18 taken 1932 times.
✓ Branch 17 → 71 taken 7 times.
✓ Branch 19 → 20 taken 1932 times.
wala::fft::engines::ntt<wala::modnum<998244353> >::extend_to(wala::fft::engines::ntt<wala::modnum<998244353> >::transformed&, int, std::span<wala::modnum<998244353> const, 18446744073709551615ul>):
✓ Branch 6 → 7 taken 2635779 times.
✓ Branch 6 → 16 taken 1971182 times.
✓ Branch 17 → 18 taken 3409 times.
✓ Branch 17 → 71 taken 449 times.
✓ Branch 19 → 20 taken 3409 times.
|
7278280 | if (t.size() == 0) { t = transform(coeffs, m); return; } |
| 41 |
8/12wala::fft::engines::ntt<wala::mod_goldilocks>::extend_to(wala::fft::engines::ntt<wala::mod_goldilocks>::transformed&, int, std::span<wala::mod_goldilocks const, 18446744073709551615ul>):
✗ Branch 16 → 11 not taken.
✗ Branch 16 → 17 not taken.
✓ Branch 76 → 46 taken 280 times.
✓ Branch 76 → 77 taken 272 times.
wala::fft::engines::ntt<wala::modnum<2013265921> >::extend_to(wala::fft::engines::ntt<wala::modnum<2013265921> >::transformed&, int, std::span<wala::modnum<2013265921> const, 18446744073709551615ul>):
✗ Branch 16 → 11 not taken.
✗ Branch 16 → 17 not taken.
✓ Branch 76 → 46 taken 10 times.
✓ Branch 76 → 77 taken 7 times.
wala::fft::engines::ntt<wala::modnum<998244353> >::extend_to(wala::fft::engines::ntt<wala::modnum<998244353> >::transformed&, int, std::span<wala::modnum<998244353> const, 18446744073709551615ul>):
✓ Branch 16 → 11 taken 2293280 times.
✓ Branch 16 → 17 taken 1971182 times.
✓ Branch 76 → 46 taken 497 times.
✓ Branch 76 → 77 taken 449 times.
|
4267492 | while (t.size() < m) { |
| 42 | 2294067 | int s = t.size(); | |
| 43 | 2294067 | t.v.resize(2 * s); | |
| 44 | // coeffs past 2s are zero: they didn't fit in the transform we're a prefix of | ||
| 45 |
4/9wala::fft::engines::ntt<wala::mod_goldilocks>::extend_to(wala::fft::engines::ntt<wala::mod_goldilocks>::transformed&, int, std::span<wala::mod_goldilocks const, 18446744073709551615ul>):
✗ Branch 12 → 13 not taken.
✗ Branch 12 → 14 not taken.
✓ Branch 67 → 68 taken 280 times.
wala::fft::engines::ntt<wala::modnum<2013265921> >::extend_to(wala::fft::engines::ntt<wala::modnum<2013265921> >::transformed&, int, std::span<wala::modnum<2013265921> const, 18446744073709551615ul>):
✗ Branch 12 → 13 not taken.
✗ Branch 12 → 14 not taken.
✓ Branch 67 → 68 taken 10 times.
wala::fft::engines::ntt<wala::modnum<998244353> >::extend_to(wala::fft::engines::ntt<wala::modnum<998244353> >::transformed&, int, std::span<wala::modnum<998244353> const, 18446744073709551615ul>):
✗ Branch 12 → 13 not taken.
✓ Branch 12 → 14 taken 2293280 times.
✓ Branch 67 → 68 taken 497 times.
|
2294067 | core::extend(std::span<num>(t.v), coeffs.first(size_t(min(sz(coeffs), 2 * s)))); |
| 46 | } | ||
| 47 | } | ||
| 48 | 3067 | static transformed downsample(const transformed& t, int n, bool odd) { | |
| 49 |
4/4wala::fft::engines::ntt<wala::mod_goldilocks>::downsample(wala::fft::engines::ntt<wala::mod_goldilocks>::transformed const&, int, bool):
✓ Branch 8 → 9 taken 612 times.
wala::fft::engines::ntt<wala::modnum<2013265921> >::downsample(wala::fft::engines::ntt<wala::modnum<2013265921> >::transformed const&, int, bool):
✓ Branch 8 → 9 taken 306 times.
wala::fft::engines::ntt<wala::modnum<998244353> >::downsample(wala::fft::engines::ntt<wala::modnum<998244353> >::transformed const&, int, bool):
✓ Branch 2 → 3 taken 1826 times.
✓ Branch 8 → 9 taken 323 times.
|
3067 | transformed r; r.v.resize(n); |
| 50 |
6/8wala::fft::engines::ntt<wala::mod_goldilocks>::downsample(wala::fft::engines::ntt<wala::mod_goldilocks>::transformed const&, int, bool):
✓ Branch 17 → 18 taken 612 times.
wala::fft::engines::ntt<wala::modnum<2013265921> >::downsample(wala::fft::engines::ntt<wala::modnum<2013265921> >::transformed const&, int, bool):
✓ Branch 17 → 18 taken 306 times.
wala::fft::engines::ntt<wala::modnum<998244353> >::downsample(wala::fft::engines::ntt<wala::modnum<998244353> >::transformed const&, int, bool):
✗ Branch 3 → 4 not taken.
✓ Branch 3 → 5 taken 1826 times.
✗ Branch 5 → 6 not taken.
✓ Branch 5 → 7 taken 1826 times.
✓ Branch 7 → 8 taken 1826 times.
✓ Branch 17 → 18 taken 323 times.
|
3067 | core::downsample(std::span<const num>(t.v), std::span<num>(r.v), odd); |
| 51 | 3067 | return r; | |
| 52 | } | ||
| 53 | 655 | static transformed upsample(const transformed& t, int n, bool odd) { | |
| 54 |
4/4wala::fft::engines::ntt<wala::mod_goldilocks>::upsample(wala::fft::engines::ntt<wala::mod_goldilocks>::transformed const&, int, bool):
✓ Branch 8 → 9 taken 24 times.
wala::fft::engines::ntt<wala::modnum<2013265921> >::upsample(wala::fft::engines::ntt<wala::modnum<2013265921> >::transformed const&, int, bool):
✓ Branch 8 → 9 taken 12 times.
wala::fft::engines::ntt<wala::modnum<998244353> >::upsample(wala::fft::engines::ntt<wala::modnum<998244353> >::transformed const&, int, bool):
✓ Branch 2 → 3 taken 590 times.
✓ Branch 8 → 9 taken 29 times.
|
655 | transformed r; r.v.resize(n); |
| 55 |
6/8wala::fft::engines::ntt<wala::mod_goldilocks>::upsample(wala::fft::engines::ntt<wala::mod_goldilocks>::transformed const&, int, bool):
✓ Branch 17 → 18 taken 24 times.
wala::fft::engines::ntt<wala::modnum<2013265921> >::upsample(wala::fft::engines::ntt<wala::modnum<2013265921> >::transformed const&, int, bool):
✓ Branch 17 → 18 taken 12 times.
wala::fft::engines::ntt<wala::modnum<998244353> >::upsample(wala::fft::engines::ntt<wala::modnum<998244353> >::transformed const&, int, bool):
✗ Branch 3 → 4 not taken.
✓ Branch 3 → 5 taken 590 times.
✗ Branch 5 → 6 not taken.
✓ Branch 5 → 7 taken 590 times.
✓ Branch 7 → 8 taken 590 times.
✓ Branch 17 → 18 taken 29 times.
|
655 | core::upsample(std::span<const num>(t.v), std::span<num>(r.v), odd); |
| 56 | 655 | return r; | |
| 57 | } | ||
| 58 | 1891 | static transformed negate_arg(const transformed& t, int n) { | |
| 59 | 2564 | assert(n >= 2 && t.size() >= n); | |
| 60 |
4/4wala::fft::engines::ntt<wala::mod_goldilocks>::negate_arg(wala::fft::engines::ntt<wala::mod_goldilocks>::transformed const&, int):
✓ Branch 16 → 29 taken 328 times.
wala::fft::engines::ntt<wala::modnum<2013265921> >::negate_arg(wala::fft::engines::ntt<wala::modnum<2013265921> >::transformed const&, int):
✓ Branch 16 → 29 taken 164 times.
wala::fft::engines::ntt<wala::modnum<998244353> >::negate_arg(wala::fft::engines::ntt<wala::modnum<998244353> >::transformed const&, int):
✓ Branch 5 → 7 taken 1218 times.
✓ Branch 16 → 29 taken 181 times.
|
1891 | transformed r; r.v.resize(n); |
| 61 |
8/8wala::fft::engines::ntt<wala::mod_goldilocks>::negate_arg(wala::fft::engines::ntt<wala::mod_goldilocks>::transformed const&, int):
✓ Branch 29 → 17 taken 7052 times.
✓ Branch 29 → 30 taken 328 times.
wala::fft::engines::ntt<wala::modnum<2013265921> >::negate_arg(wala::fft::engines::ntt<wala::modnum<2013265921> >::transformed const&, int):
✓ Branch 29 → 17 taken 3526 times.
✓ Branch 29 → 30 taken 164 times.
wala::fft::engines::ntt<wala::modnum<998244353> >::negate_arg(wala::fft::engines::ntt<wala::modnum<998244353> >::transformed const&, int):
✓ Branch 7 → 6 taken 239557132 times.
✓ Branch 7 → 8 taken 1218 times.
✓ Branch 29 → 17 taken 5838 times.
✓ Branch 29 → 30 taken 181 times.
|
239575439 | for (int j = 0; j < n; j++) r.v[j] = t.v[j ^ 1]; |
| 62 | 1891 | return r; | |
| 63 | } | ||
| 64 | // a[-k]: evaluation at w^{-brev(j)}, which is the conjugate index | ||
| 65 | 60 | static transformed of_reverse(const transformed& t, int n) { | |
| 66 | 120 | assert(t.size() >= n); | |
| 67 |
3/3wala::fft::engines::ntt<wala::mod_goldilocks>::of_reverse(wala::fft::engines::ntt<wala::mod_goldilocks>::transformed const&, int):
✓ Branch 15 → 29 taken 30 times.
wala::fft::engines::ntt<wala::modnum<2013265921> >::of_reverse(wala::fft::engines::ntt<wala::modnum<2013265921> >::transformed const&, int):
✓ Branch 15 → 29 taken 15 times.
wala::fft::engines::ntt<wala::modnum<998244353> >::of_reverse(wala::fft::engines::ntt<wala::modnum<998244353> >::transformed const&, int):
✓ Branch 15 → 29 taken 15 times.
|
60 | transformed r; r.v.resize(n); |
| 68 |
6/6wala::fft::engines::ntt<wala::mod_goldilocks>::of_reverse(wala::fft::engines::ntt<wala::mod_goldilocks>::transformed const&, int):
✓ Branch 29 → 16 taken 522 times.
✓ Branch 29 → 30 taken 30 times.
wala::fft::engines::ntt<wala::modnum<2013265921> >::of_reverse(wala::fft::engines::ntt<wala::modnum<2013265921> >::transformed const&, int):
✓ Branch 29 → 16 taken 261 times.
✓ Branch 29 → 30 taken 15 times.
wala::fft::engines::ntt<wala::modnum<998244353> >::of_reverse(wala::fft::engines::ntt<wala::modnum<998244353> >::transformed const&, int):
✓ Branch 29 → 16 taken 261 times.
✓ Branch 29 → 30 taken 15 times.
|
1104 | for (int j = 0; j < n; j++) r.v[j] = t.v[core::conj_index(j)]; |
| 69 | 60 | return r; | |
| 70 | } | ||
| 71 | 2668727 | static product mul(const transformed& a, const transformed& b, int n) { | |
| 72 | 2684625 | assert(a.size() >= n && b.size() >= n); | |
| 73 |
6/6wala::fft::engines::ntt<wala::mod_goldilocks>::mul(wala::fft::engines::ntt<wala::mod_goldilocks>::transformed const&, wala::fft::engines::ntt<wala::mod_goldilocks>::transformed const&, int):
✓ Branch 5 → 7 taken 48 times.
✓ Branch 21 → 42 taken 2675 times.
wala::fft::engines::ntt<wala::modnum<2013265921> >::mul(wala::fft::engines::ntt<wala::modnum<2013265921> >::transformed const&, wala::fft::engines::ntt<wala::modnum<2013265921> >::transformed const&, int):
✓ Branch 5 → 7 taken 48 times.
✓ Branch 21 → 42 taken 1860 times.
wala::fft::engines::ntt<wala::modnum<998244353> >::mul(wala::fft::engines::ntt<wala::modnum<998244353> >::transformed const&, wala::fft::engines::ntt<wala::modnum<998244353> >::transformed const&, int):
✓ Branch 5 → 7 taken 2660682 times.
✓ Branch 21 → 42 taken 3414 times.
|
2668727 | product p; p.v.resize(n); |
| 74 |
12/12wala::fft::engines::ntt<wala::mod_goldilocks>::mul(wala::fft::engines::ntt<wala::mod_goldilocks>::transformed const&, wala::fft::engines::ntt<wala::mod_goldilocks>::transformed const&, int):
✓ Branch 7 → 6 taken 24699142 times.
✓ Branch 7 → 8 taken 48 times.
✓ Branch 42 → 22 taken 60468 times.
✓ Branch 42 → 43 taken 2675 times.
wala::fft::engines::ntt<wala::modnum<2013265921> >::mul(wala::fft::engines::ntt<wala::modnum<2013265921> >::transformed const&, wala::fft::engines::ntt<wala::modnum<2013265921> >::transformed const&, int):
✓ Branch 7 → 6 taken 24699142 times.
✓ Branch 7 → 8 taken 48 times.
✓ Branch 42 → 22 taken 42909 times.
✓ Branch 42 → 43 taken 1860 times.
wala::fft::engines::ntt<wala::modnum<998244353> >::mul(wala::fft::engines::ntt<wala::modnum<998244353> >::transformed const&, wala::fft::engines::ntt<wala::modnum<998244353> >::transformed const&, int):
✓ Branch 7 → 6 taken 817735754 times.
✓ Branch 7 → 8 taken 2660682 times.
✓ Branch 42 → 22 taken 84804 times.
✓ Branch 42 → 43 taken 3414 times.
|
869990946 | for (int i = 0; i < n; i++) p.v[i] = a.v[i] * b.v[i]; |
| 75 | 2668727 | return p; | |
| 76 | } | ||
| 77 |
1/1✓ Branch 5 → 6 taken 537 times.
|
657 | static product sq(const transformed& a, int n) { return mul(a, a, n); } |
| 78 | 651482 | static product mul2( | |
| 79 | const transformed& a1, const transformed& b1, | ||
| 80 | const transformed& a2, const transformed& b2, | ||
| 81 | int n | ||
| 82 | ) { | ||
| 83 | 681206 | assert(a1.size() >= n && b1.size() >= n && a2.size() >= n && b2.size() >= n); | |
| 84 |
4/4wala::fft::engines::ntt<wala::mod_goldilocks>::mul2(wala::fft::engines::ntt<wala::mod_goldilocks>::transformed const&, wala::fft::engines::ntt<wala::mod_goldilocks>::transformed const&, wala::fft::engines::ntt<wala::mod_goldilocks>::transformed const&, wala::fft::engines::ntt<wala::mod_goldilocks>::transformed const&, int):
✓ Branch 33 → 72 taken 2091 times.
wala::fft::engines::ntt<wala::modnum<2013265921> >::mul2(wala::fft::engines::ntt<wala::modnum<2013265921> >::transformed const&, wala::fft::engines::ntt<wala::modnum<2013265921> >::transformed const&, wala::fft::engines::ntt<wala::modnum<2013265921> >::transformed const&, wala::fft::engines::ntt<wala::modnum<2013265921> >::transformed const&, int):
✓ Branch 33 → 72 taken 1761 times.
wala::fft::engines::ntt<wala::modnum<998244353> >::mul2(wala::fft::engines::ntt<wala::modnum<998244353> >::transformed const&, wala::fft::engines::ntt<wala::modnum<998244353> >::transformed const&, wala::fft::engines::ntt<wala::modnum<998244353> >::transformed const&, wala::fft::engines::ntt<wala::modnum<998244353> >::transformed const&, int):
✓ Branch 7 → 12 taken 644051 times.
✓ Branch 33 → 72 taken 3579 times.
|
651482 | product p; p.v.resize(n); |
| 85 |
10/10wala::fft::engines::ntt<wala::mod_goldilocks>::mul2(wala::fft::engines::ntt<wala::mod_goldilocks>::transformed const&, wala::fft::engines::ntt<wala::mod_goldilocks>::transformed const&, wala::fft::engines::ntt<wala::mod_goldilocks>::transformed const&, wala::fft::engines::ntt<wala::mod_goldilocks>::transformed const&, int):
✓ Branch 72 → 34 taken 6703 times.
✓ Branch 72 → 73 taken 2091 times.
wala::fft::engines::ntt<wala::modnum<2013265921> >::mul2(wala::fft::engines::ntt<wala::modnum<2013265921> >::transformed const&, wala::fft::engines::ntt<wala::modnum<2013265921> >::transformed const&, wala::fft::engines::ntt<wala::modnum<2013265921> >::transformed const&, wala::fft::engines::ntt<wala::modnum<2013265921> >::transformed const&, int):
✓ Branch 72 → 34 taken 5228 times.
✓ Branch 72 → 73 taken 1761 times.
wala::fft::engines::ntt<wala::modnum<998244353> >::mul2(wala::fft::engines::ntt<wala::modnum<998244353> >::transformed const&, wala::fft::engines::ntt<wala::modnum<998244353> >::transformed const&, wala::fft::engines::ntt<wala::modnum<998244353> >::transformed const&, wala::fft::engines::ntt<wala::modnum<998244353> >::transformed const&, int):
✓ Branch 8 → 9 taken 5332038 times.
✓ Branch 8 → 10 taken 5332656 times.
✓ Branch 12 → 8 taken 10664694 times.
✓ Branch 12 → 13 taken 644051 times.
✓ Branch 72 → 34 taken 10459 times.
✓ Branch 72 → 73 taken 3579 times.
|
11338566 | for (int i = 0; i < n; i++) p.v[i] = a1.v[i] * b1.v[i] + a2.v[i] * b2.v[i]; |
| 86 | 651482 | return p; | |
| 87 | } | ||
| 88 | 1702 | static product add(product&& a, const product& b) { | |
| 89 | 5106 | assert(a.size() == b.size()); | |
| 90 |
6/6wala::fft::engines::ntt<wala::mod_goldilocks>::add(wala::fft::engines::ntt<wala::mod_goldilocks>::transformed&&, wala::fft::engines::ntt<wala::mod_goldilocks>::transformed const&):
✓ Branch 32 → 15 taken 2875 times.
✓ Branch 32 → 33 taken 110 times.
wala::fft::engines::ntt<wala::modnum<2013265921> >::add(wala::fft::engines::ntt<wala::modnum<2013265921> >::transformed&&, wala::fft::engines::ntt<wala::modnum<2013265921> >::transformed const&):
✓ Branch 32 → 15 taken 2793 times.
✓ Branch 32 → 33 taken 107 times.
wala::fft::engines::ntt<wala::modnum<998244353> >::add(wala::fft::engines::ntt<wala::modnum<998244353> >::transformed&&, wala::fft::engines::ntt<wala::modnum<998244353> >::transformed const&):
✓ Branch 32 → 15 taken 15109 times.
✓ Branch 32 → 33 taken 1485 times.
|
24181 | for (int i = 0; i < a.size(); i++) a.v[i] += b.v[i]; |
| 91 | 1702 | return std::move(a); | |
| 92 | } | ||
| 93 | // sum_k finish(p)[k] * b[k] by Parseval: (1/n) sum_j P[j] B[-j] | ||
| 94 | 10 | static num dot(const product& p, const transformed& t, int n) { | |
| 95 | 30 | assert(p.size() >= n && t.size() >= n); | |
| 96 | 10 | num r = 0; | |
| 97 |
4/4wala::fft::engines::ntt<wala::mod_goldilocks>::dot(wala::fft::engines::ntt<wala::mod_goldilocks>::transformed const&, wala::fft::engines::ntt<wala::mod_goldilocks>::transformed const&, int):
✓ Branch 37 → 20 taken 87 times.
✓ Branch 37 → 38 taken 5 times.
wala::fft::engines::ntt<wala::modnum<998244353> >::dot(wala::fft::engines::ntt<wala::modnum<998244353> >::transformed const&, wala::fft::engines::ntt<wala::modnum<998244353> >::transformed const&, int):
✓ Branch 37 → 20 taken 87 times.
✓ Branch 37 → 38 taken 5 times.
|
184 | for (int j = 0; j < n; j++) r += p.v[j] * t.v[core::conj_index(j)]; |
| 98 | 30 | return r * inv(num(n)); | |
| 99 | } | ||
| 100 | 3318567 | template <typename Op = assign_op> static void finish(product&& p, std::span<num> out, Op op = {}) { | |
| 101 | 3318567 | int n = p.size(); | |
| 102 | 3318567 | assert(sz(out) <= n); | |
| 103 |
21/29void wala::fft::engines::ntt<wala::mod_goldilocks>::finish<wala::fft::add_twice_op>(wala::fft::engines::ntt<wala::mod_goldilocks>::transformed&&, std::span<wala::mod_goldilocks, 18446744073709551615ul>, wala::fft::add_twice_op):
✓ Branch 14 → 15 taken 238 times.
void wala::fft::engines::ntt<wala::mod_goldilocks>::finish<wala::fft::add_op>(wala::fft::engines::ntt<wala::mod_goldilocks>::transformed&&, std::span<wala::mod_goldilocks, 18446744073709551615ul>, wala::fft::add_op):
✓ Branch 14 → 15 taken 268 times.
void wala::fft::engines::ntt<wala::mod_goldilocks>::finish<wala::fft::detail::cut_op<wala::mod_goldilocks, wala::fft::add_twice_op> >(wala::fft::engines::ntt<wala::mod_goldilocks>::transformed&&, std::span<wala::mod_goldilocks, 18446744073709551615ul>, wala::fft::detail::cut_op<wala::mod_goldilocks, wala::fft::add_twice_op>):
✓ Branch 14 → 15 taken 84 times.
void wala::fft::engines::ntt<wala::mod_goldilocks>::finish<wala::fft::detail::cut_op<wala::mod_goldilocks, wala::fft::add_op> >(wala::fft::engines::ntt<wala::mod_goldilocks>::transformed&&, std::span<wala::mod_goldilocks, 18446744073709551615ul>, wala::fft::detail::cut_op<wala::mod_goldilocks, wala::fft::add_op>):
✓ Branch 14 → 15 taken 90 times.
void wala::fft::engines::ntt<wala::mod_goldilocks>::finish<wala::fft::detail::cut_op<wala::mod_goldilocks, wala::fft::assign_op> >(wala::fft::engines::ntt<wala::mod_goldilocks>::transformed&&, std::span<wala::mod_goldilocks, 18446744073709551615ul>, wala::fft::detail::cut_op<wala::mod_goldilocks, wala::fft::assign_op>):
✓ Branch 14 → 15 taken 17 times.
void wala::fft::engines::ntt<wala::mod_goldilocks>::finish<wala::fft::assign_op>(wala::fft::engines::ntt<wala::mod_goldilocks>::transformed&&, std::span<wala::mod_goldilocks, 18446744073709551615ul>, wala::fft::assign_op):
✗ Branch 4 → 5 not taken.
✓ Branch 4 → 6 taken 48 times.
✗ Branch 7 → 8 not taken.
✓ Branch 7 → 9 taken 48 times.
✓ Branch 14 → 15 taken 3989 times.
void wala::fft::engines::ntt<wala::modnum<2013265921> >::finish<wala::fft::assign_op>(wala::fft::engines::ntt<wala::modnum<2013265921> >::transformed&&, std::span<wala::modnum<2013265921>, 18446744073709551615ul>, wala::fft::assign_op):
✗ Branch 4 → 5 not taken.
✓ Branch 4 → 6 taken 48 times.
✗ Branch 7 → 8 not taken.
✓ Branch 7 → 9 taken 48 times.
✓ Branch 14 → 15 taken 3529 times.
void wala::fft::engines::ntt<wala::modnum<998244353> >::finish<wala::fft::add_twice_op>(wala::fft::engines::ntt<wala::modnum<998244353> >::transformed&&, std::span<wala::modnum<998244353>, 18446744073709551615ul>, wala::fft::add_twice_op):
✓ Branch 14 → 15 taken 238 times.
void wala::fft::engines::ntt<wala::modnum<998244353> >::finish<wala::fft::add_op>(wala::fft::engines::ntt<wala::modnum<998244353> >::transformed&&, std::span<wala::modnum<998244353>, 18446744073709551615ul>, wala::fft::add_op):
✓ Branch 14 → 15 taken 2003 times.
void wala::fft::engines::ntt<wala::modnum<998244353> >::finish<wala::fft::detail::cut_op<wala::modnum<998244353>, wala::fft::add_twice_op> >(wala::fft::engines::ntt<wala::modnum<998244353> >::transformed&&, std::span<wala::modnum<998244353>, 18446744073709551615ul>, wala::fft::detail::cut_op<wala::modnum<998244353>, wala::fft::add_twice_op>):
✓ Branch 14 → 15 taken 84 times.
void wala::fft::engines::ntt<wala::modnum<998244353> >::finish<wala::fft::detail::cut_op<wala::modnum<998244353>, wala::fft::add_op> >(wala::fft::engines::ntt<wala::modnum<998244353> >::transformed&&, std::span<wala::modnum<998244353>, 18446744073709551615ul>, wala::fft::detail::cut_op<wala::modnum<998244353>, wala::fft::add_op>):
✓ Branch 14 → 15 taken 177 times.
void wala::fft::engines::ntt<wala::modnum<998244353> >::finish<wala::fft::detail::cut_op<wala::modnum<998244353>, wala::fft::assign_op> >(wala::fft::engines::ntt<wala::modnum<998244353> >::transformed&&, std::span<wala::modnum<998244353>, 18446744073709551615ul>, wala::fft::detail::cut_op<wala::modnum<998244353>, wala::fft::assign_op>):
✗ Branch 4 → 5 not taken.
✓ Branch 4 → 6 taken 1647993 times.
✗ Branch 7 → 8 not taken.
✓ Branch 7 → 9 taken 1647993 times.
✓ Branch 14 → 15 taken 268 times.
void wala::fft::engines::ntt<wala::modnum<998244353> >::finish<wala::fft::assign_op>(wala::fft::engines::ntt<wala::modnum<998244353> >::transformed&&, std::span<wala::modnum<998244353>, 18446744073709551615ul>, wala::fft::assign_op):
✗ Branch 4 → 5 not taken.
✓ Branch 4 → 6 taken 1656740 times.
✗ Branch 7 → 8 not taken.
✓ Branch 7 → 9 taken 1656740 times.
✓ Branch 14 → 15 taken 2753 times.
|
3318567 | core::inverse(std::span<num>(p.v)); |
| 104 | 3332305 | num d = inv(num(n)); | |
| 105 |
34/34void wala::fft::engines::ntt<wala::mod_goldilocks>::finish<wala::fft::add_twice_op>(wala::fft::engines::ntt<wala::mod_goldilocks>::transformed&&, std::span<wala::mod_goldilocks, 18446744073709551615ul>, wala::fft::add_twice_op):
✓ Branch 38 → 28 taken 938 times.
✓ Branch 38 → 39 taken 238 times.
void wala::fft::engines::ntt<wala::mod_goldilocks>::finish<wala::fft::add_op>(wala::fft::engines::ntt<wala::mod_goldilocks>::transformed&&, std::span<wala::mod_goldilocks, 18446744073709551615ul>, wala::fft::add_op):
✓ Branch 40 → 28 taken 1456 times.
✓ Branch 40 → 41 taken 268 times.
void wala::fft::engines::ntt<wala::mod_goldilocks>::finish<wala::fft::detail::cut_op<wala::mod_goldilocks, wala::fft::add_twice_op> >(wala::fft::engines::ntt<wala::mod_goldilocks>::transformed&&, std::span<wala::mod_goldilocks, 18446744073709551615ul>, wala::fft::detail::cut_op<wala::mod_goldilocks, wala::fft::add_twice_op>):
✓ Branch 38 → 28 taken 168 times.
✓ Branch 38 → 39 taken 84 times.
void wala::fft::engines::ntt<wala::mod_goldilocks>::finish<wala::fft::detail::cut_op<wala::mod_goldilocks, wala::fft::add_op> >(wala::fft::engines::ntt<wala::mod_goldilocks>::transformed&&, std::span<wala::mod_goldilocks, 18446744073709551615ul>, wala::fft::detail::cut_op<wala::mod_goldilocks, wala::fft::add_op>):
✓ Branch 38 → 28 taken 180 times.
✓ Branch 38 → 39 taken 90 times.
void wala::fft::engines::ntt<wala::mod_goldilocks>::finish<wala::fft::detail::cut_op<wala::mod_goldilocks, wala::fft::assign_op> >(wala::fft::engines::ntt<wala::mod_goldilocks>::transformed&&, std::span<wala::mod_goldilocks, 18446744073709551615ul>, wala::fft::detail::cut_op<wala::mod_goldilocks, wala::fft::assign_op>):
✓ Branch 38 → 28 taken 250 times.
✓ Branch 38 → 39 taken 17 times.
void wala::fft::engines::ntt<wala::mod_goldilocks>::finish<wala::fft::assign_op>(wala::fft::engines::ntt<wala::mod_goldilocks>::transformed&&, std::span<wala::mod_goldilocks, 18446744073709551615ul>, wala::fft::assign_op):
✓ Branch 13 → 12 taken 22077513 times.
✓ Branch 13 → 14 taken 48 times.
✓ Branch 39 → 28 taken 52239 times.
✓ Branch 39 → 40 taken 3989 times.
void wala::fft::engines::ntt<wala::modnum<2013265921> >::finish<wala::fft::assign_op>(wala::fft::engines::ntt<wala::modnum<2013265921> >::transformed&&, std::span<wala::modnum<2013265921>, 18446744073709551615ul>, wala::fft::assign_op):
✓ Branch 13 → 12 taken 22077513 times.
✓ Branch 13 → 14 taken 48 times.
✓ Branch 39 → 28 taken 40663 times.
✓ Branch 39 → 40 taken 3529 times.
void wala::fft::engines::ntt<wala::modnum<998244353> >::finish<wala::fft::add_twice_op>(wala::fft::engines::ntt<wala::modnum<998244353> >::transformed&&, std::span<wala::modnum<998244353>, 18446744073709551615ul>, wala::fft::add_twice_op):
✓ Branch 38 → 28 taken 938 times.
✓ Branch 38 → 39 taken 238 times.
void wala::fft::engines::ntt<wala::modnum<998244353> >::finish<wala::fft::add_op>(wala::fft::engines::ntt<wala::modnum<998244353> >::transformed&&, std::span<wala::modnum<998244353>, 18446744073709551615ul>, wala::fft::add_op):
✓ Branch 40 → 28 taken 17482 times.
✓ Branch 40 → 41 taken 2003 times.
void wala::fft::engines::ntt<wala::modnum<998244353> >::finish<wala::fft::detail::cut_op<wala::modnum<998244353>, wala::fft::add_twice_op> >(wala::fft::engines::ntt<wala::modnum<998244353> >::transformed&&, std::span<wala::modnum<998244353>, 18446744073709551615ul>, wala::fft::detail::cut_op<wala::modnum<998244353>, wala::fft::add_twice_op>):
✓ Branch 38 → 28 taken 168 times.
✓ Branch 38 → 39 taken 84 times.
void wala::fft::engines::ntt<wala::modnum<998244353> >::finish<wala::fft::detail::cut_op<wala::modnum<998244353>, wala::fft::add_op> >(wala::fft::engines::ntt<wala::modnum<998244353> >::transformed&&, std::span<wala::modnum<998244353>, 18446744073709551615ul>, wala::fft::detail::cut_op<wala::modnum<998244353>, wala::fft::add_op>):
✓ Branch 38 → 28 taken 354 times.
✓ Branch 38 → 39 taken 177 times.
void wala::fft::engines::ntt<wala::modnum<998244353> >::finish<wala::fft::detail::cut_op<wala::modnum<998244353>, wala::fft::assign_op> >(wala::fft::engines::ntt<wala::modnum<998244353> >::transformed&&, std::span<wala::modnum<998244353>, 18446744073709551615ul>, wala::fft::detail::cut_op<wala::modnum<998244353>, wala::fft::assign_op>):
✓ Branch 14 → 12 taken 22153593 times.
✓ Branch 14 → 15 taken 1647993 times.
✓ Branch 38 → 28 taken 2234 times.
✓ Branch 38 → 39 taken 268 times.
void wala::fft::engines::ntt<wala::modnum<998244353> >::finish<wala::fft::assign_op>(wala::fft::engines::ntt<wala::modnum<998244353> >::transformed&&, std::span<wala::modnum<998244353>, 18446744073709551615ul>, wala::fft::assign_op):
✓ Branch 13 → 12 taken 550759905 times.
✓ Branch 13 → 14 taken 1656740 times.
✓ Branch 39 → 28 taken 44430 times.
✓ Branch 39 → 40 taken 2753 times.
|
620548591 | for (int i = 0; i < sz(out); i++) op(out[i], p.v[i] * d); |
| 106 | 3318567 | } | |
| 107 | }; | ||
| 108 | |||
| 109 | } // namespace wala::fft::engines | ||
| 110 |