mzuenni tests

1 files changed, 129 insertions, 0 deletions

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();
+}
+