#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);
Matt McCutchen's Web Site / bigint / bigint.git / blobdiff