Initial check in of big integer library

third_party/bigint/BigInteger.hh

+#ifndef BIGINTEGER_H
+#define BIGINTEGER_H
+
+#include "BigUnsigned.hh"
+
+/* A BigInteger object represents a signed integer of size limited only by
+ * available memory.  BigUnsigneds support most mathematical operators and can
+ * be converted to and from most primitive integer types.
+ *
+ * A BigInteger is just an aggregate of a BigUnsigned and a sign.  (It is no
+ * longer derived from BigUnsigned because that led to harmful implicit
+ * conversions.) */
+class BigInteger {
+
+public:
+        typedef BigUnsigned::Blk Blk;
+        typedef BigUnsigned::Index Index;
+        typedef BigUnsigned::CmpRes CmpRes;
+        static const CmpRes
+                less    = BigUnsigned::less   ,
+                equal   = BigUnsigned::equal  ,
+                greater = BigUnsigned::greater;
+        // Enumeration for the sign of a BigInteger.
+        enum Sign { negative = -1, zero = 0, positive = 1 };
+
+protected:
+        Sign sign;
+        BigUnsigned mag;
+
+public:
+        // Constructs zero.
+        BigInteger() : sign(zero), mag() {}
+
+        // Copy constructor
+        BigInteger(const BigInteger &x) : sign(x.sign), mag(x.mag) {};
+
+        // Assignment operator
+        void operator=(const BigInteger &x);
+
+        // Constructor that copies from a given array of blocks with a sign.
+        BigInteger(const Blk *b, Index blen, Sign s);
+
+        // Nonnegative constructor that copies from a given array of blocks.
+        BigInteger(const Blk *b, Index blen) : mag(b, blen) {
+                sign = mag.isZero() ? zero : positive;
+        }
+
+        // Constructor from a BigUnsigned and a sign
+        BigInteger(const BigUnsigned &x, Sign s);
+
+        // Nonnegative constructor from a BigUnsigned
+        BigInteger(const BigUnsigned &x) : mag(x) {
+                sign = mag.isZero() ? zero : positive;
+        }
+
+        // Constructors from primitive integer types
+        BigInteger(unsigned long  x);
+        BigInteger(         long  x);
+        BigInteger(unsigned int   x);
+        BigInteger(         int   x);
+        BigInteger(unsigned short x);
+        BigInteger(         short x);
+
+        /* Converters to primitive integer types
+         * The implicit conversion operators caused trouble, so these are now
+         * named. */
+        unsigned long  toUnsignedLong () const;
+        long           toLong         () const;
+        unsigned int   toUnsignedInt  () const;
+        int            toInt          () const;
+        unsigned short toUnsignedShort() const;
+        short          toShort        () const;
+protected:
+        // Helper
+        template <class X> X convertToUnsignedPrimitive() const;
+        template <class X, class UX> X convertToSignedPrimitive() const;
+public:
+
+        // ACCESSORS
+        Sign getSign() const { return sign; }
+        /* The client can't do any harm by holding a read-only reference to the
+         * magnitude. */
+        const BigUnsigned &getMagnitude() const { return mag; }
+
+        // Some accessors that go through to the magnitude
+        Index getLength() const { return mag.getLength(); }
+        Index getCapacity() const { return mag.getCapacity(); }
+        Blk getBlock(Index i) const { return mag.getBlock(i); }
+        bool isZero() const { return sign == zero; } // A bit special
+
+        // COMPARISONS
+
+        // Compares this to x like Perl's <=>
+        CmpRes compareTo(const BigInteger &x) const;
+
+        // Ordinary comparison operators
+        bool operator ==(const BigInteger &x) const {
+                return sign == x.sign && mag == x.mag;
+        }
+        bool operator !=(const BigInteger &x) const { return !operator ==(x); };
+        bool operator < (const BigInteger &x) const { return compareTo(x) == less   ; }
+        bool operator <=(const BigInteger &x) const { return compareTo(x) != greater; }
+        bool operator >=(const BigInteger &x) const { return compareTo(x) != less   ; }
+        bool operator > (const BigInteger &x) const { return compareTo(x) == greater; }
+
+        // OPERATORS -- See the discussion in BigUnsigned.hh.
+        void add     (const BigInteger &a, const BigInteger &b);
+        void subtract(const BigInteger &a, const BigInteger &b);
+        void multiply(const BigInteger &a, const BigInteger &b);
+        /* See the comment on BigUnsigned::divideWithRemainder.  Semantics
+         * differ from those of primitive integers when negatives and/or zeros
+         * are involved. */
+        void divideWithRemainder(const BigInteger &b, BigInteger &q);
+        void negate(const BigInteger &a);
+        
+        /* Bitwise operators are not provided for BigIntegers.  Use
+         * getMagnitude to get the magnitude and operate on that instead. */
+
+        BigInteger operator +(const BigInteger &x) const;
+        BigInteger operator -(const BigInteger &x) const;
+        BigInteger operator *(const BigInteger &x) const;
+        BigInteger operator /(const BigInteger &x) const;
+        BigInteger operator %(const BigInteger &x) const;
+        BigInteger operator -() const;
+
+        void operator +=(const BigInteger &x);
+        void operator -=(const BigInteger &x);
+        void operator *=(const BigInteger &x);
+        void operator /=(const BigInteger &x);
+        void operator %=(const BigInteger &x);
+        void flipSign();
+
+        // INCREMENT/DECREMENT OPERATORS
+        void operator ++(   );
+        void operator ++(int);
+        void operator --(   );
+        void operator --(int);
+};
+
+// NORMAL OPERATORS
+/* These create an object to hold the result and invoke
+ * the appropriate put-here operation on it, passing
+ * this and x.  The new object is then returned. */
+inline BigInteger BigInteger::operator +(const BigInteger &x) const {
+        BigInteger ans;
+        ans.add(*this, x);
+        return ans;
+}
+inline BigInteger BigInteger::operator -(const BigInteger &x) const {
+        BigInteger ans;
+        ans.subtract(*this, x);
+        return ans;
+}
+inline BigInteger BigInteger::operator *(const BigInteger &x) const {
+        BigInteger ans;
+        ans.multiply(*this, x);
+        return ans;
+}
+inline BigInteger BigInteger::operator /(const BigInteger &x) const {
+        if (x.isZero()) throw "BigInteger::operator /: division by zero";
+        BigInteger q, r;
+        r = *this;
+        r.divideWithRemainder(x, q);
+        return q;
+}
+inline BigInteger BigInteger::operator %(const BigInteger &x) const {
+        if (x.isZero()) throw "BigInteger::operator %: division by zero";
+        BigInteger q, r;
+        r = *this;
+        r.divideWithRemainder(x, q);
+        return r;
+}
+inline BigInteger BigInteger::operator -() const {
+        BigInteger ans;
+        ans.negate(*this);
+        return ans;
+}
+
+/*
+ * ASSIGNMENT OPERATORS
+ * 
+ * Now the responsibility for making a temporary copy if necessary
+ * belongs to the put-here operations.  See Assignment Operators in
+ * BigUnsigned.hh.
+ */
+inline void BigInteger::operator +=(const BigInteger &x) {
+        add(*this, x);
+}
+inline void BigInteger::operator -=(const BigInteger &x) {
+        subtract(*this, x);
+}
+inline void BigInteger::operator *=(const BigInteger &x) {
+        multiply(*this, x);
+}
+inline void BigInteger::operator /=(const BigInteger &x) {
+        if (x.isZero()) throw "BigInteger::operator /=: division by zero";
+        /* The following technique is slightly faster than copying *this first
+         * when x is large. */
+        BigInteger q;
+        divideWithRemainder(x, q);
+        // *this contains the remainder, but we overwrite it with the quotient.
+        *this = q;
+}
+inline void BigInteger::operator %=(const BigInteger &x) {
+        if (x.isZero()) throw "BigInteger::operator %=: division by zero";
+        BigInteger q;
+        // Mods *this by x.  Don't care about quotient left in q.
+        divideWithRemainder(x, q);
+}
+// This one is trivial
+inline void BigInteger::flipSign() {
+        sign = Sign(-sign);
+}
+
+#endif