divideWithRemainder(tmpB, q);
return;
}
-
+
// Division by zero gives quotient 0 and remainder *this
if (b.sign == zero) {
q.len = 0;
q.sign = zero;
return;
}
-
+
// Here *this != 0, b != 0.
-
+
// Do the operands have the same sign?
if (sign == b.sign) {
// Yes: easy case. Quotient is zero or positive.
* 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.
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;
if (q.len == 0)
q.sign = zero;
-
+
// WHEW!!!
}
*/
class BigInteger : public BigUnsigned {
-
+
// TYPES & CONSTANTS
public:
enum Sign { negative = -1, zero = 0, positive = 1 }; // Enumeration for the sign of a BigInteger
-
+
// FIELDS
protected:
Sign sign; // The sign of this BigInteger
-
+
// MANAGEMENT
protected:
BigInteger(Sign s, Index c) : BigUnsigned(0, c), sign(s) {}; // Creates a BigInteger with a sign and capacity
BigInteger( short x);
// Note that a BigInteger can be converted to a BigUnsigned
// automatically; this takes its absolute value.
-
+
// CONVERTERS to integral types
public:
operator unsigned long () const;
operator int () const;
operator unsigned short() const;
operator short() const;
-
+
// PICKING APART
// These accessors can be used to get the pieces of the number
public:
Sign getSign() const;
-
+
// COMPARISONS
public:
// Compares this to x like Perl's <=>
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.
* a.add(b, c) is equivalent to, but faster than, a = b + c.
// redefined for BigIntegers. Calling one of these on
// 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)
// and x (to the right of the operator) and return a new BigInteger with the result.
BigInteger operator /(const BigInteger &x) const; // Division
BigInteger operator %(const BigInteger &x) const; // Modular reduction
BigInteger operator -( ) const; // Negative
-
+
// ASSIGNMENT OPERATORS
// These perform the operation on this and x, storing the result into this.
public:
void operator /=(const BigInteger &x); // Division
void operator %=(const BigInteger &x); // Modular reduction
void flipSign(); // Negative
-
+
// INCREMENT/DECREMENT OPERATORS
// These increase or decrease the number by 1. To discourage side effects,
// these do not return *this, so prefix and postfix behave the same.
void operator ++(int); // Postfix decrement
void operator --( ); // Prefix increment
void operator --(int); // Postfix decrement
-
+
};
// PICKING APART
unsigned int pieceSizeInBits = 8 * sizeof(T);
unsigned int piecesPerBlock = sizeof(BigInteger::Blk) / sizeof(T);
unsigned int numBlocks = (length + piecesPerBlock - 1) / piecesPerBlock;
-
+
// Allocate our block array
BigInteger::Blk *blocks = new BigInteger::Blk[numBlocks];
-
+
BigInteger::Index blockNum, pieceNum, pieceNumHere;
-
+
// Convert
for (blockNum = 0, pieceNum = 0; blockNum < numBlocks; blockNum++) {
BigInteger::Blk curBlock = 0;
curBlock |= (BigInteger::Blk(data[pieceNum]) << (pieceSizeInBits * pieceNumHere));
blocks[blockNum] = curBlock;
}
-
+
// Create the BigInteger.
BigInteger x(blocks, numBlocks, sign);
-
+
delete blocks;
return x;
}
divideWithRemainder(tmpB, q);
return;
}
-
+
/*
* 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.
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).
q.len = 0;
return;
}
-
+
/*
* At this point we know *this > b > 0. (Whew!)
*/
-
+
/*
* Overall method:
*
unsigned int i2;
Blk temp;
bool borrowIn, borrowOut;
-
+
/*
* Make sure we have an extra zero block just past the value.
*
allocateAndCopy(len + 1); // Get the space.
len++; // Increase the length.
blk[origLen] = 0; // Zero the extra block.
-
+
// work2 holds part of the result of a subtraction; see above.
Blk *work2 = new Blk[len];
-
+
// Set preliminary length for quotient and make room
q.len = origLen - 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) {
// Deallocate temporary array.
// (Thanks to Brad Spencer for noticing my accidental omission of this!)
delete [] work2;
-
+
}
/*
* The out-of-bounds accesses story:
*/
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 NumberlikeArray<Blk>::Index Index; // (NlA) Type for the index of a block in the array
NumberlikeArray<Blk>::N; // Number of bits in a Blk
-
+
/*
// FIELDS
protected:
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:
// 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() : 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(unsigned short x);
BigUnsigned( short x);
~BigUnsigned() {} // Destructor
-
+
// CONVERTERS to integral types
public:
operator unsigned long () const;
operator int () const;
operator unsigned short() const;
operator short() const;
-
+
// PICKING APART
// These accessors can be used to get the pieces of the number
public:
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 <=>
* a.add(a, b); // ``Aliased'' calls now do the right thing using a
* // temporary copy, but see note on divideWithRemainder.
*/
-
+
// PUT-HERE OPERATIONS
public:
/* These 3: Two read-only operands as arguments. Result left in *this. */
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, unsigned int b); // Bitwise right shift
-
+
// NORMAL OPERATORS
// These perform the operation on this (to the left of the operator)
// and x (to the right of the operator) and return a new BigUnsigned with the result.
// Additional operators in an attempt to avoid overloading tangles.
BigUnsigned operator <<(int b) const;
BigUnsigned operator >>(int b) const;
-
+
// ASSIGNMENT OPERATORS
// These perform the operation on this and x, storing the result into this.
public:
// Additional operators in an attempt to avoid overloading tangles.
void operator <<=(int b);
void operator >>=(int b);
-
+
// 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.
void operator ++(int); // Postfix decrement
void operator --( ); // Prefix increment
void operator --(int); // Postfix decrement
-
+
// Helper function that needs access to BigUnsigned internals
friend Blk getShiftedBlock(const BigUnsigned &num, Index x, unsigned int y);
};
// 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() * BigUnsigned::N;
int minBitsPerDigit = bitLen(base) - 1;
int maxDigitLenOfX = ceilingDiv(maxBitLenOfX, minBitsPerDigit);
len = maxDigitLenOfX; // Another change to comply with `staying in bounds'; see `BigUnsigned::divideWithRemainder'.
allocate(len); // 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);
// Move on. We can't run out of room: we figured it out above.
digitNum++;
}
-
+
// Save the actual length.
len = digitNum;
}
// Save the base.
// This pattern is seldom seen in C++, but the analogous ``this.'' is common in Java.
this->base = base;
-
+
// `s.length()' is a `size_t', while `len' is a `NumberlikeArray::Index',
// also known as an `unsigned int'. Some compilers warn without this cast.
len = Index(s.length());
allocate(len);
-
+
Index digitNum, symbolNumInString;
for (digitNum = 0; digitNum < len; digitNum++) {
symbolNumInString = len - 1 - digitNum;
*/
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
*/
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:
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
return base == x.base && NumberlikeArray<Digit>::operator ==(x);
}
bool operator !=(const BigUnsignedInABase &x) const { return !operator ==(x); }
-
+
};
#endif
template <class Blk>
class NumberlikeArray {
public:
-
+
typedef unsigned int Index; // Type for the index of a block in the array
static const unsigned int N; // The number of bits in a block, defined below.
-
+
// 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
-
+
/*
* Change made on 2005.01.06:
*
* This is a great convenience because the only code that need be changed
* is the array allocation code. All other code will still work fine.
*/
-
+
// MANAGEMENT
NumberlikeArray(Index c) : cap(c), len(0) { // Creates a NumberlikeArray with a capacity
blk = (cap > 0) ? (new Blk[cap]) : NULL;
}
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
-
+
/*
* Default constructor.
*
~NumberlikeArray() { // Destructor
delete [] blk; // Does nothing and causes no error if `blk' is null.
}
-
+
// 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 { return !operator ==(x); }
-
+
};
/*
try {
BigInteger a; // a is 0
int b = 535;
-
+
a = b; // From int to BigInteger...
b = a; // ...and back, no casts required!
/*
* a special command-line option to compile code that uses
* exceptions.
*/
-
+
BigInteger c(a); // Copy a BigInteger.
-
+
// d is -314159265. The `int' literal is converted to a
// BigInteger.
BigInteger d(-314159265);
-
+
// This won't compile because the number is too big to be an
// integer literal.
//BigInteger e(3141592653589793238462643383279);
-
+
// Instead you can convert the number from a string.
std::string s("3141592653589793238462643383279");
BigInteger f = easyStringToBI(s);
-
+
// You can convert the other way too.
std::string s2 = easyBItoString(f);
-
+
// f is stringified and send to std::cout.
std::cout << f << std::endl;
-
+
/*
* Let's do some math!
*
// All five ``return-by-value'' arithmetic operators.
std::cout << (g + h) << '\n' << (g - h) << '\n' << (g * h)
<< '\n' << (g / h) << '\n' << (g % h) << std::endl;
-
+
BigUnsigned i(0xFF0000FF), j(0x0000FFFF);
// All five ``return-by-value'' bitwise operators.
std::cout.flags(std::ios::hex | std::ios::showbase);
std::cout << (i & j) << '\n' << (i | j) << '\n' << (i ^ j) << '\n'
<< (j << 21) << '\n' << (j >> 10) << '\n';
std::cout.flags(std::ios::dec);
-
+
// Let's do some heavy lifting and calculate powers of 314.
int maxPower = 10;
BigUnsigned x(1), big314(314);
std::cout << "314^" << power << " = " << x << std::endl;
x *= big314; // A BigInteger assignment operator
}
-
+
/*
* If you want to experiment with the library,
* you can add your own test code here.
*/
// std::cout << "Beginning of custom test code:" << std::endl;
-
+
} catch(char const* err) {
std::cout << "The library threw an exception:\n"
<< err << std::endl;
}
-
+
return 0;
}
Matt McCutchen's Web Site / bigint / bigint.git / commitdiff