X-Git-Url: https://mattmccutchen.net/bigint/bigint.git/blobdiff_plain/e67d60496ce8582666f1fb77503acfe5d05c70d4:/BigUnsigned.h..05780f4b578d6ae054be0b19b8498d32a4f16c60:/BigUnsigned.hh diff --git a/BigUnsigned.h b/BigUnsigned.hh similarity index 56% rename from BigUnsigned.h rename to BigUnsigned.hh index 879d713..101f697 100644 --- a/BigUnsigned.h +++ b/BigUnsigned.hh @@ -6,42 +6,68 @@ #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 { // 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::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(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() {} // Default constructor (value is 0) + BigUnsigned(const BigUnsigned &x) : NumberlikeArray(x) {} // Copy constructor + + void operator=(const BigUnsigned &x) { // Assignment operator + NumberlikeArray::operator =(x); + } + + BigUnsigned(const Blk *b, Index l) : NumberlikeArray(b, l) { // Constructor from an array of blocks + zapLeadingZeros(); + } + // Constructors from integral types BigUnsigned(unsigned long x); BigUnsigned( long x); @@ -49,7 +75,7 @@ class BigUnsigned { BigUnsigned( int x); BigUnsigned(unsigned short x); BigUnsigned( short x); - ~BigUnsigned(); // Destructor + ~BigUnsigned() {} // Destructor // CONVERTERS to integral types public: @@ -63,38 +89,67 @@ class BigUnsigned { // 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::getCapacity; + NumberlikeArray::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::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::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::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) @@ -132,41 +187,6 @@ class BigUnsigned { }; -// 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 @@ -215,6 +235,7 @@ inline BigUnsigned BigUnsigned::operator ^(const BigUnsigned &x) const { // 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); @@ -228,12 +249,18 @@ inline void BigUnsigned::operator *=(const BigUnsigned &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);