BigInteger.hh

   1 #ifndef BIGINTEGER_H
   2 #define BIGINTEGER_H
   3
   4 #include "BigUnsigned.hh"
   5
   6 /* A BigInteger object represents a signed integer of size limited only by
   7  * available memory.  BigUnsigneds support most mathematical operators and can
   8  * be converted to and from most primitive integer types.
   9  *
  10  * A BigInteger is just an aggregate of a BigUnsigned and a sign.  (It is no
  11  * longer derived from BigUnsigned because that led to harmful implicit
  12  * conversions.) */
  13 class BigInteger {
  14
  15 public:
  16         typedef BigUnsigned::Blk Blk;
  17         typedef BigUnsigned::Index Index;
  18         typedef BigUnsigned::CmpRes CmpRes;
  19         static const CmpRes
  20                 less    = BigUnsigned::less   ,
  21                 equal   = BigUnsigned::equal  ,
  22                 greater = BigUnsigned::greater;
  23         // Enumeration for the sign of a BigInteger.
  24         enum Sign { negative = -1, zero = 0, positive = 1 };
  25
  26 protected:
  27         Sign sign;
  28         BigUnsigned mag;
  29
  30 public:
  31         // Constructs zero.
  32         BigInteger() : sign(zero), mag() {}
  33
  34         // Copy constructor
  35         BigInteger(const BigInteger &x) : sign(x.sign), mag(x.mag) {};
  36
  37         // Assignment operator
  38         void operator=(const BigInteger &x);
  39
  40         // Constructor that copies from a given array of blocks with a sign.
  41         BigInteger(const Blk *b, Index blen, Sign s);
  42
  43         // Nonnegative constructor that copies from a given array of blocks.
  44         BigInteger(const Blk *b, Index blen) : mag(b, blen) {
  45                 sign = mag.isZero() ? zero : positive;
  46         }
  47
  48         // Constructor from a BigUnsigned and a sign
  49         BigInteger(const BigUnsigned &x, Sign s);
  50
  51         // Nonnegative constructor from a BigUnsigned
  52         BigInteger(const BigUnsigned &x) : mag(x) {
  53                 sign = mag.isZero() ? zero : positive;
  54         }
  55
  56         // Constructors from primitive integer types
  57         BigInteger(unsigned long  x);
  58         BigInteger(         long  x);
  59         BigInteger(unsigned int   x);
  60         BigInteger(         int   x);
  61         BigInteger(unsigned short x);
  62         BigInteger(         short x);
  63
  64         /* Converters to primitive integer types
  65          * The implicit conversion operators caused trouble, so these are now
  66          * named. */
  67         unsigned long  toUnsignedLong () const;
  68         long           toLong         () const;
  69         unsigned int   toUnsignedInt  () const;
  70         int            toInt          () const;
  71         unsigned short toUnsignedShort() const;
  72         short          toShort        () const;
  73 protected:
  74         // Helper
  75         template <class X> X convertToUnsignedPrimitive() const;
  76         template <class X, class UX> X convertToSignedPrimitive() const;
  77 public:
  78
  79         // ACCESSORS
  80         Sign getSign() const { return sign; }
  81         /* The client can't do any harm by holding a read-only reference to the
  82          * magnitude. */
  83         const BigUnsigned &getMagnitude() const { return mag; }
  84
  85         // Some accessors that go through to the magnitude
  86         Index getLength() const { return mag.getLength(); }
  87         Index getCapacity() const { return mag.getCapacity(); }
  88         Blk getBlock(Index i) const { return mag.getBlock(i); }
  89         bool isZero() const { return sign == zero; } // A bit special
  90
  91         // COMPARISONS
  92
  93         // Compares this to x like Perl's <=>
  94         CmpRes compareTo(const BigInteger &x) const;
  95
  96         // Ordinary comparison operators
  97         bool operator ==(const BigInteger &x) const {
  98                 return sign == x.sign && mag == x.mag;
  99         }
 100         bool operator !=(const BigInteger &x) const { return !operator ==(x); };
 101         bool operator < (const BigInteger &x) const { return compareTo(x) == less   ; }
 102         bool operator <=(const BigInteger &x) const { return compareTo(x) != greater; }
 103         bool operator >=(const BigInteger &x) const { return compareTo(x) != less   ; }
 104         bool operator > (const BigInteger &x) const { return compareTo(x) == greater; }
 105
 106         // OPERATORS -- See the discussion in BigUnsigned.hh.
 107         void add     (const BigInteger &a, const BigInteger &b);
 108         void subtract(const BigInteger &a, const BigInteger &b);
 109         void multiply(const BigInteger &a, const BigInteger &b);
 110         /* See the comment on BigUnsigned::divideWithRemainder.  Semantics
 111          * differ from those of primitive integers when negatives and/or zeros
 112          * are involved. */
 113         void divideWithRemainder(const BigInteger &b, BigInteger &q);
 114         void negate(const BigInteger &a);
 115
 116         /* Bitwise operators are not provided for BigIntegers.  Use
 117          * getMagnitude to get the magnitude and operate on that instead. */
 118
 119         BigInteger operator +(const BigInteger &x) const;
 120         BigInteger operator -(const BigInteger &x) const;
 121         BigInteger operator *(const BigInteger &x) const;
 122         BigInteger operator /(const BigInteger &x) const;
 123         BigInteger operator %(const BigInteger &x) const;
 124         BigInteger operator -() const;
 125
 126         void operator +=(const BigInteger &x);
 127         void operator -=(const BigInteger &x);
 128         void operator *=(const BigInteger &x);
 129         void operator /=(const BigInteger &x);
 130         void operator %=(const BigInteger &x);
 131         void flipSign();
 132
 133         // INCREMENT/DECREMENT OPERATORS
 134         void operator ++(   );
 135         void operator ++(int);
 136         void operator --(   );
 137         void operator --(int);
 138 };
 139
 140 // NORMAL OPERATORS
 141 /* These create an object to hold the result and invoke
 142  * the appropriate put-here operation on it, passing
 143  * this and x.  The new object is then returned. */
 144 inline BigInteger BigInteger::operator +(const BigInteger &x) const {
 145         BigInteger ans;
 146         ans.add(*this, x);
 147         return ans;
 148 }
 149 inline BigInteger BigInteger::operator -(const BigInteger &x) const {
 150         BigInteger ans;
 151         ans.subtract(*this, x);
 152         return ans;
 153 }
 154 inline BigInteger BigInteger::operator *(const BigInteger &x) const {
 155         BigInteger ans;
 156         ans.multiply(*this, x);
 157         return ans;
 158 }
 159 inline BigInteger BigInteger::operator /(const BigInteger &x) const {
 160         if (x.isZero()) throw "BigInteger::operator /: division by zero";
 161         BigInteger q, r;
 162         r = *this;
 163         r.divideWithRemainder(x, q);
 164         return q;
 165 }
 166 inline BigInteger BigInteger::operator %(const BigInteger &x) const {
 167         if (x.isZero()) throw "BigInteger::operator %: division by zero";
 168         BigInteger q, r;
 169         r = *this;
 170         r.divideWithRemainder(x, q);
 171         return r;
 172 }
 173 inline BigInteger BigInteger::operator -() const {
 174         BigInteger ans;
 175         ans.negate(*this);
 176         return ans;
 177 }
 178
 179 /*
 180  * ASSIGNMENT OPERATORS
 181  *
 182  * Now the responsibility for making a temporary copy if necessary
 183  * belongs to the put-here operations.  See Assignment Operators in
 184  * BigUnsigned.hh.
 185  */
 186 inline void BigInteger::operator +=(const BigInteger &x) {
 187         add(*this, x);
 188 }
 189 inline void BigInteger::operator -=(const BigInteger &x) {
 190         subtract(*this, x);
 191 }
 192 inline void BigInteger::operator *=(const BigInteger &x) {
 193         multiply(*this, x);
 194 }
 195 inline void BigInteger::operator /=(const BigInteger &x) {
 196         if (x.isZero()) throw "BigInteger::operator /=: division by zero";
 197         /* The following technique is slightly faster than copying *this first
 198          * when x is large. */
 199         BigInteger q;
 200         divideWithRemainder(x, q);
 201         // *this contains the remainder, but we overwrite it with the quotient.
 202         *this = q;
 203 }
 204 inline void BigInteger::operator %=(const BigInteger &x) {
 205         if (x.isZero()) throw "BigInteger::operator %=: division by zero";
 206         BigInteger q;
 207         // Mods *this by x.  Don't care about quotient left in q.
 208         divideWithRemainder(x, q);
 209 }
 210 // This one is trivial
 211 inline void BigInteger::flipSign() {
 212         sign = Sign(-sign);
 213 }
 214
 215 #endif