more tests

2 files changed, 157 insertions, 3 deletions

diff --git a/content/math/polynomial.cpp b/content/math/polynomial.cpp
index 44f6207..84f3aaa 100644
--- a/content/math/polynomial.cpp
+++ b/content/math/polynomial.cpp
@@ -1,7 +1,7 @@
 struct poly {
 	vector<ll> data;
 
-	poly(int deg = 0) : data(max(1, deg)) {}
+	poly(int deg = 0) : data(1 + deg) {}
 	poly(initializer_list<ll> _data) : data(_data) {}
 
 	int size() const {return sz(data);}
@@ -40,17 +40,18 @@ struct poly {
 
 	//return p(x+a)
 	poly operator<<(ll a) const {
-		poly res(size());
+		poly res(size() - 1);
 		for (int i = size() - 1; i >= 0; i--) {
 			for (int j = size() - i - 1; j >= 1; j--)
 				res[j] = (res[j] * a + res[j - 1]) % mod;
-			res[0] = (res[0] * a + res[i]) % mod;
+			res[0] = (res[0] * a + data[i]) % mod;
 		}
 		return res;
 	}
 
 	pair<poly, poly> divmod(const poly& d) const {
 		int i = size() - d.size();
+		if (i <= 0) return {{}, *this};
 		poly s(i + 1), r = *this;
 		ll inv = multInv(d.data.back(), mod);
 		for (; i >= 0; i--) {
diff --git a/test/math/polynomial.cpp b/test/math/polynomial.cpp
new file mode 100644
index 0000000..f4a9486
--- /dev/null
+++ b/test/math/polynomial.cpp
@@ -0,0 +1,153 @@
+#include "../util.h"
+#include <math/shortModInv.cpp>
+constexpr ll mod = 1'394'633'899;
+#include <math/polynomial.cpp>
+
+poly randomPoly(int deg) {
+	poly p;
+	p.data = Random::integers<ll>(deg + 1, 0, mod);
+	return p;
+}
+
+ll eval(const vector<ll>& p, ll x) {
+	ll res = 0;
+	for (ll i = 0, j = 1; i < sz(p); i++, j = (j * x) % mod) {
+		res += j * p[i];
+		res %= mod;
+	}
+	return res;
+}
+
+void test_eval() {
+	int queries = 0;
+	for (int tries = 0; tries < 100'000; tries++) {
+		int deg = Random::integer<int>(1, 30);
+		vector<ll> tmp = Random::integers<ll>(deg + 1, 0, mod);
+		poly p(deg);
+		for (int i = 0; i <= deg; i++) p[i] = tmp[i];
+
+		for (int i = 0; i <= deg + 7; i++) {
+			ll x = Random::integer<ll>(0, mod);
+
+			ll got = p(x);
+			ll expected = eval(tmp, x);
+
+			if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL;
+		}
+		queries += deg + 1;
+	}
+	cerr << "tested eval: " << queries << endl;
+}
+
+void test_add() {
+	int queries = 0;
+	for (int tries = 0; tries < 100'000; tries++) {
+		int n = Random::integer<int>(1, 30);
+		int m = Random::integer<int>(1, 30);
+		auto a = randomPoly(n);
+		auto b = randomPoly(m);
+
+		auto c = a;
+		c += b;
+
+		if (sz(c) > sz(a) && sz(c) > sz(b)) cerr << "error: wrong degree" << FAIL;
+
+		for (int i = 0; i <= n + m + 7; i++) {
+			ll x = Random::integer<ll>(0, mod);
+
+			ll got = c(x);
+			ll expected = (a(x) + b(x)) % mod;
+
+			if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL;
+		}
+		queries += n + m;
+	}
+	cerr << "tested add: " << queries << endl;
+}
+
+void test_mul() {
+	int queries = 0;
+	for (int tries = 0; tries < 100'000; tries++) {
+		int n = Random::integer<int>(1, 30);
+		int m = Random::integer<int>(1, 30);
+		auto a = randomPoly(n);
+		auto b = randomPoly(m);
+
+		auto c = a * b;
+		if (sz(c) > sz(a) + sz(b) - 1) cerr << "error: wrong degree" << FAIL;
+
+		for (int i = 0; i <= n + m + 7; i++) {
+			ll x = Random::integer<ll>(0, mod);
+
+			ll got = c(x);
+			ll expected = (a(x) * b(x)) % mod;
+
+			if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL;
+		}
+		queries += n + m;
+	}
+	cerr << "tested mul: " << queries << endl;
+}
+
+void test_shift() {
+	int queries = 0;
+	for (int tries = 0; tries < 100'000; tries++) {
+		int n = Random::integer<int>(1, 30);
+		int m = Random::integer<int>(1, 30);
+		auto a = randomPoly(n);
+
+		auto b = a << m;
+		if (sz(b) > sz(a)) cerr << sz(a) << " " << sz(b) << endl;
+		if (sz(b) > sz(a)) cerr << "error: wrong degree" << FAIL;
+
+		for (int i = 0; i <= n + 7; i++) {
+			ll x = Random::integer<ll>(0, mod);
+
+			ll got = b(x);
+			ll expected = a((x + m) % mod);
+
+			if (got != expected) {
+				for (ll y : b.data) cerr << y << " ";
+				cerr << endl;
+			}
+			if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL;
+		}
+		queries += n;
+	}
+	cerr << "tested shift: " << queries << endl;
+}
+
+void test_divmod() {
+	int queries = 0;
+	for (int tries = 0; tries < 100'000; tries++) {
+		int n = Random::integer<int>(1, 30);
+		int m = Random::integer<int>(1, 30);
+		auto a = randomPoly(n);
+		auto b = randomPoly(m);
+
+		auto [div, rem] = a.divmod(b);
+		if (sz(rem) > sz(b)) cerr << "error: wrong degree (rem)" << FAIL;
+		if (sz(div) > 1 + max<ll>(0, sz(a) - sz(b))) cerr << "error: wrong degree (div)" << FAIL;
+
+		for (int i = 0; i <= n + m; i++) {
+			ll x = Random::integer<ll>(0, mod);
+			ll d = multInv(b(x), mod);
+
+			ll got = (div(x) + rem(x) * d) % mod;
+			ll expected = (a(x) * d) % mod;
+
+			if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL;
+		}
+		queries += n + m;
+	}
+	cerr << "tested divmod: " << queries << endl;
+}
+	
+int main() {
+	test_eval();
+	test_add();
+	test_mul();
+	test_shift();
+	test_divmod();
+}
+