From e67d60496ce8582666f1fb77503acfe5d05c70d4 Mon Sep 17 00:00:00 2001 From: Matt McCutchen Date: Sat, 27 Jan 2007 16:06:12 -0500 Subject: [PATCH] Old snapshot `BigInteger-2004.12.16'; see the ChangeLog file. --- BigInteger.cpp | 553 +++++++++++++++++++++++++++++ BigInteger.h | 214 ++++++++++++ BigIntegerIO.cpp | 62 ++++ BigIntegerIO.h | 19 + BigUnsigned.cpp | 787 ++++++++++++++++++++++++++++++++++++++++++ BigUnsigned.h | 251 ++++++++++++++ Makefile | 26 ++ PowersOfThreeDemo.cpp | 18 + 8 files changed, 1930 insertions(+) create mode 100644 BigInteger.cpp create mode 100644 BigInteger.h create mode 100644 BigIntegerIO.cpp create mode 100644 BigIntegerIO.h create mode 100644 BigUnsigned.cpp create mode 100644 BigUnsigned.h create mode 100644 Makefile create mode 100644 PowersOfThreeDemo.cpp 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; +} -- 2.34.1