Initial

1 files changed, 87 insertions, 0 deletions

diff --git a/bigint.h b/bigint.h
new file mode 100644
index 0000000..6579054
--- /dev/null
+++ b/bigint.h
@@ -0,0 +1,87 @@
+#pragma once
+
+#include <iostream>
+#include <vector>
+#include <utility>
+#include <cstdint>
+
+class Bigint{
+public:
+	using digit_t=uint32_t;
+	using longdigit_t=uint64_t;
+	using slongdigit_t=int64_t;
+	static const int digit_bits=8*sizeof(digit_t);
+
+private:
+	std::vector<digit_t> digits;
+	int sign;
+
+	static void add(Bigint&,const Bigint&); //ignores sign of arguments
+	static void subtract(Bigint&,const Bigint&); //ignores sign of arguments; assumes a>=b
+	static Bigint product(const Bigint&,const Bigint&);
+
+	void shrink();
+	void normalise();
+	void checkconsistent();
+
+	std::pair<Bigint,Bigint> divmod(const Bigint&,int depth) const;
+
+public:
+	Bigint();
+	Bigint(const Bigint&)=default;
+	Bigint(Bigint&&)=default;
+	explicit Bigint(slongdigit_t);
+
+	Bigint& operator=(const Bigint&)=default;
+	Bigint& operator=(Bigint&&)=default;
+	Bigint& operator=(slongdigit_t);
+
+	Bigint& operator+=(const Bigint&);
+	Bigint& operator-=(const Bigint&);
+	Bigint& operator*=(const Bigint&);
+	Bigint& operator<<=(int);
+	Bigint& operator>>=(int);
+	Bigint& negate();
+
+	Bigint operator+(const Bigint&) const;
+	Bigint operator-(const Bigint&) const;
+	Bigint operator*(const Bigint&) const;
+	Bigint operator<<(int) const;
+	Bigint operator>>(int) const;
+	std::pair<Bigint,Bigint> divmod(const Bigint&) const;
+
+	bool operator==(const Bigint&) const;
+	bool operator!=(const Bigint&) const;
+	bool operator<(const Bigint&) const;
+	bool operator>(const Bigint&) const;
+	bool operator<=(const Bigint&) const;
+	bool operator>=(const Bigint&) const;
+	bool operator==(slongdigit_t) const;
+	bool operator!=(slongdigit_t) const;
+	bool operator<(slongdigit_t) const;
+	bool operator>(slongdigit_t) const;
+	bool operator<=(slongdigit_t) const;
+	bool operator>=(slongdigit_t) const;
+
+	int compare(const Bigint&) const; //-1: <; 0: ==; 1: >
+	int compare(slongdigit_t) const;
+	int compareAbs(const Bigint&) const; //-1: <; 0: ==; 1: >; disregards sign
+	int compareAbs(slongdigit_t) const;
+
+	int bitcount() const;
+	slongdigit_t lowdigits() const;
+
+	std::vector<char> serialise() const;
+	void deserialise(const std::vector<char>&);
+	std::vector<bool> bits() const;
+
+	friend std::istream& operator>>(std::istream&,Bigint&);
+	friend std::ostream& operator<<(std::ostream&,Bigint);
+
+	digit_t _digit(int idx) const;
+};
+
+Bigint pow(const Bigint &b,const Bigint &ex);
+
+std::istream& operator>>(std::istream&,Bigint&);
+std::ostream& operator<<(std::ostream&,Bigint);