summaryrefslogtreecommitdiff
path: root/test/math
diff options
context:
space:
mode:
Diffstat (limited to 'test/math')
-rw-r--r--test/math/divSum.cpp48
-rw-r--r--test/math/gauss.cpp2
-rw-r--r--test/math/inversionsMerge.cpp2
-rw-r--r--test/math/linearRecurrence.cpp5
-rw-r--r--test/math/linearRecurrence.cpp.awk4
-rw-r--r--test/math/linearRecurrenceNTT.cpp60
-rw-r--r--test/math/linearRecurrenceOld.cpp54
-rw-r--r--test/math/minMod.cpp92
-rw-r--r--test/math/polynomial.cpp153
-rw-r--r--test/math/recover.cpp44
-rw-r--r--test/math/rho.cpp14
-rw-r--r--test/math/transforms/seriesOperations.cpp145
12 files changed, 618 insertions, 5 deletions
diff --git a/test/math/divSum.cpp b/test/math/divSum.cpp
new file mode 100644
index 0000000..1f82387
--- /dev/null
+++ b/test/math/divSum.cpp
@@ -0,0 +1,48 @@
+#include "../util.h"
+#include <math/divSum.cpp>
+
+ll naive(ll n, ll m, ll a, ll b){
+ ll ans = 0;
+ for(ll i = 0; i < n; i++){
+ ans += (a*i+b)/m;
+ }
+ return ans;
+}
+
+void stress_test() {
+ ll queries = 0;
+ for (ll i = 0; i < 10'000; i++) {
+ int n = Random::integer<int>(1, 100);
+ int m = Random::integer<int>(1, 100);
+ int a = Random::integer<int>(0, 100);
+ int b = Random::integer<int>(0, 100);
+ ll expected = naive(n, m, a, b);
+ ll got = divSum(n, m, a, b);
+ if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL;
+ queries++;
+ }
+ cerr << "tested queries: " << queries << endl;
+}
+
+constexpr int N = 1'000'000;
+void performance_test() {
+ timer t;
+ hash_t hash = 0;
+ for (int operations = 0; operations < N; operations++) {
+ ll n = Random::integer<ll>(1, 1'000'000'000);
+ ll m = Random::integer<ll>(1, 1'000'000'000);
+ ll a = Random::integer<ll>(0, 1'000'000'000);
+ ll b = Random::integer<ll>(0, 1'000'000'000);
+ t.start();
+ hash += divSum(n, m, a, b);
+ t.stop();
+ }
+ if (t.time > 750) cerr << "too slow: " << t.time << FAIL;
+ cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+}
+
+int main() {
+ stress_test();
+ performance_test();
+}
+
diff --git a/test/math/gauss.cpp b/test/math/gauss.cpp
index 37bacce..6e4759d 100644
--- a/test/math/gauss.cpp
+++ b/test/math/gauss.cpp
@@ -14,7 +14,7 @@ vector<vector<double>> inverseMat(const vector<vector<double>>& m) {
mat[i].resize(2*n);
mat[i][n+i] = 1;
}
- gauss(n);//the unique cetc. checks are not usefull since we dont solve an lgs...
+ gauss(n); //the unique cetc. checks are not usefull since we dont solve an lgs...
vector<vector<double>> res(m);
for (int i = 0; i < n; i++) {
res[i] = vector<double>(mat[i].begin() + n, mat[i].end());
diff --git a/test/math/inversionsMerge.cpp b/test/math/inversionsMerge.cpp
index 85ab0d2..acdc555 100644
--- a/test/math/inversionsMerge.cpp
+++ b/test/math/inversionsMerge.cpp
@@ -16,7 +16,7 @@ void stress_test() {
for (ll i = 0; i < 100'000; i++) {
int n = Random::integer<int>(1, 100);
vector<ll> v(n);
- for (ll j = 0; j < n; j++) v[j] = (j-10) * 100000 + Random::integer<ll>(0, 10000);//values must be unique ):
+ for (ll j = 0; j < n; j++) v[j] = (j-10) * 100000 + Random::integer<ll>(0, 10000); //values must be unique ):
shuffle(all(v), Random::rng);
ll expected = naive(v);
ll got = mergeSort(v);
diff --git a/test/math/linearRecurrence.cpp b/test/math/linearRecurrence.cpp
index 21a8a7c..8640980 100644
--- a/test/math/linearRecurrence.cpp
+++ b/test/math/linearRecurrence.cpp
@@ -1,6 +1,11 @@
#include "../util.h"
+vector<ll> mul(const vector<ll>& a, const vector<ll>& b);
#include <math/linearRecurrence.cpp>
+vector<ll> mul(const vector<ll>& a, const vector<ll>& b) {
+ return mulSlow(a, b);
+}
+
struct RandomRecurence {
vector<ll> f, c, cache;
RandomRecurence(int n) : f(Random::integers<ll>(n, 0, mod)), c(Random::integers<ll>(n, 0, mod)), cache(f) {}
diff --git a/test/math/linearRecurrence.cpp.awk b/test/math/linearRecurrence.cpp.awk
new file mode 100644
index 0000000..902fd4b
--- /dev/null
+++ b/test/math/linearRecurrence.cpp.awk
@@ -0,0 +1,4 @@
+/vector<ll> mul/ {
+ sub(/mul/, "mulSlow")
+}
+{ print }
diff --git a/test/math/linearRecurrenceNTT.cpp b/test/math/linearRecurrenceNTT.cpp
new file mode 100644
index 0000000..e03c27e
--- /dev/null
+++ b/test/math/linearRecurrenceNTT.cpp
@@ -0,0 +1,60 @@
+#include "../util.h"
+#include <math/modPowIterativ.cpp>
+#include <math/transforms/ntt.cpp>
+#include <math/transforms/multiplyNTT.cpp>
+#define mod mod2
+#include <math/linearRecurrence.cpp>
+#undef mod
+static_assert(mod == mod2);
+
+struct RandomRecurence {
+ vector<ll> f, c, cache;
+ RandomRecurence(int n) : f(Random::integers<ll>(n, 0, mod)), c(Random::integers<ll>(n, 0, mod)), cache(f) {}
+
+ ll operator()(ll k){
+ while (sz(cache) <= k) {
+ ll cur = 0;
+ for (ll i = 0; i < sz(c); i++) {
+ cur += (c[i] * cache[sz(cache) - i - 1]) % mod;
+ }
+ cur %= mod;
+ cache.push_back(cur);
+ }
+ return cache[k];
+ }
+};
+
+void stress_test() {
+ int queries = 0;
+ for (int i = 0; i < 1'000; i++) {
+ int n = Random::integer<int>(1, 10);
+ RandomRecurence f(n);
+ for (int j = 0; j < 100; j++) {
+ ll k = Random::integer<ll>(0, 1000);
+
+ ll got = kthTerm(f.f, f.c, k);
+ ll expected = f(k);
+
+ if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL;
+ queries++;
+ }
+ }
+ cerr << "tested random queries: " << queries << endl;
+}
+
+constexpr int N = 100'000;
+void performance_test() {
+ timer t;
+ RandomRecurence f(N);
+ t.start();
+ hash_t hash = kthTerm(f.f, f.c, 1e18);
+ t.stop();
+ if (t.time > 8000) cerr << "too slow: " << t.time << FAIL;
+ cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+}
+
+int main() {
+ stress_test();
+ performance_test();
+}
+
diff --git a/test/math/linearRecurrenceOld.cpp b/test/math/linearRecurrenceOld.cpp
new file mode 100644
index 0000000..dab2256
--- /dev/null
+++ b/test/math/linearRecurrenceOld.cpp
@@ -0,0 +1,54 @@
+#include "../util.h"
+#include <math/linearRecurrenceOld.cpp>
+
+struct RandomRecurence {
+ vector<ll> f, c, cache;
+ RandomRecurence(int n) : f(Random::integers<ll>(n, 0, mod)), c(Random::integers<ll>(n, 0, mod)), cache(f) {}
+
+ ll operator()(ll k){
+ while (sz(cache) <= k) {
+ ll cur = 0;
+ for (ll i = 0; i < sz(c); i++) {
+ cur += (c[i] * cache[sz(cache) - i - 1]) % mod;
+ }
+ cur %= mod;
+ cache.push_back(cur);
+ }
+ return cache[k];
+ }
+};
+
+void stress_test() {
+ int queries = 0;
+ for (int i = 0; i < 10'000; i++) {
+ int n = Random::integer<int>(1, 10);
+ RandomRecurence f(n);
+ for (int j = 0; j < 100; j++) {
+ ll k = Random::integer<ll>(0, 1000);
+
+ ll got = kthTerm(f.f, f.c, k);
+ ll expected = f(k);
+
+ if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL;
+ queries++;
+ }
+ }
+ cerr << "tested random queries: " << queries << endl;
+}
+
+constexpr int N = 1'000;
+void performance_test() {
+ timer t;
+ RandomRecurence f(N);
+ t.start();
+ hash_t hash = kthTerm(f.f, f.c, 1e18);
+ t.stop();
+ if (t.time > 500) cerr << "too slow: " << t.time << FAIL;
+ cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+}
+
+int main() {
+ stress_test();
+ performance_test();
+}
+
diff --git a/test/math/minMod.cpp b/test/math/minMod.cpp
new file mode 100644
index 0000000..e49da11
--- /dev/null
+++ b/test/math/minMod.cpp
@@ -0,0 +1,92 @@
+#include "../util.h"
+#include <math/shortModInv.cpp>
+#include <math/minMod.cpp>
+
+ll naiveMinMod(ll n, ll m, ll a, ll b){
+ ll ans = m;
+ for(ll i = 0; i < n; i++){
+ ans = min(ans, (a*i+b)%m);
+ }
+ return ans;
+}
+
+ll naiveFirstVal(ll a, ll m, ll l, ll r){
+ for(ll i = 0; i < m; i++){
+ ll v = a*i % m;
+ if(l <= v && v <= r) return v;
+ }
+ return -1;
+}
+
+void stress_test_minMod() {
+ ll queries = 0;
+ for (ll i = 0; i < 10'000; i++) {
+ int n = Random::integer<int>(1, 100);
+ int m = Random::integer<int>(1, 100);
+ int a = Random::integer<int>(0, m);
+ int b = Random::integer<int>(0, m);
+ ll expected = naiveMinMod(n, m, a, b);
+ ll got = minMod(n, m, a, b);
+ if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL;
+ queries++;
+ }
+ cerr << "tested queries: " << queries << endl;
+}
+
+void stress_test_firstVal() {
+ ll queries = 0;
+ for (ll i = 0; i < 10'000; i++) {
+ int m = Random::integer<int>(1, 100);
+ int a = Random::integer<int>(0, m);
+ int l = Random::integer<int>(0, m);
+ int r = Random::integer<int>(0, m);
+ if(l > r) swap(l, r);
+ ll expected = naiveFirstVal(a, m, l, r);
+ ll got = firstVal(a, m, l, r);
+ if (got != expected) cerr << a << " " << m << " " << l << " " << r << "got: " << got << ", expected: " << expected << FAIL;
+ queries++;
+ }
+ cerr << "tested queries: " << queries << endl;
+}
+
+constexpr int N = 1'000'000;
+void performance_test_minMod() {
+ timer t;
+ hash_t hash = 0;
+ for (int operations = 0; operations < N; operations++) {
+ ll n = Random::integer<ll>(1, 1'000'000'000);
+ ll m = Random::integer<ll>(1, 1'000'000'000);
+ ll a = Random::integer<ll>(0, m);
+ ll b = Random::integer<ll>(0, m);
+ t.start();
+ hash += minMod(n, m, a, b);
+ t.stop();
+ }
+ if (t.time > 750) cerr << "too slow: " << t.time << FAIL;
+ cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+}
+
+void performance_test_firstVal() {
+ timer t;
+ hash_t hash = 0;
+ for (int operations = 0; operations < N; operations++) {
+ ll m = Random::integer<ll>(1, 1'000'000'000);
+ ll a = Random::integer<ll>(1, m);
+ ll l = Random::integer<ll>(0, m);
+ ll r = Random::integer<ll>(0, m);
+ if(l > r) swap(l, r);
+ t.start();
+ hash += firstVal(a, m, l, r);
+ t.stop();
+ }
+ if (t.time > 750) cerr << "too slow: " << t.time << FAIL;
+ cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+}
+
+int main() {
+ stress_test_minMod();
+ stress_test_firstVal();
+ performance_test_minMod();
+ performance_test_firstVal();
+}
+
diff --git a/test/math/polynomial.cpp b/test/math/polynomial.cpp
new file mode 100644
index 0000000..f4a9486
--- /dev/null
+++ b/test/math/polynomial.cpp
@@ -0,0 +1,153 @@
+#include "../util.h"
+#include <math/shortModInv.cpp>
+constexpr ll mod = 1'394'633'899;
+#include <math/polynomial.cpp>
+
+poly randomPoly(int deg) {
+ poly p;
+ p.data = Random::integers<ll>(deg + 1, 0, mod);
+ return p;
+}
+
+ll eval(const vector<ll>& p, ll x) {
+ ll res = 0;
+ for (ll i = 0, j = 1; i < sz(p); i++, j = (j * x) % mod) {
+ res += j * p[i];
+ res %= mod;
+ }
+ return res;
+}
+
+void test_eval() {
+ int queries = 0;
+ for (int tries = 0; tries < 100'000; tries++) {
+ int deg = Random::integer<int>(1, 30);
+ vector<ll> tmp = Random::integers<ll>(deg + 1, 0, mod);
+ poly p(deg);
+ for (int i = 0; i <= deg; i++) p[i] = tmp[i];
+
+ for (int i = 0; i <= deg + 7; i++) {
+ ll x = Random::integer<ll>(0, mod);
+
+ ll got = p(x);
+ ll expected = eval(tmp, x);
+
+ if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL;
+ }
+ queries += deg + 1;
+ }
+ cerr << "tested eval: " << queries << endl;
+}
+
+void test_add() {
+ int queries = 0;
+ for (int tries = 0; tries < 100'000; tries++) {
+ int n = Random::integer<int>(1, 30);
+ int m = Random::integer<int>(1, 30);
+ auto a = randomPoly(n);
+ auto b = randomPoly(m);
+
+ auto c = a;
+ c += b;
+
+ if (sz(c) > sz(a) && sz(c) > sz(b)) cerr << "error: wrong degree" << FAIL;
+
+ for (int i = 0; i <= n + m + 7; i++) {
+ ll x = Random::integer<ll>(0, mod);
+
+ ll got = c(x);
+ ll expected = (a(x) + b(x)) % mod;
+
+ if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL;
+ }
+ queries += n + m;
+ }
+ cerr << "tested add: " << queries << endl;
+}
+
+void test_mul() {
+ int queries = 0;
+ for (int tries = 0; tries < 100'000; tries++) {
+ int n = Random::integer<int>(1, 30);
+ int m = Random::integer<int>(1, 30);
+ auto a = randomPoly(n);
+ auto b = randomPoly(m);
+
+ auto c = a * b;
+ if (sz(c) > sz(a) + sz(b) - 1) cerr << "error: wrong degree" << FAIL;
+
+ for (int i = 0; i <= n + m + 7; i++) {
+ ll x = Random::integer<ll>(0, mod);
+
+ ll got = c(x);
+ ll expected = (a(x) * b(x)) % mod;
+
+ if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL;
+ }
+ queries += n + m;
+ }
+ cerr << "tested mul: " << queries << endl;
+}
+
+void test_shift() {
+ int queries = 0;
+ for (int tries = 0; tries < 100'000; tries++) {
+ int n = Random::integer<int>(1, 30);
+ int m = Random::integer<int>(1, 30);
+ auto a = randomPoly(n);
+
+ auto b = a << m;
+ if (sz(b) > sz(a)) cerr << sz(a) << " " << sz(b) << endl;
+ if (sz(b) > sz(a)) cerr << "error: wrong degree" << FAIL;
+
+ for (int i = 0; i <= n + 7; i++) {
+ ll x = Random::integer<ll>(0, mod);
+
+ ll got = b(x);
+ ll expected = a((x + m) % mod);
+
+ if (got != expected) {
+ for (ll y : b.data) cerr << y << " ";
+ cerr << endl;
+ }
+ if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL;
+ }
+ queries += n;
+ }
+ cerr << "tested shift: " << queries << endl;
+}
+
+void test_divmod() {
+ int queries = 0;
+ for (int tries = 0; tries < 100'000; tries++) {
+ int n = Random::integer<int>(1, 30);
+ int m = Random::integer<int>(1, 30);
+ auto a = randomPoly(n);
+ auto b = randomPoly(m);
+
+ auto [div, rem] = a.divmod(b);
+ if (sz(rem) > sz(b)) cerr << "error: wrong degree (rem)" << FAIL;
+ if (sz(div) > 1 + max<ll>(0, sz(a) - sz(b))) cerr << "error: wrong degree (div)" << FAIL;
+
+ for (int i = 0; i <= n + m; i++) {
+ ll x = Random::integer<ll>(0, mod);
+ ll d = multInv(b(x), mod);
+
+ ll got = (div(x) + rem(x) * d) % mod;
+ ll expected = (a(x) * d) % mod;
+
+ if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL;
+ }
+ queries += n + m;
+ }
+ cerr << "tested divmod: " << queries << endl;
+}
+
+int main() {
+ test_eval();
+ test_add();
+ test_mul();
+ test_shift();
+ test_divmod();
+}
+
diff --git a/test/math/recover.cpp b/test/math/recover.cpp
new file mode 100644
index 0000000..6f89e5a
--- /dev/null
+++ b/test/math/recover.cpp
@@ -0,0 +1,44 @@
+#include "../util.h"
+#include <math/recover.cpp>
+#include <math/shortModInv.cpp>
+
+void stress_test() {
+ ll queries = 0;
+ timer t;
+ for (int i = 0; i < 500; i++) {
+ ll p = Random::prime<ll>(10000);
+ for (ll j = 0; 2*j*j < p; j++) {
+ for (ll b = 1; 2*b*b < p; b++) {
+ if (gcd(j, b) != 1) continue;
+ for (ll a : {-j, j}) {
+ ll c = a * multInv(b, p);
+
+ t.start();
+ auto [x, y] = recover(c, p);
+ t.stop();
+
+ if (a != x || b != y) cerr << "got: " << x << "/" << y << ", expected: " << a << "/" << b << FAIL;
+ queries++;
+ }
+ }
+ }
+ for (ll c = 0; c < p; c++) {
+ t.start();
+ auto [x, y] = recover(c, p);
+ t.stop();
+
+ if (y < 0) continue;
+ if (y == 0) cerr << "error: y=0" << FAIL;
+ ll got = (((x * multInv(y, p)) % p) + p) % p;
+ if (got != c) cerr << "got: " << got << ", expected: " << c << FAIL;
+ queries++;
+ }
+ }
+ cerr << "tested random queries: " << queries << endl;
+ if (t.time > 500) cerr << "too slow: " << t.time << FAIL;
+ cerr << "tested performance: " << t.time << "ms" << endl;
+}
+
+int main() {
+ stress_test();
+}
diff --git a/test/math/rho.cpp b/test/math/rho.cpp
index 5e4792a..941524b 100644
--- a/test/math/rho.cpp
+++ b/test/math/rho.cpp
@@ -96,17 +96,25 @@ void stress_test() {
cerr << "stress tested: " << t.time << "ms" << endl;
}
-constexpr int N = 2'000;
+ll randomHard(ll lim) {
+ ll root2 = sqrt(lim);
+ ll root3 = cbrt(lim);
+ ll a = Random::prime<ll>(root2 / 2 - root3, root2 / 2 + root3);
+ ll b = Random::prime<ll>(lim / a - root3, lim / a);
+ return a * b;
+}
+
+constexpr int N = 200;
void performance_test() {
timer t;
hash_t hash = 0;
for (int operations = 0; operations < N; operations++) {
- ll x = Random::integer<ll>(1e18 / 2, 1e18);
+ ll x = randomHard(1e18);
t.start();
hash += factor(x).size();
t.stop();
}
- if (t.time > 500) cerr << "too slow: " << t.time << FAIL;
+ if (t.time > 750) cerr << "too slow: " << t.time << FAIL;
cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
}
diff --git a/test/math/transforms/seriesOperations.cpp b/test/math/transforms/seriesOperations.cpp
new file mode 100644
index 0000000..ee30e00
--- /dev/null
+++ b/test/math/transforms/seriesOperations.cpp
@@ -0,0 +1,145 @@
+#include "../../util.h"
+#include <math/modPowIterativ.cpp>
+#include <math/transforms/ntt.cpp>
+#include <math/transforms/multiplyNTT.cpp>
+#pragma GCC diagnostic ignored "-Wunused-variable"
+#include <math/transforms/seriesOperations.cpp>
+
+namespace reference {//checked against yosupo
+ vector<ll> poly_inv(vector<ll> a, int n){
+ vector<ll> q = {powMod(a[0], mod-2, mod)};
+ for(int len = 1; len < n; len *= 2){
+ vector<ll> a2 = a, q2 = q;
+ a2.resize(2*len), q2.resize(2*len);
+ ntt(q2);
+ for(int j = 0; j < 2; j++){
+ ntt(a2);
+ for(int i = 0; i < 2*len; i++) a2[i] = a2[i] * q2[i] % mod;
+ ntt(a2, true);
+ for(int i = 0; i < len; i++) a2[i] = 0;
+ }
+ for(int i = len; i < min(n, 2*len); i++) q.push_back((mod - a2[i]) % mod);
+ }
+ return q;
+ }
+
+ vector<ll> poly_deriv(vector<ll> a){
+ for(int i = 0; i < sz(a)-1; i++)
+ a[i] = a[i+1] * (i+1) % mod;
+ a.pop_back();
+ return a;
+ }
+
+ vector<ll> poly_integr(vector<ll> a){
+ if(a.empty()) return {0};
+ a.push_back(a.back() * powMod(sz(a), mod-2, mod) % mod);
+ for(int i = sz(a)-2; i > 0; i--)
+ a[i] = a[i-1] * powMod(i, mod-2, mod) % mod;
+ a[0] = 0;
+ return a;
+ }
+
+ vector<ll> poly_log(vector<ll> a, int n){
+ a = mul(poly_deriv(a), poly_inv(a, n));
+ a.resize(n-1);
+ a = poly_integr(a);
+ return a;
+ }
+
+ vector<ll> poly_exp(vector<ll> a, int n){
+ vector<ll> q = {1};
+ for(int len = 1; len < n; len *= 2){
+ vector<ll> p = poly_log(q, 2*len);
+ for(int i = 0; i < 2*len; i++)
+ p[i] = (mod - p[i] + (i < sz(a) ? a[i] : 0)) % mod;
+ vector<ll> q2 = q;
+ q2.resize(2*len);
+ ntt(p), ntt(q2);
+ for(int i = 0; i < 2*len; i++) p[i] = p[i] * q2[i] % mod;
+ ntt(p, true);
+ for(int i = len; i < min(n, 2*len); i++) q.push_back(p[i]);
+ }
+ return q;
+ }
+}
+
+void test_inv() {
+ ll queries = 0;
+ for (ll i = 0; i < 50'000; i++) {
+ int n = Random::integer<int>(1, 100);
+ int m = Random::integer<int>(1, 100);
+ vector<ll> a = Random::integers<ll>(n, 0, mod);
+
+ auto got = poly_inv(a, m);
+ auto expected = reference::poly_inv(a, m);
+ if (got != expected) cerr << "error" << FAIL;
+ queries += n;
+ }
+ cerr << "tested inv: " << queries << endl;
+}
+
+void test_deriv() {
+ ll queries = 0;
+ for (ll i = 0; i < 50'000; i++) {
+ int n = Random::integer<int>(1, 100);
+ vector<ll> a = Random::integers<ll>(n, 0, mod);
+
+ auto got = poly_deriv(a);
+ auto expected = reference::poly_deriv(a);
+ if (got != expected) cerr << "error" << FAIL;
+ queries += n;
+ }
+ cerr << "tested deriv: " << queries << endl;
+}
+
+void test_integr() {
+ ll queries = 0;
+ for (ll i = 0; i < 50'000; i++) {
+ int n = Random::integer<int>(1, 100);
+ vector<ll> a = Random::integers<ll>(n, 0, mod);
+
+ auto got = poly_deriv(a);
+ auto expected = reference::poly_deriv(a);
+ if (got != expected) cerr << "error" << FAIL;
+ queries += n;
+ }
+ cerr << "tested integr: " << queries << endl;
+}
+
+void test_log() {
+ ll queries = 0;
+ for (ll i = 0; i < 50'000; i++) {
+ int n = Random::integer<int>(1, 100);
+ int m = Random::integer<int>(1, 100);
+ vector<ll> a = Random::integers<ll>(n, 0, mod);
+
+ auto got = poly_log(a, m);
+ auto expected = reference::poly_log(a, m);
+ if (got != expected) cerr << "error" << FAIL;
+ queries += n;
+ }
+ cerr << "tested log: " << queries << endl;
+}
+
+void test_exp() {
+ ll queries = 0;
+ for (ll i = 0; i < 50'000; i++) {
+ int n = Random::integer<int>(1, 100);
+ int m = Random::integer<int>(1, 100);
+ vector<ll> a = Random::integers<ll>(n, 0, mod);
+
+ auto got = poly_exp(a, m);
+ auto expected = reference::poly_exp(a, m);
+ if (got != expected) cerr << "error" << FAIL;
+ queries += n;
+ }
+ cerr << "tested exp: " << queries << endl;
+}
+
+int main() {
+ test_inv();
+ test_deriv();
+ test_integr();
+ test_log();
+ test_exp();
+}
generated by cgit v1.2.3 (git 2.39.1) at 2025-12-23 19:14:57 +0000