/*
* Matt McCutchen's Big Integer Library
-* See: http://mysite.verizon.net/mccutchen/bigint/
+* http://mysite.verizon.net/mccutchen/bigint/
*/
-#include "BigInteger.h"
+#include "BigInteger.hh"
// MANAGEMENT
}
// Constructor from an array of blocks and a sign
-BigInteger::BigInteger(const Blk *b, BlkNum l, Sign s) : BigUnsigned(b, l) {
+BigInteger::BigInteger(const Blk *b, Index l, Sign s) : BigUnsigned(b, l) {
switch (s) {
case zero:
case positive:
sign = (len == 0) ? zero : s;
break;
default:
- throw "BigInteger::BigInteger(Blk *, BlkNum, Sign): Invalid sign";
+ throw "BigInteger::BigInteger(Blk *, Index, Sign): Invalid sign";
}
}
sign = (len == 0) ? zero : s;
break;
default:
- throw "BigInteger::BigInteger(Blk *, BlkNum, Sign): Invalid sign";
+ throw "BigInteger::BigInteger(Blk *, Index, Sign): Invalid sign";
}
}
BigUnsigned::multiply(a, b);
}
-// Division
-void BigInteger::divide(const BigInteger &a, const BigInteger &b) {
+/*
+* DIVISION WITH REMAINDER
+* Please read the comments before the definition of
+* `BigUnsigned::divideWithRemainder' in `BigUnsigned.cc' for lots of
+* information you should know before reading this function.
+*
+* Following Knuth, I decree that x / y is to be
+* 0 if y==0 and floor(real-number x / y) if y!=0.
+* Then x % y shall be x - y*(integer x / y).
+*
+* Note that x = y * (x / y) + (x % y) always holds.
+* In addition, (x % y) is from 0 to y - 1 if y > 0,
+* and from -(|y| - 1) to 0 if y < 0. (x % y) = x if y = 0.
+*
+* Examples: (q = a / b, r = a % b)
+* a b q r
+* === === === ===
+* 4 3 1 1
+* -4 3 -2 2
+* 4 -3 -2 -2
+* -4 -3 1 -1
+*/
+void BigInteger::divideWithRemainder(const BigInteger &b, BigInteger &q) {
// 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;
+ if (this == &b || this == &q || &b == &q)
+ throw "BigInteger::divideWithRemainder: One of the arguments is the invoked object";
+ // Division by zero gives quotient 0 and remainder *this
+ if (b.sign == zero) {
+ q.len = 0;
+ q.sign = zero;
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;
+ // 0 / b gives quotient 0 and remainder 0
+ if (sign == zero) {
+ q.len = 0;
+ q.sign = zero;
return;
}
- // Perform modular reduction on the magnitudes
- BigUnsigned::modulo(a, b);
- // If the result is zero, set the sign to zero.
+
+ // Here *this != 0, b != 0.
+
+ // Do the operands have the same sign?
+ if (sign == b.sign) {
+ // Yes: easy case. Quotient is zero or positive.
+ q.sign = positive;
+ } else {
+ // No: harder case. Quotient is negative.
+ q.sign = negative;
+ // Decrease the magnitude of the dividend by one.
+ BigUnsigned::operator --();
+ /*
+ * We tinker with the dividend before and with the
+ * quotient and remainder after so that the result
+ * comes out right. To see why it works, consider the following
+ * list of examples, where A is the magnitude-decreased
+ * a, Q and R are the results of BigUnsigned division
+ * with remainder on A and |b|, and q and r are the
+ * final results we want:
+ *
+ * a A b Q R q r
+ * -3 -2 3 0 2 -1 0
+ * -4 -3 3 1 0 -2 2
+ * -5 -4 3 1 1 -2 1
+ * -6 -5 3 1 2 -2 0
+ *
+ * It appears that we need a total of 3 corrections:
+ * Decrease the magnitude of a to get A. Increase the
+ * magnitude of Q to get q (and make it negative).
+ * Find r = (b - 1) - R and give it the desired sign.
+ */
+ }
+
+ // Divide the magnitudes.
+ BigUnsigned::divideWithRemainder(b, q);
+
+ if (sign != b.sign) {
+ // More for the harder case (as described):
+ // Increase the magnitude of the quotient by one.
+ q.BigUnsigned::operator ++();
+ // Modify the remainder.
+ BigUnsigned temp(*this);
+ BigUnsigned::subtract(b, temp);
+ BigUnsigned::operator --();
+ }
+
+ // Sign of the remainder is always the sign of the divisor b.
+ sign = b.sign;
+
+ // Set signs to zero as necessary. (Thanks David Allen!)
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;
- }
+ if (q.len == 0)
+ q.sign = zero;
+
+ // WHEW!!!
}
// Negation
#ifndef BIGINTEGER
#define BIGINTEGER
-#include "BigUnsigned.h"
+#include "BigUnsigned.hh"
/*
-*
* 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.
+* and many math operations are defined on BigIntegers.
*
* 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.
+* were written digit by digit in base 256 ^ sizeof(unsigned long).
*
* This class is derived from BigUnsigned, which represents
-* a large nonnegative integer. This should be understood
+* a large nonnegative integer. BigUnsigned should be studied
* 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.
// MANAGEMENT
protected:
- BigInteger(Sign s, BlkNum c); // Creates a BigInteger with a sign and capacity
+ BigInteger(Sign s, Index c) : BigUnsigned(0, c), sign(s) {}; // Creates a BigInteger with a sign and capacity
public:
- BigInteger(); // Default constructor (value is 0)
- BigInteger(const BigInteger &x); // Copy constructor
+
+ BigInteger() : BigUnsigned(), sign(zero) {} // Default constructor (value is 0)
+ BigInteger(const BigInteger &x) : BigUnsigned(x), sign(x.sign) {}; // 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 Blk *b, Index l) : BigUnsigned(b, l) { // Constructor from an array of blocks
+ sign = (len == 0) ? zero : positive;
+ }
+ BigInteger(const Blk *b, Index l, Sign s); // Constructor from an array of blocks and a sign
+ BigInteger(const BigUnsigned &x) : BigUnsigned(x) { // Constructor from a BigUnsigned
+ sign = (len == 0) ? zero : positive;
+ }
BigInteger(const BigUnsigned &x, Sign s); // Constructor from a BigUnsigned and a sign
// Constructors from integral types
BigInteger(unsigned long x);
// 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;
+ bool operator ==(const BigInteger &x) const {
+ return sign == x.sign && BigUnsigned::operator ==(x);
+ }
+ bool operator !=(const BigInteger &x) const { return !operator ==(x); };
+ bool operator < (const BigInteger &x) const { return compareTo(x) == less ; }
+ bool operator <=(const BigInteger &x) const { return compareTo(x) != greater; }
+ bool operator >=(const BigInteger &x) const { return compareTo(x) != less ; }
+ bool operator > (const BigInteger &x) const { return compareTo(x) == greater; }
// PUT-HERE OPERATIONS
/* These store the result of the operation on the arguments into this.
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
+ /* Divisive stuff
+ * `a.divideWithRemainder(b, q)' is like `q = a / b, a %= b'.
+ * Semantics similar to Donald E. Knuth's are used for / and %,
+ * and these usually differ from the semantics of primitive-type
+ * / and % when negatives and/or zeroes are involved.
+ * Look in `BigInteger.cc' for details.
+ */
+ void divideWithRemainder(const BigInteger &b, BigInteger &q);
+ void divide(const BigInteger &a, const BigInteger &b) {
+ // Division, deprecated and provided for compatibility
+ BigInteger a2(a);
+ a2.divideWithRemainder(b, *this);
+ // quotient now in *this
+ // don't care about remainder left in a2
+ }
+ void modulo(const BigInteger &a, const BigInteger &b) {
+ // Modular reduction, deprecated and provided for compatibility
+ *this = a;
+ BigInteger q;
+ divideWithRemainder(b, q);
+ // remainder now in *this
+ // don't care about quotient left in q
+ }
+ 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.
+ // a BigInteger will convert it to a BigUnsigned,
+ // which takes its absolute value.
// NORMAL OPERATORS
// These perform the operation on this (to the left of the operator)
};
-// 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
multiply(thisCopy, x);
}
inline void BigInteger::operator /=(const BigInteger &x) {
+ // Updated for divideWithRemainder
BigInteger thisCopy(*this);
- divide(thisCopy, x);
+ thisCopy.divideWithRemainder(x, *this);
+ // quotient left in *this
+ // don't care about remainder left in thisCopy
}
inline void BigInteger::operator %=(const BigInteger &x) {
- BigInteger thisCopy(*this);
- modulo(thisCopy, x);
+ // Shortcut (woohoo!)
+ BigInteger q;
+ divideWithRemainder(x, q);
+ // remainder left in *this
+ // don't care about quotient left in q
}
// This one is trivial
inline void BigInteger::flipSign() {
+++ /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 "BigIntegerUtils.hh"
+#include "BigUnsignedInABase.hh"
+
+/*
+* This file includes:
+* (1) `std::string <=> BigUnsigned/BigInteger' conversion routines easier than `BigUnsignedInABase'
+* (2) << and >> operators for BigUnsigned/BigInteger, std::istream/std::ostream
+*/
+
+std::string easyBUtoString(const BigUnsigned &x) {
+ return std::string(BigUnsignedInABase(x, 10));
+}
+
+std::string easyBItoString(const BigInteger &x) {
+ return (x.getSign() == BigInteger::negative) ?
+ (std::string("-") + easyBUtoString(x)) : (easyBUtoString(x));
+}
+
+BigUnsigned easyStringToBU(const std::string &s) {
+ return BigUnsigned(BigUnsignedInABase(s, 10));
+}
+
+BigInteger easyStringToBI(const std::string &s) {
+ return (s[0] == '-') ?
+ BigInteger(easyStringToBU(s.substr(1, s.length() - 1)), BigInteger::negative) :
+ BigInteger(easyStringToBU(s));
+}
+
+// Outputs x to os, obeying the flags `dec', `hex', `bin', and `showbase'.
+std::ostream &operator <<(std::ostream &os, const BigUnsigned &x) {
+ BigUnsignedInABase::Base base;
+ long osFlags = os.flags();
+ if (osFlags & os.dec)
+ base = 10;
+ else if (osFlags & os.hex) {
+ base = 16;
+ if (osFlags & os.showbase)
+ os << "0x";
+ } else if (osFlags & os.oct) {
+ base = 8;
+ if (osFlags & os.showbase)
+ os << '0';
+ } else
+ throw "std::ostream << BigUnsigned: Could not determine the desired base from output-stream flags";
+ std::string s = std::string(BigUnsignedInABase(x, base));
+ os << s;
+ return os;
+}
+// Outputs x to os, obeying the flags `dec', `hex', `bin', and `showbase'.
+// My somewhat arbitrary policy: a negative sign comes before a base indicator (like -0xFF).
+std::ostream &operator <<(std::ostream &os, const BigInteger &x) {
+ if (x.getSign() == BigInteger::negative)
+ os << '-';
+ os << (const BigUnsigned &)(x);
+ return os;
+}
--- /dev/null
+/*
+* Matt McCutchen's Big Integer Library
+* http://mysite.verizon.net/mccutchen/bigint/
+*/
+
+#ifndef BIGINTEGERUTILS
+#define BIGINTEGERUTILS
+
+#include "BigInteger.hh"
+#include <string>
+#include <iostream>
+
+/*
+* This file includes:
+* (1) `std::string <=> BigUnsigned/BigInteger' conversion routines easier than `BigUnsignedInABase'
+* (2) << and >> operators for BigUnsigned/BigInteger, std::istream/std::ostream
+*/
+
+// Conversion routines. Base 10 only.
+std::string easyBUtoString(const BigUnsigned &x);
+std::string easyBItoString(const BigInteger &x);
+BigUnsigned easyStringToBU(const std::string &s);
+BigInteger easyStringToBI(const std::string &s);
+
+// Outputs x to os, obeying the flags `dec', `hex', `bin', and `showbase'.
+std::ostream &operator <<(std::ostream &os, const BigUnsigned &x);
+
+// Outputs x to os, obeying the flags `dec', `hex', `bin', and `showbase'.
+// My somewhat arbitrary policy: a negative sign comes before a base indicator (like -0xFF).
+std::ostream &operator <<(std::ostream &os, const BigInteger &x);
+
+#endif
--- /dev/null
+/*
+* Matt McCutchen's Big Integer Library
+* http://mysite.verizon.net/mccutchen/bigint/
+*/
+
+#include "BigUnsigned.hh"
+
+// The "management" routines that used to be here are now in NumberlikeArray.cpp.
+
+/*
+* 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[0] = 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[0] = 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[0] = 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[0] = 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[0] = 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[0] = 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[0];
+ 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[0] & lMask) == blk[0])
+ return (long) blk[0];
+ 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[0] & uiMask) == blk[0])
+ return (unsigned int) blk[0];
+ 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[0] & iMask) == blk[0])
+ return (int) blk[0];
+ 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[0] & usMask) == blk[0])
+ return (unsigned short) blk[0];
+ 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[0] & sMask) == blk[0])
+ return (short) blk[0];
+ 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.
+ Index i = len;
+ while (i > 0) {
+ i--;
+ if (blk[i] == x.blk[i])
+ continue;
+ else if (blk[i] > x.blk[i])
+ 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;
+ Index 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;
+ }
+ // 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, carryIn = false; i < b2->len; i++) {
+ // Add input blocks
+ temp = a2->blk[i] + b2->blk[i];
+ // If a rollover occurred, the result is less than either input.
+ // This test is used many times in the BigUnsigned code.
+ carryOut = (temp < a2->blk[i]);
+ // If a carry was input, handle it
+ if (carryIn) {
+ temp++;
+ carryOut |= (temp == 0);
+ }
+ blk[i] = 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++) {
+ temp = a2->blk[i] + 1;
+ carryIn = (temp == 0);
+ blk[i] = temp;
+ }
+ // If the carry was resolved but the larger number
+ // still has blocks, copy them over.
+ for (; i < a2->len; i++)
+ blk[i] = a2->blk[i];
+ // Set the extra block if there's still a carry, decrease length otherwise
+ if (carryIn)
+ blk[i] = 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;
+ Index i;
+ // Set preliminary length and make room
+ len = a.len;
+ allocate(len);
+ // For each block index that is present in both inputs...
+ for (i = 0, borrowIn = false; i < b.len; i++) {
+ temp = a.blk[i] - b.blk[i];
+ // If a reverse rollover occurred, the result is greater than the block from a.
+ borrowOut = (temp > a.blk[i]);
+ // Handle an incoming borrow
+ if (borrowIn) {
+ borrowOut |= (temp == 0);
+ temp--;
+ }
+ blk[i] = 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++) {
+ borrowIn = (a.blk[i] == 0);
+ blk[i] = a.blk[i] - 1;
+ }
+ // If there's still a borrow, the result is negative.
+ // Throw an exception, but zero out this object first just in case.
+ 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++)
+ blk[i] = a.blk[i];
+ // 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
+ Index i, j, k;
+ unsigned int i2;
+ Blk aBlk, bHigh, temp;
+ bool carryIn, carryOut;
+ // Set preliminary length and make room
+ len = a.len + b.len;
+ allocate(len);
+ // Zero out this object
+ for (i = 0; i < len; i++)
+ blk[i] = 0;
+ // For each block of the first number...
+ for (i = 0; i < a.len; i++) {
+ // For each 1-bit of that block...
+ for (i2 = 0, aBlk = a.blk[i]; 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. */
+ bHigh = 0;
+ for (j = 0, k = i, carryIn = false; j < b.len; j++, k++) {
+ temp = blk[k] + ((b.blk[j] << i2) | bHigh);
+ carryOut = (temp < blk[k]);
+ if (carryIn) {
+ temp++;
+ carryOut |= (temp == 0);
+ }
+ blk[k] = temp;
+ carryIn = carryOut;
+ bHigh = (i2 == 0) ? 0 : b.blk[j] >> (8 * sizeof(Blk) - i2);
+ }
+ temp = blk[k] + bHigh;
+ carryOut = (temp < blk[k]);
+ if (carryIn) {
+ temp++;
+ carryOut |= (temp == 0);
+ }
+ blk[k] = temp;
+ carryIn = carryOut;
+ k++; // Added by Matt 2004.12.23: Move to the next block. It belongs here (and there was a corresponding line in the division routine), but I'm not certain whether it ever matters.
+ for (; carryIn; k++) {
+ blk[k]++;
+ carryIn = (blk[k] == 0);
+ }
+ }
+ }
+ // Zap possible leading zero
+ if (blk[len - 1] == 0)
+ len--;
+}
+
+/*
+* DIVISION WITH REMAINDER
+* The functionality of divide, modulo, and %= is included in this one monstrous call,
+* which deserves some explanation.
+*
+* The division *this / b is performed.
+* Afterwards, q has the quotient, and *this has the remainder.
+* Thus, a call is like q = *this / b, *this %= b.
+*
+* This seemingly bizarre pattern of inputs and outputs has a justification. The
+* ``put-here operations'' are supposed to be fast. Therefore, they accept inputs
+* and provide outputs in the most convenient places so that no value ever needs
+* to be copied in its entirety. That way, the client can perform exactly the
+* copying it needs depending on where the inputs are and where it wants the output.
+*/
+void BigUnsigned::divideWithRemainder(const BigUnsigned &b, BigUnsigned &q) {
+ // Block unsafe calls
+ if (this == &b || &q == &b || this == &q)
+ throw "BigUnsigned::divideWithRemainder: Some two objects involved are the same";
+
+ /*
+ * Note that the mathematical definition of mod (I'm trusting Knuth) is somewhat
+ * different from the way the normal C++ % operator behaves in the case of division by 0.
+ * This function does it Knuth's way.
+ *
+ * We let a / 0 == 0 (it doesn't matter) and a % 0 == a, no exceptions thrown.
+ * This allows us to preserve both Knuth's demand that a mod 0 == a
+ * and the useful property that (a / b) * b + (a % b) == a.
+ */
+ if (b.len == 0) {
+ q.len = 0;
+ return;
+ }
+
+ /*
+ * If *this.len < b.len, then *this < b, and we can be sure that b doesn't go into
+ * *this at all. The quotient is 0 and *this is already the remainder (so leave it alone).
+ */
+ if (len < b.len) {
+ q.len = 0;
+ return;
+ }
+
+ /*
+ * At this point we know *this > b > 0. (Whew!)
+ */
+
+ /* DEBUG *
+ std::cout << "divideWithRemainder starting\n"
+ << "length of dividend: " << len
+ << "\nlast block of dividend: " << getBlock(0)
+ << "\nlength of divisor: " << b.len
+ << "\nlast block of divisor: " << b.getBlock(0)
+ << std::endl; */
+
+ /*
+ * Overall method: Subtract b, shifted varying amounts to
+ * the left, from this, setting the bit in the quotient q
+ * whenever the subtraction succeeds. Eventually q will contain the entire
+ * quotient, and this will be left with the remainder.
+ *
+ * We use work2 to temporarily store the result of a subtraction.
+ * But we don't even compute the i lowest blocks of the result,
+ * because they are unaffected (we shift left i places).
+ * */
+ // Variables for the calculation
+ Index i, j, k;
+ unsigned int i2;
+ Blk bHigh, temp;
+ bool borrowIn, borrowOut;
+
+ // Make sure we have an extra zero block just past the value,
+ // but don't increase the logical length. A shifted subtraction
+ // (for example, subtracting 1 << 2 from 4) might stick into
+ // this block.
+ allocateAndCopy(len + 1);
+ blk[len] = 0;
+
+ // work2 holds part of the result of a subtraction.
+ // (There's no work1. The name work2 is from a previous version.)
+ Blk *work2 = new Blk[len];
+
+ // Set preliminary length for quotient and make room
+ q.len = len - b.len + 1;
+ q.allocate(q.len);
+ // Zero out the quotient
+ for (i = 0; i < q.len; i++)
+ q.blk[i] = 0;
+
+ // For each possible left-shift of b in blocks...
+ i = q.len;
+ while (i > 0) {
+ i--;
+ // For each possible left-shift of b in bits...
+ q.blk[i] = 0;
+ i2 = 8 * sizeof(Blk);
+ while (i2 > 0) {
+ i2--;
+ /*
+ * Subtract b, shifted left i blocks and i2 bits, from this.
+ * and store the answer in work2.
+ *
+ * Compare this to the middle section of `multiply'. They
+ * are in many ways analogous.
+ */
+ bHigh = 0;
+ for (j = 0, k = i, borrowIn = false; j < b.len; j++, k++) {
+ temp = blk[k] - ((b.blk[j] << i2) | bHigh);
+ borrowOut = (temp > blk[k]);
+ if (borrowIn) {
+ borrowOut |= (temp == 0);
+ temp--;
+ }
+ work2[j] = temp;
+ borrowIn = borrowOut;
+ bHigh = (i2 == 0) ? 0 : b.blk[j] >> (8 * sizeof(Blk) - i2);
+ }
+ temp = blk[k] - bHigh;
+ borrowOut = (temp > blk[k]);
+ if (borrowIn) {
+ borrowOut |= (temp == 0);
+ temp--;
+ }
+ work2[j] = temp;
+ borrowIn = borrowOut;
+ j++;
+ k++;
+ for (; k < len && borrowIn; j++, k++) {
+ borrowIn = (blk[k] == 0);
+ work2[j] = blk[k] - 1;
+ }
+ /* If the subtraction was performed successfully (!borrowIn), set bit i2
+ * in block i of the quotient, and copy the changed portion of
+ * work2 back to this. Otherwise, reset that bit and move on. */
+ if (!borrowIn) {
+ q.blk[i] |= (1 << i2);
+ while (j > 0) {
+ j--;
+ k--;
+ blk[k] = work2[j];
+ }
+ }
+ }
+ }
+ // Zap possible leading zero in quotient
+ if (q.blk[q.len - 1] == 0)
+ q.len--;
+ // Zap any/all leading zeros in remainder
+ zapLeadingZeros();
+ // Deallocate temporary array.
+ // (Thanks to Brad Spencer for noticing my accidental omission of this!)
+ delete [] work2;
+
+ /* DEBUG *
+ std::cout << "divideWithRemainder complete\n"
+ << "length of quotient: " << q.len
+ << "\nlast block of quotient: " << q.getBlock(0)
+ << "\nlength of remainder: " << len
+ << "\nlast block of remainder: " << getBlock(0)
+ << std::endl; */
+}
+
+// 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);
+ Index i;
+ for (i = 0; i < len; i++)
+ blk[i] = a.blk[i] & b.blk[i];
+ 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";
+ Index i;
+ const BigUnsigned *a2, *b2;
+ if (a.len >= b.len) {
+ a2 = &a;
+ b2 = &b;
+ } else {
+ a2 = &b;
+ b2 = &a;
+ }
+ allocate(a2->len);
+ for (i = 0; i < b2->len; i++)
+ blk[i] = a2->blk[i] | b2->blk[i];
+ for (; i < a2->len; i++)
+ blk[i] = a2->blk[i];
+ 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";
+ Index i;
+ const BigUnsigned *a2, *b2;
+ if (a.len >= b.len) {
+ a2 = &a;
+ b2 = &b;
+ } else {
+ a2 = &b;
+ b2 = &a;
+ }
+ allocate(b2->len);
+ for (i = 0; i < b2->len; i++)
+ blk[i] = a2->blk[i] ^ b2->blk[i];
+ for (; i < a2->len; i++)
+ blk[i] = a2->blk[i];
+ len = a2->len;
+ zapLeadingZeros();
+}
+
+// INCREMENT/DECREMENT OPERATORS
+
+// Prefix increment
+void BigUnsigned::operator ++() {
+ Index i;
+ bool carry = true;
+ for (i = 0; i < len && carry; i++) {
+ blk[i]++;
+ carry = (blk[i] == 0);
+ }
+ if (carry) {
+ // Matt fixed a bug 2004.12.24: next 2 lines used to say allocateAndCopy(len + 1)
+ len++;
+ allocateAndCopy(len);
+ blk[i] = 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";
+ Index i;
+ bool borrow = true;
+ for (i = 0; borrow; i++) {
+ borrow = (blk[i] == 0);
+ blk[i]--;
+ }
+ // Zap possible leading zero (there can only be one)
+ 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/
-*/
-
-#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 --();
-}
-
#ifndef BIGUNSIGNED
#define BIGUNSIGNED
+#include "NumberlikeArray.hh"
+
/*
* 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.
+* and many math operations are defined on BigUnsigneds.
*
* 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.
+* were written digit by digit in base 256 ^ sizeof(unsigned long).
+*
+* The memory-management details that used to be in here have
+* been moved into NumberlikeArray, which BigUnsigned now derives from.
+* `(NlA)' means that member(s) are declared identically in NumberlikeArray.
+* Such members are either redeclared here to make them public or are
+* here, commented out, for reference.
*/
-class BigUnsigned {
+class BigUnsigned : protected NumberlikeArray<unsigned long> {
// 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
+ typedef NumberlikeArray<Blk>::Index Index; // (NlA) 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
+ Index cap; // (NlA) The current allocated capacity of this BigUnsigned (in blocks)
+ Index len; // (NlA) The actual length of the number stored in this BigUnsigned (in blocks)
+ Blk *blk; // (NlA) 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
+ // These members generally defer to those in NumberlikeArray, possibly with slight changes.
+ // It might be nice if one could request that constructors be inherited in C++.
+
+ BigUnsigned(int, Index c) : NumberlikeArray<Blk>(0, c) {} // Creates a BigUnsigned with a capacity
+
+ void zapLeadingZeros() { // Decreases len to eliminate leading zeros
+ while (len > 0 && blk[len - 1] == 0)
+ len--;
+ }
+
+ //void allocate(Index c); // (NlA) Ensures the number array has at least the indicated capacity, maybe discarding contents
+ //void allocateAndCopy(Index c); // (NlA) 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
+ BigUnsigned() : NumberlikeArray<Blk>() {} // Default constructor (value is 0)
+ BigUnsigned(const BigUnsigned &x) : NumberlikeArray<Blk>(x) {} // Copy constructor
+
+ void operator=(const BigUnsigned &x) { // Assignment operator
+ NumberlikeArray<Blk>::operator =(x);
+ }
+
+ BigUnsigned(const Blk *b, Index l) : NumberlikeArray<Blk>(b, l) { // Constructor from an array of blocks
+ zapLeadingZeros();
+ }
+
// Constructors from integral types
BigUnsigned(unsigned long x);
BigUnsigned( long x);
BigUnsigned( int x);
BigUnsigned(unsigned short x);
BigUnsigned( short x);
- ~BigUnsigned(); // Destructor
+ ~BigUnsigned() {} // Destructor
// CONVERTERS to integral types
public:
// 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
+ NumberlikeArray<Blk>::getCapacity;
+ NumberlikeArray<Blk>::getLength;
+ // 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.
+ Blk getBlock(Index i) const { return i >= len ? 0 : blk[i]; }
+ // Note how we replace one level of abstraction with another. Isn't that neat?
+ bool isZero() const { return NumberlikeArray<Blk>::isEmpty(); } // 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;
+ NumberlikeArray<Blk>::operator ==; // (NlA) The body used to be `{ return compareTo(x) == equal; }'. For performance reasons we use NumberlikeArray code that only worries about (in)equality and doesn't waste time determining which is bigger
+ NumberlikeArray<Blk>::operator !=; // (NlA) Ditto.
+ bool operator < (const BigUnsigned &x) const { return compareTo(x) == less ; }
+ bool operator <=(const BigUnsigned &x) const { return compareTo(x) != greater; }
+ bool operator >=(const BigUnsigned &x) const { return compareTo(x) != less ; }
+ bool operator > (const BigUnsigned &x) const { return compareTo(x) == greater; }
// 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:
+ // Easy 3
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
+ /* Divisive stuff
+ * `a.divideWithRemainder(b, q)' is like `q = a / b, a %= b'.
+ * Semantics similar to Donald E. Knuth's are used for / and %,
+ * and these differ from the semantics of primitive-type
+ * / and % under division by zero.
+ * Look in `BigUnsigned.cc' for details.
+ */
+ void divideWithRemainder(const BigUnsigned &b, BigUnsigned &q);
+ void divide(const BigUnsigned &a, const BigUnsigned &b) {
+ // Division, deprecated and provided for compatibility
+ BigUnsigned a2(a);
+ a2.divideWithRemainder(b, *this);
+ // quotient now in *this
+ // don't care about remainder left in a2
+ }
+ void modulo(const BigUnsigned &a, const BigUnsigned &b) {
+ // Modular reduction, deprecated and provided for compatibility
+ *this = a;
+ BigUnsigned q;
+ divideWithRemainder(b, q);
+ // remainder now in *this
+ // don't care about quotient left in q
+ }
+ // Bitwise
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
+
+ // These functions are declared but not defined. (Sorry.)
+ // Trying to call either will result in a link-time error.
+ void bitShiftLeft (const BigUnsigned &a, unsigned int b); // Bitwise left shift
+ void bitShiftRight(const BigUnsigned &a, unsigned int b); // Bitwise right shift
// NORMAL OPERATORS
// These perform the operation on this (to the left of the operator)
};
-// 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
// ASSIGNMENT OPERATORS
// These create a copy of this, then invoke the appropriate
// put-here operation on this, passing the copy and x.
+// Exception: those updated for divideWithRemainder.
inline void BigUnsigned::operator +=(const BigUnsigned &x) {
BigUnsigned thisCopy(*this);
add(thisCopy, x);
multiply(thisCopy, x);
}
inline void BigUnsigned::operator /=(const BigUnsigned &x) {
+ // Updated for divideWithRemainder
BigUnsigned thisCopy(*this);
- divide(thisCopy, x);
+ thisCopy.divideWithRemainder(x, *this);
+ // quotient left in *this
+ // don't care about remainder left in thisCopy
}
inline void BigUnsigned::operator %=(const BigUnsigned &x) {
- BigUnsigned thisCopy(*this);
- modulo(thisCopy, x);
+ // Shortcut (woohoo!)
+ BigUnsigned q;
+ divideWithRemainder(x, q);
+ // remainder left in *this
+ // don't care about quotient left in q
}
inline void BigUnsigned::operator &=(const BigUnsigned &x) {
BigUnsigned thisCopy(*this);
--- /dev/null
+/*
+* Matt McCutchen's Big Integer Library
+* http://mysite.verizon.net/mccutchen/bigint/
+*/
+
+#include "BigUnsignedInABase.hh"
+
+namespace {
+ unsigned int bitLen(unsigned int x) {
+ unsigned int len = 0;
+ while (x > 0) {
+ x >>= 1;
+ len++;
+ }
+ return len;
+ }
+ unsigned int ceilingDiv(unsigned int a, unsigned int b) {
+ return (a + b - 1) / b;
+ }
+}
+
+BigUnsignedInABase::BigUnsignedInABase(const BigUnsigned &x, Base base) {
+ // Check the base
+ if (base < 2)
+ throw "BigUnsignedInABase(BigUnsigned, Base): The base must be at least 2";
+ // Save the base.
+ // This pattern is seldom seen in C++, but the analogous ``this.'' is common in Java.
+ this->base = base;
+
+ // Get an upper bound on how much space we need
+ int maxBitLenOfX = x.getLength() * 8 * sizeof(BigUnsigned::Blk);
+ int minBitsPerDigit = bitLen(base) - 1;
+ int maxDigitLenOfX = ceilingDiv(maxBitLenOfX, minBitsPerDigit);
+ allocate(maxDigitLenOfX); // Get the space
+
+ BigUnsigned x2(x), buBase(base);
+ Index digitNum = 0;
+
+ while (!x2.isZero()) {
+ // Get last digit. This is like `lastDigit = x2 % buBase, x2 /= buBase'.
+ BigUnsigned lastDigit(x2);
+ lastDigit.divideWithRemainder(buBase, x2);
+ // Save the digit.
+ blk[digitNum] = Digit(lastDigit); // invokes `BigUnsigned ==> unsigned short' converter
+ // Move on. We can't run out of room: we figured it out above.
+ digitNum++;
+ }
+
+ // Save the eventual length.
+ len = digitNum;
+}
+
+BigUnsignedInABase::operator BigUnsigned() const {
+ BigUnsigned ans(0), buBase(base), temp;
+ Index digitNum = len;
+ while (digitNum > 0) {
+ digitNum--;
+ temp.multiply(ans, buBase);
+ ans.add(temp, BigUnsigned(blk[digitNum]));
+ }
+ return ans;
+}
+
+BigUnsignedInABase::BigUnsignedInABase(const std::string &s, Base base) {
+ // Check the base.
+ if (base > 36)
+ throw "BigUnsignedInABase(std::string, Base): The default string conversion routines use the symbol set 0-9, A-Z and therefore support only up to base 36. You tried a conversion with a base over 36; write your own string conversion routine.";
+ // Save the base.
+ // This pattern is seldom seen in C++, but the analogous ``this.'' is common in Java.
+ this->base = base;
+
+ len = s.length();
+ allocate(len);
+
+ Index digitNum, symbolNumInString;
+ for (digitNum = 0; digitNum < len; digitNum++) {
+ symbolNumInString = len - 1 - digitNum;
+ char theSymbol = s[symbolNumInString];
+ if (theSymbol >= '0' && theSymbol <= '9')
+ blk[digitNum] = theSymbol - '0';
+ else if (theSymbol >= 'A' && theSymbol <= 'Z')
+ blk[digitNum] = theSymbol - 'A' + 10;
+ else if (theSymbol >= 'a' && theSymbol <= 'z')
+ blk[digitNum] = theSymbol - 'a' + 10;
+ else
+ throw "BigUnsignedInABase(std::string, Base): Bad symbol in input. Only 0-9, A-Z, a-z are accepted.";
+ }
+ zapLeadingZeros();
+}
+
+BigUnsignedInABase::operator std::string() const {
+ if (base > 36)
+ throw "BigUnsignedInABase ==> std::string: The default string conversion routines use the symbol set 0-9, A-Z and therefore support only up to base 36. You tried a conversion with a base over 36; write your own string conversion routine.";
+ if (len == 0)
+ return std::string("0");
+ std::string s;
+ s.reserve(len);
+ Index digitNum, symbolNumInString;
+ for (symbolNumInString = 0; symbolNumInString < len; symbolNumInString++) {
+ digitNum = len - 1 - symbolNumInString;
+ Digit theDigit = blk[digitNum];
+ if (theDigit < 10)
+ s.push_back(char('0' + theDigit));
+ else
+ s.push_back(char('A' + theDigit - 10));
+ }
+ return s;
+}
--- /dev/null
+/*
+* Matt McCutchen's Big Integer Library
+* http://mysite.verizon.net/mccutchen/bigint/
+*/
+
+#ifndef BIGUNSIGNEDINABASE
+#define BIGUNSIGNEDINABASE
+
+#include "NumberlikeArray.hh"
+#include "BigUnsigned.hh"
+#include <string>
+
+/*
+* A BigUnsignedInABase object represents a nonnegative
+* integer of size limited only by available memory,
+* represented in a user-specified base that can fit in
+* an `unsigned short' (most can, and this saves memory).
+*
+* BigUnsignedInABase is intended as an intermediary class
+* with little functionality of its own. BigUnsignedInABase
+* objects can be constructed from, and converted to,
+* BigUnsigneds (requiring multiplication, mods, etc.) and
+* `std::string's (by switching digit values for appropriate
+* characters).
+*
+* BigUnsignedInABase is similar to BigUnsigned. Note the following:
+*
+* (1) They represent the number in exactly the same way, except
+* that BigUnsignedInABase uses ``digits'' (or Digit) where BigUnsigned uses
+* ``blocks'' (or Blk).
+*
+* (2) Both use the management features of NumberlikeArray. (In fact,
+* my desire to add a BigUnsignedInABase class without duplicating a
+* lot of code led me to introduce NumberlikeArray.)
+*
+* (3) The only arithmetic operation supported by BigUnsignedInABase
+* is an equality test. Use BigUnsigned for arithmetic.
+*/
+
+class BigUnsignedInABase : protected NumberlikeArray<unsigned short> {
+
+ // TYPES
+ public:
+ typedef unsigned short Digit; // The digit type that BigUnsignedInABases are built from
+ typedef Digit Base;
+
+ // FIELDS
+ protected:
+ Base base; // The base of this BigUnsignedInABase
+
+ // MANAGEMENT
+ protected:
+ // These members generally defer to those in NumberlikeArray, possibly with slight changes.
+ // It might be nice if one could request that constructors be inherited in C++.
+
+ BigUnsignedInABase(int, Index c) : NumberlikeArray<Digit>(0, c) {} // Creates a BigUnsignedInABase with a capacity
+
+ void zapLeadingZeros() { // Decreases len to eliminate leading zeros
+ while (len > 0 && blk[len - 1] == 0)
+ len--;
+ }
+
+ //void allocate(Index c); // (NlA) Ensures the number array has at least the indicated capacity, maybe discarding contents
+ //void allocateAndCopy(Index c); // (NlA) Ensures the number array has at least the indicated capacity, preserving its contents
+
+ public:
+ BigUnsignedInABase() : NumberlikeArray<Digit>(), base(2) {} // Default constructor (value is 0 in base 2)
+ BigUnsignedInABase(const BigUnsignedInABase &x) : NumberlikeArray<Digit>(x), base(x.base) {} // Copy constructor
+
+ void operator =(const BigUnsignedInABase &x) { // Assignment operator
+ NumberlikeArray<Digit>::operator =(x);
+ base = x.base;
+ }
+
+ BigUnsignedInABase(const Digit *d, Index l) : NumberlikeArray<Digit>(d, l) { // Constructor from an array of digits
+ zapLeadingZeros();
+ }
+
+ // LINKS TO BIGUNSIGNED
+ BigUnsignedInABase(const BigUnsigned &x, Base base);
+ operator BigUnsigned() const;
+
+ /* LINKS TO STRINGS
+ *
+ * These use the symbols ``0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ'' to represent
+ * digits of 0 through 35. When parsing strings, lowercase is also accepted.
+ *
+ * All string representations are big-endian (big-place-value digits first).
+ * (Computer scientists have adopted zero-based counting; why can't they
+ * tolerate little-endian numbers? It makes a lot of sense!)
+ *
+ * No string representation has a ``base indicator'' like ``0x''.
+ *
+ * An exception is made for zero: it is converted to ``0'' and not the empty string.
+ *
+ * If you want different conventions, write your
+ * own routines to go between BigUnsignedInABase and strings. It's not hard.
+ */
+ operator std::string() const;
+ BigUnsignedInABase(const std::string &s, Base base);
+
+ // PICKING APART
+ // These accessors can be used to get the pieces of the number
+ public:
+ Base getBase() const { return base; }
+ NumberlikeArray<Digit>::getCapacity; // (NlA)
+ NumberlikeArray<Digit>::getLength; // (NlA)
+ // Note that getDigit returns 0 if the digit 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.
+ Digit getDigit(Index i) const { return i >= len ? 0 : blk[i]; }
+ // Note how we replace one level of abstraction with another.
+ bool isZero() const { return NumberlikeArray<Digit>::isEmpty(); } // Often convenient for loops
+
+ // EQUALITY TEST
+ public:
+ // Equality test
+ bool operator ==(const BigUnsignedInABase &x) const {
+ return base == x.base && NumberlikeArray<Digit>::operator ==(x);
+ }
+ bool operator !=(const BigUnsignedInABase &x) const { return !operator ==(x); }
+
+};
+
+#endif
# http://mysite.verizon.net/mccutchen/bigint/
# for more information and the latest version.
#
-# December 16, 2004 version
+# December 23, 2004 development version
#
+# NEWS:
+# We're now using array indexes instead of pointers.
+# After having used pointers for faster speed, I decided
+# that they detracted too much from the readability of
+# the program and that a good optimizing compiler should
+# be able to produce as efficient code.
-library : BigUnsigned.o BigInteger.o BigIntegerIO.o
+# The implicit rules we need
+%.tag : %
+ touch $@
+%.o : %.cc
+ g++ -c -O -Wall -Wextra -pedantic $<
-BigUnsigned.o : BigUnsigned.h BigUnsigned.cpp
- g++ -c BigUnsigned.cpp
+# Default target
+library : NumberlikeArray.hh.tag BigUnsigned.o BigInteger.o BigUnsignedInABase.o BigIntegerUtils.o
-BigInteger.o : BigUnsigned.h BigInteger.h BigInteger.cpp
- g++ -c BigInteger.cpp
+# Extra `include' dependencies
+BigUnsigned.hh.tag : NumberlikeArray.hh.tag
+BigUnsigned.o : BigUnsigned.hh.tag
+BigInteger.hh.tag : BigUnsigned.hh.tag
+BigInteger.o : BigInteger.hh.tag
+BigUnsignedInABase.hh.tag : BigUnsigned.hh.tag
+BigUnsignedInABase.o : BigUnsignedInABase.hh.tag
+BigIntegerUtils.hh.tag : BigInteger.hh.tag
+BigIntegerUtils.o : BigIntegerUtils.hh.tag
-BigIntegerIO.o : BigUnsigned.h BigInteger.h BigIntegerIO.cpp
- g++ -c BigIntegerIO.cpp
+# sample program
+sample : library sample.cc
+ g++ -osample *.o sample.cc
-po3demo : library PowersOfThreeDemo.cpp
- g++ -opo3demo BigUnsigned.o BigInteger.o BigIntegerIO.o PowersOfThreeDemo.cpp
+clean :
+ rm -f *.tag *.o sample
-clean :
- rm -f *.o po3demo
+# The ``.tag'' mechanism allows for proper recompilation when a header file
+# changes, considering that some header files may include others.
+#
+# If a header file X includes other header
+# files Y and Z, we create a file X.tag that depends
+# on X, Y.tag, and Z.tag. Other headers that include X should
+# depend on X.tag.
+#
+# Suppose Y is subsequently changed. X doesn't get ``recompiled'',
+# but anything that includes X should be recompiled. Well, Y.tag becomes
+# out-of-date, so X.tag becomes out-of-date, so anything depending on X.tag
+# (that is, anything including X) becomes out-of-date. Magic!
+#
+# In this system, the tag files are empty files used only for their
+# timestamps. If one wished to use precompiled headers, one could use
+# ``.gch'' files exactly how ``.tag'' files are used now, except that
+# their contents would be meaningful.
+#
+# However, the same sort of ``deadly diamond'' problem that surfaces with
+# multiple inheritance also applies to precompiled headers. The ``#ifndef''
+# mechanism that prevents multiple inclusion doesn't work when headers are
+# compiled independently in a hierarchical structure, since the second
+# inclusion of a file won't even know there was a first inclusion. For
+# this reason, I just use ``.tag''s.
--- /dev/null
+/*
+* Matt McCutchen's Big Integer Library
+* http://mysite.verizon.net/mccutchen/bigint/
+*/
+
+#ifndef NUMBERLIKEARRAY
+#define NUMBERLIKEARRAY
+
+/*
+* A NumberlikeArray<Block> object holds a dynamically
+* allocated array of Blocks. It provides certain basic
+* memory management features needed by both BigUnsigned
+* and BigUnsignedInABase, which are both derived from it.
+*
+* NumberlikeArray provides no information hiding, so make
+* sure you know what you are doing if you use it directly.
+* Classes derived from it will probably wish to pass on
+* some members of NumberlikeArray to their clients while
+* keeping some safe for themselves. These classes should
+* use protected inheritance and manually make some members
+* public with declarations like this:
+*
+* public:
+* NumberlikeArray< whatever >::getLength;
+*/
+
+template <class Blk>
+class NumberlikeArray {
+ public:
+
+ typedef unsigned int Index; // Type for the index of a block in the array
+
+ // FIELDS
+ Index cap; // The current allocated capacity of this NumberlikeArray (in blocks)
+ Index len; // The actual length of the value stored in this NumberlikeArray (in blocks)
+ Blk *blk; // Dynamically allocated array of the blocks
+
+ // MANAGEMENT
+ NumberlikeArray(int, Index c) : cap(c), len(0) { // Creates a NumberlikeArray with a capacity
+ blk = new Blk[cap];
+ }
+ void allocate(Index c); // Ensures the array has at least the indicated capacity, maybe discarding contents
+ void allocateAndCopy(Index c); // Ensures the array has at least the indicated capacity, preserving its contents
+
+ NumberlikeArray() : cap(0), len(0) { // Default constructor (empty array)
+ blk = new Blk[0];
+ }
+ NumberlikeArray(const NumberlikeArray<Blk> &x); // Copy constructor
+ void operator=(const NumberlikeArray<Blk> &x); // Assignment operator
+ NumberlikeArray(const Blk *b, Index l); // Constructor from an array of blocks
+ ~NumberlikeArray() { // Destructor
+ delete [] blk;
+ }
+
+ // PICKING APART
+ // These accessors can be used to get the pieces of the value
+ Index getCapacity() const { return cap; }
+ Index getLength() const { return len; }
+ Blk getBlock(Index i) const { return blk[i]; };
+ bool isEmpty() const { return len == 0; }
+
+ // Equality comparison: checks if arrays have same length and matching values
+ // Derived classes may wish to override these if differing arrays can
+ // sometimes be considered equivalent.
+ bool operator ==(const NumberlikeArray<Blk> &x) const;
+ bool operator !=(const NumberlikeArray<Blk> &x) const;
+
+};
+
+/*
+* BELOW THIS POINT are template definitions; above are declarations.
+*
+* Definitions would ordinarily belong in a file NumberlikeArray.cc so that they would
+* be compiled once into NumberlikeArray.o and then linked.
+*
+* However, because of the way templates are usually implemented,
+* template ``definitions'' are treated as declarations by the compiler.
+* When someone uses an instance of the template, definitions are generated,
+* and the linker is smart enough to toss duplicate definitions for the same
+* instance generated by different files.
+*
+* Thus, the template ``definitions'' for NumberlikeArray must appear in this header file
+* so other files including NumberlikeArray will be able to generate real definitions.
+*/
+
+// MANAGEMENT
+
+// This routine is called to ensure the array is at least a
+// certain size before another value is written into it.
+template <class Blk>
+void NumberlikeArray<Blk>::allocate(Index 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 array is at least a
+// certain size without losing its contents.
+template <class Blk>
+void NumberlikeArray<Blk>::allocateAndCopy(Index 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
+ Index i;
+ for (i = 0; i < len; i++)
+ blk[i] = oldBlk[i];
+ // Delete the old array
+ delete [] oldBlk;
+ }
+}
+
+// Copy constructor
+template <class Blk>
+NumberlikeArray<Blk>::NumberlikeArray(const NumberlikeArray<Blk> &x) : len(x.len) {
+ // Create array
+ cap = len;
+ blk = new Blk[cap];
+ // Copy blocks
+ Index i;
+ for (i = 0; i < len; i++)
+ blk[i] = x.blk[i];
+}
+
+// Assignment operator
+template <class Blk>
+void NumberlikeArray<Blk>::operator=(const NumberlikeArray<Blk> &x) {
+ // Calls like a = a have no effect
+ if (this == &x)
+ return;
+ // Copy length
+ len = x.len;
+ // Expand array if necessary
+ allocate(len);
+ // Copy number blocks
+ Index i;
+ for (i = 0; i < len; i++)
+ blk[i] = x.blk[i];
+}
+
+// Constructor from an array of blocks
+template <class Blk>
+NumberlikeArray<Blk>::NumberlikeArray(const Blk *b, Index l) : cap(l), len(l) {
+ // Create array
+ blk = new Blk[cap];
+ // Copy blocks
+ Index i;
+ for (i = 0; i < len; i++)
+ blk[i] = b[i];
+}
+
+
+// EQUALITY TEST
+// This uses == to compare Blks for equality.
+// Therefore, Blks must have an == operator with the desired semantics.
+template <class Blk>
+bool NumberlikeArray<Blk>::operator ==(const NumberlikeArray<Blk> &x) const {
+ // Different lengths imply different objects.
+ if (len != x.len)
+ return false;
+ else {
+ // Compare matching blocks one by one.
+ Index i;
+ for (i = 0; i < len; i++)
+ if (blk[i] != x.blk[i])
+ return false;
+ // If no blocks differed, the objects are equal.
+ return true;
+ }
+}
+
+#endif
+++ /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;
-}
--- /dev/null
+=================================================================
+Matt McCutchen's Big Integer Library
+A C++ library that does arithmetic on integers of unlimited size.
+=================================================================
+Version 2004.12.24.2
+
+This library contains two classes, BigUnsigned and BigInteger, that represent nonnegative integers and integers, respectively. Each provides the operations listed below and possibly others:
++, -, *, /, %, unary -
++=, -=, *=, /=, %=, ++, --
+==, !=, <, <=, >, >=
+&, |, ^
+
+To get started using this library, look at the code in `sample.cc'. Type `make sample' to compile the sample program in `sample.cc' so you can see what it does.
+
+This library includes a makefile. To compile it, just type `make'; you'll get some `.o' files. Include `.hh' files and link with `.o' files as necessary for your programming projects.
+
+Please see the project Web site at
+ http://mysite.verizon.net/mccutchen/bigint/
+for more information and the latest version.
+
+Change Log:
+===========
+
+2004.12.24.2 version:
+I tied down a couple of loose ends involving division/modulo. I added an explanation of put-here vs. overloaded operators in the sample program; this has confused too many people. Miscellaneous other improvements.
+
+I believe that, at this point, the Big Integer Library makes no assumptions about the word size of the machine it is using. `BigUnsigned::Blk' is always an `unsigned long', whatever that may be, and its size is computed with `sizeof' when necessary. However, just in case, I would be interested to have someone test the library on a non-32-bit machine to see if it works.
+
+2004.12.24 version:
+This is a _major_ upgrade to the library. Among the things that have changed:
+
+I wrote the original version of the library, particularly the four ``classical algorithms'' in `BigUnsigned.cc', using array indexing. Then I rewrote it to use pointers because I thought that would be faster. But recently, I revisited the code in `BigUnsigned.cc' and found that I could not begin to understand what it was doing.
+
+I have decided that the drawbacks of pointers, increased coding difficulty and reduced code readability, far outweigh their speed benefits. Plus, any modern optimizing compiler should produce fast code either way. Therefore, I rewrote the library to use array indexing again. (Thank goodness for regular-expression find-and-replace. It saved me a lot of time.)
+
+The put-here operations `divide' and `modulo' of each of `BigUnsigned' and `BigInteger' have been supplanted by a single operation `divideWithRemainder'. Read the profuse comments for more information on its exact behavior.
+
+There is a new class `BigUnsignedInABase' that is like `BigUnsigned' but uses a user-specified, small base instead of `256 ^ sizeof(unsigned long)'. Much of the code common to the two has been factored out into `NumberlikeArray'.
+
+`BigUnsignedInABase' facilitates conversion between `BigUnsigned's and digit-by-digit string representations using `std::string'. Convenience routines to do this conversion are in `BigIntegerUtils.hh'. `iostream' compatibility has been improved.
+
+I would like to thank Chris Morbitzer for the e-mail message that catalyzed this major upgrade. He wanted a way to convert a string to a BigInteger. One thing just led to another, roughly in reverse order from how they are listed here.
+
+2004.1216 version:
+Brad Spencer pointed out a memory leak in `BigUnsigned::divide'. It is fixed in the December 16, 2004 version.
+
+2004.1205 version:
+After months of inactivity, I fixed a bug in the `BigInteger' division routine; thanks to David Allen for reporting the bug. I also added simple routines for decimal output to `std::ostream's, and there is a demo that prints out powers of 3.
+
+===================
\ No newline at end of file
--- /dev/null
+/*
+* Matt McCutchen's Big Integer Library
+* http://mysite.verizon.net/mccutchen/bigint/
+*/
+
+/*
+* This sample file demonstrates the most important features of the Big Integer Library.
+*
+* To get started quickly with the library, imitate the code in `main' below.
+*
+* If you want more detail or more speed or can't find a feature here,
+* look in the appropriate source file. This file shows only the more ``user-friendly'' features;
+* the other features are messier but worth learning eventually.
+*
+* GO FORTH and play with many-digit numbers! (c.f. The TeXbook.)
+*/
+
+#include "BigUnsigned.hh"
+#include "BigInteger.hh"
+#include "BigIntegerUtils.hh"
+
+#include <string>
+#include <iostream>
+
+int main() {
+ try {
+ BigInteger a; // a is 0
+ int b = 535;
+
+ a = b; // From int to BigUnsigned...
+ b = a; // ...and back, no casts required!
+ /*
+ * If a were too big for an int you'd get a runtime exception. The Big Integer Library
+ * throws C-strings (that is, `const char *'s) when something goes wrong. It's a good
+ * idea to catch them. Some C++ compilers need a special command-line option to compile
+ * code that uses throw/catch.
+ */
+
+ BigInteger c(a); // Copy them.
+
+ BigInteger d(-314159265); // c is -314159265. The `int' literal is converted to a BigInteger.
+
+ // Ahem: that's too big to be an `int' literal (or even a `long' literal)!
+ // Disillusion yourself now -- this won't compile.
+ //BigInteger e(3141592653589793238462643383279);
+
+ std::string s("3141592653589793238462643383279");
+ BigInteger f = easyStringToBI(s);
+ // Ah. The string is converted to a BigInteger, and strings can be as long as you want.
+
+ std::string s2 = easyBItoString(f); // You can convert the other way too.
+
+ std::cout << f << std::endl; // f is stringified and send to std::cout.
+
+ /*
+ * Let's do some math!
+ *
+ * The Big Integer Library provides three kinds of operators:
+ *
+ * (1) Overloaded ``value'' operators: +, -, *, /, %, unary -.
+ * Big-integer code using these operators looks identical to
+ * code using the primitive integer types. The operator takes
+ * one or two BigInteger inputs and returns a BigInteger result,
+ * which can then be assigned to a BigInteger variable or used
+ * in an expression.
+ *
+ * (2) Overloaded assignment operators: +=, -=, *=, /=, %=,
+ * ++, --, flipSign.
+ * Again, these are used on BigIntegers just like on ints.
+ * They take one writable BigInteger that both provides an
+ * operand and receives a result. The first five also take
+ * a second read-only operand.
+ *
+ * (3) ``Put-here'' operations: `add', `subtract', etc.
+ * Use these if and only if you are concerned about performance.
+ * They require fewer BigInteger copy-constructions and assignments
+ * than do operators in (1) or (2). Most take two read-only operands
+ * and save the result in the invoked object `*this', whose previous
+ * value is irrelevant. `divideWithRemainder' is an exception.
+ * <<< NOTE >>>: Put-here operations do not return a value: they don't need to!!
+ */
+
+ BigInteger g(314159), h(265);
+ // All five ``value'' operators
+ std::cout << (g + h) << '\n' << (g - h) << '\n' << (g * h)
+ << '\n' << (g / h) << '\n' << (g % h) << std::endl;
+
+ BigInteger i(5), j(10), k;
+ // These two lines do the same thing: k is set to a BigInteger containing 15.
+ k = i + j;
+ k.add(i, j);
+
+ // Let's do some heavy lifting.
+ std::cout << "Powers of 3" << std::endl;
+ std::cout << "How many do you want?" << std::endl;
+ int maxPower;
+ std::cin >> maxPower;
+
+ BigUnsigned x(1), three(3);
+ for (int power = 0; power <= maxPower; power++) {
+ std::cout << "3^" << power << " = " << x << std::endl;
+ x *= three; // A BigInteger assignment operator
+ }
+
+ std::cout << "There you go. Goodbye." << std::endl;
+
+ } catch(char const* err){
+ std::cout << "Sorry, the library threw an exception:\n"
+ << err << std::endl;
+ }
+ return 0;
+}
+
+/*
+* Here is the output of a sample run of this sample program:
+
+3141592653589793238462643383279
+314424
+313894
+83252135
+1185
+134
+Powers of 3
+How many do you want?
+2
+3^0 = 1
+3^1 = 3
+3^2 = 9
+There you go. Goodbye.
+
+*/
Matt McCutchen's Web Site / bigint / bigint.git / commitdiff