BigInteger.hh

   1 #ifndef BIGINTEGER_H
   2 #define BIGINTEGER_H
   3
   4 #include "BigUnsigned.hh"
   5
   6 /*
   7  * A BigInteger object represents a signed integer of size
   8  * limited only by available memory.  A BigInteger can be
   9  * created from and converted back to most integral types,
  10  * and many math operations are defined on BigIntegers.
  11  *
  12  * The number is stored as a series of blocks in a
  13  * dynamically allocated array.  It is as if the number
  14  * were written digit by digit in base 2 ^ N, **where N is the
  15  * number of bits in an unsigned long.**
  16  *
  17  * This class is derived from BigUnsigned, which represents
  18  * a large nonnegative integer.  BigUnsigned should be studied
  19  * first, as only new or different things are declared here.
  20  * Some things are redeclared so that they use the BigInteger
  21  * versions of methods, rather than the BigUnsigned versions.
  22  */
  23
  24 class BigInteger : public BigUnsigned {
  25
  26         // TYPES & CONSTANTS
  27         public:
  28         enum Sign { negative = -1, zero = 0, positive = 1 }; // Enumeration for the sign of a BigInteger
  29
  30         // FIELDS
  31         protected:
  32         Sign sign; // The sign of this BigInteger
  33
  34         // MANAGEMENT
  35         protected:
  36         BigInteger(Sign s, Index c) : BigUnsigned(0, c), sign(s) {}; // Creates a BigInteger with a sign and capacity
  37         public:
  38
  39         BigInteger() : BigUnsigned(), sign(zero) {} // Default constructor (value is 0)
  40         BigInteger(const BigInteger &x) : BigUnsigned(x), sign(x.sign) {}; // Copy constructor
  41         void operator=(const BigInteger &x); // Assignment operator
  42         BigInteger(const Blk *b, Index l) : BigUnsigned(b, l) { // Constructor from an array of blocks
  43                 sign = (len == 0) ? zero : positive;
  44         }
  45         BigInteger(const Blk *b, Index l, Sign s); // Constructor from an array of blocks and a sign
  46         BigInteger(const BigUnsigned &x) : BigUnsigned(x) { // Constructor from a BigUnsigned
  47                 sign = (len == 0) ? zero : positive;
  48         }
  49         BigInteger(const BigUnsigned &x, Sign s); // Constructor from a BigUnsigned and a sign
  50         // Constructors from integral types
  51         BigInteger(unsigned long  x);
  52         BigInteger(         long  x);
  53         BigInteger(unsigned int   x);
  54         BigInteger(         int   x);
  55         BigInteger(unsigned short x);
  56         BigInteger(         short x);
  57         // Note that a BigInteger can be converted to a BigUnsigned
  58         // automatically; this takes its absolute value.
  59
  60         // CONVERTERS to integral types
  61         public:
  62         operator unsigned long () const;
  63         operator          long () const;
  64         operator unsigned int  () const;
  65         operator          int  () const;
  66         operator unsigned short() const;
  67         operator          short() const;
  68
  69         // PICKING APART
  70         // These accessors can be used to get the pieces of the number
  71         public:
  72         Sign getSign() const;
  73
  74         // COMPARISONS
  75         public:
  76         // Compares this to x like Perl's <=>
  77         CmpRes compareTo(const BigInteger &x) const;
  78         // Normal comparison operators
  79         bool operator ==(const BigInteger &x) const {
  80                 return sign == x.sign && BigUnsigned::operator ==(x);
  81         }
  82         bool operator !=(const BigInteger &x) const { return !operator ==(x); };
  83         bool operator < (const BigInteger &x) const { return compareTo(x) == less   ; }
  84         bool operator <=(const BigInteger &x) const { return compareTo(x) != greater; }
  85         bool operator >=(const BigInteger &x) const { return compareTo(x) != less   ; }
  86         bool operator > (const BigInteger &x) const { return compareTo(x) == greater; }
  87
  88         // PUT-HERE OPERATIONS
  89         /* These store the result of the operation on the arguments into this.
  90          * a.add(b, c) is equivalent to, but faster than, a = b + c.
  91          * See explanation of "put-here operations" in BigUnsigned.cc . */
  92         public:
  93         void add     (const BigInteger &a, const BigInteger &b); // Addition
  94         void subtract(const BigInteger &a, const BigInteger &b); // Subtraction
  95         void multiply(const BigInteger &a, const BigInteger &b); // Multiplication
  96         /* Divisive stuff
  97          * `a.divideWithRemainder(b, q)' is like `q = a / b, a %= b'.
  98          * Semantics similar to Donald E. Knuth's are used for / and %,
  99          * and these usually differ from the semantics of primitive-type
 100          * / and % when negatives and/or zeroes are involved.
 101          * Look in `BigInteger.cc' for details.
 102          * `a.divideWithRemainder(b, a)' causes an exception: it doesn't make
 103          * sense to write quotient and remainder into the same variable.
 104          */
 105         void divideWithRemainder(const BigInteger &b, BigInteger &q);
 106         void divide(const BigInteger &a, const BigInteger &b) {
 107                 BigInteger a2(a);
 108                 a2.divideWithRemainder(b, *this);
 109                 // quotient now in *this
 110                 // don't care about remainder left in a2
 111         }
 112         void modulo(const BigInteger &a, const BigInteger &b) {
 113                 *this = a;
 114                 BigInteger q;
 115                 divideWithRemainder(b, q);
 116                 // remainder now in *this
 117                 // don't care about quotient left in q
 118         }
 119         void negate(const BigInteger &a); // Negative
 120         // Some operations are inherently unsigned and are not
 121         // redefined for BigIntegers.  Calling one of these on
 122         // a BigInteger will convert it to a BigUnsigned,
 123         // which takes its absolute value.
 124
 125         // NORMAL OPERATORS
 126         // These perform the operation on this (to the left of the operator)
 127         // and x (to the right of the operator) and return a new BigInteger with the result.
 128         public:
 129         BigInteger operator +(const BigInteger &x) const; // Addition
 130         BigInteger operator -(const BigInteger &x) const; // Subtraction
 131         BigInteger operator *(const BigInteger &x) const; // Multiplication
 132         BigInteger operator /(const BigInteger &x) const; // Division
 133         BigInteger operator %(const BigInteger &x) const; // Modular reduction
 134         BigInteger operator -(                   ) const; // Negative
 135
 136         // ASSIGNMENT OPERATORS
 137         // These perform the operation on this and x, storing the result into this.
 138         public:
 139         void operator +=(const BigInteger &x); // Addition
 140         void operator -=(const BigInteger &x); // Subtraction
 141         void operator *=(const BigInteger &x); // Multiplication
 142         void operator /=(const BigInteger &x); // Division
 143         void operator %=(const BigInteger &x); // Modular reduction
 144         void flipSign();                       // Negative
 145
 146         // INCREMENT/DECREMENT OPERATORS
 147         // These increase or decrease the number by 1.  To discourage side effects,
 148         // these do not return *this, so prefix and postfix behave the same.
 149         public:
 150         void operator ++(   ); // Prefix  increment
 151         void operator ++(int); // Postfix decrement
 152         void operator --(   ); // Prefix  increment
 153         void operator --(int); // Postfix decrement
 154
 155 };
 156
 157 // PICKING APART
 158 inline BigInteger::Sign BigInteger::getSign() const { return sign; }
 159
 160 // NORMAL OPERATORS
 161 /* These create an object to hold the result and invoke
 162  * the appropriate put-here operation on it, passing
 163  * this and x.  The new object is then returned. */
 164 inline BigInteger BigInteger::operator +(const BigInteger &x) const {
 165         BigInteger ans;
 166         ans.add(*this, x);
 167         return ans;
 168 }
 169 inline BigInteger BigInteger::operator -(const BigInteger &x) const {
 170         BigInteger ans;
 171         ans.subtract(*this, x);
 172         return ans;
 173 }
 174 inline BigInteger BigInteger::operator *(const BigInteger &x) const {
 175         BigInteger ans;
 176         ans.multiply(*this, x);
 177         return ans;
 178 }
 179 inline BigInteger BigInteger::operator /(const BigInteger &x) const {
 180         BigInteger ans;
 181         ans.divide(*this, x);
 182         return ans;
 183 }
 184 inline BigInteger BigInteger::operator %(const BigInteger &x) const {
 185         BigInteger ans;
 186         ans.modulo(*this, x);
 187         return ans;
 188 }
 189 inline BigInteger BigInteger::operator -() const {
 190         BigInteger ans;
 191         ans.negate(*this);
 192         return ans;
 193 }
 194
 195 /*
 196  * ASSIGNMENT OPERATORS
 197  *
 198  * Now the responsibility for making a temporary copy if necessary
 199  * belongs to the put-here operations.  See Assignment Operators in
 200  * BigUnsigned.hh.
 201  */
 202 inline void BigInteger::operator +=(const BigInteger &x) {
 203         add(*this, x);
 204 }
 205 inline void BigInteger::operator -=(const BigInteger &x) {
 206         subtract(*this, x);
 207 }
 208 inline void BigInteger::operator *=(const BigInteger &x) {
 209         multiply(*this, x);
 210 }
 211 inline void BigInteger::operator /=(const BigInteger &x) {
 212         // Updated for divideWithRemainder
 213         BigInteger thisCopy(*this);
 214         thisCopy.divideWithRemainder(x, *this);
 215         // quotient left in *this
 216         // don't care about remainder left in thisCopy
 217 }
 218 inline void BigInteger::operator %=(const BigInteger &x) {
 219         // Shortcut (woohoo!)
 220         BigInteger q;
 221         divideWithRemainder(x, q);
 222         // remainder left in *this
 223         // don't care about quotient left in q
 224 }
 225 // This one is trivial
 226 inline void BigInteger::flipSign() {
 227         sign = Sign(-sign);
 228 }
 229
 230 #endif