From: Matt McCutchen Date: Sat, 27 Jan 2007 21:06:12 +0000 (-0500) Subject: Old snapshot `BigInteger-2004.12.16'; see the ChangeLog file. X-Git-Tag: v2007.07.07~21 X-Git-Url: https://mattmccutchen.net/bigint/bigint.git/commitdiff_plain/e67d60496ce8582666f1fb77503acfe5d05c70d4 Old snapshot `BigInteger-2004.12.16'; see the ChangeLog file. --- e67d60496ce8582666f1fb77503acfe5d05c70d4 diff --git a/BigInteger.cpp b/BigInteger.cpp new file mode 100644 index 0000000..13a6003 --- /dev/null +++ b/BigInteger.cpp @@ -0,0 +1,553 @@ +/* +* Matt McCutchen's Big Integer Library +* See: http://mysite.verizon.net/mccutchen/bigint/ +*/ + +#include "BigInteger.h" + +// MANAGEMENT + +// Assignment operator +void BigInteger::operator =(const BigInteger &x) { + // Calls like a = a have no effect + if (this == &x) + return; + // Copy sign + sign = x.sign; + // Copy the rest + BigUnsigned::operator =(x); +} + +// Constructor from an array of blocks and a sign +BigInteger::BigInteger(const Blk *b, BlkNum l, Sign s) : BigUnsigned(b, l) { + switch (s) { + case zero: + case positive: + case negative: + sign = (len == 0) ? zero : s; + break; + default: + throw "BigInteger::BigInteger(Blk *, BlkNum, Sign): Invalid sign"; + } +} + +// Constructor from a BigUnsigned and a sign +BigInteger::BigInteger(const BigUnsigned &x, Sign s) : BigUnsigned(x) { + switch (s) { + case zero: + case positive: + case negative: + sign = (len == 0) ? zero : s; + break; + default: + throw "BigInteger::BigInteger(Blk *, BlkNum, Sign): Invalid sign"; + } +} + +/* +* The steps for construction of a BigInteger +* from an integral value x are as follows: +* 1. If x is zero, create an empty BigInteger and stop. +* 2. Allocate a one-block number array. +* 3. If x is positive (or of an unsigned type), set the +* sign of the BigInteger to positive. +* 4. If x is of a signed type and is negative, set the +* sign of the BigInteger to negative. +* 5. If x is of a signed type, convert x (or -x if x < 0) +* to the unsigned type of the same length. +* 6. Expand x (or the result of step 5) to a Blk, +* and store it in the number array. +*/ + +BigInteger::BigInteger(unsigned long x) { + if (x == 0) { + cap = 0; + blk = new Blk[0]; + sign = zero; + len = 0; + } else { + cap = 1; + blk = new Blk[1]; + sign = positive; + len = 1; + *blk = Blk(x); + } +} + +BigInteger::BigInteger(long x) { + if (x > 0) { + cap = 1; + blk = new Blk[1]; + sign = positive; + len = 1; + *blk = Blk(x); + } else if (x < 0) { + cap = 1; + blk = new Blk[1]; + sign = negative; + len = 1; + *blk = Blk(-x); + } else { + cap = 0; + blk = new Blk[0]; + sign = zero; + len = 0; + } +} + +BigInteger::BigInteger(unsigned int x) { + if (x == 0) { + cap = 0; + blk = new Blk[0]; + sign = zero; + len = 0; + } else { + cap = 1; + blk = new Blk[1]; + sign = positive; + len = 1; + *blk = Blk(x); + } +} + +BigInteger::BigInteger(int x) { + if (x > 0) { + cap = 1; + blk = new Blk[1]; + sign = positive; + len = 1; + *blk = Blk(x); + } else if (x < 0) { + cap = 1; + blk = new Blk[1]; + sign = negative; + len = 1; + *blk = Blk(-x); + } else { + cap = 0; + blk = new Blk[0]; + sign = zero; + len = 0; + } +} + +BigInteger::BigInteger(unsigned short x) { + if (x == 0) { + cap = 0; + blk = new Blk[0]; + sign = zero; + len = 0; + } else { + cap = 1; + blk = new Blk[1]; + sign = positive; + len = 1; + *blk = Blk(x); + } +} + +BigInteger::BigInteger(short x) { + if (x > 0) { + cap = 1; + blk = new Blk[1]; + sign = positive; + len = 1; + *blk = Blk(x); + } else if (x < 0) { + cap = 1; + blk = new Blk[1]; + sign = negative; + len = 1; + *blk = Blk(-x); + } else { + cap = 0; + blk = new Blk[0]; + sign = zero; + len = 0; + } +} + +// CONVERTERS +/* +* The steps for conversion of a BigInteger to an +* integral type are as follows: +* 1. If the BigInteger is zero, return zero. +* 2. If the BigInteger is positive: +* 3. If it is more than one block long or its lowest +* block has bits set out of the range of the target +* type, throw an exception. +* 4. Otherwise, convert the lowest block to the +* target type and return it. +* 5. If the BigInteger is negative: +* 6. If the target type is unsigned, throw an exception. +* 7. If it is more than one block long or its lowest +* block has bits set out of the range of the target +* type, throw an exception. +* 8. Otherwise, convert the lowest block to the +* target type, negate it, and return it. +*/ + +namespace { + // These masks are used to test whether a Blk has bits + // set out of the range of a smaller integral type. Note + // that this range is not considered to include the sign bit. + const BigUnsigned::Blk lMask = ~0 >> 1; + const BigUnsigned::Blk uiMask = (unsigned int)(~0); + const BigUnsigned::Blk iMask = uiMask >> 1; + const BigUnsigned::Blk usMask = (unsigned short)(~0); + const BigUnsigned::Blk sMask = usMask >> 1; +} + +BigInteger::operator unsigned long() const { + switch (sign) { + case zero: + return 0; + case positive: + if (len == 1) + return *blk; + else + throw "BigInteger operator unsigned long() const: Value is too big for an unsigned long"; + case negative: + throw "BigInteger operator unsigned long() const: Cannot convert a negative integer to an unsigned type"; + default: + throw "BigInteger: Internal error"; + } +} + +BigInteger::operator long() const { + switch (sign) { + case zero: + return 0; + case positive: + if (len == 1 && (*blk & ~lMask) == 0) + return long(*blk); + else + throw "BigInteger operator long() const: Value is too big for a long"; + case negative: + if (len == 1 && (*blk & ~lMask) == 0) + return -long(*blk); + else + throw "BigInteger operator long() const: Value is too big for a long"; + default: + throw "BigInteger: Internal error"; + } +} + +BigInteger::operator unsigned int() const { + switch (sign) { + case zero: + return 0; + case positive: + if (len == 1 && (*blk & ~uiMask) == 0) + return (unsigned int)(*blk); + else + throw "BigInteger operator unsigned int() const: Value is too big for an unsigned int"; + case negative: + throw "BigInteger operator unsigned int() const: Cannot convert a negative integer to an unsigned type"; + default: + throw "BigInteger: Internal error"; + } +} + +BigInteger::operator int() const { + switch (sign) { + case zero: + return 0; + case positive: + if (len == 1 && (*blk & ~iMask) == 0) + return int(*blk); + else + throw "BigInteger operator int() const: Value is too big for an int"; + case negative: + if (len == 1 && (*blk & ~iMask) == 0) + return -int(*blk); + else + throw "BigInteger operator int() const: Value is too big for an int"; + default: + throw "BigInteger: Internal error"; + } +} + +BigInteger::operator unsigned short() const { + switch (sign) { + case zero: + return 0; + case positive: + if (len == 1 && (*blk & ~usMask) == 0) + return (unsigned short)(*blk); + else + throw "BigInteger operator unsigned short() const: Value is too big for an unsigned short"; + case negative: + throw "BigInteger operator unsigned short() const: Cannot convert a negative integer to an unsigned type"; + default: + throw "BigInteger: Internal error"; + } +} + +BigInteger::operator short() const { + switch (sign) { + case zero: + return 0; + case positive: + if (len == 1 && (*blk & ~sMask) == 0) + return short(*blk); + else + throw "BigInteger operator short() const: Value is too big for a short"; + case negative: + if (len == 1 && (*blk & ~sMask) == 0) + return -short(*blk); + else + throw "BigInteger operator short() const: Value is too big for a short"; + default: + throw "BigInteger: Internal error"; + } +} + +// COMPARISON +BigInteger::CmpRes BigInteger::compareTo(const BigInteger &x) const { + // A greater sign implies a greater number + if (sign < x.sign) + return less; + else if (sign > x.sign) + return greater; + else switch (sign) { + // If the signs are the same... + case zero: + return equal; // Two zeros are equal + case positive: + // Compare the magnitudes + return BigUnsigned::compareTo(x); + case negative: + // Compare the magnitudes, but return the opposite result + return CmpRes(-BigUnsigned::compareTo(x)); + default: + throw "BigInteger: Internal error"; + } +} + +// PUT-HERE OPERATIONS +// These do some messing around to determine the sign of the result, +// then call one of BigUnsigned's put-heres. + +// Addition +void BigInteger::add(const BigInteger &a, const BigInteger &b) { + // Block unsafe calls + if (this == &a || this == &b) + throw "BigInteger::add: One of the arguments is the invoked object"; + // If one argument is zero, copy the other. + if (a.sign == zero) + operator =(b); + else if (b.sign == zero) + operator =(a); + // If the arguments have the same sign, take the + // common sign and add their magnitudes. + else if (a.sign == b.sign) { + sign = a.sign; + BigUnsigned::add(a, b); + } else { + // Otherwise, their magnitudes must be compared. + switch (a.BigUnsigned::compareTo(b)) { + // If their magnitudes are the same, copy zero. + case equal: + len = 0; + sign = zero; + break; + // Otherwise, take the sign of the greater, and subtract + // the lesser magnitude from the greater magnitude. + case greater: + sign = a.sign; + BigUnsigned::subtract(a, b); + break; + case less: + sign = b.sign; + BigUnsigned::subtract(b, a); + break; + } + } +} + +// Subtraction +void BigInteger::subtract(const BigInteger &a, const BigInteger &b) { + // Notice that this routine is identical to BigInteger::add, + // if one replaces b.sign by its opposite. + // Block unsafe calls + if (this == &a || this == &b) + throw "BigInteger::subtract: One of the arguments is the invoked object"; + // If a is zero, copy b and flip its sign. If b is zero, copy a. + if (a.sign == zero) { + BigUnsigned::operator =(b); + sign = Sign(-sign); + } else if (b.sign == zero) + operator =(a); + // If their signs differ, take a.sign and add the magnitudes. + else if (a.sign != b.sign) { + sign = a.sign; + BigUnsigned::add(a, b); + } else { + // Otherwise, their magnitudes must be compared. + switch (a.BigUnsigned::compareTo(b)) { + // If their magnitudes are the same, copy zero. + case equal: + len = 0; + sign = zero; + break; + // If a's magnitude is greater, take a.sign and + // subtract a from b. + case greater: + sign = a.sign; + BigUnsigned::subtract(a, b); + break; + // If b's magnitude is greater, take the opposite + // of b.sign and subtract b from a. + case less: + sign = Sign(-b.sign); + BigUnsigned::subtract(b, a); + break; + } + } +} + +// Multiplication +void BigInteger::multiply(const BigInteger &a, const BigInteger &b) { + // Block unsafe calls + if (this == &a || this == &b) + throw "BigInteger::multiply: One of the arguments is the invoked object"; + // If one object is zero, copy zero and return. + if (a.sign == zero || b.sign == zero) { + sign = zero; + len = 0; + return; + } + // If the signs of the arguments are the same, the result + // is positive, otherwise it is negative. + sign = (a.sign == b.sign) ? positive : negative; + // Multiply the magnitudes. + BigUnsigned::multiply(a, b); +} + +// Division +void BigInteger::divide(const BigInteger &a, const BigInteger &b) { + // Block unsafe calls + if (this == &a || this == &b) + throw "BigInteger::divide: One of the arguments is the invoked object"; + // If b is zero, the caller has tried to divide by zero. Throw an exception. + if (b.sign == zero) + throw "BigInteger::divide: Division by zero"; + // Otherwise if a is zero, copy zero and return. + else if (a.sign == zero) { + sign = zero; + len = 0; + return; + } + // If the signs of the arguments are the same, the result + // is positive, otherwise it is negative. + sign = (a.sign == b.sign) ? positive : negative; + // Divide the magnitudes. + // Note: This is integer division. Any fractional part + // of the result is truncated toward zero. + BigUnsigned::divide(a, b); + // If the result is zero, set the sign to zero. + if (len == 0) + sign = zero; +} + +// Modular reduction +void BigInteger::modulo(const BigInteger &a, const BigInteger &b) { + /* Note that the mathematical definition of mod is somewhat + * different from the way the normal C++ % operator behaves. + * This function does it the mathematical way. */ + // Block unsafe calls + if (this == &a || this == &b) + throw "BigInteger::modulo: One of the arguments is the invoked object"; + // If b is zero, copy a and return. By the mathematical definition, + // x mod 0 = x, though the normal C++ % would throw an exception. + if (b.len == 0) { + operator =(a); + return; + // If a is zero, copy zero and return. + } else if (a.sign == zero) { + sign = zero; + len = 0; + return; + } + // Perform modular reduction on the magnitudes + BigUnsigned::modulo(a, b); + // If the result is zero, set the sign to zero. + if (len == 0) + sign = zero; + else { + /* If necessary, flip the result over zero so that it has the + * same sign as the modulus (by the mathematical definition). + * The normal C++ % does not perform this step and always + * takes the sign of the first input. */ + if (a.sign != b.sign) { + BigUnsigned temp(*this); + BigUnsigned::subtract(b, temp); + } + sign = b.sign; + } +} + +// Negation +void BigInteger::negate(const BigInteger &a) { + // Block unsafe calls + if (this == &a) + throw "BigInteger::negate: The argument is the invoked object"; + // Copy a's magnitude + BigUnsigned::operator =(a); + // Copy the opposite of a.sign + sign = Sign(-a.sign); +} + +// INCREMENT/DECREMENT OPERATORS + +// Prefix increment +void BigInteger::operator ++() { + switch (sign) { + case zero: + allocate(1); + sign = positive; + len = 1; + *blk = 1; + break; + case positive: + BigUnsigned::operator ++(); + break; + case negative: + BigUnsigned::operator --(); + if (len == 0) + sign = zero; + break; + } +} + +// Postfix increment: same as prefix +void BigInteger::operator ++(int) { + operator ++(); +} + +// Prefix decrement +void BigInteger::operator --() { + switch (sign) { + case zero: + allocate(1); + sign = negative; + len = 1; + *blk = 1; + break; + case negative: + BigUnsigned::operator ++(); + break; + case positive: + BigUnsigned::operator --(); + if (len == 0) + sign = zero; + break; + } +} + +// Postfix decrement: same as prefix +void BigInteger::operator --(int) { + operator --(); +} + diff --git a/BigInteger.h b/BigInteger.h new file mode 100644 index 0000000..2c0faf4 --- /dev/null +++ b/BigInteger.h @@ -0,0 +1,214 @@ +/* +* Matt McCutchen's Big Integer Library +* http://mysite.verizon.net/mccutchen/bigint/ +*/ + +#ifndef BIGINTEGER +#define BIGINTEGER + +#include "BigUnsigned.h" + +/* +* +* A BigInteger object represents a signed integer of size +* limited only by available memory. A BigInteger can be +* created from and converted back to most integral types, +* and many math operations are defined on them. +* +* The number is stored as a series of blocks in a +* dynamically allocated array. It is as if the numbers +* were written digit by digit in base 2^32. +* +* This class is derived from BigUnsigned, which represents +* a large nonnegative integer. This should be understood +* first, as only new or different things are declared here. +* Some things are redeclared so that they use the BigInteger +* versions of methods, rather than the BigUnsigned versions. +*/ + +class BigInteger : public BigUnsigned { + + // TYPES & CONSTANTS + public: + enum Sign { negative = -1, zero = 0, positive = 1 }; // Enumeration for the sign of a BigInteger + + // FIELDS + protected: + Sign sign; // The sign of this BigInteger + + // MANAGEMENT + protected: + BigInteger(Sign s, BlkNum c); // Creates a BigInteger with a sign and capacity + public: + BigInteger(); // Default constructor (value is 0) + BigInteger(const BigInteger &x); // Copy constructor + void operator=(const BigInteger &x); // Assignment operator + BigInteger(const Blk *b, BlkNum l); // Constructor from an array of blocks + BigInteger(const Blk *b, BlkNum l, Sign s); // Constructor from an array of blocks and a sign + BigInteger(const BigUnsigned &x); // Constructor from a BigUnsigned + BigInteger(const BigUnsigned &x, Sign s); // Constructor from a BigUnsigned and a sign + // Constructors from integral types + BigInteger(unsigned long x); + BigInteger( long x); + BigInteger(unsigned int x); + BigInteger( int x); + BigInteger(unsigned short x); + BigInteger( short x); + // Note that a BigInteger can be converted to a BigUnsigned + // automatically; this takes its absolute value. + + // CONVERTERS to integral types + public: + operator unsigned long () const; + operator long () const; + operator unsigned int () const; + operator int () const; + operator unsigned short() const; + operator short() const; + + // PICKING APART + // These accessors can be used to get the pieces of the number + public: + Sign getSign() const; + + // COMPARISONS + public: + // Compares this to x like Perl's <=> + CmpRes compareTo(const BigInteger &x) const; + // Normal comparison operators + bool operator ==(const BigInteger &x) const; + bool operator !=(const BigInteger &x) const; + bool operator < (const BigInteger &x) const; + bool operator <=(const BigInteger &x) const; + bool operator >=(const BigInteger &x) const; + bool operator > (const BigInteger &x) const; + + // PUT-HERE OPERATIONS + /* These store the result of the operation on the arguments into this. + * a.add(b, c) is equivalent to, but faster than, a = b + c. + * Calls like a.operation(a, b) are unsafe and not allowed. */ + public: + void add (const BigInteger &a, const BigInteger &b); // Addition + void subtract(const BigInteger &a, const BigInteger &b); // Subtraction + void multiply(const BigInteger &a, const BigInteger &b); // Multiplication + void divide (const BigInteger &a, const BigInteger &b); // Division + void modulo (const BigInteger &a, const BigInteger &b); // Modular reduction + void negate (const BigInteger &a ); // Negative + // Some operations are inherently unsigned and are not + // redefined for BigIntegers. Calling one of these on + // a BigInteger will take its absolute value first. + + // NORMAL OPERATORS + // These perform the operation on this (to the left of the operator) + // and x (to the right of the operator) and return a new BigInteger with the result. + public: + BigInteger operator +(const BigInteger &x) const; // Addition + BigInteger operator -(const BigInteger &x) const; // Subtraction + BigInteger operator *(const BigInteger &x) const; // Multiplication + BigInteger operator /(const BigInteger &x) const; // Division + BigInteger operator %(const BigInteger &x) const; // Modular reduction + BigInteger operator -( ) const; // Negative + + // ASSIGNMENT OPERATORS + // These perform the operation on this and x, storing the result into this. + public: + void operator +=(const BigInteger &x); // Addition + void operator -=(const BigInteger &x); // Subtraction + void operator *=(const BigInteger &x); // Multiplication + void operator /=(const BigInteger &x); // Division + void operator %=(const BigInteger &x); // Modular reduction + void flipSign(); // Negative + + // INCREMENT/DECREMENT OPERATORS + // These increase or decrease the number by 1. To discourage side effects, + // these do not return *this, so prefix and postfix behave the same. + public: + void operator ++( ); // Prefix increment + void operator ++(int); // Postfix decrement + void operator --( ); // Prefix increment + void operator --(int); // Postfix decrement + +}; + +// MANAGEMENT +inline BigInteger::BigInteger(Sign s, BlkNum c) : BigUnsigned(0, c), sign(s) { } +inline BigInteger::BigInteger() : BigUnsigned(), sign(zero) { } +inline BigInteger::BigInteger(const BigInteger &x) : BigUnsigned(x), sign(x.sign) { } +inline BigInteger::BigInteger(const Blk *b, BlkNum l) : BigUnsigned(b, l) { sign = (len == 0) ? zero : positive; } +inline BigInteger::BigInteger(const BigUnsigned &x) : BigUnsigned(x) { sign = (len == 0) ? zero : positive; } + +// PICKING APART +inline BigInteger::Sign BigInteger::getSign() const { return sign; } + +// COMPARISONS +inline bool BigInteger::operator==(const BigInteger &x) const { return compareTo(x) == equal ; } +inline bool BigInteger::operator!=(const BigInteger &x) const { return compareTo(x) != equal ; } +inline bool BigInteger::operator< (const BigInteger &x) const { return compareTo(x) == less ; } +inline bool BigInteger::operator<=(const BigInteger &x) const { return compareTo(x) != greater; } +inline bool BigInteger::operator>=(const BigInteger &x) const { return compareTo(x) != less ; } +inline bool BigInteger::operator> (const BigInteger &x) const { return compareTo(x) == greater; } + +// 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 { + BigInteger ans; + ans.divide(*this, x); + return ans; +} +inline BigInteger BigInteger::operator %(const BigInteger &x) const { + BigInteger ans; + ans.modulo(*this, x); + return ans; +} +inline BigInteger BigInteger::operator -() const { + BigInteger ans; + ans.negate(*this); + return ans; +} + +// ASSIGNMENT OPERATORS +// These create a copy of this, then invoke the appropriate +// put-here operation on this, passing the copy and x. +inline void BigInteger::operator +=(const BigInteger &x) { + BigInteger thisCopy(*this); + add(thisCopy, x); +} +inline void BigInteger::operator -=(const BigInteger &x) { + BigInteger thisCopy(*this); + subtract(thisCopy, x); +} +inline void BigInteger::operator *=(const BigInteger &x) { + BigInteger thisCopy(*this); + multiply(thisCopy, x); +} +inline void BigInteger::operator /=(const BigInteger &x) { + BigInteger thisCopy(*this); + divide(thisCopy, x); +} +inline void BigInteger::operator %=(const BigInteger &x) { + BigInteger thisCopy(*this); + modulo(thisCopy, x); +} +// This one is trivial +inline void BigInteger::flipSign() { + sign = Sign(-sign); +} + +#endif diff --git a/BigIntegerIO.cpp b/BigIntegerIO.cpp new file mode 100644 index 0000000..ffee874 --- /dev/null +++ b/BigIntegerIO.cpp @@ -0,0 +1,62 @@ +/* +* Big Integer Library +* Filename: BigIntegerIO.h +* Author: Matt McCutchen +* Version: 2004.1205 +*/ + +#include "BigIntegerIO.h" + +std::ostream& operator<<(std::ostream &os, BigUnsigned x) { + if (x.getLength() == 0) + os << '0'; + else { + BigUnsigned ten(10); + + /* + * This buffer is filled with the decimal digits of x. + * sizeof(BigUnsigned::Blk) * x.getLength() is an upper bound on the + * number of bytes in x, and a byte takes at most 3 decimal + * digits, so this is a convenient upper bound. + */ + char *buf = new char[sizeof(BigUnsigned::Blk) * x.getLength() * 3]; + //std::cout << "bufferlength" << sizeof(BigUnsigned::Blk) * x.getLength() * 3<< std::endl; + int bufPos = 0; // first unfilled position + + // While x is not zero... + while (!x.isZero()) { + //std::cout << "bufPos=" << bufPos << std::endl; + // Get next digit + buf[bufPos] = char(int(x % ten) + '0'); + // Remove it from x + x /= ten; + // Next buffer slot + bufPos++; + } + + // Now print the digits to os. + while (bufPos > 0) { + bufPos--; + os << buf[bufPos]; + } + + // Free the buffer and return the stream (as customary) + delete buf; + return os; + } +} + +std::ostream& operator<<(std::ostream &os, BigInteger x) { + switch (x.getSign()) { + case BigInteger::positive: + os << BigUnsigned(x); + break; + case BigInteger::zero: + os << '0'; + break; + case BigInteger::negative: + os << '-' << BigUnsigned(x); + break; + } + return os; +} diff --git a/BigIntegerIO.h b/BigIntegerIO.h new file mode 100644 index 0000000..356fee0 --- /dev/null +++ b/BigIntegerIO.h @@ -0,0 +1,19 @@ +/* +* Matt McCutchen's Big Integer Library +* See: http://mysite.verizon.net/mccutchen/bigint/ +*/ + +#ifndef BIGINTEGERIO +#define BIGINTEGERIO + +#include "BigUnsigned.h" +#include "BigInteger.h" +#include + +// Some I/O routines for BigIntegers and BigUnsigneds + +// Both of these output x to os in decimal notation. +std::ostream &operator <<(std::ostream &os, BigUnsigned x); +std::ostream &operator <<(std::ostream &os, BigInteger x); + +#endif diff --git a/BigUnsigned.cpp b/BigUnsigned.cpp new file mode 100644 index 0000000..6864d1c --- /dev/null +++ b/BigUnsigned.cpp @@ -0,0 +1,787 @@ +/* +* Matt McCutchen's Big Integer Library +* http://mysite.verizon.net/mccutchen/bigint/ +*/ + +#include "BigUnsigned.h" + +// MANAGEMENT + +// This routine is called to ensure the number array is at least a +// certain size before the result of an operation is written over it. +void BigUnsigned::allocate(BlkNum c) { + // If the requested capacity is more than the current capacity... + if (c > cap) { + // Delete the old number array + delete [] blk; + // Allocate the new array + cap = c; + blk = new Blk[cap]; + } +} + +// This routine is called to ensure the number array is at least a +// certain size without losing its contents. +void BigUnsigned::allocateAndCopy(BlkNum c) { + // If the requested capacity is more than the current capacity... + if (c > cap) { + Blk *oldBlk = blk; + // Allocate the new number array + cap = c; + blk = new Blk[cap]; + // Copy number blocks + BlkNum i; + Blk *blkI; + const Blk *oldBlkI; + for (i = 0, blkI = blk, oldBlkI = oldBlk; i < len; i++, blkI++, oldBlkI++) + *blkI = *oldBlkI; + // Delete the old array + delete [] oldBlk; + } +} + +// Copy constructor +BigUnsigned::BigUnsigned(const BigUnsigned &x) : len(x.len) { + // Create number array + cap = len; + blk = new Blk[cap]; + // Copy number blocks + BlkNum i; + Blk *blkI; + const Blk *xBlkI; + for (i = 0, blkI = blk, xBlkI = x.blk; i < len; i++, blkI++, xBlkI++) + *blkI = *xBlkI; +} + +// Assignment operator +void BigUnsigned::operator=(const BigUnsigned &x) { + // Calls like a = a have no effect + if (this == &x) + return; + // Copy length + len = x.len; + // Expand number array if necessary + allocate(len); + // Copy number blocks + BlkNum i; + Blk *blkI; + const Blk *xBlkI; + for (i = 0, blkI = blk, xBlkI = x.blk; i < len; i++, blkI++, xBlkI++) + *blkI = *xBlkI; +} + +// Constructor from an array of blocks +BigUnsigned::BigUnsigned(const Blk *b, BlkNum l) : cap(l), len(l) { + // Create number array + blk = new Blk[cap]; + // Copy number blocks + BlkNum i; + Blk *blkI; + const Blk *bI; + for (i = 0, blkI = blk, bI = b; i < len; i++, blkI++, bI++) + *blkI = *bI; + zapLeadingZeros(); +} + +/* +* The steps for construction of a BigUnsigned +* from an integral value x are as follows: +* 1. If x is zero, create an empty BigUnsigned and stop. +* 2. If x is negative, throw an exception. +* 3. Allocate a one-block number array. +* 4. If x is of a signed type, convert x to the unsigned +* type of the same length. +* 5. Expand x to a Blk, and store it in the number array. +*/ + +BigUnsigned::BigUnsigned(unsigned long x) { + if (x == 0) { + cap = 0; + blk = new Blk[0]; + len = 0; + } else { + cap = 1; + blk = new Blk[1]; + len = 1; + *blk = Blk(x); + } +} + +BigUnsigned::BigUnsigned(long x) { + if (x == 0) { + cap = 0; + blk = new Blk[0]; + len = 0; + } else if (x > 0) { + cap = 1; + blk = new Blk[1]; + len = 1; + *blk = Blk(x); + } else + throw "BigUnsigned::BigUnsigned(long): Cannot construct a BigUnsigned from a negative number"; +} + +BigUnsigned::BigUnsigned(unsigned int x) { + if (x == 0) { + cap = 0; + blk = new Blk[0]; + len = 0; + } else { + cap = 1; + blk = new Blk[1]; + len = 1; + *blk = Blk(x); + } +} + +BigUnsigned::BigUnsigned(int x) { + if (x == 0) { + cap = 0; + blk = new Blk[0]; + len = 0; + } else if (x > 0) { + cap = 1; + blk = new Blk[1]; + len = 1; + *blk = Blk(x); + } else + throw "BigUnsigned::BigUnsigned(int): Cannot construct a BigUnsigned from a negative number"; +} + +BigUnsigned::BigUnsigned(unsigned short x) { + if (x == 0) { + cap = 0; + blk = new Blk[0]; + len = 0; + } else { + cap = 1; + blk = new Blk[1]; + len = 1; + *blk = Blk(x); + } +} + +BigUnsigned::BigUnsigned(short x) { + if (x == 0) { + cap = 0; + blk = new Blk[0]; + len = 0; + } else if (x > 0) { + cap = 1; + blk = new Blk[1]; + len = 1; + *blk = Blk(x); + } else + throw "BigUnsigned::BigUnsigned(short): Cannot construct a BigUnsigned from a negative number"; +} + +// CONVERTERS +/* +* The steps for conversion of a BigUnsigned to an +* integral type are as follows: +* 1. If the BigUnsigned is zero, return zero. +* 2. If it is more than one block long or its lowest +* block has bits set out of the range of the target +* type, throw an exception. +* 3. Otherwise, convert the lowest block to the +* target type and return it. +*/ + +namespace { + // These masks are used to test whether a Blk has bits + // set out of the range of a smaller integral type. Note + // that this range is not considered to include the sign bit. + const BigUnsigned::Blk lMask = ~0 >> 1; + const BigUnsigned::Blk uiMask = (unsigned int)(~0); + const BigUnsigned::Blk iMask = uiMask >> 1; + const BigUnsigned::Blk usMask = (unsigned short)(~0); + const BigUnsigned::Blk sMask = usMask >> 1; +} + +BigUnsigned::operator unsigned long() const { + if (len == 0) + return 0; + else if (len == 1) + return (unsigned long) *blk; + else + throw "BigUnsigned::operator unsigned long: Value is too big for an unsigned long"; +} + +BigUnsigned::operator long() const { + if (len == 0) + return 0; + else if (len == 1 && (*blk & lMask) == *blk) + return (long) *blk; + else + throw "BigUnsigned::operator long: Value is too big for a long"; +} + +BigUnsigned::operator unsigned int() const { + if (len == 0) + return 0; + else if (len == 1 && (*blk & uiMask) == *blk) + return (unsigned int) *blk; + else + throw "BigUnsigned::operator unsigned int: Value is too big for an unsigned int"; +} + +BigUnsigned::operator int() const { + if (len == 0) + return 0; + else if (len == 1 && (*blk & iMask) == *blk) + return (int) *blk; + else + throw "BigUnsigned::operator int: Value is too big for an int"; +} + +BigUnsigned::operator unsigned short() const { + if (len == 0) + return 0; + else if (len == 1 && (*blk & usMask) == *blk) + return (unsigned short) *blk; + else + throw "BigUnsigned::operator unsigned short: Value is too big for an unsigned short"; +} + +BigUnsigned::operator short() const { + if (len == 0) + return 0; + else if (len == 1 && (*blk & sMask) == *blk) + return (short) *blk; + else + throw "BigUnsigned::operator short: Value is too big for a short"; +} + +// COMPARISON +BigUnsigned::CmpRes BigUnsigned::compareTo(const BigUnsigned &x) const { + // A bigger length implies a bigger number. + if (len < x.len) + return less; + else if (len > x.len) + return greater; + else { + // Compare blocks one by one from left to right. + BlkNum i = len; + const Blk *blkI = blk + len; + const Blk *xBlkI = x.blk + len; + while (i > 0) { + i--; + blkI--; + xBlkI--; + if (*blkI == *xBlkI) + continue; + else if (*blkI > *xBlkI) + return greater; + else + return less; + } + // If no blocks differed, the numbers are equal. + return equal; + } +} + +// PUT-HERE OPERATIONS + +// Addition +void BigUnsigned::add(const BigUnsigned &a, const BigUnsigned &b) { + // Block unsafe calls + if (this == &a || this == &b) + throw "BigUnsigned::add: One of the arguments is the invoked object"; + // If one argument is zero, copy the other. + if (a.len == 0) { + operator =(b); + return; + } else if (b.len == 0) { + operator =(a); + return; + } + // Carries in and out of an addition stage + bool carryIn, carryOut; + Blk temp; + BlkNum i; + // a2 points to the longer input, b2 points to the shorter + const BigUnsigned *a2, *b2; + if (a.len >= b.len) { + a2 = &a; + b2 = &b; + } else { + a2 = &b; + b2 = &a; + } + // These point directly to the position of interest in the + // corresponding block arrays, for faster access. + Blk *blkI; + const Blk *a2BlkI, *b2BlkI; + // Set prelimiary length and make room in this BigUnsigned + len = a2->len + 1; + allocate(len); + // For each block index that is present in both inputs... + for (i = 0, blkI = blk, a2BlkI = a2->blk, b2BlkI = b2->blk, + carryIn = false; i < b2->len; i++, blkI++, a2BlkI++, b2BlkI++) { + // Add input blocks + temp = *a2BlkI + *b2BlkI; + // If a rollover occurred, the result is less than either input. + // This test is used many times in the BigUnsigned code. + carryOut = (temp < *a2BlkI); + // If a carry was input, handle it + if (carryIn) { + temp++; + carryOut |= (temp == 0); + } + *blkI = temp; // Save the addition result + carryIn = carryOut; // Pass the carry along + } + // If there is a carry left over, increase blocks until + // one does not roll over. + for (; i < a2->len && carryIn; i++, blkI++, a2BlkI++) { + temp = *a2BlkI + 1; + carryIn = (temp == 0); + *blkI = temp; + } + // If the carry was resolved but the larger number + // still has blocks, copy them over. + for (; i < a2->len; i++, blkI++, a2BlkI++) + *blkI = *a2BlkI; + // Set the extra block if there's still a carry, decrease length otherwise + if (carryIn) + *blkI = 1; + else + len--; +} + +// Subtraction +void BigUnsigned::subtract(const BigUnsigned &a, const BigUnsigned &b) { + // Block unsafe calls + if (this == &a || this == &b) + throw "BigUnsigned::subtract: One of the arguments is the invoked object"; + // If b is zero, copy a. If a is shorter than b, the result is negative. + if (b.len == 0) { + operator =(a); + return; + } else if (a.len < b.len) + throw "BigUnsigned::subtract: Negative result in unsigned calculation"; + bool borrowIn, borrowOut; + Blk temp; + BlkNum i; + // These point directly to the position of interest in the + // corresponding block arrays, for faster access. + Blk *blkI; + const Blk *aBlkI, *bBlkI; + // Set preliminary length and make room + len = a.len; + allocate(len); + // For each block index that is present in both inputs... + for (i = 0, blkI = blk, aBlkI = a.blk, bBlkI = b.blk, + borrowIn = false; i < b.len; i++, blkI++, aBlkI++, bBlkI++) { + temp = *aBlkI - *bBlkI; + // If a reverse rollover occurred, the result is greater than the block from a. + borrowOut = (temp > *aBlkI); + // Handle an incoming borrow + if (borrowIn) { + borrowOut |= (temp == 0); + temp--; + } + *blkI = temp; // Save the subtraction result + borrowIn = borrowOut; // Pass the borrow along + } + // If there is a borrow left over, decrease blocks until + // one does not reverse rollover. + for (; i < a.len && borrowIn; i++, blkI++, aBlkI++) { + borrowIn = (*aBlkI == 0); + *blkI = *aBlkI - 1; + } + // If there's still a borrow, the result is negative. + // Throw an exception, but zero out this object first. + if (borrowIn) { + len = 0; + throw "BigUnsigned::subtract: Negative result in unsigned calculation"; + } else // Copy over the rest of the blocks + for (; i < a.len; i++, blkI++, aBlkI++) + *blkI = *aBlkI; + // Zap leading zeros + zapLeadingZeros(); +} + +// Multiplication +void BigUnsigned::multiply(const BigUnsigned &a, const BigUnsigned &b) { + // Block unsafe calls + if (this == &a || this == &b) + throw "BigUnsigned::multiply: One of the arguments is the invoked object"; + // If either a or b is zero, set to zero. + if (a.len == 0 || b.len == 0) { + len = 0; + return; + } + // Overall method: this = 0, then for each 1-bit of a, add b + // to this shifted the appropriate amount. + // Variables for the calculation + BlkNum i, j; + unsigned int i2; + Blk aBlk, bHigh, temp; + bool carryIn, carryOut; + // These point directly to the positions of interest in the + // corresponding block arrays, for faster access. + Blk *blkI, *blkK; + const Blk *aBlkI, *bBlkJ; + // Set preliminary length and make room + len = a.len + b.len; + allocate(len); + // Zero out this object + for (i = 0, blkI = blk; i < len; i++, blkI++) + *blkI = 0; + // For each block of the first number... + for (i = 0, blkI = blk, aBlkI = a.blk; i < a.len; i++, blkI++, aBlkI++) + // For each 1-bit of that block... + for (i2 = 0, aBlk = *aBlkI; aBlk != 0; i2++, aBlk >>= 1) { + if ((aBlk & 1) == 0) + continue; + /* Add b to this, shifted left i blocks and i2 bits. + * j is the index in b, and k = i + j is the index in this. + * The low bits of b.blk[j] are shifted and added to blk[k]. + * bHigh is used to carry the high bits to the next addition. */ + carryIn = false; + bHigh = 0; + for (j = 0, bBlkJ = b.blk, blkK = blkI; j < b.len; j++, bBlkJ++, blkK++) { + temp = *blkK + ((*bBlkJ << i2) | bHigh); + carryOut = (temp < *blkK); + if (carryIn) { + temp++; + carryOut |= (temp == 0); + } + *blkK = temp; + carryIn = carryOut; + bHigh = (i2 == 0) ? 0 : *bBlkJ >> (8 * sizeof(Blk) - i2); + } + temp = *blkK + bHigh; + carryOut = (temp < *blkK); + if (carryIn) { + temp++; + carryOut |= (temp == 0); + } + *blkK = temp; + carryIn = carryOut; + for (; carryIn; blkK++) { + (*blkK)++; + carryIn = (*blkK == 0); + } + } + // Zap leading zero + if (blk[len - 1] == 0) + len--; +} + +// Division +void BigUnsigned::divide(const BigUnsigned &a, const BigUnsigned &b) { + // Note: This is integer division. Any fractional part + // of the result is truncated. + // Block unsafe calls + if (this == &a || this == &b) + throw "BigUnsigned::divide: One of the arguments is the invoked object"; + // If b is zero, throw an exception. If a is zero, set to zero. + else if (b.len == 0) + throw "BigUnsigned::divide: Division by zero"; + else if (a.len < b.len) { + len = 0; + return; + } + /* Overall method: Subtract b, shifted varying amounts to + * the left, from a, setting the bit in the quotient + * whenever the subtraction succeeds. */ + // Variables for the calculation + BlkNum i, j, k; + unsigned int i2; + Blk bHigh, temp; + bool borrowIn, borrowOut; + // work1 is a copy of a that can be modified + // after each successful subtraction. + Blk *work1 = new Blk[a.len + 1]; + Blk *work1I = work1; + const Blk *aBlkI = a.blk; + for (i = 0; i < a.len; i++, work1I++, aBlkI++) + *work1I = *aBlkI; + *work1I = 0; + // work2 holds part of the result of a subtraction + Blk *work2 = new Blk[a.len + 1]; + // These point directly to the positions of interest in the + // corresponding block arrays, for faster access. + Blk *blkI, *work1K, *work2J; + const Blk *bBlkJ; + // Set preliminary length and make room + len = a.len - b.len + 1; + allocate(len); + // For each possible left-shift of b in blocks... + i = len; + blkI = blk + len; + work1I = work1 + len; + while (i > 0) { + i--; + blkI--; + work1I--; + // For each possible left-shift of b in bits... + *blkI = 0; + i2 = 8 * sizeof(Blk); + while (i2 > 0) { + i2--; + // Subtract b, shifted left i blocks and i2 bits, from work1 + // and store the answer in work2. See note in BigUnsigned::multiply. + bHigh = 0; + for (j = 0, bBlkJ = b.blk, work2J = work2, k = i, work1K = work1I, + borrowIn = false; j < b.len; j++, bBlkJ++, work2J++, k++, work1K++) { + temp = *work1K - ((*bBlkJ << i2) | bHigh); + borrowOut = (temp > *work1K); + if (borrowIn) { + borrowOut |= (temp == 0); + temp--; + } + *work2J = temp; + borrowIn = borrowOut; + bHigh = (i2 == 0) ? 0 : *bBlkJ >> (8 * sizeof(Blk) - i2); + } + temp = *work1K - bHigh; + borrowOut = (temp > *work1K); + if (borrowIn) { + borrowOut |= (temp == 0); + temp--; + } + *work2J = temp; + borrowIn = borrowOut; + j++; + work2J++; + k++; + work1K++; + for (; k < a.len + 1 && borrowIn; j++, work2J++, k++, work1K++) { + borrowIn = (*work1K == 0); + *work2J = *work1K - 1; + } + /* If the subtraction was performed successfully, set bit i2 + * in block i of the quotient, and copy the changed portion of + * work2 back to work1. Otherwise, reset that bit and move on. */ + if (!borrowIn) { + *blkI |= (1 << i2); + while (j > 0) { + j--; + work2J--; + k--; + work1K--; + *work1K = *work2J; + } + } + } + } + // Zap leading zero + if (blk[len - 1] == 0) + len--; + // Deallocate temporary arrays. + // (Thanks to Brad Spencer for noticing my accidental omission of this!) + delete [] work1; + delete [] work2; +} + +// Modulo +void BigUnsigned::modulo(const BigUnsigned &a, const BigUnsigned &b) { + /* Note that the mathematical definition of mod is somewhat + * different from the way the normal C++ % operator behaves. + * This function does it the mathematical way. */ + // Block unsafe calls + if (this == &a || this == &b) + throw "BigUnsigned::modulo: One of the arguments is the invoked object"; + // If b is zero, copy a and return. By the mathematical definition, + // x mod 0 = x, though the normal C++ % would throw an exception. + else if (b.len == 0) { + len = 0; + return; + // If a is zero, set to zero and return. + } else if (a.len < b.len) { + operator =(a); + return; + } + /* Overall method: Copy a into this. Then subtract b, + * shifted varying amounts to the left, from this. + * When no more subtraction is possible, stop; this + * will contain the remainder. + * This is very similar to the division routine, except + * that whether or not a subtraction succeeds is ignored, + * and "this" serves the purpose of work1. */ + // Variables for the calculation + BlkNum i, j, k; + unsigned int i2; + Blk bHigh, temp; + bool borrowIn, borrowOut; + allocate(a.len + 1); + operator =(a); + blk[len] = 0; + // work2 holds part of the result of a subtraction + Blk *work2 = new Blk[a.len + 1]; + // These point directly to the positions of interest in the + // corresponding block arrays, for faster access. + Blk *blkI, *blkK, *work2J; + const Blk *bBlkJ; + // For each possible left-shift of b in blocks... + i = len; + blkI = blk + len; + while (i > 0) { + i--; + blkI--; + // For each possible left-shift of b in bits... + i2 = 8 * sizeof(Blk); + while (i2 > 0) { + i2--; + // Subtract b, shifted left i blocks and i2 bits, from work1 + // and store the answer in work2. See note in BigUnsigned::multiply. + bHigh = 0; + for (j = 0, bBlkJ = b.blk, work2J = work2, k = i, blkK = blkI, + borrowIn = false; j < b.len; j++, bBlkJ++, work2J++, k++, blkK++) { + temp = *blkK - ((*bBlkJ << i2) | bHigh); + borrowOut = (temp > *blkK); + if (borrowIn) { + borrowOut |= (temp == 0); + temp--; + } + *work2J = temp; + borrowIn = borrowOut; + bHigh = (i2 == 0) ? 0 : *bBlkJ >> (8 * sizeof(Blk) - i2); + } + temp = *blkK - bHigh; + borrowOut = (temp > *blkK); + if (borrowIn) { + borrowOut |= (temp == 0); + temp--; + } + *work2J = temp; + borrowIn = borrowOut; + j++; + work2J++; + k++; + blkK++; + for (; k < a.len + 1 && borrowIn; j++, work2J++, k++, blkK++) { + borrowIn = (*blkK == 0); + *work2J = *blkK - 1; + } + // If the subtraction was performed successfully, set bit i2 + // in block i of the quotient, and copy the changed portion of + // work2 back to this. + if (!borrowIn) + while (j > 0) { + j--; + work2J--; + k--; + blkK--; + *blkK = *work2J; + } + } + } + // Blocks higher than the last block of the modulus are zero. + len = b.len; + // Zap leading zeros + zapLeadingZeros(); +} + +// Bitwise and +void BigUnsigned::bitAnd(const BigUnsigned &a, const BigUnsigned &b) { + // Block unsafe calls + if (this == &a || this == &b) + throw "BigUnsigned::bitAnd: One of the arguments is the invoked object"; + len = (a.len >= b.len) ? b.len : a.len; + allocate(len); + BlkNum i; + Blk *blkI; + const Blk *aBlkI, *bBlkI; + for (i = 0, blkI = blk, aBlkI = a.blk, bBlkI = b.blk; + i < len; i++, blkI++, aBlkI++, bBlkI++) + *blkI = *aBlkI & *bBlkI; + zapLeadingZeros(); +} + +// Bitwise or +void BigUnsigned::bitOr(const BigUnsigned &a, const BigUnsigned &b) { + // Block unsafe calls + if (this == &a || this == &b) + throw "BigUnsigned::bitOr: One of the arguments is the invoked object"; + BlkNum i; + Blk *blkI; + const BigUnsigned *a2, *b2; + if (a.len >= b.len) { + a2 = &a; + b2 = &b; + } else { + a2 = &b; + b2 = &a; + } + allocate(a2->len); + const Blk *a2BlkI, *b2BlkI; + for (i = 0, blkI = blk, a2BlkI = a2->blk, b2BlkI = b2->blk; + i < b2->len; i++, blkI++, a2BlkI++, b2BlkI++) + *blkI = *a2BlkI | *b2BlkI; + for (; i < a2->len; i++, blkI++, a2BlkI++) + *blkI = *a2BlkI; + len = a2->len; +} + +// Bitwise xor +void BigUnsigned::bitXor(const BigUnsigned &a, const BigUnsigned &b) { + // Block unsafe calls + if (this == &a || this == &b) + throw "BigUnsigned::bitXor: One of the arguments is the invoked object"; + BlkNum i; + Blk *blkI; + const BigUnsigned *a2, *b2; + if (a.len >= b.len) { + a2 = &a; + b2 = &b; + } else { + a2 = &b; + b2 = &a; + } + allocate(b2->len); + const Blk *a2BlkI, *b2BlkI; + for (i = 0, blkI = blk, a2BlkI = a2->blk, b2BlkI = b2->blk; + i < b2->len; i++, blkI++, a2BlkI++, b2BlkI++) + *blkI = *a2BlkI ^ *b2BlkI; + for (; i < a2->len; i++, blkI++, a2BlkI++) + *blkI = *a2BlkI; + len = a2->len; + zapLeadingZeros(); +} + +// INCREMENT/DECREMENT OPERATORS + +// Prefix increment +void BigUnsigned::operator ++() { + BlkNum i; + Blk *blkI; + bool carry = true; + for (i = 0, blkI = blk; i < len && carry; i++) { + (*blkI)++; + carry = (*blkI == 0); + } + if (carry) { + allocateAndCopy(len + 1); + *blkI = 1; + } +} + +// Postfix increment: same as prefix +void BigUnsigned::operator ++(int) { + operator ++(); +} + +// Prefix decrement +void BigUnsigned::operator --() { + if (len == 0) + throw "BigUnsigned::operator --(): Cannot decrement an unsigned zero"; + BlkNum i; + Blk *blkI; + bool borrow = true; + for (i = 0, blkI = blk; borrow; i++) { + borrow = (*blkI == 0); + (*blkI)--; + } + if (blk[len - 1] == 0) + len--; +} + +// Postfix decrement: same as prefix +void BigUnsigned::operator --(int) { + operator --(); +} + diff --git a/BigUnsigned.h b/BigUnsigned.h new file mode 100644 index 0000000..879d713 --- /dev/null +++ b/BigUnsigned.h @@ -0,0 +1,251 @@ +/* +* Matt McCutchen's Big Integer Library +* http://mysite.verizon.net/mccutchen/bigint/ +*/ + +#ifndef BIGUNSIGNED +#define BIGUNSIGNED + +/* +* A BigUnsigned object represents a nonnegative integer of size +* limited only by available memory. A BigUnsigned can be +* created from and converted back to most integral types, +* and many math operations are defined on them. +* +* The number is stored as a series of blocks in a +* dynamically allocated array. It is as if the numbers +* were written digit by digit in base 2^32. +*/ + +class BigUnsigned { + + // TYPES & CONSTANTS + public: + enum CmpRes { less = -1, equal = 0, greater = 1 }; // Enumeration for the result of a comparison + typedef unsigned long Blk; // The number block type that BigUnsigneds are built from + typedef unsigned int BlkNum; // Type for the index of a block in the array + + // FIELDS + protected: + BlkNum cap; // The current allocated capacity of this BigUnsigned (in blocks) + BlkNum len; // The actual length of the number stored in this BigUnsigned (in blocks) + Blk *blk; // Dynamically allocated array of the number blocks + + // MANAGEMENT + protected: + BigUnsigned(int, BlkNum c); // Creates a BigUnsigned with a capacity + void zapLeadingZeros(); // Decreases len to eliminate leading zeros + void allocate(BlkNum c); // Ensures the number array has at least the indicated capacity, maybe discarding contents + void allocateAndCopy(BlkNum c); // Ensures the number array has at least the indicated capacity, preserving its contents + public: + BigUnsigned(); // Default constructor (value is 0) + BigUnsigned(const BigUnsigned &x); // Copy constructor + void operator=(const BigUnsigned &x); // Assignment operator + BigUnsigned(const Blk *b, BlkNum l); // Constructor from an array of blocks + // Constructors from integral types + BigUnsigned(unsigned long x); + BigUnsigned( long x); + BigUnsigned(unsigned int x); + BigUnsigned( int x); + BigUnsigned(unsigned short x); + BigUnsigned( short x); + ~BigUnsigned(); // Destructor + + // CONVERTERS to integral types + public: + operator unsigned long () const; + operator long () const; + operator unsigned int () const; + operator int () const; + operator unsigned short() const; + operator short() const; + + // PICKING APART + // These accessors can be used to get the pieces of the number + public: + BlkNum getCapacity() const; + BlkNum getLength() const; + Blk getBlock(BlkNum i) const; + bool isZero() const; // Often convenient for loops + + // COMPARISONS + public: + // Compares this to x like Perl's <=> + CmpRes compareTo(const BigUnsigned &x) const; + // Normal comparison operators + bool operator ==(const BigUnsigned &x) const; + bool operator !=(const BigUnsigned &x) const; + bool operator < (const BigUnsigned &x) const; + bool operator <=(const BigUnsigned &x) const; + bool operator >=(const BigUnsigned &x) const; + bool operator > (const BigUnsigned &x) const; + + // PUT-HERE OPERATIONS + /* These store the result of the operation on the arguments into this. + * a.add(b, c) is equivalent to, but faster than, a = b + c. + * Calls like a.operation(a, b) are unsafe and not allowed. */ + public: + void add (const BigUnsigned &a, const BigUnsigned &b); // Addition + void subtract (const BigUnsigned &a, const BigUnsigned &b); // Subtraction + void multiply (const BigUnsigned &a, const BigUnsigned &b); // Multiplication + void divide (const BigUnsigned &a, const BigUnsigned &b); // Division + void modulo (const BigUnsigned &a, const BigUnsigned &b); // Modular reduction + void bitAnd (const BigUnsigned &a, const BigUnsigned &b); // Bitwise AND + void bitOr (const BigUnsigned &a, const BigUnsigned &b); // Bitwise OR + void bitXor (const BigUnsigned &a, const BigUnsigned &b); // Bitwise XOR + void bitShiftLeft (const BigUnsigned &a, unsigned int b); // Bitwise left shift + void bitShiftRight(const BigUnsigned &a, const BigUnsigned &b); // Bitwise right shift + + // NORMAL OPERATORS + // These perform the operation on this (to the left of the operator) + // and x (to the right of the operator) and return a new BigUnsigned with the result. + public: + BigUnsigned operator +(const BigUnsigned &x) const; // Addition + BigUnsigned operator -(const BigUnsigned &x) const; // Subtraction + BigUnsigned operator *(const BigUnsigned &x) const; // Multiplication + BigUnsigned operator /(const BigUnsigned &x) const; // Division + BigUnsigned operator %(const BigUnsigned &x) const; // Modular reduction + BigUnsigned operator &(const BigUnsigned &x) const; // Bitwise AND + BigUnsigned operator |(const BigUnsigned &x) const; // Bitwise OR + BigUnsigned operator ^(const BigUnsigned &x) const; // Bitwise XOR + + // ASSIGNMENT OPERATORS + // These perform the operation on this and x, storing the result into this. + public: + void operator +=(const BigUnsigned &x); // Addition + void operator -=(const BigUnsigned &x); // Subtraction + void operator *=(const BigUnsigned &x); // Multiplication + void operator /=(const BigUnsigned &x); // Division + void operator %=(const BigUnsigned &x); // Modular reduction + void operator &=(const BigUnsigned &x); // Bitwise AND + void operator |=(const BigUnsigned &x); // Bitwise OR + void operator ^=(const BigUnsigned &x); // Bitwise XOR + + // INCREMENT/DECREMENT OPERATORS + // These increase or decrease the number by 1. To discourage side effects, + // these do not return *this, so prefix and postfix behave the same. + public: + void operator ++( ); // Prefix increment + void operator ++(int); // Postfix decrement + void operator --( ); // Prefix increment + void operator --(int); // Postfix decrement + +}; + +// MANAGEMENT + +inline BigUnsigned::BigUnsigned(int, BlkNum c) : cap(c), len(0) { + blk = new Blk[cap]; +} + +inline void BigUnsigned::zapLeadingZeros() { + for (Blk *blkLenM1 = blk + len - 1; len > 0 && *blkLenM1 == 0; len--, blkLenM1--) + ; +} + +inline BigUnsigned::BigUnsigned() : cap(0), len(0) { + blk = new Blk[0]; +} + +inline BigUnsigned::~BigUnsigned() { + delete [] blk; +} + +// PICKING APART +inline BigUnsigned::BlkNum BigUnsigned::getCapacity() const { return cap; } +inline BigUnsigned::BlkNum BigUnsigned::getLength() const { return len; } +// Note that getBlock returns 0 if the block index is beyond the length of the number. +// A routine that uses this accessor can safely assume a BigUnsigned has 0s infinitely to the left. +inline BigUnsigned::Blk BigUnsigned::getBlock(BlkNum i) const { return i >= len ? 0 : blk[i]; } +inline bool BigUnsigned::isZero() const { return len == 0; } + +// COMPARISONS +inline bool BigUnsigned::operator==(const BigUnsigned &x) const { return compareTo(x) == equal ; } +inline bool BigUnsigned::operator!=(const BigUnsigned &x) const { return compareTo(x) != equal ; } +inline bool BigUnsigned::operator< (const BigUnsigned &x) const { return compareTo(x) == less ; } +inline bool BigUnsigned::operator<=(const BigUnsigned &x) const { return compareTo(x) != greater; } +inline bool BigUnsigned::operator>=(const BigUnsigned &x) const { return compareTo(x) != less ; } +inline bool BigUnsigned::operator> (const BigUnsigned &x) const { return compareTo(x) == greater; } + +// 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 BigUnsigned BigUnsigned::operator +(const BigUnsigned &x) const { + BigUnsigned ans; + ans.add(*this, x); + return ans; +} +inline BigUnsigned BigUnsigned::operator -(const BigUnsigned &x) const { + BigUnsigned ans; + ans.subtract(*this, x); + return ans; +} +inline BigUnsigned BigUnsigned::operator *(const BigUnsigned &x) const { + BigUnsigned ans; + ans.multiply(*this, x); + return ans; +} +inline BigUnsigned BigUnsigned::operator /(const BigUnsigned &x) const { + BigUnsigned ans; + ans.divide(*this, x); + return ans; +} +inline BigUnsigned BigUnsigned::operator %(const BigUnsigned &x) const { + BigUnsigned ans; + ans.modulo(*this, x); + return ans; +} +inline BigUnsigned BigUnsigned::operator &(const BigUnsigned &x) const { + BigUnsigned ans; + ans.bitAnd(*this, x); + return ans; +} +inline BigUnsigned BigUnsigned::operator |(const BigUnsigned &x) const { + BigUnsigned ans; + ans.bitOr(*this, x); + return ans; +} +inline BigUnsigned BigUnsigned::operator ^(const BigUnsigned &x) const { + BigUnsigned ans; + ans.bitXor(*this, x); + return ans; +} + +// ASSIGNMENT OPERATORS +// These create a copy of this, then invoke the appropriate +// put-here operation on this, passing the copy and x. +inline void BigUnsigned::operator +=(const BigUnsigned &x) { + BigUnsigned thisCopy(*this); + add(thisCopy, x); +} +inline void BigUnsigned::operator -=(const BigUnsigned &x) { + BigUnsigned thisCopy(*this); + subtract(thisCopy, x); +} +inline void BigUnsigned::operator *=(const BigUnsigned &x) { + BigUnsigned thisCopy(*this); + multiply(thisCopy, x); +} +inline void BigUnsigned::operator /=(const BigUnsigned &x) { + BigUnsigned thisCopy(*this); + divide(thisCopy, x); +} +inline void BigUnsigned::operator %=(const BigUnsigned &x) { + BigUnsigned thisCopy(*this); + modulo(thisCopy, x); +} +inline void BigUnsigned::operator &=(const BigUnsigned &x) { + BigUnsigned thisCopy(*this); + bitAnd(thisCopy, x); +} +inline void BigUnsigned::operator |=(const BigUnsigned &x) { + BigUnsigned thisCopy(*this); + bitOr(thisCopy, x); +} +inline void BigUnsigned::operator ^=(const BigUnsigned &x) { + BigUnsigned thisCopy(*this); + bitXor(thisCopy, x); +} + +#endif diff --git a/Makefile b/Makefile new file mode 100644 index 0000000..8231720 --- /dev/null +++ b/Makefile @@ -0,0 +1,26 @@ +# +# Matt McCutchen's Big Integer Library +# +# Please see the project Web site at +# http://mysite.verizon.net/mccutchen/bigint/ +# for more information and the latest version. +# +# December 16, 2004 version +# + +library : BigUnsigned.o BigInteger.o BigIntegerIO.o + +BigUnsigned.o : BigUnsigned.h BigUnsigned.cpp + g++ -c BigUnsigned.cpp + +BigInteger.o : BigUnsigned.h BigInteger.h BigInteger.cpp + g++ -c BigInteger.cpp + +BigIntegerIO.o : BigUnsigned.h BigInteger.h BigIntegerIO.cpp + g++ -c BigIntegerIO.cpp + +po3demo : library PowersOfThreeDemo.cpp + g++ -opo3demo BigUnsigned.o BigInteger.o BigIntegerIO.o PowersOfThreeDemo.cpp + +clean : + rm -f *.o po3demo diff --git a/PowersOfThreeDemo.cpp b/PowersOfThreeDemo.cpp new file mode 100644 index 0000000..efd62a3 --- /dev/null +++ b/PowersOfThreeDemo.cpp @@ -0,0 +1,18 @@ +#include +#include +#include "BigUnsigned.h" +#include "BigInteger.h" +#include "BigIntegerIO.h" + +int main() { + std::cout << "POWERS OF THREE DEMO" << std::endl; + std::cout << "Uses Matt McCutchen's Big Integer Library" << std::endl; + + BigUnsigned x(1), three(3); + for (int power = 0; power <= 500; power++) { + std::cout << "3^" << power << " = " << x << std::endl; + x *= three; + } + + return 0; +}