BigInteger.hh

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