From 9a337c68ff0ac8c1cd18be2917318f273af7d8a0 Mon Sep 17 00:00:00 2001 From: tomsmeding Date: Wed, 12 Oct 2016 23:10:29 +0200 Subject: Comment bigint (and fix indentation in gf28) --- bigint.h | 41 +++++++++++++++++++++++------------------ 1 file changed, 23 insertions(+), 18 deletions(-) (limited to 'bigint.h') diff --git a/bigint.h b/bigint.h index a3c5be3..cff7bd4 100644 --- a/bigint.h +++ b/bigint.h @@ -6,24 +6,30 @@ #include #include +//A bigint implementation based on unsigned 32-bit digits. +//The implementation relies on having native 64-bit arithmetic (or specifically, +//(2*digit_bits)-bit arithmetic). class Bigint{ public: typedef uint32_t digit_t; - typedef int32_t sdigit_t; - typedef uint64_t longdigit_t; - typedef int64_t slongdigit_t; + typedef int32_t sdigit_t; //signed version + typedef uint64_t longdigit_t; //should be twice as large as digit_t + typedef int64_t slongdigit_t; //signed version static const int digit_bits=8*sizeof(digit_t); private: - std::vector digits; - int sign; + std::vector digits; //little-endian order + int sign; //-1 for negative, 1 for positive; -0 is not a valid state static void add(Bigint&,const Bigint&); //ignores sign of arguments - static void subtract(Bigint&,const Bigint&); //ignores sign of arguments; assumes a>=b + static void subtract(Bigint&,const Bigint&); //ignores sign of arguments static Bigint product(const Bigint&,const Bigint&); - void shrink(); - void normalise(); + void shrink(); //prune unnecessary zero digits on top + void normalise(); //make sure -0 doesn't occur + + //This function is called from all relevant return points of the member functions. It's + //basically a debug check, but it can't hurt to have it since it takes few cpu cycles. void checkconsistent(); std::pair divmod(const Bigint&,int depth,int maxdepth) const; //ignores all signs @@ -32,8 +38,9 @@ public: Bigint(); Bigint(const Bigint&)=default; Bigint(Bigint&&); - explicit Bigint(const std::string&); - explicit Bigint(sdigit_t); + + explicit Bigint(const std::string&); //Initialise with a large value + explicit Bigint(sdigit_t); //Initialise with a small value explicit Bigint(digit_t); explicit Bigint(slongdigit_t); explicit Bigint(longdigit_t); @@ -54,6 +61,8 @@ public: Bigint& operator<<=(int); Bigint& operator>>=(int); Bigint& negate(); + //Division and modulo operators are explicitly NOT included, to promote clever usage + //of the divmod function, which combines both. Bigint operator+(const Bigint&) const; Bigint operator-(const Bigint&) const; @@ -93,22 +102,18 @@ public: bool odd() const; std::string serialiseMantissa() const; //stores everything but the sign - - //restores non-negative number; can throw invalid_argument - void deserialiseMantissa(const std::string&); - std::vector bits() const; + void deserialiseMantissa(const std::string&); //restores non-negative number; can throw invalid_argument + std::vector bits() const; //Stores bits in little-endian order friend std::istream& operator>>(std::istream&,Bigint&); friend std::ostream& operator<<(std::ostream&,Bigint); - digit_t _digit(int idx) const; - - static Bigint mone; + static Bigint mone; //Some small values to save a constructor call static Bigint zero; static Bigint one; static Bigint two; }; std::istream& operator>>(std::istream&,Bigint&); -std::ostream& operator<<(std::ostream&,Bigint); +std::ostream& operator<<(std::ostream&,Bigint); //The output operator supports the `hex` modifier -- cgit v1.2.3-70-g09d2