BigInteger.h

   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.h"
  10
  11 /*
  12 *
  13 * A BigInteger object represents a signed integer of size
  14 * limited only by available memory.  A BigInteger can be
  15 * created from and converted back to most integral types,
  16 * and many math operations are defined on them.
  17 *
  18 * The number is stored as a series of blocks in a
  19 * dynamically allocated array.  It is as if the numbers
  20 * were written digit by digit in base 2^32.
  21 *
  22 * This class is derived from BigUnsigned, which represents
  23 * a large nonnegative integer.  This should be understood
  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, BlkNum c); // Creates a BigInteger with a sign and capacity
  42         public:
  43         BigInteger(); // Default constructor (value is 0)
  44         BigInteger(const BigInteger &x); // Copy constructor
  45         void operator=(const BigInteger &x); // Assignment operator
  46         BigInteger(const Blk *b, BlkNum l); // Constructor from an array of blocks
  47         BigInteger(const Blk *b, BlkNum l, Sign s); // Constructor from an array of blocks and a sign
  48         BigInteger(const BigUnsigned &x); // Constructor from a BigUnsigned
  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         bool operator !=(const BigInteger &x) const;
  81         bool operator < (const BigInteger &x) const;
  82         bool operator <=(const BigInteger &x) const;
  83         bool operator >=(const BigInteger &x) const;
  84         bool operator > (const BigInteger &x) const;
  85
  86         // PUT-HERE OPERATIONS
  87         /* These store the result of the operation on the arguments into this.
  88         * a.add(b, c) is equivalent to, but faster than, a = b + c.
  89         * Calls like a.operation(a, b) are unsafe and not allowed. */
  90         public:
  91         void add     (const BigInteger &a, const BigInteger &b); // Addition
  92         void subtract(const BigInteger &a, const BigInteger &b); // Subtraction
  93         void multiply(const BigInteger &a, const BigInteger &b); // Multiplication
  94         void divide  (const BigInteger &a, const BigInteger &b); // Division
  95         void modulo  (const BigInteger &a, const BigInteger &b); // Modular reduction
  96         void negate  (const BigInteger &a                     ); // Negative
  97         // Some operations are inherently unsigned and are not
  98         // redefined for BigIntegers.  Calling one of these on
  99         // a BigInteger will take its absolute value first.
 100
 101         // NORMAL OPERATORS
 102         // These perform the operation on this (to the left of the operator)
 103         // and x (to the right of the operator) and return a new BigInteger with the result.
 104         public:
 105         BigInteger operator +(const BigInteger &x) const; // Addition
 106         BigInteger operator -(const BigInteger &x) const; // Subtraction
 107         BigInteger operator *(const BigInteger &x) const; // Multiplication
 108         BigInteger operator /(const BigInteger &x) const; // Division
 109         BigInteger operator %(const BigInteger &x) const; // Modular reduction
 110         BigInteger operator -(                   ) const; // Negative
 111
 112         // ASSIGNMENT OPERATORS
 113         // These perform the operation on this and x, storing the result into this.
 114         public:
 115         void operator +=(const BigInteger &x); // Addition
 116         void operator -=(const BigInteger &x); // Subtraction
 117         void operator *=(const BigInteger &x); // Multiplication
 118         void operator /=(const BigInteger &x); // Division
 119         void operator %=(const BigInteger &x); // Modular reduction
 120         void flipSign();                       // Negative
 121
 122         // INCREMENT/DECREMENT OPERATORS
 123         // These increase or decrease the number by 1.  To discourage side effects,
 124         // these do not return *this, so prefix and postfix behave the same.
 125         public:
 126         void operator ++(   ); // Prefix  increment
 127         void operator ++(int); // Postfix decrement
 128         void operator --(   ); // Prefix  increment
 129         void operator --(int); // Postfix decrement
 130
 131 };
 132
 133 // MANAGEMENT
 134 inline BigInteger::BigInteger(Sign s, BlkNum c) : BigUnsigned(0, c), sign(s) { }
 135 inline BigInteger::BigInteger() : BigUnsigned(), sign(zero) { }
 136 inline BigInteger::BigInteger(const BigInteger &x) : BigUnsigned(x), sign(x.sign) { }
 137 inline BigInteger::BigInteger(const Blk *b, BlkNum l) : BigUnsigned(b, l) { sign = (len == 0) ? zero : positive; }
 138 inline BigInteger::BigInteger(const BigUnsigned &x) : BigUnsigned(x) { sign = (len == 0) ? zero : positive; }
 139
 140 // PICKING APART
 141 inline BigInteger::Sign BigInteger::getSign() const { return sign; }
 142
 143 // COMPARISONS
 144 inline bool BigInteger::operator==(const BigInteger &x) const { return compareTo(x) == equal  ; }
 145 inline bool BigInteger::operator!=(const BigInteger &x) const { return compareTo(x) != equal  ; }
 146 inline bool BigInteger::operator< (const BigInteger &x) const { return compareTo(x) == less   ; }
 147 inline bool BigInteger::operator<=(const BigInteger &x) const { return compareTo(x) != greater; }
 148 inline bool BigInteger::operator>=(const BigInteger &x) const { return compareTo(x) != less   ; }
 149 inline bool BigInteger::operator> (const BigInteger &x) const { return compareTo(x) == greater; }
 150
 151 // NORMAL OPERATORS
 152 /* These create an object to hold the result and invoke
 153 * the appropriate put-here operation on it, passing
 154 * this and x.  The new object is then returned. */
 155 inline BigInteger BigInteger::operator +(const BigInteger &x) const {
 156         BigInteger ans;
 157         ans.add(*this, x);
 158         return ans;
 159 }
 160 inline BigInteger BigInteger::operator -(const BigInteger &x) const {
 161         BigInteger ans;
 162         ans.subtract(*this, x);
 163         return ans;
 164 }
 165 inline BigInteger BigInteger::operator *(const BigInteger &x) const {
 166         BigInteger ans;
 167         ans.multiply(*this, x);
 168         return ans;
 169 }
 170 inline BigInteger BigInteger::operator /(const BigInteger &x) const {
 171         BigInteger ans;
 172         ans.divide(*this, x);
 173         return ans;
 174 }
 175 inline BigInteger BigInteger::operator %(const BigInteger &x) const {
 176         BigInteger ans;
 177         ans.modulo(*this, x);
 178         return ans;
 179 }
 180 inline BigInteger BigInteger::operator -() const {
 181         BigInteger ans;
 182         ans.negate(*this);
 183         return ans;
 184 }
 185
 186 // ASSIGNMENT OPERATORS
 187 // These create a copy of this, then invoke the appropriate
 188 // put-here operation on this, passing the copy and x.
 189 inline void BigInteger::operator +=(const BigInteger &x) {
 190         BigInteger thisCopy(*this);
 191         add(thisCopy, x);
 192 }
 193 inline void BigInteger::operator -=(const BigInteger &x) {
 194         BigInteger thisCopy(*this);
 195         subtract(thisCopy, x);
 196 }
 197 inline void BigInteger::operator *=(const BigInteger &x) {
 198         BigInteger thisCopy(*this);
 199         multiply(thisCopy, x);
 200 }
 201 inline void BigInteger::operator /=(const BigInteger &x) {
 202         BigInteger thisCopy(*this);
 203         divide(thisCopy, x);
 204 }
 205 inline void BigInteger::operator %=(const BigInteger &x) {
 206         BigInteger thisCopy(*this);
 207         modulo(thisCopy, x);
 208 }
 209 // This one is trivial
 210 inline void BigInteger::flipSign() {
 211         sign = Sign(-sign);
 212 }
 213
 214 #endif