--- /dev/null
+/*
+* 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 --();
+}
+
--- /dev/null
+/*
+* 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
--- /dev/null
+/*
+* 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;
+}
--- /dev/null
+/*
+* Matt McCutchen's Big Integer Library
+* See: http://mysite.verizon.net/mccutchen/bigint/
+*/
+
+#ifndef BIGINTEGERIO
+#define BIGINTEGERIO
+
+#include "BigUnsigned.h"
+#include "BigInteger.h"
+#include <iostream>
+
+// 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
--- /dev/null
+/*
+* 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 --();
+}
+
--- /dev/null
+/*
+* 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
--- /dev/null
+#
+# 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
--- /dev/null
+#include <string>
+#include <iostream>
+#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;
+}
Matt McCutchen's Web Site / bigint / bigint.git / commitdiff