diff options
Diffstat (limited to 'test/math')
51 files changed, 3001 insertions, 0 deletions
diff --git a/test/math/berlekampMassey.cpp b/test/math/berlekampMassey.cpp new file mode 100644 index 0000000..58fd143 --- /dev/null +++ b/test/math/berlekampMassey.cpp @@ -0,0 +1,68 @@ +#include "../util.h" +#include <math/modPowIterativ.cpp> +#include <math/berlekampMassey.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) {} + RandomRecurence(const vector<ll>& f_, const vector<ll>& c_) : c(c_), cache(f_) { + if (cache.size() < c.size()) cerr << "wrong size" << FAIL; + cache.resize(c.size()); + f = cache; + } + + 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 < 50'000; i++) { + int n = Random::integer<int>(1, 10); + RandomRecurence expected(n); + + ll k = Random::integer<ll>(2*n, 100); + vector<ll> s(k); + for (ll j = 0; j < k; j++) s[j] = expected(j); + + auto res = BerlekampMassey(s); + RandomRecurence got(s, res); + + for (ll j = 0; j < 3*k; j++) { + if (got(j) != expected(j)) cerr << "got: " << got(j) << ", expected: " << expected(j) << FAIL; + } + + queries += k; + } + cerr << "tested random queries: " << queries << endl; +} + +constexpr int N = 5'000; +void performance_test() { + timer t; + RandomRecurence f(N); + f(2*N); + t.start(); + auto res = BerlekampMassey(f.cache); + t.stop(); + hash_t hash = 0; + for (ll x : res) hash += x; + 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/bigint.cpp b/test/math/bigint.cpp new file mode 100644 index 0000000..3fc4ac1 --- /dev/null +++ b/test/math/bigint.cpp @@ -0,0 +1,122 @@ +#include "../util.h" +#include <math/bigint.cpp> + +template<ll MOD> +struct modInt { + ll value = 0; + modInt() {} + modInt(const bigint& x) { + stringstream a; + a << x; + string b = a.str(); + for (ll i = b[0] == '-' ? 1 : 0; i < sz(b); i++) { + value *= 10; + value += b[i] - '0'; + value %= MOD; + } + if (b[0] == '-') value = (MOD - value) % MOD; + } + + modInt(ll x) : value(((x % MOD) + MOD) % MOD) {} + + modInt operator+(modInt o) const {return value + o.value;} + modInt operator-(modInt o) const {return value - o.value;} + modInt operator*(modInt o) const {return value * o.value;} + + modInt& operator+=(modInt o) {return *this = *this + o;} + modInt& operator-=(modInt o) {return *this = *this - o;} + modInt& operator*=(modInt o) {return *this = *this * o;} + + ll& operator*() {return value;} + bool operator==(const modInt& o) const {return value == o.value;} + bool operator!=(const modInt& o) const {return value != o.value;} +}; + +constexpr ll MOD = 1'394'633'899; +constexpr ll POOL = 8; + +void stress_test() { + int queries = 0; + for (int tries = 0; tries < 1000; tries++) { + vector<modInt<MOD>> expectedPool(POOL); + vector<bigint> gotPool(POOL); + for (int i = 0; i < POOL; i++) { + ll x = Random::integer<ll>(-1'000'000'000'000'000'000ll, 1'000'000'000'000'000'000ll); + expectedPool[i] = x; + gotPool[i] = x; + if (expectedPool[i] != modInt<MOD>(gotPool[i])) cerr << "error: 0" << FAIL; + } + for (int i = 0; i < 200; i++) { + int a = Random::integer<int>(0, POOL); + int b = Random::integer<int>(0, POOL); + int o = Random::integer<int>(0, 3); + + if (Random::integer<int>(0, 2) == 0) {//x= + auto tmpExpected = expectedPool[a]; + auto tmpGot = gotPool[a]; + + if (o == 0) { + tmpExpected += expectedPool[b]; + tmpGot += gotPool[b]; + } + if (o == 1) { + tmpExpected -= expectedPool[b]; + tmpGot -= gotPool[b]; + } + if (o == 2) { + tmpExpected -= expectedPool[b]; + tmpGot -= gotPool[b]; + } + + if (tmpExpected != modInt<MOD>(tmpGot)) { + cerr << gotPool[a]; + if (o == 0) cerr << "+"; + if (o == 1) cerr << "-"; + if (o == 2) cerr << "*"; + cerr << gotPool[b] << "=" << tmpGot << endl; + cerr << "error: 1" << FAIL; + } + + expectedPool[b] = tmpExpected; + gotPool[b] = tmpGot; + } else {//x + int c = Random::integer<int>(0, POOL); + + modInt<MOD> tmpExpected; + bigint tmpGot; + + if (o == 0) { + tmpExpected = expectedPool[a] + expectedPool[b]; + tmpGot = gotPool[a] + gotPool[b]; + } + if (o == 1) { + tmpExpected = expectedPool[a] - expectedPool[b]; + tmpGot = gotPool[a] - gotPool[b]; + } + if (o == 2) { + tmpExpected = expectedPool[a] * expectedPool[b]; + tmpGot = gotPool[a] * gotPool[b]; + } + + if (tmpExpected != modInt<MOD>(tmpGot)) { + cerr << gotPool[a]; + if (o == 0) cerr << "+"; + if (o == 1) cerr << "-"; + if (o == 2) cerr << "*"; + cerr << gotPool[b] << "=" << tmpGot << endl; + cerr << "error: 2" << FAIL; + } + + expectedPool[c] = tmpExpected; + gotPool[c] = tmpGot; + } + queries++; + } + } + cerr << "tested random queries: " << queries << endl; +} + +int main() { + stress_test(); +} + diff --git a/test/math/binomial0.cpp b/test/math/binomial0.cpp new file mode 100644 index 0000000..00c04d4 --- /dev/null +++ b/test/math/binomial0.cpp @@ -0,0 +1,31 @@ +#include "../util.h" +#include <math/extendedEuclid.cpp> +#include <math/multInv.cpp> +constexpr ll mod = 1'394'633'899; +#include <math/binomial0.cpp> + + +void stress_test() { + vector<ll> last = {1}; + ll queries = 0; + for (ll i = 0; i < 10'000; i++) { + for (ll j = 0; j <= i; j++) { + ll got = calc_binom(i, j); + ll expected = last[j]; + if (got != expected) cerr << "calc_binom(" << i << ", " << j << "), got: " << got << ", expected: " << expected << FAIL; + } + queries += sz(last); + + last.push_back(1); + for (ll j = i; j > 0; j--) { + last[j] = (last[j] + last[j - 1]) % mod; + } + } + cerr << "tested queries: " << queries << endl; +} + +int main() { + precalc(); + stress_test(); +} + diff --git a/test/math/binomial1.cpp b/test/math/binomial1.cpp new file mode 100644 index 0000000..f6fe20b --- /dev/null +++ b/test/math/binomial1.cpp @@ -0,0 +1,27 @@ +#include "../util.h" +#include <math/binomial1.cpp> + + +void stress_test() { + vector<ll> last = {1}; + ll queries = 0; + for (ll i = 0; i <= 61; i++) { + for (ll j = 0; j <= i; j++) { + ll got = calc_binom(i, j); + ll expected = last[j]; + if (got != expected) cerr << "calc_binom(" << i << ", " << j << "), got: " << got << ", expected: " << expected << FAIL; + } + queries += sz(last); + + last.push_back(1); + for (ll j = i; j > 0; j--) { + last[j] = last[j] + last[j - 1]; + } + } + cerr << "tested queries: " << queries << endl; +} + +int main() { + stress_test(); +} + diff --git a/test/math/binomial2.cpp b/test/math/binomial2.cpp new file mode 100644 index 0000000..b55c8af --- /dev/null +++ b/test/math/binomial2.cpp @@ -0,0 +1,29 @@ +#include "../util.h" +#include <math/primeSieve.cpp> +#include <math/binomial2.cpp> + + +void stress_test() { + vector<ll> last = {1}; + ll queries = 0; + for (ll i = 0; i <= 1000; i++) { + for (ll j = 0; j <= i; j++) { + ll got = calc_binom(i, j); + ll expected = last[j]; + if (got != expected) cerr << "calc_binom(" << i << ", " << j << "), got: " << got << ", expected: " << expected << FAIL; + } + queries += sz(last); + + last.push_back(1); + for (ll j = i; j > 0; j--) { + last[j] = (last[j] + last[j - 1]) % mod; + } + } + cerr << "tested queries: " << queries << endl; +} + +int main() { + primeSieve(); + stress_test(); +} + diff --git a/test/math/binomial3.cpp b/test/math/binomial3.cpp new file mode 100644 index 0000000..4a99689 --- /dev/null +++ b/test/math/binomial3.cpp @@ -0,0 +1,31 @@ +#include "../util.h" +#include <math/extendedEuclid.cpp> +#include <math/multInv.cpp> +#include <math/binomial3.cpp> + + +constexpr ll mod = 503; + +void stress_test() { + vector<ll> last = {1}; + ll queries = 0; + for (ll i = 0; i < mod; i++) { + for (ll j = 0; j <= i; j++) { + ll got = calc_binom(i, j, mod); + ll expected = last[j]; + if (got != expected) cerr << "calc_binom(" << i << ", " << j << "), got: " << got << ", expected: " << expected << FAIL; + } + queries += sz(last); + + last.push_back(1); + for (ll j = i; j > 0; j--) { + last[j] = (last[j] + last[j - 1]) % mod; + } + } + cerr << "tested queries: " << queries << endl; +} + +int main() { + stress_test(); +} + diff --git a/test/math/chineseRemainder.cpp b/test/math/chineseRemainder.cpp new file mode 100644 index 0000000..26e71de --- /dev/null +++ b/test/math/chineseRemainder.cpp @@ -0,0 +1,47 @@ +#include "../util.h" +#include <math/extendedEuclid.cpp> +#include <math/chineseRemainder.cpp> + +struct NAIVE { + vector<pair<ll, ll>> added; + void add(ll a, ll m) { + added.emplace_back(a, m); + } + ll sol() const { + ll n = 1; + for (auto [_, x] : added) n = lcm(n, x); + for (ll i = 0; i < n; i++) { + bool ok = true; + for (auto [a, m] : added) { + ok &= (i % m) == a; + } + if (ok) return i; + } + return -1; + } +}; + +void stress_test() { + ll queries = 0; + ll withSol = 0; + for (ll i = 0; i < 100'000; i++) { + CRT crt; + NAIVE naive; + for (ll j = 0; j < 3; j++) { + int m = Random::integer<int>(1, 50); + int a = Random::integer<int>(0, m); + crt.add(a, m); + naive.add(a, m); + } + if (crt.hasSol != (naive.sol() >= 0)) cerr << "error" << FAIL; + if (crt.hasSol && crt.sol != naive.sol()) cerr << "got: " << (ll)crt.sol << ", expected: " << naive.sol() << FAIL; + queries += crt.M; + withSol += crt.hasSol; + } + cerr << "tested queries: " << queries << "(" << withSol << ")" << endl; +} + +int main() { + stress_test(); +} + diff --git a/test/math/cycleDetection.cpp b/test/math/cycleDetection.cpp new file mode 100644 index 0000000..bf57aed --- /dev/null +++ b/test/math/cycleDetection.cpp @@ -0,0 +1,47 @@ +#include "../util.h" +#include <datastructures/pbds.cpp> +#include <math/cycleDetection.cpp> + +pair<ll, ll> naive(ll x0, function<ll(ll)> f) { + map<ll, ll> seen; + ll d = 0; + while (seen.find(x0) == seen.end()) { + seen[x0] = d; + d++; + x0 = f(x0); + } + return {seen[x0], d - seen[x0]}; +} + +void stress_test() { + ll queries = 0; + for (ll i = 0; i < 1000'000; i++) { + int m = Random::integer<int>(1, 100); + int c = Random::integer<int>(0, m); + auto f = [&](ll x){return (x*x + c) % m;}; + int x0 = Random::integer<int>(0, m); + auto got = cycleDetection(x0, f); + auto expected = naive(x0, f); + if (got != expected) cerr << "error: " << got.first << " " << got.second << " " << expected.first << " " << expected.second << FAIL; + queries += got.second; + } + cerr << "tested queries: " << queries << endl; +} + +constexpr ll M = 18'086'183; +void performance_test() { + timer t; + auto f = [&](ll x){return (1337*x + 42) % M;}; + t.start(); + auto [a, b] = cycleDetection(42, f); + t.stop(); + hash_t hash = a + b; + 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/discreteLogarithm.cpp b/test/math/discreteLogarithm.cpp new file mode 100644 index 0000000..0f9eecf --- /dev/null +++ b/test/math/discreteLogarithm.cpp @@ -0,0 +1,64 @@ +#include "../util.h" +#include <math/modPowIterativ.cpp> +#include <math/legendre.cpp> + +ll overwrite = 0; +ll getMemory(ll /**/) {return overwrite - 1;} //dlog code adds one... +#define sqrtl getMemory +#include <math/discreteLogarithm.cpp> +#undef sqrtl + +template<typename F> +void stress_test(F&& f) { + ll work = 0; + for (ll tries = 0; tries < 3'000; tries++) { + ll p = Random::prime<ll>(1'000); + overwrite = f(p); + ll a = Random::integer<ll>(1, p); + vector<bool> naive(p); + for (ll i = 0, j = 1; i < p; i++, j = (j * a) % p) { + naive[j] = true; + } + for (ll b = 0; b < p; b++) { + ll got = dlog(a, b, p); + if (got < -1 || got >= p) cerr << "error: out of range" << FAIL; + if ((got >= 0) != naive[b]) { + cerr << a << " " << b << " " << p << endl; + cerr << got << endl; + cerr << "error" << FAIL; + } + if (got >= 0 && powMod(a, got, p) != b) { + cerr << a << "^" << got << " = " << powMod(a, got, p) << " != " << b << " % " << p << endl; + cerr << "error: wrong" << FAIL; + } + work++; + } + } + cerr << "stress tested: " << work << endl; +} + +constexpr int N = 25; +constexpr ll mod = 1'394'633'899; +void performance_test() { + timer t; + hash_t hash = 0; + overwrite = sqrt(mod); + for (int operations = 0; operations < N; operations++) { + ll a = Random::integer<ll>(1, mod); + ll b = Random::integer<ll>(0, mod); + t.start(); + hash += dlog(a, b, mod); + 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([](ll p){return sqrtl(p);}); + stress_test([](ll p){return min<ll>(10, p - 1);}); + stress_test([](ll p){return min<ll>(p - 1, sqrtl(p) + 100);}); + performance_test(); +} + diff --git a/test/math/discreteNthRoot.cpp b/test/math/discreteNthRoot.cpp new file mode 100644 index 0000000..d595e6d --- /dev/null +++ b/test/math/discreteNthRoot.cpp @@ -0,0 +1,78 @@ +#include "../util.h" +#define ll lll +#include <math/modPowIterativ.cpp> +#undef ll +#include <math/millerRabin.cpp> +#include <math/rho.cpp> + +ll phi(ll pk, ll p, ll /*k*/) {return pk - pk / p;} +ll phi(ll n) { // O(sqrt(n)) + ll res = 1; + for (ll p = 2; p * p <= n; p++) { + if (n % p == 0) { + ll pk = 1; + ll k = 0; + do { + n /= p; + pk *= p; + k++; + } while (n % p == 0); + res *= phi(pk, p, k); + }} + if (n > 1) res *= phi(n, n, 1); + return res; +} + +#include <math/primitiveRoot.cpp> +#include <math/discreteLogarithm.cpp> +#include <math/discreteNthRoot.cpp> + +//x^a=b mod m +ll naiveRoot(ll a, ll b, ll m) { + for (ll i = 0; i < m; i++) { + if (powMod(i, a, m) == b) return i; + } + return -1; +} + +void stress_test() { + int queries = 0; + int found = 0; + for (int tries = 0; tries < 50'000; tries++) { + ll p = Random::prime<ll>(0, 1000); + ll a = Random::integer<ll>(1, p); + ll b = Random::integer<ll>(1, p); + + ll got = root(a, b, p); + ll expected = naiveRoot(a, b, p); + + if (got < -1 || got >= p) cerr << "error: out of range" << FAIL; + if (got >= 0 && powMod(got, a, p) != b) cerr << "error: wrong" << FAIL; + if ((got >= 0) != (expected >= 0)) cerr << "error" << FAIL; + queries++; + if (expected >= 0) found++; + } + cerr << "tested random queries: " << queries << " (" << found << ")" << endl; +} + +constexpr int N = 50; +constexpr ll mod = 1'394'633'899; +void performance_test() { + timer t; + hash_t hash = 0; + for (int i = 0; i < N; i++) { + ll a = Random::integer<ll>(1, mod); + ll b = Random::integer<ll>(1, mod); + t.start(); + hash += root(a, b, mod); + 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/divisors.cpp b/test/math/divisors.cpp new file mode 100644 index 0000000..2402d2a --- /dev/null +++ b/test/math/divisors.cpp @@ -0,0 +1,65 @@ +#include "../util.h" +#define ll lll +#include <math/modPowIterativ.cpp> +#undef ll +#include <math/millerRabin.cpp> + +bool isSquare(ll x) { + ll r = sqrtl(x); + while (r*r > x) r--; + while ((r+1)*(r+1) <= x) r++; + return r*r==x; +} + +#include <math/divisors.cpp> + +ll naive(ll x) { + ll res = 0; + for (ll i = 1; i*i <= x; i++) { + if (x % i == 0) { + res++; + if (i*i != x) res++; + } + } + return res; +} + +void stress_test() { + ll work = 0; + for (ll i = 0; i < 1'000; i++) { + ll x = Random::integer<ll>(1, 1'000'000'000'000); + auto got = countDivisors(x); + auto expected = naive(x); + if (got != expected) cerr << "error: " << x << FAIL; + work += sqrt(x); + } + for (ll i = 0; i < 100'000; i++) { + ll x = Random::integer<ll>(1, 1'000'000); + auto got = countDivisors(x); + auto expected = naive(x); + if (got != expected) cerr << "error: " << x << FAIL; + work += sqrt(x); + } + cerr << "stress tested: " << work << endl; +} + +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); + t.start(); + hash += countDivisors(x); + 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/extendedEuclid.cpp b/test/math/extendedEuclid.cpp new file mode 100644 index 0000000..597f722 --- /dev/null +++ b/test/math/extendedEuclid.cpp @@ -0,0 +1,41 @@ +#include "../util.h" +#include <math/extendedEuclid.cpp> + +void stress_test() { + if (extendedEuclid(0, 0)[0] != 0) cerr << "error: extendedEuclid(0, 0)" << FAIL; + ll queries = 0; + timer t; + for (int i = 0; i < 1'000'000; i++) { + ll a = Random::integer<ll>(0, 1'000'000'000); + ll b = 0; + { + t.start(); + auto [got, x, y] = extendedEuclid(a, b); + t.stop(); + ll expected = std::gcd(a, b); + if (got != expected) cerr << "gcd(" << a << ", " << b << "), got: " << got << ", expected: " << expected << FAIL; + if (abs(x) >= max<ll>(2, abs(b))) cerr << "invalid x" << FAIL; + if (abs(y) >= max<ll>(2, abs(a))) cerr << "invalid y" << FAIL; + if (a*x + b*y != expected) cerr << "invalid x or y" << FAIL; + } + b = Random::integer<ll>(0, 1'000'000'000); + { + t.start(); + auto [got, x, y] = extendedEuclid(a, b); + t.stop(); + ll expected = std::gcd(a, b); + if (got != expected) cerr << "gcd(" << a << ", " << b << "), got: " << got << ", expected: " << expected << FAIL; + if (abs(x) >= max<ll>(2, abs(b))) cerr << "invalid x" << FAIL; + if (abs(y) >= max<ll>(2, abs(a))) cerr << "invalid y" << FAIL; + if (a*x + b*y != expected) cerr << "invalid x or y" << 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/gauss.cpp b/test/math/gauss.cpp new file mode 100644 index 0000000..37bacce --- /dev/null +++ b/test/math/gauss.cpp @@ -0,0 +1,118 @@ +#include "../util.h" +constexpr double EPS = 1e-9; +constexpr int UNIQUE = 1; +constexpr int INCONSISTENT = 2; +constexpr int MULTIPLE = 3; +vector<vector<double>> mat; +#include <math/gauss.cpp> + +vector<vector<double>> inverseMat(const vector<vector<double>>& m) { + int n = sz(m); + mat = m; + for (int i = 0; i < n; i++) { + if (sz(mat[i]) != n) cerr << "error: no square matrix" << FAIL; + 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... + vector<vector<double>> res(m); + for (int i = 0; i < n; i++) { + res[i] = vector<double>(mat[i].begin() + n, mat[i].end()); + for (int j = 0; j < n; j++) { + if (j != i && mat[i][j] != 0) cerr << "error: not full rank?" << FAIL; + if (j == i && mat[i][j] == 0) cerr << "error: not full rank?" << FAIL; + } + } + return res; +} + +vector<vector<double>> mul(const vector<vector<double>>& a, const vector<vector<double>>& b) { + int n = sz(a); + int m = sz(b[0]); + int x = sz(b); + if (sz(a[0]) != sz(b)) cerr << "error: wrong dimensions" << FAIL; + vector<vector<double>> res(n, vector<double>(m)); + for (int i = 0; i < n; i++) { + for (int j = 0; j < m; j++) { + for (int k = 0; k < x; k++) { + res[i][j] += a[i][k] * b[k][j]; + } + } + } + return res; +} + +void test_tiny() { + mat = { + {1, 2, 3, 4}, + {0, 5, 6, 7}, + {0, 0, 8, 9}, + }; + if (gauss(sz(mat)) != UNIQUE) cerr << "error: 1" << FAIL; + + mat = { + {-1, 1, 0, -1}, + { 2, 6, 0, 10}, + { 1, -2, 0, 0}, + }; + if (gauss(sz(mat)) != MULTIPLE) cerr << "error: 2" << FAIL; + + mat = { + {-1, 1, 0, -1}, + { 2, 6, 0, 10}, + { 1, -2, 0, 1}, + }; + if (gauss(sz(mat)) != INCONSISTENT) cerr << "error: 3" << FAIL; +} + +void stress_test_inv() { + ll queries = 0; + for (int tries = 0; tries < 20'000; tries++) { + int n = Random::integer<int>(1, 30); + + vector<vector<double>> m(n); + for (auto& v : m) v = Random::reals<double>(n, 0, 1'000); + // m hopefully has full rank... + + auto inv = inverseMat(m); + + auto prod = mul(m, inv); + + for (int i = 0; i < n; i++) { + for (int j = 0; j < n; j++) { + if (i == j && abs(prod[i][j] - 1) >= EPS) cerr << "error: not inverted " << prod[i][j] << FAIL; + if (i != j && abs(prod[i][j] - 0) >= EPS) cerr << "error: not inverted " << prod[i][j] << FAIL; + } + } + + queries += n; + } + cerr << "tested random queries: " << queries << endl; +} + +constexpr int N = 250; +void performance_test() { + timer t; + + vector<vector<double>> m(N); + for (auto& v : m) v = Random::reals<double>(N, 0, 1'000); + mat = m; + + t.start(); + gauss(N); + t.stop(); + hash_t hash = 0; + for (int i = 0; i < N; i++) { + for (int j = 0; j < N; j++) { + hash += mat[i][j]; + } + } + if (t.time > 500) cerr << "too slow: " << t.time << FAIL; + cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; +} + +int main() { + test_tiny(); + stress_test_inv(); + performance_test(); +} diff --git a/test/math/gcd-lcm.cpp b/test/math/gcd-lcm.cpp new file mode 100644 index 0000000..294095b --- /dev/null +++ b/test/math/gcd-lcm.cpp @@ -0,0 +1,46 @@ +#include "../util.h" +#include <math/gcd-lcm.cpp> + +void stress_test() { + if (::gcd(0, 0) != 0) cerr << "error: gcd(0, 0)" << FAIL; + if (::lcm(0, 0) != 0) cerr << "error: lcm(0, 0)" << FAIL; + ll queries = 0; + timer t; + for (int i = 0; i < 1'000'000; i++) { + ll a = Random::integer<ll>(0, 1'000'000'000); + ll b = 0; + { + ll got = ::gcd(a, b); + ll expected = std::gcd(a, b); + if (got != expected) cerr << "gcd(" << a << ", " << b << "), got: " << got << ", expected: " << expected << FAIL; + } + { + ll got = ::lcm(a, b); + ll expected = std::lcm(a, b); + if (got != expected) cerr << "lcm(" << a << ", " << b << "), got: " << got << ", expected: " << expected << FAIL; + } + b = Random::integer<ll>(0, 1'000'000'000); + { + t.start(); + ll got = ::gcd(a, b); + t.stop(); + ll expected = std::gcd(a, b); + if (got != expected) cerr << "gcd(" << a << ", " << b << "), got: " << got << ", expected: " << expected << FAIL; + } + { + t.start(); + ll got = ::lcm(a, b); + t.stop(); + ll expected = std::lcm(a, b); + if (got != expected) cerr << "lcm(" << a << ", " << b << "), got: " << got << ", expected: " << expected << FAIL; + } + queries++; + } + cerr << "tested random queries: " << queries << endl; + if (t.time > 750) cerr << "too slow: " << t.time << FAIL; + cerr << "tested performance: " << t.time << "ms" << endl; +} + +int main() { + stress_test(); +} diff --git a/test/math/goldenSectionSearch.cpp b/test/math/goldenSectionSearch.cpp new file mode 100644 index 0000000..565a21c --- /dev/null +++ b/test/math/goldenSectionSearch.cpp @@ -0,0 +1,74 @@ +#include "../util.h" +#include <math/goldenSectionSearch.cpp> + +struct RandomFunction { + ld min; + vector<pair<ld, int>> polys; + RandomFunction(ld l, ld r) : min(Random::real<ld>(l, r)) { + do { + polys.emplace_back( + Random::real<ld>(0, 1e9), + 2 * Random::integer<int>(1, 5) + ); + } while(false && Random::integer<int>(4) != 0); + } + + ld operator()(ld x){ + ld res = 0; + for (auto [m, p] : polys) { + res += m * pow(x - min, p); + } + return res; + } + + friend ostream& operator<<(ostream& os, const RandomFunction& f) { + string plus = ""; + for (auto [m, p] : f.polys) { + os << setprecision(15) << plus << m << "*(x-" << f.min << ")**" << p; + plus = "+"; + } + return os; + } +}; + +void stress_test() { + int queries = 0; + for (int i = 0; i < 50'000; i++) { + ld l = Random::real<double>(-200, 200); + ld r = Random::real<double>(-200, 200); + if (l > r) swap(l, r); + + RandomFunction f(l, r); + + ld got = gss(l, r, f); + ld expected = f.min; + if (float_error(got, expected) > 1e-6) { + cerr << f << endl; + cerr << "got: " << got << ", expected: " << expected << FAIL; + } + queries++; + } + cerr << "tested random queries: " << queries << endl; +} + +constexpr int N = 10'000; +void performance_test() { + timer t; + RandomFunction f(-200, 200); + f.polys.resize(1); + + hash_t hash = 0; + for (int i = 0; i < N; i++) { + t.start(); + hash += gss(-200, 200, f); + t.stop(); + } + if (t.time > 1000) 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/inversions.cpp b/test/math/inversions.cpp new file mode 100644 index 0000000..d2a54b7 --- /dev/null +++ b/test/math/inversions.cpp @@ -0,0 +1,43 @@ +#include "../util.h" +#include <datastructures/pbds.cpp> +#include <math/inversions.cpp> + +ll naive(const vector<ll>& v) { + ll res = 0; + for (ll i = 0; i < sz(v); i++) { + for (ll j = 0; j < i; j++) { + if (v[j] > v[i]) res++; + } + } + return res; +} + +void stress_test() { + ll queries = 0; + for (ll i = 0; i < 100'000; i++) { + int n = Random::integer<int>(1, 100); + auto v = Random::integers<ll>(n, -50, 50); + ll got = inversions(v); + ll expected = naive(v); + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + queries += n; + } + cerr << "tested queries: " << queries << endl; +} + +constexpr int N = 200'000; +void performance_test() { + timer t; + auto v = Random::integers<ll>(N, -10'000, 10'000); + t.start(); + hash_t hash = inversions(v); + 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/inversionsMerge.cpp b/test/math/inversionsMerge.cpp new file mode 100644 index 0000000..85ab0d2 --- /dev/null +++ b/test/math/inversionsMerge.cpp @@ -0,0 +1,46 @@ +#include "../util.h" +#include <math/inversionsMerge.cpp> + +ll naive(const vector<ll>& v) { + ll res = 0; + for (ll i = 0; i < sz(v); i++) { + for (ll j = 0; j < i; j++) { + if (v[j] > v[i]) res++; + } + } + return res; +} + +void stress_test() { + ll queries = 0; + 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 ): + shuffle(all(v), Random::rng); + ll expected = naive(v); + ll got = mergeSort(v); + if (got != expected) { + cerr << "got: " << got << ", expected: " << expected << FAIL; + } + queries += n; + } + cerr << "tested queries: " << queries << endl; +} + +constexpr int N = 2'000'000; //10 times faster +void performance_test() { + timer t; + auto v = Random::integers<ll>(N, -10'000, 10'000); + t.start(); + hash_t hash = mergeSort(v); + 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/kthperm.cpp b/test/math/kthperm.cpp new file mode 100644 index 0000000..16691b9 --- /dev/null +++ b/test/math/kthperm.cpp @@ -0,0 +1,38 @@ +#include "../util.h" +#include <datastructures/pbds.cpp> +#include <math/kthperm.cpp> + +void stress_test() { + ll queries = 0; + for (ll i = 0; i < 10'000; i++) { + int n = Random::integer<int>(1, 100); + vector<ll> expected(n); + iota(all(expected), 0); + ll k = 0; + do { + auto got = kthperm(n, k); + if (got != expected) cerr << "error" << FAIL; + k++; + } while (k < 100 && next_permutation(all(expected))); + queries += n; + } + cerr << "tested queries: " << queries << endl; +} + +constexpr int N = 500'000; +void performance_test() { + timer t; + t.start(); + auto got = kthperm(N, 4'168'751'907'498'170ll); + t.stop(); + hash_t hash = 0; + for (ll i = 0; i < N; i++) hash += i * got[i]; + 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/kthperm_permIndex.cpp b/test/math/kthperm_permIndex.cpp new file mode 100644 index 0000000..d84524e --- /dev/null +++ b/test/math/kthperm_permIndex.cpp @@ -0,0 +1,21 @@ +#include "../util.h" +#include <datastructures/pbds.cpp> +#include <math/kthperm.cpp> +#include <math/permIndex.cpp> + +void stress_test() { + ll queries = 0; + for (ll i = 0; i < 10'000; i++) { + ll n = Random::integer<ll>(20, 1000); + ll expected = Random::integer<ll>(0, 1'000'000'000'000'000'000); + ll got = permIndex(kthperm(n, expected)); + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + queries += n; + } + cerr << "tested queries: " << queries << endl; +} + +int main() { + stress_test(); +} + diff --git a/test/math/legendre.cpp b/test/math/legendre.cpp new file mode 100644 index 0000000..f210b57 --- /dev/null +++ b/test/math/legendre.cpp @@ -0,0 +1,43 @@ +#include "../util.h" +#define ll lll +#include <math/modPowIterativ.cpp> +#undef ll +#include <math/legendre.cpp> + +void stress_test() { + ll work = 0; + for (ll i = 0; i < 5'000; i++) { + ll p = Random::prime<ll>(5'000); + vector<bool> isSquare(p); + for (ll j = 1; j < p; j++) isSquare[(j*j) % p] = true; + for (ll j = 0; j < p; j++) { + auto got = legendre(j, p); + auto expected = j == 0 ? 0 : (isSquare[j] ? 1 : -1); + if (got != expected) cerr << "error: " << j << " " << p << FAIL; + } + work += p; + } + cerr << "stress tested: " << work << endl; +} + +constexpr int N = 1'000'000; +constexpr ll mod = 1'394'633'899; +void performance_test() { + timer t; + hash_t hash = 0; + for (int operations = 0; operations < N; operations++) { + ll j = Random::integer<ll>(mod); + t.start(); + hash += legendre(j, mod); + 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/lgsFp.cpp b/test/math/lgsFp.cpp new file mode 100644 index 0000000..08f8f84 --- /dev/null +++ b/test/math/lgsFp.cpp @@ -0,0 +1,118 @@ +#include "../util.h" +#include <math/shortModInv.cpp> +vector<vector<ll>> mat; +#include <math/lgsFp.cpp> + +constexpr ll mod = 1'000'000'007; + +vector<vector<ll>> inverseMat(const vector<vector<ll>>& m) { + int n = sz(m); + mat = m; + for (int i = 0; i < n; i++) { + if (sz(mat[i]) != n) cerr << "error: no square matrix" << FAIL; + mat[i].resize(2*n); + mat[i][n+i] = 1; + } + gauss(n, mod); + vector<vector<ll>> res(m); + for (int i = 0; i < n; i++) { + res[i] = vector<ll>(mat[i].begin() + n, mat[i].end()); + for (int j = 0; j < n; j++) { + if (j != i && mat[i][j] != 0) cerr << "error: not full rank?" << FAIL; + if (j == i && mat[i][j] != 1) cerr << "error: not full rank?" << FAIL; + } + } + return res; +} + +vector<vector<ll>> mul(const vector<vector<ll>>& a, const vector<vector<ll>>& b) { + int n = sz(a); + int m = sz(b[0]); + int x = sz(b); + if (sz(a[0]) != sz(b)) cerr << "error: wrong dimensions" << FAIL; + vector<vector<ll>> res(n, vector<ll>(m)); + for (int i = 0; i < n; i++) { + for (int j = 0; j < m; j++) { + for (int k = 0; k < x; k++) { + res[i][j] += a[i][k] * b[k][j]; + res[i][j] %= mod; + } + } + } + return res; +} + +//this should just not crash... +void test_square() { + ll queries = 0; + hash_t hash = 0; + for (int tries = 0; tries < 1'000; tries++) { + int n = Random::integer<int>(1, 30); + + vector<vector<ll>> m(n); + for (auto& v : m) v = Random::integers<ll>(n, 0, mod); + mat = m; + gauss(n, mod); + + for (int i = 0; i < n; i++) { + for (int j = 0; j < n; j++) { + hash += mat[i][j]; + } + } + + queries += n; + } + cerr << "tested sqaures: " << queries << " (hash: " << hash << ")" << endl;; +} + +void stress_test_inv() { + ll queries = 0; + for (int tries = 0; tries < 20'000; tries++) { + int n = Random::integer<int>(1, 30); + + vector<vector<ll>> m(n); + for (auto& v : m) v = Random::integers<ll>(n, 0, mod); + // m hopefully has full rank... + + auto inv = inverseMat(m); + + auto prod = mul(m, inv); + + for (int i = 0; i < n; i++) { + for (int j = 0; j < n; j++) { + if (i == j && prod[i][j] != 1) cerr << "error: not inverted" << FAIL; + if (i != j && prod[i][j] != 0) cerr << "error: not inverted" << FAIL; + } + } + + queries += n; + } + cerr << "tested random queries: " << queries << endl; +} + +constexpr int N = 250; +void performance_test() { + timer t; + + vector<vector<ll>> m(N); + for (auto& v : m) v = Random::integers<ll>(N, 0, mod); + mat = m; + + t.start(); + gauss(N, mod); + t.stop(); + hash_t hash = 0; + for (int i = 0; i < N; i++) { + for (int j = 0; j < N; j++) { + hash += mat[i][j]; + } + } + if (t.time > 500) cerr << "too slow: " << t.time << FAIL; + cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; +} + +int main() { + test_square(); + stress_test_inv(); + performance_test(); +} diff --git a/test/math/linearCongruence.cpp b/test/math/linearCongruence.cpp new file mode 100644 index 0000000..ba8eeac --- /dev/null +++ b/test/math/linearCongruence.cpp @@ -0,0 +1,53 @@ +#include "../util.h" +#include <math/extendedEuclid.cpp> +#include <math/multInv.cpp> +#include <math/linearCongruence.cpp> + +ll naive(ll a, ll b, ll m) { + for (ll x = 0; x < m; x++) { + if ((a * x) % m == b) return x; + } + return -1; +} + +void stress_test() { + ll work = 0; + ll positive = 0; + for (ll tries = 0; tries < 500'000; tries++) { + ll m = Random::integer<ll>(0, 1'000); + ll a = Random::integer<ll>(0, m); + ll b = Random::integer<ll>(0, m); + + ll got = solveLinearCongruence(a, b, m); + ll expected = naive(a, b, m); + + if (got != expected) cerr << "got: " << got << ", expected: " << expected << endl; + work++; + if (got >= 0) positive++; + } + cerr << "stress tested: " << work << " (" << positive << ")" << endl; +} + +constexpr int N = 500'000; +void performance_test() { + timer t; + hash_t hash = 0; + for (int operations = 0; operations < N; operations++) { + ll m = Random::integer<ll>(0, 1'0000'000'000); + ll a = Random::integer<ll>(0, m); + ll b = Random::integer<ll>(0, m); + + t.start(); + hash += solveLinearCongruence(a, b, m); + 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/linearRecurence.cpp b/test/math/linearRecurence.cpp new file mode 100644 index 0000000..a5290e5 --- /dev/null +++ b/test/math/linearRecurence.cpp @@ -0,0 +1,54 @@ +#include "../util.h" +#include <math/linearRecurence.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/linearSieve.cpp b/test/math/linearSieve.cpp new file mode 100644 index 0000000..8ea822b --- /dev/null +++ b/test/math/linearSieve.cpp @@ -0,0 +1,71 @@ +#include "../util.h" +namespace expected { +#include <math/primeSieve.cpp> +} +#pragma GCC diagnostic ignored "-Wunused-parameter" +#include <math/linearSieve.cpp> + +void stress_test() { + expected::primeSieve(); + expected::primes.resize(primes.size()); + if (expected::primes != primes) cerr << "error: primes" << FAIL; + int queries = 0; + for (int i = 1; i < 1'000'000; i++) { + auto got = sieved[i]; + auto expected = naive(i); + if (got != expected) cerr << i << ", got: " << got << ", expected: " << expected << FAIL; + queries++; + } + for (int i = 0; i < 1'000'000; i++) { + ll x = Random::integer<ll>(2, N); + auto got = sieved[x]; + auto expected = naive(x); + if (got != expected) cerr << x << ", got: " << got << ", expected: " << expected << FAIL; + queries++; + } + cerr << "tested queries: " << queries << endl; +} + +void test_tiny() { + if (mu( 3, 3, 1) != -1) cerr << "error: 1" << FAIL; + if (mu( 9, 3, 2) != 0) cerr << "error: 2" << FAIL; + if (mu(27, 3, 3) != 0) cerr << "error: 3" << FAIL; + + if (phi( 3, 3, 1) != 2) cerr << "error: 4" << FAIL; + if (phi( 9, 3, 2) != 6) cerr << "error: 5" << FAIL; + if (phi(27, 3, 3) != 18) cerr << "error: 6" << FAIL; + + if (div( 3, 3, 1) != 2) cerr << "error: 7" << FAIL; + if (div( 9, 3, 2) != 3) cerr << "error: 8" << FAIL; + if (div(27, 3, 3) != 4) cerr << "error: 9" << FAIL; + + if (divSum( 3, 3, 1) != 4) cerr << "error: 10" << FAIL; + if (divSum( 9, 3, 2) != 13) cerr << "error: 11" << FAIL; + if (divSum(27, 3, 3) != 40) cerr << "error: 12" << FAIL; + + if (square( 3, 3, 1) != 1) cerr << "error: 13" << FAIL; + if (square( 9, 3, 2) != 9) cerr << "error: 14" << FAIL; + if (square(27, 3, 3) != 9) cerr << "error: 15" << FAIL; + + if (squareFree( 3, 3, 1) != 3) cerr << "error: 13" << FAIL; + if (squareFree( 9, 3, 2) != 3) cerr << "error: 14" << FAIL; + if (squareFree(27, 3, 3) != 3) cerr << "error: 15" << FAIL; + cerr << "tested tiny" << endl; +} + +void performance_test() { + timer t; + t.start(); + sieve(); + hash_t hash = sz(primes); + t.stop(); + if (t.time > 500) cerr << "too slow: " << t.time << FAIL; + cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; +} + +int main() { + performance_test(); + stress_test(); + test_tiny(); +} + diff --git a/test/math/longestIncreasingSubsequence.cpp b/test/math/longestIncreasingSubsequence.cpp new file mode 100644 index 0000000..407dafe --- /dev/null +++ b/test/math/longestIncreasingSubsequence.cpp @@ -0,0 +1,76 @@ +#include "../util.h" +constexpr ll INF = LL::INF; +#include <math/longestIncreasingSubsequence.cpp> +#define lis unstrictLis +#define lower_bound upper_bound +#include <math/longestIncreasingSubsequence.cpp> +#undef lower_bound +#undef lis + +template<bool STRICT> +bool isLis(const vector<ll>& a, const vector<int>& lis) { + for (int i = 1; i < sz(lis); i++) { + if (lis[i-1] >= lis[i]) return false; + if (a[lis[i-1]] > a[lis[i]]) return false; + if (STRICT && a[lis[i-1]] == a[lis[i]]) return false; + } + return true; +} + +template<bool STRICT> +vector<int> naive(const vector<ll>& a) { + vector<int> res; + for (ll i = 1; i < (1ll << sz(a)); i++) { + vector<int> tmp; + for (ll j = 0; j < sz(a); j++) { + if (((i >> j) & 1) != 0) tmp.push_back(j); + } + if (sz(tmp) >= sz(res) && isLis<STRICT>(a, tmp)) res = tmp; + } + return res; +} + +void stress_test() { + ll queries = 0; + for (ll i = 0; i < 10'000; i++) { + int n = Random::integer<int>(1, 12); + auto a = Random::integers<ll>(n, -10, 10); + auto expected = naive<true>(a); + auto got = lis(a); + if (got != expected) cerr << "error: strict" << FAIL; + queries += n; + } + for (ll i = 0; i < 10'000; i++) { + int n = Random::integer<int>(1, 12); + auto a = Random::integers<ll>(n, -10, 10); + auto expected = naive<false>(a); + auto got = unstrictLis(a); + if (got != expected) cerr << "error: not strict" << FAIL; + queries += n; + } + cerr << "tested random queries: " << queries << endl; +} + +constexpr int N = 1'000'000; +void performance_test() { + timer t; + auto a = Random::integers<ll>(N, -10'000, 10'000); + auto b = Random::integers<ll>(N, -10'000, 10'000); + sort(all(b)); + auto c = Random::integers<ll>(N, -10'000, 10'000); + sort(all(c)); + reverse(all(c)); + hash_t hash = 0; + t.start(); + hash += lis(a).size(); + hash += lis(b).size(); + hash += lis(c).size(); + 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/matrixPower.cpp b/test/math/matrixPower.cpp new file mode 100644 index 0000000..4dfb0a8 --- /dev/null +++ b/test/math/matrixPower.cpp @@ -0,0 +1,116 @@ +#include "../util.h" + +constexpr ll mod = 1'394'633'899; + +struct mat { + vector<vector<ll>> m; + mat(int dim = 0, int diag = 1) : m(dim, vector<ll>(dim)) { + for (int i = 0; i < dim; i++) m[i][i] = diag; + } + mat(const vector<ll> c) : m(sz(c), vector<ll>(sz(c))) { + m[0] = c; + for (ll i = 1; i < sz(c); i++) { + m[i][i-1] = 1; + } + } + + mat operator*(const mat& o) const { + int dim = sz(m); + mat res(dim, 0); + for (int i = 0; i < dim; i++) { + for (int j = 0; j < dim; j++) { + for (int k = 0; k < dim; k++) { + res.m[i][j] += m[i][k] * o.m[k][j]; + res.m[i][j] %= mod; + } + } + } + return res; + } + + vector<ll> operator*(const vector<ll>& o) const { + int dim = sz(m); + vector<ll> res(dim); + for (int i = 0; i < dim; i++) { + for (int j = 0; j < dim; j++) { + res[i] += m[i][j] * o[j]; + res[i] %= mod; + } + } + return res; + } +}; + +#include <math/matrixPower.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); + precalc(mat(f.c)); + auto tmp = f.f; + reverse(all(tmp)); + + for (int j = 0; j < 100; j++) { + ll k = Random::integer<ll>(0, 1000); + + vector<ll> got = calc(k, tmp); + vector<ll> expected(sz(f.f)); + for (ll l = 0; l < n; l++) expected[n - 1 - l] = f(k + l); + + if (got != expected) cerr << "error" << FAIL; + queries++; + } + } + cerr << "tested random queries: " << queries << endl; +} + +constexpr int N = 100; +constexpr int M = 500; +void performance_test() { + timer t; + RandomRecurence f(N); + auto tmp = f.f; + reverse(all(tmp)); + + t.start(); + precalc(mat(f.c)); + t.stop(); + if (t.time > 500) cerr << "too slow precalc: " << t.time << FAIL; + cerr << "tested performance: " << t.time << "ms" << endl; + + t.reset(); + hash_t hash = 0; + for (int i = 0; i < M; i++) { + ll k = Random::integer<ll>(1e17,1e18); + t.start(); + hash += calc(k, tmp).back(); + 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/millerRabin.base32.cpp b/test/math/millerRabin.base32.cpp new file mode 100644 index 0000000..742d353 --- /dev/null +++ b/test/math/millerRabin.base32.cpp @@ -0,0 +1,137 @@ +#include "../util.h" +#define ll lll +#include <math/modPowIterativ.cpp> +#undef ll + +//this is hacky... +#define bool }\ +constexpr auto bases64 = c20::to_array(ignore::bases32);\ +bool +namespace ignore { +#include <math/millerRabin.cpp> +#undef bool + +bool naive(ll x) { + for (ll i = 2; i*i <= x; i++) { + if (x % i == 0) return false; + } + return x > 1; +} + +ll mul(const map<ll, int>& facts) { + ll res = 1; + for (auto [p, c] : facts) { + for (int i = 0; i < c; i++) res *= p; + } + if (abs(res) > (1ll << 62)) cerr << "invalid number: " << res << FAIL; + return res; +} + +void extra_tests() { + vector<map<ll, int>> test = { + {{-1, 1}, {1, 1}}, + {{-2, 1}, {1, 1}}, + {{-7, 1}, {1, 1}}, + {{-19812365821, 1}, {1, 1}}, + {}, // 1 + {{2, 1}}, + {{3, 1}}, + {{2, 2}}, + {{5, 1}}, + {{2, 1}, {3, 1}}, + {{2, 2}, {3, 1}}, + {{2, 1}, {3, 2}}, + {{2, 2}, {3, 2}}, + {{2, 62}}, + {{2, 18}, {5, 18}}, + {{352523, 1}, {352817, 1}}, + {{41, 1}, {71, 1}, {421, 1}, {811, 1}}, + {{11, 1}, {17, 1}, {31, 1}, {61, 1}, {73, 1}, {66361, 1}}, + {{500000003, 1}, {1999999973, 1}}, + {{65537, 2}}, + {{999665081, 1}, {999716071, 1}}, + {{550177, 1}, {1100353, 1}, {1650529, 1}}, + {{459397, 1}, {918793, 1}, {1378189, 1}}, + {{37, 1}, {109, 1}}, + {{31, 1}, {151, 1}}, + {{239, 1}, {1429, 1}}, + {{89, 1}, {1093, 1}}, + {{2, 3}, {15800133918749317, 1}}, + {{12251, 1}, {85751, 1}}, + {{3, 1}, {5, 3}, {131, 1}, {6855593, 1}}, + {{5, 1}, {1927962474784631, 1}}, + {{197279, 1}, {1775503, 1}}, + {{3716371, 1}, {14865481, 1}}, + {{3, 1}, {5, 1}, {3075593, 1}, {3075593, 1}}, + {{4880401, 1}, {9760801, 1}}, + {{2822159, 1}, {11288633, 1}}, + {{3290341, 1}, {6580681, 1}}, + {{611557, 1}, {1834669, 1}}, + {{9227, 1}, {894923, 1}, {968731, 1}}, + {{3, 4}, {13, 1}, {62633, 2}}, + {{2, 2}, {3, 1}, {5, 1}, {167, 2}, {299197, 2}}, + {{332721269, 1}, {560937673, 1}}, + {{30702523, 1}, {122810089, 1}}, + {{24786439, 1}, {123932191, 1}}, + {{382500329, 1}, {1530001313, 1}}, + {{2, 4}, {5, 4}, {13, 1}, {30839, 2}}, + {{3, 1}, {385417, 1}, {7985344259, 1}}, + {{2, 4}, {3, 1}, {5, 1}, {7, 2}, {61, 1}, {179, 2}, {1381, 2}}, + {{627838711, 1}, {1212379867, 1}}, + {{3, 5}, {5, 3}, {41, 2}, {157321, 2}}, + {{5, 2}, {13, 1}}, + {{3, 1}, {5, 5}}, + {{2, 1}, {73, 1}, {193, 1}}, + {{5, 2}, {13, 1}, {19, 1}, {73, 1}}, + {{2, 3}, {3, 1}, {407521, 1}}, + {{2, 1}, {3, 1}, {299210837, 1}}, + {{2, 8}, {3, 4}, {5, 2}, {7, 2}, {11, 1}, {13, 1}, {17, 1}, {19, 1}, {23, 1}, {29, 1}, {3137, 1}}, + }; + + timer t; + for (auto factors : test) { + ll x = mul(factors); + if (x >= 1ll << 32) continue; + t.start(); + auto got = isPrime(x); + t.stop(); + bool expected = sz(factors) == 1 && factors.begin()->second == 1; + if (got != expected) cerr << "error: " << x << FAIL; + } + if (t.time > 10) cerr << "too slow" << FAIL; + cerr << "stress tested: " << t.time << "ms" << endl; +} + +void stress_test() { + ll work = 0; + for (ll i = 0; i < 10'000; i++) { + ll x = Random::integer<ll>(1, 1ll << 32); + auto got = isPrime(x); + auto expected = naive(x); + if (got != expected) cerr << "error: " << x << FAIL; + work += sqrt(x); + } + cerr << "stress tested: " << work << endl; +} + +constexpr int N = 200'000; +void performance_test() { + timer t; + hash_t hash = 0; + for (int operations = 0; operations < N; operations++) { + ll x = Random::integer<ll>(1ll << 31, 1ll << 32); + t.start(); + hash += isPrime(x); + t.stop(); + } + if (t.time > 500) cerr << "too slow: " << t.time << FAIL; + cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; +} + + +int main() { + extra_tests(); + stress_test(); + performance_test(); +} + diff --git a/test/math/millerRabin.cpp b/test/math/millerRabin.cpp new file mode 100644 index 0000000..fd98586 --- /dev/null +++ b/test/math/millerRabin.cpp @@ -0,0 +1,129 @@ +#include "../util.h" +#define ll lll +#include <math/modPowIterativ.cpp> +#undef ll +#include <math/millerRabin.cpp> + +bool naive(ll x) { + for (ll i = 2; i*i <= x; i++) { + if (x % i == 0) return false; + } + return x > 1; +} + +ll mul(const map<ll, int>& facts) { + ll res = 1; + for (auto [p, c] : facts) { + for (int i = 0; i < c; i++) res *= p; + } + if (abs(res) > (1ll << 62)) cerr << "invalid number: " << res << FAIL; + return res; +} + +void extra_tests() { + vector<map<ll, int>> test = { + {{-1, 1}, {1, 1}}, + {{-2, 1}, {1, 1}}, + {{-7, 1}, {1, 1}}, + {{-19812365821, 1}, {1, 1}}, + {}, // 1 + {{2, 1}}, + {{3, 1}}, + {{2, 2}}, + {{5, 1}}, + {{2, 1}, {3, 1}}, + {{2, 2}, {3, 1}}, + {{2, 1}, {3, 2}}, + {{2, 2}, {3, 2}}, + {{2, 62}}, + {{2, 18}, {5, 18}}, + {{352523, 1}, {352817, 1}}, + {{41, 1}, {71, 1}, {421, 1}, {811, 1}}, + {{11, 1}, {17, 1}, {31, 1}, {61, 1}, {73, 1}, {66361, 1}}, + {{500000003, 1}, {1999999973, 1}}, + {{65537, 2}}, + {{999665081, 1}, {999716071, 1}}, + {{550177, 1}, {1100353, 1}, {1650529, 1}}, + {{459397, 1}, {918793, 1}, {1378189, 1}}, + {{37, 1}, {109, 1}}, + {{31, 1}, {151, 1}}, + {{239, 1}, {1429, 1}}, + {{89, 1}, {1093, 1}}, + {{2, 3}, {15800133918749317, 1}}, + {{12251, 1}, {85751, 1}}, + {{3, 1}, {5, 3}, {131, 1}, {6855593, 1}}, + {{5, 1}, {1927962474784631, 1}}, + {{197279, 1}, {1775503, 1}}, + {{3716371, 1}, {14865481, 1}}, + {{3, 1}, {5, 1}, {3075593, 1}, {3075593, 1}}, + {{4880401, 1}, {9760801, 1}}, + {{2822159, 1}, {11288633, 1}}, + {{3290341, 1}, {6580681, 1}}, + {{611557, 1}, {1834669, 1}}, + {{9227, 1}, {894923, 1}, {968731, 1}}, + {{3, 4}, {13, 1}, {62633, 2}}, + {{2, 2}, {3, 1}, {5, 1}, {167, 2}, {299197, 2}}, + {{332721269, 1}, {560937673, 1}}, + {{30702523, 1}, {122810089, 1}}, + {{24786439, 1}, {123932191, 1}}, + {{382500329, 1}, {1530001313, 1}}, + {{2, 4}, {5, 4}, {13, 1}, {30839, 2}}, + {{3, 1}, {385417, 1}, {7985344259, 1}}, + {{2, 4}, {3, 1}, {5, 1}, {7, 2}, {61, 1}, {179, 2}, {1381, 2}}, + {{627838711, 1}, {1212379867, 1}}, + {{3, 5}, {5, 3}, {41, 2}, {157321, 2}}, + {{5, 2}, {13, 1}}, + {{3, 1}, {5, 5}}, + {{2, 1}, {73, 1}, {193, 1}}, + {{5, 2}, {13, 1}, {19, 1}, {73, 1}}, + {{2, 3}, {3, 1}, {407521, 1}}, + {{2, 1}, {3, 1}, {299210837, 1}}, + {{2, 8}, {3, 4}, {5, 2}, {7, 2}, {11, 1}, {13, 1}, {17, 1}, {19, 1}, {23, 1}, {29, 1}, {3137, 1}}, + }; + + timer t; + for (auto factors : test) { + ll x = mul(factors); + t.start(); + auto got = isPrime(x); + t.stop(); + bool expected = sz(factors) == 1 && factors.begin()->second == 1; + if (got != expected) cerr << "error: " << x << FAIL; + } + if (t.time > 10) cerr << "too slow" << FAIL; + cerr << "stress tested: " << t.time << "ms" << endl; +} + +void stress_test() { + ll work = 0; + for (ll i = 0; i < 10'000; i++) { + ll x = Random::integer<ll>(1, 1'000'000'000'000); + auto got = isPrime(x); + auto expected = naive(x); + if (got != expected) cerr << "error: " << x << FAIL; + work += sqrt(x); + } + cerr << "stress tested: " << work << endl; +} + +constexpr int N = 200'000; +void performance_test() { + timer t; + hash_t hash = 0; + for (int operations = 0; operations < N; operations++) { + ll x = Random::integer<ll>(1e18 / 2, 1e18); + t.start(); + hash += isPrime(x); + t.stop(); + } + if (t.time > 500) cerr << "too slow: " << t.time << FAIL; + cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; +} + + +int main() { + extra_tests(); + stress_test(); + performance_test(); +} + diff --git a/test/math/modExp.cpp b/test/math/modExp.cpp new file mode 100644 index 0000000..ebb38eb --- /dev/null +++ b/test/math/modExp.cpp @@ -0,0 +1,42 @@ +#include "../util.h" +#include <math/modExp.cpp> + +void stress_test() { + ll queries = 0; + for (ll i = 0; i < 10'000; i++) { + int a = Random::integer<int>(1, 100); + int n = Random::integer<int>(2, 100); + ll expected = 1; + ll k = 0; + do { + auto got = powMod(a, k, n); + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + k++; + expected = (expected * a) % n; + } while (k < 100); + queries += n; + } + 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 a = Random::integer<ll>(0, 1'000'000'000); + ll b = Random::integer<ll>(0, 1'000'000'000); + ll n = Random::integer<ll>(2, 1'000'000'000); + t.start(); + hash += powMod(a, b, n); + 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/modMulIterativ.cpp b/test/math/modMulIterativ.cpp new file mode 100644 index 0000000..4f794c5 --- /dev/null +++ b/test/math/modMulIterativ.cpp @@ -0,0 +1,57 @@ +#include "../util.h" +#include <math/modMulIterativ.cpp> + +void stress_test() { + ll queries = 0; + for (ll i = 0; i < 10'000; i++) { + int a = Random::integer<int>(1, 100); + int n = Random::integer<int>(2, 100); + ll expected = 0; + ll k = 0; + do { + auto got = mulMod(a, k, n); + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + k++; + expected = (expected + a) % n; + } while (k < 100); + queries += n; + } + cerr << "tested queries: " << queries << endl; +} + +void stress_test_large() { + ll queries = 0; + for (ll i = 0; i < 1000'000; i++) { + ll a = Random::integer<ll>(0, 1'000'000'000'000'000'000); + ll b = Random::integer<ll>(0, 1'000'000'000'000'000'000); + ll n = Random::integer<ll>(2, 1'000'000'000'000'000'000); + ll expected = (lll)a * b % n; + auto got = mulMod(a, b, n); + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + queries += n; + } + cerr << "tested queries: " << queries << endl; +} + +constexpr int N = 500'000; +void performance_test() { + timer t; + hash_t hash = 0; + for (int operations = 0; operations < N; operations++) { + ll a = Random::integer<ll>(0, 1'000'000'000'000'000'000); + ll b = Random::integer<ll>(0, 1'000'000'000'000'000'000); + ll n = Random::integer<ll>(2, 1'000'000'000'000'000'000); + t.start(); + hash += mulMod(a, b, n); + 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(); + stress_test_large(); + performance_test(); +} + diff --git a/test/math/modPowIterativ.cpp b/test/math/modPowIterativ.cpp new file mode 100644 index 0000000..2cf0eb4 --- /dev/null +++ b/test/math/modPowIterativ.cpp @@ -0,0 +1,42 @@ +#include "../util.h" +#include <math/modPowIterativ.cpp> + +void stress_test() { + ll queries = 0; + for (ll i = 0; i < 10'000; i++) { + int a = Random::integer<int>(1, 100); + int n = Random::integer<int>(2, 100); + ll expected = 1; + ll k = 0; + do { + auto got = powMod(a, k, n); + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + k++; + expected = (expected * a) % n; + } while (k < 100); + queries += n; + } + 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 a = Random::integer<ll>(0, 1'000'000'000); + ll b = Random::integer<ll>(0, 1'000'000'000); + ll n = Random::integer<ll>(2, 1'000'000'000); + t.start(); + hash += powMod(a, b, n); + 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/multInv.cpp b/test/math/multInv.cpp new file mode 100644 index 0000000..93763c5 --- /dev/null +++ b/test/math/multInv.cpp @@ -0,0 +1,40 @@ +#include "../util.h" +#include <math/extendedEuclid.cpp> +#include <math/multInv.cpp> + +void stress_test() { + ll queries = 0; + for (int i = 0; i < 10'000'000; i++) { + ll n = Random::integer<ll>(2, 1'000'000'000); + ll x = 0; + do { + x = Random::integer<ll>(0, n); + } while (gcd(x, n) != 1); + ll y = multInv(x, n); + ll got = (x*y) % n; + if (got != 1) cerr << "got: " << got << ", expected: 1" << 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 a = Random::integer<ll>(0, 1'000'000'000); + ll b = Random::integer<ll>(2, 1'000'000'000); + t.start(); + hash += multInv(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/permIndex.cpp b/test/math/permIndex.cpp new file mode 100644 index 0000000..61d34c8 --- /dev/null +++ b/test/math/permIndex.cpp @@ -0,0 +1,39 @@ +#include "../util.h" +#include <datastructures/pbds.cpp> +#include <math/permIndex.cpp> + +void stress_test() { + ll queries = 0; + for (ll i = 0; i < 10'000; i++) { + int n = Random::integer<int>(1, 100); + vector<ll> cur(n); + iota(all(cur), 0); + ll expected = 0; + do { + auto got = permIndex(cur); + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + expected++; + } while (expected < 100 && next_permutation(all(cur))); + queries += n; + } + cerr << "tested queries: " << queries << endl; +} + +constexpr int N = 500'000; +void performance_test() { + timer t; + vector<ll> cur(N); + iota(all(cur), 0); + reverse(cur.end() - 10, cur.end()); + t.start(); + auto hash = permIndex(cur); + 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/piLegendre.cpp b/test/math/piLegendre.cpp new file mode 100644 index 0000000..c3513bf --- /dev/null +++ b/test/math/piLegendre.cpp @@ -0,0 +1,40 @@ +#include "../util.h" +#include <math/primeSieve.cpp> +namespace legendre { + #include <math/piLegendre.cpp> +} +namespace lehmer { + #include <math/piLehmer.cpp> +} + +void stress_test() { + int queries = 0; + for (int i = 0; i < 1'000; i++) { + ll x = Random::integer<ll>(0, 1'000'000'000); + auto got = legendre::pi(x); + auto expected = lehmer::pi(x); + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + queries++; + } + cerr << "tested random queries: " << queries << endl; +} + +void performance_test() { + timer t; + hash_t hash = 0; + for (int i = 0; i < 1; i++) { + ll x = Random::integer<ll>(0, 1000'000'000'000); + t.start(); + hash += legendre::pi(x); + t.stop(); + } + if (t.time > 1500) cerr << "too slow: " << t.time << FAIL; + cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; +} + +int main() { + lehmer::init(); + performance_test(); + stress_test(); +} + diff --git a/test/math/piLehmer.cpp b/test/math/piLehmer.cpp new file mode 100644 index 0000000..d84466f --- /dev/null +++ b/test/math/piLehmer.cpp @@ -0,0 +1,42 @@ +#include "../util.h" +#include <math/primeSieve.cpp> +namespace legendre { + #include <math/piLegendre.cpp> +} +namespace lehmer { + #include <math/piLehmer.cpp> +} + +void stress_test() { + int queries = 0; + for (int i = 0; i < 1'000; i++) { + ll x = Random::integer<ll>(0, 1'000'000'000); + auto got = lehmer::pi(x); + auto expected = legendre::pi(x); + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + queries++; + } + cerr << "tested random queries: " << queries << endl; +} + +void performance_test() { + timer t; + hash_t hash = 0; + t.start(); + lehmer::init(); + t.stop(); + for (int i = 0; i < 1; i++) { + ll x = Random::integer<ll>(0, 1000'000'000'000); + t.start(); + hash += lehmer::pi(x); + t.stop(); + } + if (t.time > 1500) cerr << "too slow: " << t.time << FAIL; + cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; +} + +int main() { + performance_test(); + stress_test(); +} + diff --git a/test/math/primeSieve.cpp b/test/math/primeSieve.cpp new file mode 100644 index 0000000..78a50d2 --- /dev/null +++ b/test/math/primeSieve.cpp @@ -0,0 +1,47 @@ +#include "../util.h" +#include <math/primeSieve.cpp> + +bool naive(ll x) { + for (ll i = 2; i*i <= x; i++) { + if (x % i == 0) return false; + } + return x > 1; +} + +void stress_test() { + int queries = 0; + vector<ll> found; + for (int i = -5; i < 1'000'000; i++) { + auto got = isPrime(i); + auto expected = naive(i); + if (got != expected) cerr << "error: " << i << FAIL; + if (got) found.push_back(i); + queries++; + } + primes.resize(sz(found)); + if (primes != found) cerr << "error: primes" << FAIL; + for (int i = 0; i < 1'000'000; i++) { + ll x = Random::integer<ll>(2, N); + auto got = isPrime(x); + auto expected = naive(x); + if (got != expected) cerr << "error: " << x << FAIL; + queries++; + } + cerr << "tested queries: " << queries << endl; +} + +void performance_test() { + timer t; + t.start(); + primeSieve(); + hash_t hash = sz(primes); + t.stop(); + if (t.time > 500) cerr << "too slow: " << t.time << FAIL; + cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; +} + +int main() { + performance_test(); + stress_test(); +} + diff --git a/test/math/primitiveRoot.cpp b/test/math/primitiveRoot.cpp new file mode 100644 index 0000000..cd0b388 --- /dev/null +++ b/test/math/primitiveRoot.cpp @@ -0,0 +1,82 @@ +#include "../util.h" +#define ll lll +#include <math/modPowIterativ.cpp> +#undef ll +#include <math/millerRabin.cpp> +#include <math/rho.cpp> + +ll phi(ll pk, ll p, ll /*k*/) {return pk - pk / p;} +ll phi(ll n) { // O(sqrt(n)) + ll res = 1; + for (ll p = 2; p * p <= n; p++) { + if (n % p == 0) { + ll pk = 1; + ll k = 0; + do { + n /= p; + pk *= p; + k++; + } while (n % p == 0); + res *= phi(pk, p, k); + }} + if (n > 1) res *= phi(n, n, 1); + return res; +} + +#include <math/primitiveRoot.cpp> + +bool naiveIsPrimitive(ll g, ll n) { + if (gcd(g, n) != 1) return false; + vector<bool> seen(n); + ll c = g; + for (ll i = 0; i < n; i++) { + seen[c] = true; + c = (c * g) % n; + } + ll res = 0; + for (bool x : seen) if (x) res++; + return res == phi(n); +} + +void stress_test() { + int queries = 0; + for (int tries = 0; tries < 20'000; tries++) { + ll a = Random::integer<ll>(1, 3); + ll p = Random::prime<ll>(0, 1000); + ll k = p == 2 ? 1 : Random::integer<ll>(1, log(100'000) / log(p) + 1); + + ll x = a; + for (int i = 0; i < k; i++) x *= p; + + ll got = findPrimitive(x); + + if (got < 0 || got >= x) cerr << "error: out of range" << FAIL; + if (!naiveIsPrimitive(got, x)) cerr << "error: wrong" << got << " " << x << FAIL; + queries++; + } + cerr << "tested random queries: " << queries << endl; +} + +void stress_test2() { + int queries = 0; + for (int x = 2; x < 5'000; x++) { + map<ll, int> facts; + factor(x, facts); + if (x % 2 == 0) facts.erase(facts.find(2)); + bool expected = sz(facts) == 1; + if (x % 4 == 0) expected = false; + if (x == 2 || x == 4) expected = true; + + bool got = findPrimitive(x) >= 0; + + if (got != expected) cerr << "error" << FAIL; + queries++; + } + cerr << "tested random queries: " << queries << endl; +} + +int main() { + stress_test(); + stress_test2(); +} + diff --git a/test/math/rho.cpp b/test/math/rho.cpp new file mode 100644 index 0000000..5e4792a --- /dev/null +++ b/test/math/rho.cpp @@ -0,0 +1,117 @@ +#include "../util.h" +#define ll lll +#include <math/modPowIterativ.cpp> +#undef ll +#include <math/millerRabin.cpp> +#include <math/rho.cpp> + +map<ll, int> factor(ll n) { + map<ll, int> facts; + factor(n, facts); + return facts; +} + +ll mul(const map<ll, int>& facts) { + ll res = 1; + for (auto [p, c] : facts) { + for (int i = 0; i < c; i++) res *= p; + } + if (res < 1 || res > (1ll << 62)) cerr << "invalid number: " << res << FAIL; + return res; +} + +void stress_test() { + vector<map<ll, int>> test = { + {}, // 1 + {{2, 1}}, + {{3, 1}}, + {{2, 2}}, + {{5, 1}}, + {{2, 1}, {3, 1}}, + {{2, 2}, {3, 1}}, + {{2, 1}, {3, 2}}, + {{2, 2}, {3, 2}}, + {{2, 62}}, + {{2, 18}, {5, 18}}, + {{352523, 1}, {352817, 1}}, + {{41, 1}, {71, 1}, {421, 1}, {811, 1}}, + {{11, 1}, {17, 1}, {31, 1}, {61, 1}, {73, 1}, {66361, 1}}, + {{500000003, 1}, {1999999973, 1}}, + {{65537, 2}}, + {{999665081, 1}, {999716071, 1}}, + {{550177, 1}, {1100353, 1}, {1650529, 1}}, + {{459397, 1}, {918793, 1}, {1378189, 1}}, + {{37, 1}, {109, 1}}, + {{31, 1}, {151, 1}}, + {{239, 1}, {1429, 1}}, + {{89, 1}, {1093, 1}}, + {{2, 3}, {15800133918749317, 1}}, + {{12251, 1}, {85751, 1}}, + {{3, 1}, {5, 3}, {131, 1}, {6855593, 1}}, + {{5, 1}, {1927962474784631, 1}}, + {{197279, 1}, {1775503, 1}}, + {{3716371, 1}, {14865481, 1}}, + {{3, 1}, {5, 1}, {3075593, 1}, {3075593, 1}}, + {{4880401, 1}, {9760801, 1}}, + {{2822159, 1}, {11288633, 1}}, + {{3290341, 1}, {6580681, 1}}, + {{611557, 1}, {1834669, 1}}, + {{9227, 1}, {894923, 1}, {968731, 1}}, + {{3, 4}, {13, 1}, {62633, 2}}, + {{2, 2}, {3, 1}, {5, 1}, {167, 2}, {299197, 2}}, + {{332721269, 1}, {560937673, 1}}, + {{30702523, 1}, {122810089, 1}}, + {{24786439, 1}, {123932191, 1}}, + {{382500329, 1}, {1530001313, 1}}, + {{2, 4}, {5, 4}, {13, 1}, {30839, 2}}, + {{3, 1}, {385417, 1}, {7985344259, 1}}, + {{2, 4}, {3, 1}, {5, 1}, {7, 2}, {61, 1}, {179, 2}, {1381, 2}}, + {{627838711, 1}, {1212379867, 1}}, + {{3, 5}, {5, 3}, {41, 2}, {157321, 2}}, + {{5, 2}, {13, 1}}, + {{3, 1}, {5, 5}}, + {{2, 1}, {73, 1}, {193, 1}}, + {{5, 2}, {13, 1}, {19, 1}, {73, 1}}, + {{2, 3}, {3, 1}, {407521, 1}}, + {{2, 1}, {3, 1}, {299210837, 1}}, + {{2, 8}, {3, 4}, {5, 2}, {7, 2}, {11, 1}, {13, 1}, {17, 1}, {19, 1}, {23, 1}, {29, 1}, {3137, 1}}, + }; + + timer t; + for (auto expected : test) { + ll x = mul(expected); + t.start(); + auto got = factor(x); + t.stop(); + if (got != expected) { + cerr << "number: " << x << endl; + cerr << "got:" << endl; + for (auto [p, c] : got) cerr << p << "^" << c << endl; + cerr << "expected" << endl; + for (auto [p, c] : expected) cerr << p << "^" << c << endl; + cerr << FAIL; + } + } + if (t.time > 100) cerr << "too slow" << FAIL; + cerr << "stress tested: " << t.time << "ms" << endl; +} + +constexpr int N = 2'000; +void performance_test() { + timer t; + hash_t hash = 0; + for (int operations = 0; operations < N; operations++) { + ll x = Random::integer<ll>(1e18 / 2, 1e18); + t.start(); + hash += factor(x).size(); + 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/shortModInv.cpp b/test/math/shortModInv.cpp new file mode 100644 index 0000000..26960bf --- /dev/null +++ b/test/math/shortModInv.cpp @@ -0,0 +1,39 @@ +#include "../util.h" +#include <math/shortModInv.cpp> + +void stress_test() { + ll queries = 0; + for (int i = 0; i < 10'000'000; i++) { + ll n = Random::integer<ll>(2, 1'000'000'000); + ll x = 0; + do { + x = Random::integer<ll>(0, n); + } while (gcd(x, n) != 1); + ll y = multInv(x, n); + ll got = (x*y) % n; + if (got != 1) cerr << "got: " << got << ", expected: 1" << 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 a = Random::integer<ll>(0, 1'000'000'000); + ll b = Random::integer<ll>(2, 1'000'000'000); + t.start(); + hash += multInv(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/simpson.cpp b/test/math/simpson.cpp new file mode 100644 index 0000000..d7cdba3 --- /dev/null +++ b/test/math/simpson.cpp @@ -0,0 +1,63 @@ +#include "../util.h" +std::function<double(double)> f; +constexpr double EPS = 1e-9; +#include <math/simpson.cpp> + +struct RandomPolynom { + vector<double> polynom; + RandomPolynom(int deg) : polynom(deg) { + for (auto& x : polynom) x = Random::real<double>(-100, 100); + } + double operator()(double x) const { + double res = 0; + double xx = 1; + for (double y : polynom ) { + res += xx * y; + xx *= x; + } + return res; + } + double area(double a, double b) const { + double res = 0; + double aa = a; + double bb = b; + ll d = 1; + for (double y : polynom) { + res += bb / d * y; + res -= aa / d * y; + aa *= a; + bb *= b; + d++; + } + return res; + } +}; + +void stress_test() { + timer t; + ll queries = 0; + for (int tries = 0; tries < 1'000; tries++) { + ll n = Random::integer<ll>(0, 6); + RandomPolynom poly(n); + f = poly; + for (ll i = 0; i < 200; i++) { + double l = Random::real<double>(-20, 20); + double r = Random::real<double>(-20, 20); + if (l > r) swap(l, r); + + t.start(); + double got = integrate(l, r); + t.stop(); + double expected = poly.area(l, r); + if (float_error(got, expected) > 1e-6) cerr << fixed << setprecision(20) << "got: " << got << ", expected: " << expected << FAIL; + queries++; + } + } + if (t.time > 5000) cerr << "too slow: " << t.time << FAIL; + cerr << "tested random queries: " << queries << " (" << t.time << "ms)" << endl; +} + +int main() { + stress_test(); +} + diff --git a/test/math/sqrtModCipolla.cpp b/test/math/sqrtModCipolla.cpp new file mode 100644 index 0000000..26d975b --- /dev/null +++ b/test/math/sqrtModCipolla.cpp @@ -0,0 +1,48 @@ +#include "../util.h" +#include <math/modPowIterativ.cpp> +#include <math/legendre.cpp> +mt19937 rng(123456789); +#include <math/sqrtModCipolla.cpp> + +void stress_test(ll range) { + ll work = 0; + for (ll i = 0; i < 10'000; i++) { + ll p = Random::prime<ll>(range); + for (ll j = 0; j < 100; j++) { + ll x = Random::integer<ll>(0, p); + if (legendre(x, p) < 0) continue; + + ll got = sqrtMod(x, p); + if (got < 0 || got >= p) cerr << "error: out of range" << FAIL; + if ((got * got) % p != x) cerr << "error: not root" << FAIL; + work++; + } + } + cerr << "stress tested: " << work << endl; +} + +constexpr int N = 200'000; +constexpr ll mod = 1'394'633'899; +void performance_test() { + timer t; + hash_t hash = 0; + for (int operations = 0; operations < N; operations++) { + ll x; + do { + x = Random::integer<ll>(0, mod); + } while (legendre(x, mod) >= 0); + t.start(); + hash += sqrtMod(x, mod); + 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(1'000); + stress_test(1'000'000'000); + performance_test(); +} + diff --git a/test/math/transforms/andTransform.cpp b/test/math/transforms/andTransform.cpp new file mode 100644 index 0000000..fa029f6 --- /dev/null +++ b/test/math/transforms/andTransform.cpp @@ -0,0 +1,38 @@ +#include "../../util.h" +#include <math/transforms/andTransform.cpp> + +void stress_test() { + ll queries = 0; + for (ll i = 0; i < 10'000; i++) { + int n = 1ll << Random::integer<int>(0, 10); + auto expected = Random::integers<ll>(n, -1000, 1000); + auto got = expected; + fft(got, false); + fft(got, true); + if (got != expected) cerr << "error" << FAIL; + queries += n; + } + cerr << "tested queries: " << queries << endl; +} + +constexpr int N = 1ll << 23; +void performance_test() { + timer t; + vector<ll> a = Random::integers<ll>(N, -1000, 1000); + vector<ll> b = Random::integers<ll>(N, -1000, 1000); + t.start(); + fft(a, true); + fft(b, false); + t.stop(); + hash_t hash = 0; + for (ll i = 0; i < N; i++) hash += i * a[i]; + for (ll i = 0; i < N; i++) hash += i * b[i]; + 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/transforms/bitwiseTransforms.cpp b/test/math/transforms/bitwiseTransforms.cpp new file mode 100644 index 0000000..132740c --- /dev/null +++ b/test/math/transforms/bitwiseTransforms.cpp @@ -0,0 +1,38 @@ +#include "../../util.h" +#include <math/transforms/bitwiseTransforms.cpp> + +void stress_test() { + ll queries = 0; + for (ll i = 0; i < 10'000; i++) { + int n = 1ll << Random::integer<int>(0, 10); + auto expected = Random::integers<ll>(n, -1000, 1000); + auto got = expected; + bitwiseConv(got, false); + bitwiseConv(got, true); + if (got != expected) cerr << "error" << FAIL; + queries += n; + } + cerr << "tested queries: " << queries << endl; +} + +constexpr int N = 1ll << 23; +void performance_test() { + timer t; + vector<ll> a = Random::integers<ll>(N, -1000, 1000); + vector<ll> b = Random::integers<ll>(N, -1000, 1000); + t.start(); + bitwiseConv(a, true); + bitwiseConv(b, false); + t.stop(); + hash_t hash = 0; + for (ll i = 0; i < N; i++) hash += i * a[i]; + for (ll i = 0; i < N; i++) hash += i * b[i]; + 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/transforms/fft.cpp b/test/math/transforms/fft.cpp new file mode 100644 index 0000000..858676b --- /dev/null +++ b/test/math/transforms/fft.cpp @@ -0,0 +1,51 @@ +#include "../../util.h" +#include <math/transforms/fft.cpp> + +vector<cplx> to_cplx(const vector<ll>& in) { + vector<cplx> res(sz(in)); + for (int i = 0; i < sz(in); i++) res[i] = in[i]; + return res; +} + +vector<ll> from_cplx(const vector<cplx>& in) { + vector<ll> res(sz(in)); + for (int i = 0; i < sz(in); i++) res[i] = llround(real(in[i])); + return res; +} + +void stress_test() { + ll queries = 0; + for (ll i = 0; i < 10'000; i++) { + int n = 1ll << Random::integer<int>(0, 10); + auto expected = Random::integers<ll>(n, -1000, 1000); + vector<cplx> tmp = to_cplx(expected); + fft(tmp, false); + fft(tmp, true); + auto got = from_cplx(tmp); + if (got != expected) cerr << "error" << FAIL; + queries += n; + } + cerr << "tested queries: " << queries << endl; +} + +constexpr int N = 1ll << 21; +void performance_test() { + timer t; + auto a = to_cplx(Random::integers<ll>(N, -1000, 1000)); + auto b = to_cplx(Random::integers<ll>(N, -1000, 1000)); + t.start(); + fft(a, true); + fft(b, false); + t.stop(); + hash_t hash = 0; + for (ll i = 0; i < N; i++) hash += i * llround(real(a[i])); + for (ll i = 0; i < N; i++) hash += i * llround(real(b[i])); + 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/transforms/fftMul.cpp b/test/math/transforms/fftMul.cpp new file mode 100644 index 0000000..5933864 --- /dev/null +++ b/test/math/transforms/fftMul.cpp @@ -0,0 +1,62 @@ +#include "../../util.h" +#include <math/modPowIterativ.cpp> +#include <math/transforms/fft.cpp> +#pragma GCC diagnostic ignored "-Wnarrowing" +#include <math/transforms/fftMul.cpp> + +vector<ll> from_cplx(const vector<cplx>& in) { + vector<ll> res(sz(in)); + for (int i = 0; i < sz(in); i++) res[i] = llround(real(in[i])); + return res; +} + +vector<ll> naive(const vector<ll>& a, const vector<ll>& b) { + vector<ll> res; + for (ll i = 1;; i *= 2) { + if (sz(a) + sz(b) <= i) { + res.resize(i, 0); + break; + } + } + for (int i = 0; i < sz(a); i++) { + for (int j = 0; j < sz(b); j++) { + res[i+j] += a[i] * b[j]; + } + } + return res; +} + +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); + auto a = Random::integers<ll>(n, -1000, 1000); + auto b = Random::integers<ll>(m, -1000, 1000); + auto expected = naive(a, b); + auto got = from_cplx(mul(a, b)); + if (got != expected) cerr << "error" << FAIL; + queries += n; + } + cerr << "tested queries: " << queries << endl; +} + +constexpr int N = 1ll << 20; +void performance_test() { + timer t; + vector<ll> a = Random::integers<ll>(N, -1000, 1000); + vector<ll> b = Random::integers<ll>(N, -1000, 1000); + t.start(); + auto got = from_cplx(mul(a, b)); + t.stop(); + hash_t hash = 0; + for (ll i = 0; i < N; i++) hash += i * got[i]; + 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/transforms/multiplyBitwise.cpp b/test/math/transforms/multiplyBitwise.cpp new file mode 100644 index 0000000..bc73290 --- /dev/null +++ b/test/math/transforms/multiplyBitwise.cpp @@ -0,0 +1,55 @@ +#include "../../util.h" +#include <math/modPowIterativ.cpp> +#include <math/transforms/bitwiseTransforms.cpp> +#include <math/transforms/multiplyBitwise.cpp> + +vector<ll> naive(const vector<ll>& a, const vector<ll>& b) { + vector<ll> res; + for (ll i = 1;; i *= 2) { + if (sz(a) <= i && sz(b) <= i) { + res.resize(i, 0); + break; + } + } + for (int i = 0; i < sz(a); i++) { + for (int j = 0; j < sz(b); j++) { + res[i&j] += a[i] * b[j]; + } + } + return res; +} + +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); + auto a = Random::integers<ll>(n, -1000, 1000); + auto b = Random::integers<ll>(m, -1000, 1000); + auto expected = naive(a, b); + auto got = mul(a, b); + if (got != expected) cerr << "error" << FAIL; + queries += n; + } + cerr << "tested queries: " << queries << endl; +} + +constexpr int N = 1ll << 22; +void performance_test() { + timer t; + vector<ll> a = Random::integers<ll>(N, -1000, 1000); + vector<ll> b = Random::integers<ll>(N, -1000, 1000); + t.start(); + auto got = mul(a, b); + t.stop(); + hash_t hash = 0; + for (ll i = 0; i < N; i++) hash += i * got[i]; + 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/transforms/multiplyFFT.cpp b/test/math/transforms/multiplyFFT.cpp new file mode 100644 index 0000000..782be1b --- /dev/null +++ b/test/math/transforms/multiplyFFT.cpp @@ -0,0 +1,55 @@ +#include "../../util.h" +#include <math/modPowIterativ.cpp> +#include <math/transforms/fft.cpp> +#include <math/transforms/multiplyFFT.cpp> + +vector<ll> naive(const vector<ll>& a, const vector<ll>& b) { + vector<ll> res; + for (ll i = 1;; i *= 2) { + if (sz(a) + sz(b) <= i) { + res.resize(i, 0); + break; + } + } + for (int i = 0; i < sz(a); i++) { + for (int j = 0; j < sz(b); j++) { + res[i+j] += a[i] * b[j]; + } + } + return res; +} + +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); + auto a = Random::integers<ll>(n, -1000, 1000); + auto b = Random::integers<ll>(m, -1000, 1000); + auto expected = naive(a, b); + auto got = mul(a, b); + if (got != expected) cerr << "error" << FAIL; + queries += n; + } + cerr << "tested queries: " << queries << endl; +} + +constexpr int N = 1ll << 19; +void performance_test() { + timer t; + vector<ll> a = Random::integers<ll>(N, -1000, 1000); + vector<ll> b = Random::integers<ll>(N, -1000, 1000); + t.start(); + auto got = mul(a, b); + t.stop(); + hash_t hash = 0; + for (ll i = 0; i < N; i++) hash += i * got[i]; + 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/transforms/multiplyNTT.cpp b/test/math/transforms/multiplyNTT.cpp new file mode 100644 index 0000000..70fc137 --- /dev/null +++ b/test/math/transforms/multiplyNTT.cpp @@ -0,0 +1,56 @@ +#include "../../util.h" +#include <math/modPowIterativ.cpp> +#include <math/transforms/ntt.cpp> +#include <math/transforms/multiplyNTT.cpp> + +vector<ll> naive(const vector<ll>& a, const vector<ll>& b) { + vector<ll> res; + for (ll i = 1;; i *= 2) { + if (sz(a) + sz(b) <= i) { + res.resize(i, 0); + break; + } + } + for (int i = 0; i < sz(a); i++) { + for (int j = 0; j < sz(b); j++) { + res[i+j] += a[i] * b[j]; + res[i+j] %= mod; + } + } + return res; +} + +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); + auto a = Random::integers<ll>(n, 0, mod); + auto b = Random::integers<ll>(m, 0, mod); + auto expected = naive(a, b); + auto got = mul(a, b); + if (got != expected) cerr << "error" << FAIL; + queries += n; + } + cerr << "tested queries: " << queries << endl; +} + +constexpr int N = 1ll << 20; +void performance_test() { + timer t; + vector<ll> a = Random::integers<ll>(N, 0, mod); + vector<ll> b = Random::integers<ll>(N, 0, mod); + t.start(); + auto got = mul(a, b); + t.stop(); + hash_t hash = 0; + for (ll i = 0; i < N; i++) hash += i * got[i]; + 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/transforms/ntt.cpp b/test/math/transforms/ntt.cpp new file mode 100644 index 0000000..cd32073 --- /dev/null +++ b/test/math/transforms/ntt.cpp @@ -0,0 +1,39 @@ +#include "../../util.h" +#include <math/modPowIterativ.cpp> +#include <math/transforms/ntt.cpp> + +void stress_test() { + ll queries = 0; + for (ll i = 0; i < 10'000; i++) { + int n = 1ll << Random::integer<int>(0, 10); + auto expected = Random::integers<ll>(n, 0, mod); + auto got = expected; + ntt(got, false); + ntt(got, true); + if (got != expected) cerr << "error" << FAIL; + queries += n; + } + cerr << "tested queries: " << queries << endl; +} + +constexpr int N = 1ll << 22; +void performance_test() { + timer t; + vector<ll> a = Random::integers<ll>(N, 0, mod); + vector<ll> b = Random::integers<ll>(N, 0, mod); + t.start(); + ntt(a, true); + ntt(b, false); + t.stop(); + hash_t hash = 0; + for (ll i = 0; i < N; i++) hash += i * a[i]; + for (ll i = 0; i < N; i++) hash += i * b[i]; + 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/transforms/orTransform.cpp b/test/math/transforms/orTransform.cpp new file mode 100644 index 0000000..0ec9155 --- /dev/null +++ b/test/math/transforms/orTransform.cpp @@ -0,0 +1,38 @@ +#include "../../util.h" +#include <math/transforms/orTransform.cpp> + +void stress_test() { + ll queries = 0; + for (ll i = 0; i < 10'000; i++) { + int n = 1ll << Random::integer<int>(0, 10); + auto expected = Random::integers<ll>(n, -1000, 1000); + auto got = expected; + fft(got, false); + fft(got, true); + if (got != expected) cerr << "error" << FAIL; + queries += n; + } + cerr << "tested queries: " << queries << endl; +} + +constexpr int N = 1ll << 23; +void performance_test() { + timer t; + vector<ll> a = Random::integers<ll>(N, -1000, 1000); + vector<ll> b = Random::integers<ll>(N, -1000, 1000); + t.start(); + fft(a, true); + fft(b, false); + t.stop(); + hash_t hash = 0; + for (ll i = 0; i < N; i++) hash += i * a[i]; + for (ll i = 0; i < N; i++) hash += i * b[i]; + 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/transforms/xorTransform.cpp b/test/math/transforms/xorTransform.cpp new file mode 100644 index 0000000..17b0f6f --- /dev/null +++ b/test/math/transforms/xorTransform.cpp @@ -0,0 +1,38 @@ +#include "../../util.h" +#include <math/transforms/xorTransform.cpp> + +void stress_test() { + ll queries = 0; + for (ll i = 0; i < 10'000; i++) { + int n = 1ll << Random::integer<int>(0, 10); + auto expected = Random::integers<ll>(n, -1000, 1000); + auto got = expected; + fft(got, false); + fft(got, true); + if (got != expected) cerr << "error" << FAIL; + queries += n; + } + cerr << "tested queries: " << queries << endl; +} + +constexpr int N = 1ll << 23; +void performance_test() { + timer t; + vector<ll> a = Random::integers<ll>(N, -1000, 1000); + vector<ll> b = Random::integers<ll>(N, -1000, 1000); + t.start(); + fft(a, true); + fft(b, false); + t.stop(); + hash_t hash = 0; + for (ll i = 0; i < N; i++) hash += i * a[i]; + for (ll i = 0; i < N; i++) hash += i * b[i]; + 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(); +} + |