summaryrefslogtreecommitdiff
path: root/third_party/bigint/BigInteger.hh
diff options
context:
space:
mode:
Diffstat (limited to 'third_party/bigint/BigInteger.hh')
-rw-r--r--third_party/bigint/BigInteger.hh215
1 files changed, 215 insertions, 0 deletions
diff --git a/third_party/bigint/BigInteger.hh b/third_party/bigint/BigInteger.hh
new file mode 100644
index 0000000000..cf6e91056f
--- /dev/null
+++ b/third_party/bigint/BigInteger.hh
@@ -0,0 +1,215 @@
+#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