fft/common.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include <algorithm> | ||
| 4 | #include <iterator> | ||
| 5 | #include <span> | ||
| 6 | #include <utility> | ||
| 7 | #include <vector> | ||
| 8 | |||
| 9 | /** | ||
| 10 | * Author: Andrew He | ||
| 11 | * Source: http://neerc.ifmo.ru/trains/toulouse/2017/fft2.pdf | ||
| 12 | * Papers about accuracy: http://www.daemonology.net/papers/fft.pdf, http://www.cs.berkeley.edu/~fateman/papers/fftvsothers.pdf | ||
| 13 | * For integers rounding works if $(|a| + |b|)\max(a, b) < \mathtt{\sim} 10^9$, or in theory maybe $10^6$. | ||
| 14 | * | ||
| 15 | * Abstraction layers: | ||
| 16 | * fft_core<num> FFT itself and other ops on rings with 2^k-th roots of unity. We use bit-reversed indexing in the frequency domain. | ||
| 17 | * | ||
| 18 | * engines Engines for packing/unpacking arbitrary rings for convolution (the `engine` concept). | ||
| 19 | * Still expose (opaque) transform-domain objects for caching/fusion. | ||
| 20 | * | ||
| 21 | * multiply layer Wrappers for convolving bounded sequences: track length/truncation. | ||
| 22 | * | ||
| 23 | * value types series::vec<E, exact> - R[[x]] | ||
| 24 | * series::exact<E> - exact (finite-support) power series | ||
| 25 | * series::trunc<E> - truncated prefix of an (infinite) power series | ||
| 26 | * | ||
| 27 | * polynomials - R[x]. Under x -> 1/x a polynomial becomes a Laurent polynomial in 1/x; | ||
| 28 | * shifting by x^{deg P} (reversal) lands it in R[[x]], and we store that exact series. | ||
| 29 | * poly::vec<E> - polynomial type, supporting natural indexing | ||
| 30 | * poly::form<E> - finite-support linear forms, via the pairing <P, S> = [x^0] P(1/x) S(x) | ||
| 31 | * a linear form is one side of this pairing, applied to the other | ||
| 32 | * | ||
| 33 | * online_multiplier<E> - online (relaxed) multiplication of 2 sequences in n log^2 n time | ||
| 34 | * ap_sampled_poly<E> - a polynomial stored as its evaluations on an arithmetic progression | ||
| 35 | */ | ||
| 36 | |||
| 37 | namespace ecnerwala { | ||
| 38 | |||
| 39 |
9/18int ecnerwala::sz<std::vector<mod_goldilocks, std::allocator<mod_goldilocks> > const&>(std::vector<mod_goldilocks, std::allocator<mod_goldilocks> > const&):
✗ Branch 2 → 3 not taken.
✓ Branch 2 → 4 taken 384 times.
int ecnerwala::sz<std::vector<modnum<2013265921>, std::allocator<modnum<2013265921> > > const&>(std::vector<modnum<2013265921>, std::allocator<modnum<2013265921> > > const&):
✗ Branch 2 → 3 not taken.
✓ Branch 2 → 4 taken 240 times.
int ecnerwala::sz<std::vector<modnum<998244353>, std::allocator<modnum<998244353> > > const&>(std::vector<modnum<998244353>, std::allocator<modnum<998244353> > > const&):
✗ Branch 2 → 3 not taken.
✓ Branch 2 → 4 taken 23353009 times.
int ecnerwala::sz<std::vector<ecnerwala::fft::cplx<double>, std::allocator<ecnerwala::fft::cplx<double> > > const&>(std::vector<ecnerwala::fft::cplx<double>, std::allocator<ecnerwala::fft::cplx<double> > > const&):
✗ Branch 2 → 3 not taken.
✓ Branch 2 → 4 taken 240 times.
int ecnerwala::sz<std::vector<mod_goldilocks, std::allocator<mod_goldilocks> >&>(std::vector<mod_goldilocks, std::allocator<mod_goldilocks> >&):
✗ Branch 2 → 3 not taken.
✓ Branch 2 → 4 taken 264 times.
int ecnerwala::sz<std::vector<modnum<2013265921>, std::allocator<modnum<2013265921> > >&>(std::vector<modnum<2013265921>, std::allocator<modnum<2013265921> > >&):
✗ Branch 2 → 3 not taken.
✓ Branch 2 → 4 taken 264 times.
int ecnerwala::sz<std::vector<modnum<998244353>, std::allocator<modnum<998244353> > >&>(std::vector<modnum<998244353>, std::allocator<modnum<998244353> > >&):
✗ Branch 2 → 3 not taken.
✓ Branch 2 → 4 taken 10575731 times.
int ecnerwala::sz<std::vector<ecnerwala::fft::cplx<double>, std::allocator<ecnerwala::fft::cplx<double> > >&>(std::vector<ecnerwala::fft::cplx<double>, std::allocator<ecnerwala::fft::cplx<double> > >&):
✗ Branch 2 → 3 not taken.
✓ Branch 2 → 4 taken 364 times.
int ecnerwala::sz<std::vector<int, std::allocator<int> >&>(std::vector<int, std::allocator<int> >&):
✗ Branch 2 → 3 not taken.
✓ Branch 2 → 4 taken 24283140 times.
|
831601384 | template<class T> int sz(T&& arg) { using std::size; return int(size(std::forward<T>(arg))); } |
| 40 |
10/13None:
✓ Branch 2 → 3 taken 3298363 times.
✓ Branch 2 → 4 taken 140 times.
✓ Branch 6 → 7 taken 137 times.
✓ Branch 6 → 8 taken 9 times.
✓ Branch 8 → 9 taken 55 times.
✓ Branch 8 → 10 taken 4 times.
✓ Branch 11 → 12 taken 20 times.
✗ Branch 11 → 13 not taken.
ecnerwala::nextPow2(int):
✓ Branch 2 → 3 taken 3271 times.
✗ Branch 2 → 4 not taken.
✓ Branch 2 → 5 taken 1850 times.
✗ Branch 3 → 4 not taken.
✓ Branch 3 → 5 taken 3271 times.
|
3303849 | inline int nextPow2(int s) { return 1 << (s > 1 ? 32 - __builtin_clz(s-1) : 0); } |
| 41 | |||
| 42 | namespace fft { | ||
| 43 | |||
| 44 | using std::swap; | ||
| 45 | using std::vector; | ||
| 46 | using std::min; | ||
| 47 | using std::max; | ||
| 48 | |||
| 49 | // Reusable scratch buffers. Not thread-safe by default: this is deliberately plain | ||
| 50 | // static storage so single-threaded programs pay no TLS indirection; define | ||
| 51 | // ECNERWALA_FFT_POOL_STORAGE to `thread_local` for multithreaded use. | ||
| 52 | #ifndef ECNERWALA_FFT_POOL_STORAGE | ||
| 53 | #define ECNERWALA_FFT_POOL_STORAGE | ||
| 54 | #endif | ||
| 55 | template <typename T> struct buffer_pool { | ||
| 56 | static inline ECNERWALA_FFT_POOL_STORAGE std::vector<std::vector<T>> free_list; | ||
| 57 | struct handle { | ||
| 58 | std::vector<T> v; | ||
| 59 |
6/8ecnerwala::fft::buffer_pool<mod_goldilocks>::handle::handle(int):
✓ Branch 2 → 3 taken 96 times.
✓ Branch 2 → 6 taken 48 times.
ecnerwala::fft::buffer_pool<modnum<2013265921> >::handle::handle(int):
✓ Branch 2 → 3 taken 96 times.
✓ Branch 2 → 6 taken 48 times.
ecnerwala::fft::buffer_pool<modnum<998244353> >::handle::handle(int):
✓ Branch 2 → 3 taken 1330034 times.
✓ Branch 2 → 6 taken 326 times.
ecnerwala::fft::buffer_pool<ecnerwala::fft::cplx<double> >::handle::handle(int):
✗ Branch 2 → 3 not taken.
✗ Branch 2 → 6 not taken.
|
1345723 | explicit handle(int n) { |
| 60 |
30/32ecnerwala::fft::buffer_pool<mod_goldilocks>::handle::handle(int):
✓ Branch 2 → 3 taken 96 times.
✓ Branch 2 → 6 taken 48 times.
✓ Branch 7 → 8 taken 6363 times.
✓ Branch 7 → 14 taken 22 times.
ecnerwala::fft::buffer_pool<modnum<1000000007> >::handle::handle(int):
✓ Branch 7 → 8 taken 856 times.
✓ Branch 7 → 14 taken 16 times.
ecnerwala::fft::buffer_pool<modnum<2013265921> >::handle::handle(int):
✓ Branch 2 → 3 taken 96 times.
✓ Branch 2 → 6 taken 48 times.
✓ Branch 7 → 8 taken 6293 times.
✓ Branch 7 → 14 taken 16 times.
ecnerwala::fft::buffer_pool<modnum<998244353> >::handle::handle(int):
✓ Branch 2 → 3 taken 1330034 times.
✓ Branch 2 → 6 taken 326 times.
✓ Branch 7 → 8 taken 942 times.
✓ Branch 7 → 14 taken 20 times.
ecnerwala::fft::buffer_pool<ecnerwala::fft::cplx<double> >::handle::handle(int):
✗ Branch 2 → 3 not taken.
✗ Branch 2 → 6 not taken.
✓ Branch 7 → 8 taken 8 times.
✓ Branch 7 → 14 taken 3 times.
ecnerwala::fft::buffer_pool<ecnerwala::fft::engines::trunc_series<modnum<1000000007>, 2> >::handle::handle(int):
✓ Branch 7 → 8 taken 38 times.
✓ Branch 7 → 14 taken 2 times.
ecnerwala::fft::buffer_pool<ecnerwala::fft::engines::trunc_series<modnum<1000000007>, 3> >::handle::handle(int):
✓ Branch 7 → 8 taken 38 times.
✓ Branch 7 → 14 taken 2 times.
ecnerwala::fft::buffer_pool<ecnerwala::fft::engines::trunc_series<modnum<998244353>, 3> >::handle::handle(int):
✓ Branch 7 → 8 taken 39 times.
✓ Branch 7 → 14 taken 1 time.
ecnerwala::fft::buffer_pool<ecnerwala::fft::engines::mat<modnum<1000000007>, 2> >::handle::handle(int):
✓ Branch 7 → 8 taken 40 times.
✓ Branch 7 → 14 taken 2 times.
ecnerwala::fft::buffer_pool<ecnerwala::fft::engines::mat<modnum<1000000007>, 3> >::handle::handle(int):
✓ Branch 7 → 8 taken 156 times.
✓ Branch 7 → 14 taken 2 times.
ecnerwala::fft::buffer_pool<ecnerwala::fft::engines::mat<modnum<998244353>, 3> >::handle::handle(int):
✓ Branch 7 → 8 taken 157 times.
✓ Branch 7 → 14 taken 1 time.
ecnerwala::fft::buffer_pool<double>::handle::handle(int):
✓ Branch 7 → 8 taken 54 times.
✓ Branch 7 → 14 taken 4 times.
|
1345723 | if (!free_list.empty()) { |
| 61 | 1345210 | v = std::move(free_list.back()); | |
| 62 | 1345210 | free_list.pop_back(); | |
| 63 | } | ||
| 64 |
15/16ecnerwala::fft::buffer_pool<mod_goldilocks>::handle::handle(int):
✓ Branch 6 → 7 taken 144 times.
✓ Branch 21 → 22 taken 6385 times.
ecnerwala::fft::buffer_pool<modnum<1000000007> >::handle::handle(int):
✓ Branch 21 → 22 taken 872 times.
ecnerwala::fft::buffer_pool<modnum<2013265921> >::handle::handle(int):
✓ Branch 6 → 7 taken 144 times.
✓ Branch 21 → 22 taken 6309 times.
ecnerwala::fft::buffer_pool<modnum<998244353> >::handle::handle(int):
✓ Branch 6 → 7 taken 1330360 times.
✓ Branch 21 → 22 taken 962 times.
ecnerwala::fft::buffer_pool<ecnerwala::fft::cplx<double> >::handle::handle(int):
✗ Branch 6 → 7 not taken.
✓ Branch 19 → 20 taken 11 times.
ecnerwala::fft::buffer_pool<ecnerwala::fft::engines::trunc_series<modnum<1000000007>, 2> >::handle::handle(int):
✓ Branch 19 → 20 taken 40 times.
ecnerwala::fft::buffer_pool<ecnerwala::fft::engines::trunc_series<modnum<1000000007>, 3> >::handle::handle(int):
✓ Branch 19 → 20 taken 40 times.
ecnerwala::fft::buffer_pool<ecnerwala::fft::engines::trunc_series<modnum<998244353>, 3> >::handle::handle(int):
✓ Branch 19 → 20 taken 40 times.
ecnerwala::fft::buffer_pool<ecnerwala::fft::engines::mat<modnum<1000000007>, 2> >::handle::handle(int):
✓ Branch 19 → 20 taken 42 times.
ecnerwala::fft::buffer_pool<ecnerwala::fft::engines::mat<modnum<1000000007>, 3> >::handle::handle(int):
✓ Branch 19 → 20 taken 158 times.
ecnerwala::fft::buffer_pool<ecnerwala::fft::engines::mat<modnum<998244353>, 3> >::handle::handle(int):
✓ Branch 19 → 20 taken 158 times.
ecnerwala::fft::buffer_pool<double>::handle::handle(int):
✓ Branch 18 → 19 taken 58 times.
|
1360251 | v.assign(n, T()); |
| 65 | 1345723 | } | |
| 66 | ✗ | handle(const handle&) = delete; | |
| 67 | ✗ | handle& operator=(const handle&) = delete; | |
| 68 | ✗ | handle(handle&& o) noexcept : v(std::move(o.v)) {} | |
| 69 |
18/40ecnerwala::fft::buffer_pool<mod_goldilocks>::handle::~handle():
✗ Branch 2 → 3 not taken.
✓ Branch 2 → 4 taken 144 times.
✓ Branch 4 → 5 taken 144 times.
✗ Branch 4 → 6 not taken.
✓ Branch 7 → 8 taken 6385 times.
✗ Branch 7 → 12 not taken.
ecnerwala::fft::buffer_pool<modnum<1000000007> >::handle::~handle():
✓ Branch 7 → 8 taken 872 times.
✗ Branch 7 → 12 not taken.
ecnerwala::fft::buffer_pool<modnum<2013265921> >::handle::~handle():
✗ Branch 2 → 3 not taken.
✓ Branch 2 → 4 taken 144 times.
✓ Branch 4 → 5 taken 144 times.
✗ Branch 4 → 6 not taken.
✓ Branch 7 → 8 taken 6309 times.
✗ Branch 7 → 12 not taken.
ecnerwala::fft::buffer_pool<modnum<998244353> >::handle::~handle():
✗ Branch 2 → 3 not taken.
✓ Branch 2 → 4 taken 1330360 times.
✓ Branch 4 → 5 taken 1330360 times.
✗ Branch 4 → 6 not taken.
✓ Branch 7 → 8 taken 962 times.
✗ Branch 7 → 12 not taken.
ecnerwala::fft::buffer_pool<ecnerwala::fft::cplx<double> >::handle::~handle():
✗ Branch 2 → 3 not taken.
✗ Branch 2 → 4 not taken.
✗ Branch 4 → 5 not taken.
✗ Branch 4 → 6 not taken.
✓ Branch 7 → 8 taken 11 times.
✗ Branch 7 → 12 not taken.
ecnerwala::fft::buffer_pool<ecnerwala::fft::engines::trunc_series<modnum<1000000007>, 2> >::handle::~handle():
✓ Branch 7 → 8 taken 40 times.
✗ Branch 7 → 12 not taken.
ecnerwala::fft::buffer_pool<ecnerwala::fft::engines::trunc_series<modnum<1000000007>, 3> >::handle::~handle():
✓ Branch 7 → 8 taken 40 times.
✗ Branch 7 → 12 not taken.
ecnerwala::fft::buffer_pool<ecnerwala::fft::engines::trunc_series<modnum<998244353>, 3> >::handle::~handle():
✓ Branch 7 → 8 taken 40 times.
✗ Branch 7 → 12 not taken.
ecnerwala::fft::buffer_pool<ecnerwala::fft::engines::mat<modnum<1000000007>, 2> >::handle::~handle():
✓ Branch 7 → 8 taken 42 times.
✗ Branch 7 → 12 not taken.
ecnerwala::fft::buffer_pool<ecnerwala::fft::engines::mat<modnum<1000000007>, 3> >::handle::~handle():
✓ Branch 7 → 8 taken 158 times.
✗ Branch 7 → 12 not taken.
ecnerwala::fft::buffer_pool<ecnerwala::fft::engines::mat<modnum<998244353>, 3> >::handle::~handle():
✓ Branch 7 → 8 taken 158 times.
✗ Branch 7 → 12 not taken.
ecnerwala::fft::buffer_pool<double>::handle::~handle():
✓ Branch 7 → 8 taken 58 times.
✗ Branch 7 → 12 not taken.
|
1360798 | ~handle() { if (v.capacity()) free_list.push_back(std::move(v)); } |
| 70 |
3/4✓ Branch 11 → 12 taken 11556440 times.
✓ Branch 11 → 13 taken 10521129 times.
✗ Branch 15 → 16 not taken.
✓ Branch 15 → 17 taken 22077513 times.
|
107500709 | T& operator[](int i) { return v[i]; } |
| 71 | ✗ | operator std::span<T>() { return std::span<T>(v); } | |
| 72 |
17/23✗ Branch 5 → 6 not taken.
✓ Branch 5 → 7 taken 537 times.
✗ Branch 6 → 7 not taken.
✓ Branch 6 → 8 taken 585 times.
✓ Branch 7 → 8 taken 537 times.
✓ Branch 8 → 9 taken 585 times.
✗ Branch 9 → 10 not taken.
✓ Branch 9 → 11 taken 48 times.
✓ Branch 11 → 12 taken 48 times.
✗ Branch 15 → 16 not taken.
✓ Branch 15 → 17 taken 29 times.
✗ Branch 16 → 17 not taken.
✓ Branch 16 → 18 taken 96 times.
✓ Branch 17 → 18 taken 29 times.
✓ Branch 17 → 19 taken 1327590 times.
✓ Branch 18 → 19 taken 96 times.
✓ Branch 19 → 20 taken 1327590 times.
✓ Branch 19 → 21 taken 96 times.
✓ Branch 21 → 22 taken 96 times.
✓ Branch 25 → 26 taken 1667 times.
✗ Branch 27 → 28 not taken.
✓ Branch 27 → 29 taken 1667 times.
✓ Branch 29 → 30 taken 1667 times.
|
2685945 | std::span<T> span() { return std::span<T>(v); } |
| 73 | }; | ||
| 74 |
29/29✓ Branch 4 → 5 taken 478 times.
✓ Branch 5 → 6 taken 48 times.
✓ Branch 5 → 15 taken 96 times.
✓ Branch 7 → 8 taken 895 times.
✓ Branch 9 → 10 taken 232 times.
✓ Branch 10 → 42 taken 895 times.
✓ Branch 12 → 13 taken 3475 times.
✓ Branch 12 → 74 taken 40 times.
✓ Branch 14 → 15 taken 4 times.
✓ Branch 15 → 16 taken 5461 times.
✓ Branch 15 → 77 taken 284 times.
✓ Branch 16 → 17 taken 1667 times.
✓ Branch 17 → 18 taken 26 times.
✓ Branch 18 → 19 taken 369 times.
✓ Branch 18 → 50 taken 1939 times.
✓ Branch 18 → 59 taken 40 times.
✓ Branch 19 → 56 taken 174 times.
✓ Branch 21 → 62 taken 122 times.
✓ Branch 22 → 59 taken 58 times.
✓ Branch 26 → 27 taken 1667 times.
✓ Branch 33 → 34 taken 14 times.
✓ Branch 35 → 36 taken 14 times.
✓ Branch 43 → 44 taken 155 times.
✓ Branch 47 → 48 taken 123 times.
✓ Branch 48 → 49 taken 4 times.
✓ Branch 48 → 65 taken 7 times.
✓ Branch 72 → 73 taken 133 times.
✓ Branch 114 → 115 taken 18 times.
✓ Branch 130 → 131 taken 115 times.
|
1345579 | static handle get(int n) { return handle(n); } |
| 75 | }; | ||
| 76 | |||
| 77 | /* namespace fft */ } | ||
| 78 | |||
| 79 | /* namespace ecnerwala */ } | ||
| 80 |