zmodn

test (9023B)

---

 #if 0
 
 cc=${CC:-g++}
 bin="$(mktemp)"
 ${cc} -x c++ -std=c++20 -o "$bin" -g -O0 "$(realpath $0)"
 echo "Running $bin"
 "$bin"
 
 exit 0
 #endif
 
 #include "zmodn.h"
 #include "bigint.h"
 
 #if defined(__clang__) && __clang_major__ >= 16
 #include "bitint_wrapper.h"
 #endif
 
 #include <concepts>
 #include <functional>
 #include <iostream>
 #include <optional>
 
 template<typename S, typename T>
 requires std::convertible_to<S, T> || std::convertible_to<T, S>
 void assert_equal(S actual, T expected) {
 	if (actual != expected) {
 		std::cout << "Error!" << std::endl;
 		std::cout << "Expected: " << expected << std::endl;
 		std::cout << "But got:  " << actual << std::endl;
 		exit(1);
 	}
 }
 
 class Test {
 public:
 	std::string name;
 	std::function<void()> f;
 } tests[] = {
 {
 	.name = "Constructor 2 mod 3",
 	.f = []() {
 		Zmod<3> two = Zmod<3>(2);
 		assert_equal(two.toint(), INT64_C(2));
 	}
 },
 {
 	.name = "Constructor -7 mod 3",
 	.f = []() {
 		Zmod<3> z = -7;
 		assert_equal(z, Zmod<3>(2));
 	}
 },
 {
 	.name = "1+1 mod 2",
 	.f = []() {
 		auto oneplusone = Zmod<2>(1) + Zmod<2>(1);
 		assert_equal(oneplusone, Zmod<2>(0));
 	}
 },
 {
 	.name = "2 -= 5 (mod 4)",
 	.f = []() {
 		Zmod<4> z = 2;
 		auto diff = (z -= 5);
 		assert_equal(z, Zmod<4>(1));
 		assert_equal(diff, Zmod<4>(1));
 	}
 },
 {
 	.name = "Inverse of 0 mod 2",
 	.f = []() {
 		Zmod<2> z = 0;
 		auto inv = z.inverse();
 		assert_equal(inv.has_value(), false);
 	}
 },
 {
 	.name = "Inverse of 1 mod 2",
 	.f = []() {
 		Zmod<2> z = 1;
 		auto inv = z.inverse();
 		assert_equal(inv.has_value(), true);
 		assert_equal(inv.value(), Zmod<2>(1));
 	}
 },
 {
 	.name = "Inverse of 5 mod 7",
 	.f = []() {
 		Zmod<7> z = 5;
 		auto inv = z.inverse();
 		assert_equal(inv.has_value(), true);
 		assert_equal(inv.value(), Zmod<7>(3));
 	}
 },
 {
 	.name = "Inverse of 4 mod 12",
 	.f = []() {
 		Zmod<12> z = 4;
 		auto inv = z.inverse();
 		assert_equal(inv.has_value(), false);
 	}
 },
 {
 	.name = "4 / 7 (mod 12)",
 	.f = []() {
 		Zmod<12> n = 4;
 		Zmod<12> d = 7;
 		auto inv = n / d;
 		assert_equal(inv.has_value(), true);
 		assert_equal(inv.value(), Zmod<12>(4));
 	}
 },
 {
 	.name = "4 /= 7 (mod 12)",
 	.f = []() {
 		Zmod<12> n = 4;
 		Zmod<12> d = 7;
 		auto inv = (n /= d);
 		assert_equal(inv.has_value(), true);
 		assert_equal(inv.value(), Zmod<12>(4));
 		assert_equal(n, Zmod<12>(4));
 	}
 },
 {
 	.name = "Multiplication overflow",
 	.f = []() {
 		Zmod<10> n = 8;
 		Zmod<10> m = 9;
 		auto prod = m * n;
 		assert_equal(prod.toint(), 2);
 	}
 },
 {
 	.name = "Multiplication and assignment overflow",
 	.f = []() {
 		Zmod<10> n = 8;
 		Zmod<10> m = 9;
 		n *= m;
 		assert_equal(n.toint(), 2);
 	}
 },
 {
 	.name = "2^12 mod 154",
 	.f = []() {
 		Zmod<154> b = 2;
 		auto p = b ^ 12;
 		assert_equal(p, 92);
 	}
 },
 {
 	.name = "BigInt constructor zero",
 	.f = []() {
 		BigInt x;
 		BigInt y(0);
 
 		assert_equal(x, y);
 	}
 },
 {
 	.name = "BigInt constructor one digit",
 	.f = []() {
 		BigInt x(12345);
 		BigInt y("12345");
 
 		assert_equal(x, y);
 	}
 },
 {
 	.name = "BigInt constructor many small digits",
 	.f = []() {
 		BigInt<20, 2> x(123456789);
 		BigInt<20, 2> y("123456789");
 
 		assert_equal(x, y);
 	}
 },
 {
 	.name = "BigInt constructor negative many small digits",
 	.f = []() {
 		BigInt<20, 2> x(-123456789);
 		BigInt<20, 2> y("-123456789");
 
 		assert_equal(x, y);
 	}
 },
 {
 	.name = "BigInt operator==",
 	.f = []() {
 		BigInt<20, 2> x(123456789);
 		BigInt<20, 2> y("123456789");
 		BigInt<20, 2> z("12456789");
 
 		bool eq = (x == y);
 		bool diff = (x == z);
 
 		assert_equal(eq, true);
 		assert_equal(diff, false);
 	},
 },
 {
 	.name = "BigInt operator== negative",
 	.f = []() {
 		BigInt<20, 2> x("-123456789");
 		BigInt<20, 2> z("123456789");
 
 		bool diff = (x == z);
 
 		assert_equal(diff, false);
 	},
 },
 {
 	.name = "BigInt operator!= true",
 	.f = []() {
 		BigInt<20, 2> x(12345678);
 		BigInt<20, 2> y("123456789");
 		BigInt<20, 2> z("123456789");
 
 		bool diff = (x != y);
 		bool eq = (y != z);
 
 		assert_equal(diff, true);
 		assert_equal(eq, false);
 	},
 },
 {
 	.name = "BigInt operator< and operator>",
 	.f = []() {
 		BigInt<20, 2> x(7891);
 		BigInt<20, 2> y(7881);
 	
 		bool t = (y < x);
 		bool f = (x < y);
 
 		assert_equal(t, true);
 		assert_equal(f, false);
 	}
 },
 {
 	.name = "BigInt operator< both negative",
 	.f = []() {
 		BigInt<20, 2> x(-7891);
 		BigInt<20, 2> y(-7881);
 	
 		bool cmp = (x < y);
 
 		assert_equal(cmp, true);
 	}
 },
 {
 	.name = "BigInt operator< different sign",
 	.f = []() {
 		BigInt<20, 2> x(-7);
 		BigInt<20, 2> y(7);
 	
 		bool cmp = (x < y);
 
 		assert_equal(cmp, true);
 	}
 },
 {
 	.name = "BigInt abs",
 	.f = []() {
 		BigInt<20, 2> x(-1234567);
 		BigInt<20, 2> y(7654321);
 
 		assert_equal(x.abs(), BigInt<20, 2>(1234567));
 		assert_equal(y.abs(), y);
 	}
 },
 {
 	.name = "BigInt opposite",
 	.f = []() {
 		BigInt<20, 2> x(-1234567);
 		BigInt<20, 2> y(7654321);
 
 		assert_equal(-x, BigInt<20, 2>(1234567));
 		assert_equal(-y, BigInt<20, 2>(-7654321));
 	}
 },
 {
 	.name = "BigInt -0 == 0",
 	.f = []() {
 		BigInt z(0);
 
 		assert_equal(-z, z);
 	}
 },
 {
 	.name = "BigInt sum",
 	.f = []() {
 		BigInt<20, 2> x("987608548588589");
 		BigInt<20, 2> y("6793564545455289");
 		BigInt<20, 2> z("7781173094043878");
 
 		assert_equal(x+y, z);
 	}
 },
 {
 	.name = "BigInt sum both negative",
 	.f = []() {
 		BigInt<20, 2> x("-987608548588589");
 		BigInt<20, 2> y("-6793564545455289");
 		BigInt<20, 2> z("-7781173094043878");
 
 		assert_equal(x+y, z);
 	}
 },
 {
 	.name = "BigInt sum negative + positive, result positive",
 	.f = []() {
 		BigInt<20, 2> x("-987608548588589");
 		BigInt<20, 2> y("6793564545455289");
 		BigInt<20, 2> z("5805955996866700");
 
 		assert_equal(x+y, z);
 	}
 },
 {
 	.name = "BigInt sum positive + negative, result negative",
 	.f = []() {
 		BigInt<20, 2> x("987608548588589");
 		BigInt<20, 2> y("-6793564545455289");
 		BigInt<20, 2> z("-5805955996866700");
 
 		assert_equal(x+y, z);
 	}
 },
 {
 	.name = "BigInt difference",
 	.f = []() {
 		BigInt<20, 2> x("2342442323434134");
 		BigInt<20, 2> y("2524342523342342");
 		BigInt<20, 2> z("-181900199908208");
 
 		assert_equal(x-y, z);
 	}
 },
 {
 	.name = "BigInt product",
 	.f = []() {
 		BigInt<100, 3> x("134142345244134");
 		BigInt<100, 3> y("-56543047058245");
 		BigInt<100, 3> z("-7584816939642416135042584830");
 
 		assert_equal(x*y, z);
 	}
 },
 {
 	.name = "BigInt operator+=",
 	.f = []() {
 		BigInt<20, 2> x("987608548588589");
 		BigInt<20, 2> y("6793564545455289");
 		BigInt<20, 2> z("7781173094043878");
 
 		x += y;
 
 		assert_equal(x, z);
 	}
 },
 {
 	.name = "BigInt 14 / 3",
 	.f = []() {
 		BigInt x(14);
 		BigInt y(3);
 
 		assert_equal(x / y, 4);
 	}
 },
 {
 	.name = "BigInt 14 % 3",
 	.f = []() {
 		BigInt x(14);
 		BigInt y(3);
 
 		assert_equal(x % y, 2);
 	}
 },
 {
 	.name = "BigInt 14 / -3",
 	.f = []() {
 		BigInt x(14);
 		BigInt y(-3);
 
 		assert_equal(x / y, -5);
 	}
 },
 {
 	.name = "BigInt 14 % -3",
 	.f = []() {
 		BigInt x(14);
 		BigInt y(-3);
 
 		assert_equal(x % y, -1);
 	}
 },
 {
 	.name = "BigInt -14 / 3",
 	.f = []() {
 		BigInt x(-14);
 		BigInt y(3);
 
 		assert_equal(x / y, -5);
 	}
 },
 {
 	.name = "BigInt -14 % 3",
 	.f = []() {
 		BigInt x(-14);
 		BigInt y(3);
 
 		assert_equal(x % y, 1);
 	}
 },
 {
 	.name = "BigInt -14 / -3",
 	.f = []() {
 		BigInt x(-14);
 		BigInt y(-3);
 
 		assert_equal(x / y, 4);
 	}
 },
 {
 	.name = "BigInt -14 % -3",
 	.f = []() {
 		BigInt x(-14);
 		BigInt y(-3);
 
 		assert_equal(x % y, -2);
 	}
 },
 {
 	.name = "BigInt division large numbers, quotient = 0",
 	.f = []() {
 		BigInt<50, 3> x("4534435234134244242");
 		BigInt<50, 3> y("7832478748237487343");
 
 		assert_equal(x / y, 0);
 	}
 },
 {
 	.name = "BigInt division large numbers",
 	.f = []() {
 		BigInt<50, 3> x("12344534435234134244242");
 		BigInt<50, 3> y("7832478748237487343");
 		BigInt<50, 3> z(1576);
 
 		assert_equal(x / y, z);
 	}
 },
 {
 	.name = "BigInt modulo large numbers",
 	.f = []() {
 		BigInt<50, 3> x("12344534435234134244242");
 		BigInt<50, 3> y("7832478748237487343");
 		BigInt<50, 3> z("547928011854191674");
 
 		assert_equal(x % y, z);
 	}
 },
 {
 	.name = "Zmod with BigInt constructor",
 	.f = []() {
 		constexpr BigInt<50, 3> N("78923471");
 		constexpr BigInt<50, 3> x("145452451");
 		Zmod<N> xmodN(x);
 
 		assert_equal(xmodN.toint(), x % N);
 	}
 },
 {
 	.name = "Zmod with BigInt big inverse",
 	.f = []() {
 		constexpr BigInt<50, 3> N("7520824651249795349285");
 		constexpr BigInt<50, 3> x("234589234599896924596");
 		constexpr BigInt<50, 3> expected("5901181270843786267351");
 		Zmod<N> xmodN(x);
 
 		auto inv = xmodN.inverse();
 
 		assert_equal(inv.has_value(), true);
 		assert_equal(inv.value().toint(), expected);
 	}
 },
 #if defined(__clang__) && __clang_major__ >= 16
 {
 	.name = "Zmod with BitInt",
 	.f = []() {
 		constexpr BitInt N{1000000000000LL}; // 1e12
 		BitInt a{600000000000LL}; // 6e11
 		BitInt b{700000000000LL}; // 7e11
 		BitInt c{300000000000LL}; // 3e11
 
 		Zmod<N> a_modN(a), b_modN(b), c_modN(c);
 		assert_equal(a_modN + b_modN, c_modN);
 	}
 },
 #endif
 /*
 {
 	.name = "This does not compile",
 	.f = []() {
 		constexpr double N = 1.2;
 		Zmod<N> x;
 	}
 }
 */
 };
 
 int main() {
 	for (auto t : tests) {
 		std::cout << t.name << ": ";
 		t.f();
 		std::cout << "OK" << std::endl;
 	}
 	std::cout << "All tests passed" << std::endl;
 	return 0;
 }