-/*
-* Matt McCutchen's Big Integer Library
-*/
-
-#ifndef BIGINTEGER
-#define BIGINTEGER
+#ifndef BIGINTEGER_H
+#define BIGINTEGER_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 BigIntegers.
-*
-* The number is stored as a series of blocks in a
-* dynamically allocated array. It is as if the number
-* were written digit by digit in base 2 ^ N, **where N is the
-* number of bits in an unsigned long.**
-*
-* This class is derived from BigUnsigned, which represents
-* 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.
-*/
+ * 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 BigIntegers.
+ *
+ * The number is stored as a series of blocks in a
+ * dynamically allocated array. It is as if the number
+ * were written digit by digit in base 2 ^ N, **where N is the
+ * number of bits in an unsigned long.**
+ *
+ * This class is derived from BigUnsigned, which represents
+ * 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.
+ */
class BigInteger : public BigUnsigned {
// TYPES & CONSTANTS
- public:
+public:
enum Sign { negative = -1, zero = 0, positive = 1 }; // Enumeration for the sign of a BigInteger
// FIELDS
- protected:
+protected:
Sign sign; // The sign of this BigInteger
// MANAGEMENT
- protected:
+protected:
BigInteger(Sign s, Index c) : BigUnsigned(0, c), sign(s) {}; // Creates a BigInteger with a sign and capacity
- public:
+public:
BigInteger() : BigUnsigned(), sign(zero) {} // Default constructor (value is 0)
BigInteger(const BigInteger &x) : BigUnsigned(x), sign(x.sign) {}; // Copy constructor
// automatically; this takes its absolute value.
// CONVERTERS to integral types
- public:
+public:
operator unsigned long () const;
operator long () const;
operator unsigned int () const;
// PICKING APART
// These accessors can be used to get the pieces of the number
- public:
+public:
Sign getSign() const;
// COMPARISONS
- public:
+public:
// Compares this to x like Perl's <=>
CmpRes compareTo(const BigInteger &x) const;
// Normal comparison operators
// 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.
- * See explanation of "put-here operations" in BigUnsigned.cc . */
- public:
+ * a.add(b, c) is equivalent to, but faster than, a = b + c.
+ * See explanation of "put-here operations" in BigUnsigned.cc . */
+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
/* 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.
- * `a.divideWithRemainder(b, a)' causes an exception: it doesn't make
- * sense to write quotient and remainder into the same variable.
- */
+ * `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.
+ * `a.divideWithRemainder(b, a)' causes an exception: it doesn't make
+ * sense to write quotient and remainder into the same variable.
+ */
void divideWithRemainder(const BigInteger &b, BigInteger &q);
void divide(const BigInteger &a, const BigInteger &b) {
BigInteger a2(a);
// 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:
+public:
BigInteger operator +(const BigInteger &x) const; // Addition
BigInteger operator -(const BigInteger &x) const; // Subtraction
BigInteger operator *(const BigInteger &x) const; // Multiplication
// ASSIGNMENT OPERATORS
// These perform the operation on this and x, storing the result into this.
- public:
+public:
void operator +=(const BigInteger &x); // Addition
void operator -=(const BigInteger &x); // Subtraction
void operator *=(const BigInteger &x); // Multiplication
// 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:
+public:
void operator ++( ); // Prefix increment
void operator ++(int); // Postfix decrement
void operator --( ); // Prefix increment
// 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. */
+ * 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);