From a898bac55c6cd7c51fef5e6735aa3a316a18da7b Mon Sep 17 00:00:00 2001 From: mzuenni Date: Wed, 11 Sep 2024 10:39:00 +0200 Subject: change tests --- test/math/linearRecurenceOld.cpp | 54 ---------------------------- test/math/linearRecurrence.cpp | 15 ++++---- test/math/linearRecurrence.cpp.awk | 4 +++ test/math/linearRecurrenceNTT.cpp | 60 +++++++++++++++++++++++++++++++ test/math/linearRecurrenceOld.cpp | 54 ++++++++++++++++++++++++++++ test/math/linearRecurrenceSlowMul.cpp | 67 ----------------------------------- 6 files changed, 127 insertions(+), 127 deletions(-) delete mode 100644 test/math/linearRecurenceOld.cpp create mode 100644 test/math/linearRecurrence.cpp.awk create mode 100644 test/math/linearRecurrenceNTT.cpp create mode 100644 test/math/linearRecurrenceOld.cpp delete mode 100644 test/math/linearRecurrenceSlowMul.cpp (limited to 'test/math') diff --git a/test/math/linearRecurenceOld.cpp b/test/math/linearRecurenceOld.cpp deleted file mode 100644 index dab2256..0000000 --- a/test/math/linearRecurenceOld.cpp +++ /dev/null @@ -1,54 +0,0 @@ -#include "../util.h" -#include - -struct RandomRecurence { - vector f, c, cache; - RandomRecurence(int n) : f(Random::integers(n, 0, mod)), c(Random::integers(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(1, 10); - RandomRecurence f(n); - for (int j = 0; j < 100; j++) { - ll k = Random::integer(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/linearRecurrence.cpp b/test/math/linearRecurrence.cpp index 50e98a0..f0ebe76 100644 --- a/test/math/linearRecurrence.cpp +++ b/test/math/linearRecurrence.cpp @@ -1,9 +1,12 @@ #include "../util.h" -#include -#include -#include +vector mul(const vector& a, const vector& b); #include +vector mul(const vector& a, const vector& b) { + return mulSlow(a, b); +} + + struct RandomRecurence { vector f, c, cache; RandomRecurence(int n) : f(Random::integers(n, 0, mod)), c(Random::integers(n, 0, mod)), cache(f) {} @@ -23,7 +26,7 @@ struct RandomRecurence { void stress_test() { int queries = 0; - for (int i = 0; i < 1'000; i++) { + for (int i = 0; i < 10'000; i++) { int n = Random::integer(1, 10); RandomRecurence f(n); for (int j = 0; j < 100; j++) { @@ -39,14 +42,14 @@ void stress_test() { cerr << "tested random queries: " << queries << endl; } -constexpr int N = 100'000; +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 > 8000) cerr << "too slow: " << t.time << FAIL; + if (t.time > 500) cerr << "too slow: " << t.time << FAIL; cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; } 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 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 +#include +#include +#define mod mod2 +#include +#undef mod +static_assert(mod == mod2); + +struct RandomRecurence { + vector f, c, cache; + RandomRecurence(int n) : f(Random::integers(n, 0, mod)), c(Random::integers(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(1, 10); + RandomRecurence f(n); + for (int j = 0; j < 100; j++) { + ll k = Random::integer(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 + +struct RandomRecurence { + vector f, c, cache; + RandomRecurence(int n) : f(Random::integers(n, 0, mod)), c(Random::integers(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(1, 10); + RandomRecurence f(n); + for (int j = 0; j < 100; j++) { + ll k = Random::integer(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/linearRecurrenceSlowMul.cpp b/test/math/linearRecurrenceSlowMul.cpp deleted file mode 100644 index 205e584..0000000 --- a/test/math/linearRecurrenceSlowMul.cpp +++ /dev/null @@ -1,67 +0,0 @@ -#include "../util.h" - -constexpr ll mod = 998244353; -vector mul(const vector &a, const vector &b){ - vector c(sz(a) + sz(b) - 1); - for(int i = 0; i < sz(a); i++){ - for(int j = 0; j < sz(b); j++){ - c[i+j] += a[i]*b[j] % mod; - } - } - for(ll &x : c) x %= mod; - return c; -} - -#include - -struct RandomRecurence { - vector f, c, cache; - RandomRecurence(int n) : f(Random::integers(n, 0, mod)), c(Random::integers(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(1, 10); - RandomRecurence f(n); - for (int j = 0; j < 100; j++) { - ll k = Random::integer(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(); -} - -- cgit v1.2.3