/*
-* Matt McCutchen's Big Integer Library
-*/
+ * Matt McCutchen's Big Integer Library
+ */
#include "BigInteger.hh"
}
/*
-* The steps for construction of a BigInteger
-* from an integral value x are as follows:
-* 1. If x is zero, create an empty BigInteger and stop.
-* 2. Allocate a one-block number array.
-* 3. If x is positive (or of an unsigned type), set the
-* sign of the BigInteger to positive.
-* 4. If x is of a signed type and is negative, set the
-* sign of the BigInteger to negative.
-* 5. If x is of a signed type, convert x (or -x if x < 0)
-* to the unsigned type of the same length.
-* 6. Expand x (or the result of step 5) to a Blk,
-* and store it in the number array.
-*
-* See remarks in `BigUnsigned.cc' and `NumberlikeArray.hh'
-* about new handling of zero-length arrays.
-*/
+ * The steps for construction of a BigInteger
+ * from an integral value x are as follows:
+ * 1. If x is zero, create an empty BigInteger and stop.
+ * 2. Allocate a one-block number array.
+ * 3. If x is positive (or of an unsigned type), set the
+ * sign of the BigInteger to positive.
+ * 4. If x is of a signed type and is negative, set the
+ * sign of the BigInteger to negative.
+ * 5. If x is of a signed type, convert x (or -x if x < 0)
+ * to the unsigned type of the same length.
+ * 6. Expand x (or the result of step 5) to a Blk,
+ * and store it in the number array.
+ *
+ * See remarks in `BigUnsigned.cc' and `NumberlikeArray.hh'
+ * about new handling of zero-length arrays.
+ */
BigInteger::BigInteger(unsigned long x) {
if (x == 0)
// CONVERTERS
/*
-* The steps for conversion of a BigInteger to an
-* integral type are as follows:
-* 1. If the BigInteger is zero, return zero.
-* 2. If the BigInteger is positive:
-* 3. 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.
-* 4. Otherwise, convert the lowest block to the
-* target type and return it.
-* 5. If the BigInteger is negative:
-* 6. If the target type is unsigned, throw an exception.
-* 7. 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.
-* 8. Otherwise, convert the lowest block to the
-* target type, negate it, and return it.
-*/
+ * The steps for conversion of a BigInteger to an
+ * integral type are as follows:
+ * 1. If the BigInteger is zero, return zero.
+ * 2. If the BigInteger is positive:
+ * 3. 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.
+ * 4. Otherwise, convert the lowest block to the
+ * target type and return it.
+ * 5. If the BigInteger is negative:
+ * 6. If the target type is unsigned, throw an exception.
+ * 7. 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.
+ * 8. Otherwise, convert the lowest block to the
+ * target type, negate it, and return it.
+ */
namespace {
// These masks are used to test whether a Blk has bits
}
/*
-* 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
-*/
+ * 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) {
// Defend against aliased calls;
// same idea as in BigUnsigned::divideWithRemainder .
// 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.
- */
+ * 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.
/*
-* Matt McCutchen's Big Integer Library
-*/
+ * Matt McCutchen's Big Integer Library
+ */
#ifndef BIGINTEGER
#define BIGINTEGER
#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 {
// 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 . */
+ * 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 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);
/*
-* Matt McCutchen's Big Integer Library
-*/
+ * Matt McCutchen's Big Integer Library
+ */
// This header file includes all the other header files.
/*
-* Matt McCutchen's Big Integer Library
-*/
+ * Matt McCutchen's Big Integer Library
+ */
#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
-*/
+ * 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));
/*
-* Matt McCutchen's Big Integer Library
-*/
+ * Matt McCutchen's Big Integer Library
+ */
#ifndef BIGINTEGERUTILS
#define BIGINTEGERUTILS
#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
-*/
+ * 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::ostream &operator <<(std::ostream &os, const BigInteger &x);
/*
-* =================================
-* BELOW THIS POINT are template definitions; above are declarations. See `NumberlikeArray.hh'.
-*/
+ * =================================
+ * BELOW THIS POINT are template definitions; above are declarations. See `NumberlikeArray.hh'.
+ */
/*
-* Converts binary data to a BigInteger.
-* Pass an array `data', its length, and the desired sign.
-*
-* Elements of `data' may be of any type `T' that has the following
-* two properties (this includes almost all integral types):
-*
-* (1) `sizeof(T)' correctly gives the amount of binary data in one
-* value of `T' and is a factor of `sizeof(Blk)'.
-*
-* (2) When a value of `T' is casted to a `Blk', the low bytes of
-* the result contain the desired binary data.
-*/
+ * Converts binary data to a BigInteger.
+ * Pass an array `data', its length, and the desired sign.
+ *
+ * Elements of `data' may be of any type `T' that has the following
+ * two properties (this includes almost all integral types):
+ *
+ * (1) `sizeof(T)' correctly gives the amount of binary data in one
+ * value of `T' and is a factor of `sizeof(Blk)'.
+ *
+ * (2) When a value of `T' is casted to a `Blk', the low bytes of
+ * the result contain the desired binary data.
+ */
template <class T>
BigInteger easyDataToBI(const T* data, BigInteger::Index length, BigInteger::Sign sign) {
// really ceiling(numBytes / sizeof(BigInteger::Blk))
/*
-* Matt McCutchen's Big Integer Library
-*/
+ * Matt McCutchen's Big Integer Library
+ */
#include "BigUnsigned.hh"
// The "management" routines that used to be here are now in NumberlikeArray.hh.
/*
-* 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.
-*
-* Since 2005.01.06, NumberlikeArray uses `NULL' rather
-* than a real array if one of zero length is needed.
-* These constructors implicitly call NumberlikeArray's
-* default constructor, which sets `blk = NULL, cap = len = 0'.
-* So if the input number is zero, they can just return.
-* See remarks in `NumberlikeArray.hh'.
-*/
+ * 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.
+ *
+ * Since 2005.01.06, NumberlikeArray uses `NULL' rather
+ * than a real array if one of zero length is needed.
+ * These constructors implicitly call NumberlikeArray's
+ * default constructor, which sets `blk = NULL, cap = len = 0'.
+ * So if the input number is zero, they can just return.
+ * See remarks in `NumberlikeArray.hh'.
+ */
BigUnsigned::BigUnsigned(unsigned long x) {
if (x == 0)
// 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.
-*/
+ * 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
// PUT-HERE OPERATIONS
/*
-* Below are implementations of the four basic arithmetic operations
-* for `BigUnsigned's. Their purpose is to use a mechanism that can
-* calculate the sum, difference, product, and quotient/remainder of
-* two individual blocks in order to calculate the sum, difference,
-* product, and quotient/remainder of two multi-block BigUnsigned
-* numbers.
-*
-* As alluded to in the comment before class `BigUnsigned',
-* these algorithms bear a remarkable similarity (in purpose, if
-* not in implementation) to the way humans operate on big numbers.
-* The built-in `+', `-', `*', `/' and `%' operators are analogous
-* to elementary-school ``math facts'' and ``times tables''; the
-* four routines below are analogous to ``long division'' and its
-* relatives. (Only a computer can ``memorize'' a times table with
-* 18446744073709551616 entries! (For 32-bit blocks.))
-*
-* The discovery of these four algorithms, called the ``classical
-* algorithms'', marked the beginning of the study of computer science.
-* See Section 4.3.1 of Knuth's ``The Art of Computer Programming''.
-*/
+ * Below are implementations of the four basic arithmetic operations
+ * for `BigUnsigned's. Their purpose is to use a mechanism that can
+ * calculate the sum, difference, product, and quotient/remainder of
+ * two individual blocks in order to calculate the sum, difference,
+ * product, and quotient/remainder of two multi-block BigUnsigned
+ * numbers.
+ *
+ * As alluded to in the comment before class `BigUnsigned',
+ * these algorithms bear a remarkable similarity (in purpose, if
+ * not in implementation) to the way humans operate on big numbers.
+ * The built-in `+', `-', `*', `/' and `%' operators are analogous
+ * to elementary-school ``math facts'' and ``times tables''; the
+ * four routines below are analogous to ``long division'' and its
+ * relatives. (Only a computer can ``memorize'' a times table with
+ * 18446744073709551616 entries! (For 32-bit blocks.))
+ *
+ * The discovery of these four algorithms, called the ``classical
+ * algorithms'', marked the beginning of the study of computer science.
+ * See Section 4.3.1 of Knuth's ``The Art of Computer Programming''.
+ */
/*
* On most calls to put-here operations, it's safe to read the inputs little by
}
/*
-* About the multiplication and division algorithms:
-*
-* I searched unsucessfully for fast built-in operations like the `b_0'
-* and `c_0' Knuth describes in Section 4.3.1 of ``The Art of Computer
-* Programming'' (replace `place' by `Blk'):
-*
-* ``b_0[:] multiplication of a one-place integer by another one-place
-* integer, giving a two-place answer;
-*
-* ``c_0[:] division of a two-place integer by a one-place integer,
-* provided that the quotient is a one-place integer, and yielding
-* also a one-place remainder.''
-*
-* I also missed his note that ``[b]y adjusting the word size, if
-* necessary, nearly all computers will have these three operations
-* available'', so I gave up on trying to use algorithms similar to his.
-* A future version of the library might include such algorithms; I
-* would welcome contributions from others for this.
-*
-* I eventually decided to use bit-shifting algorithms. To multiply `a'
-* and `b', we zero out the result. Then, for each `1' bit in `a', we
-* shift `b' left the appropriate amount and add it to the result.
-* Similarly, to divide `a' by `b', we shift `b' left varying amounts,
-* repeatedly trying to subtract it from `a'. When we succeed, we note
-* the fact by setting a bit in the quotient. While these algorithms
-* have the same O(n^2) time complexity as Knuth's, the ``constant factor''
-* is likely to be larger.
-*
-* Because I used these algorithms, which require single-block addition
-* and subtraction rather than single-block multiplication and division,
-* the innermost loops of all four routines are very similar. Study one
-* of them and all will become clear.
-*/
+ * About the multiplication and division algorithms:
+ *
+ * I searched unsucessfully for fast built-in operations like the `b_0'
+ * and `c_0' Knuth describes in Section 4.3.1 of ``The Art of Computer
+ * Programming'' (replace `place' by `Blk'):
+ *
+ * ``b_0[:] multiplication of a one-place integer by another one-place
+ * integer, giving a two-place answer;
+ *
+ * ``c_0[:] division of a two-place integer by a one-place integer,
+ * provided that the quotient is a one-place integer, and yielding
+ * also a one-place remainder.''
+ *
+ * I also missed his note that ``[b]y adjusting the word size, if
+ * necessary, nearly all computers will have these three operations
+ * available'', so I gave up on trying to use algorithms similar to his.
+ * A future version of the library might include such algorithms; I
+ * would welcome contributions from others for this.
+ *
+ * I eventually decided to use bit-shifting algorithms. To multiply `a'
+ * and `b', we zero out the result. Then, for each `1' bit in `a', we
+ * shift `b' left the appropriate amount and add it to the result.
+ * Similarly, to divide `a' by `b', we shift `b' left varying amounts,
+ * repeatedly trying to subtract it from `a'. When we succeed, we note
+ * the fact by setting a bit in the quotient. While these algorithms
+ * have the same O(n^2) time complexity as Knuth's, the ``constant factor''
+ * is likely to be larger.
+ *
+ * Because I used these algorithms, which require single-block addition
+ * and subtraction rather than single-block multiplication and division,
+ * the innermost loops of all four routines are very similar. Study one
+ * of them and all will become clear.
+ */
/*
-* This is a little inline function used by both the multiplication
-* routine and the division routine.
-*
-* `getShiftedBlock' returns the `x'th block of `num << y'.
-* `y' may be anything from 0 to N - 1, and `x' may be anything from
-* 0 to `num.len'.
-*
-* Two things contribute to this block:
-*
-* (1) The `N - y' low bits of `num.blk[x]', shifted `y' bits left.
-*
-* (2) The `y' high bits of `num.blk[x-1]', shifted `N - y' bits right.
-*
-* But we must be careful if `x == 0' or `x == num.len', in
-* which case we should use 0 instead of (2) or (1), respectively.
-*
-* If `y == 0', then (2) contributes 0, as it should. However,
-* in some computer environments, for a reason I cannot understand,
-* `a >> b' means `a >> (b % N)'. This means `num.blk[x-1] >> (N - y)'
-* will return `num.blk[x-1]' instead of the desired 0 when `y == 0';
-* the test `y == 0' handles this case specially.
-*/
+ * This is a little inline function used by both the multiplication
+ * routine and the division routine.
+ *
+ * `getShiftedBlock' returns the `x'th block of `num << y'.
+ * `y' may be anything from 0 to N - 1, and `x' may be anything from
+ * 0 to `num.len'.
+ *
+ * Two things contribute to this block:
+ *
+ * (1) The `N - y' low bits of `num.blk[x]', shifted `y' bits left.
+ *
+ * (2) The `y' high bits of `num.blk[x-1]', shifted `N - y' bits right.
+ *
+ * But we must be careful if `x == 0' or `x == num.len', in
+ * which case we should use 0 instead of (2) or (1), respectively.
+ *
+ * If `y == 0', then (2) contributes 0, as it should. However,
+ * in some computer environments, for a reason I cannot understand,
+ * `a >> b' means `a >> (b % N)'. This means `num.blk[x-1] >> (N - y)'
+ * will return `num.blk[x-1]' instead of the desired 0 when `y == 0';
+ * the test `y == 0' handles this case specially.
+ */
inline BigUnsigned::Blk getShiftedBlock(const BigUnsigned &num,
BigUnsigned::Index x, unsigned int y) {
BigUnsigned::Blk part1 = (x == 0 || y == 0) ? 0 : (num.blk[x - 1] >> (BigUnsigned::N - y));
return;
}
/*
- * Overall method:
- *
- * Set this = 0.
- * For each 1-bit of `a' (say the `i2'th bit of block `i'):
- * Add `b << (i blocks and i2 bits)' to *this.
- */
+ * Overall method:
+ *
+ * Set this = 0.
+ * For each 1-bit of `a' (say the `i2'th bit of block `i'):
+ * Add `b << (i blocks and i2 bits)' to *this.
+ */
// Variables for the calculation
Index i, j, k;
unsigned int i2;
if ((a.blk[i] & (Blk(1) << i2)) == 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.
- *
- * `getShiftedBlock', a short inline function defined above,
- * is now used for the bit handling. It replaces the more
- * complex `bHigh' code, in which each run of the loop dealt
- * immediately with the low bits and saved the high bits to
- * be picked up next time. The last run of the loop used to
- * leave leftover high bits, which were handled separately.
- * Instead, this loop runs an additional time with j == b.len.
- * These changes were made on 2005.01.11.
- */
+ * 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.
+ *
+ * `getShiftedBlock', a short inline function defined above,
+ * is now used for the bit handling. It replaces the more
+ * complex `bHigh' code, in which each run of the loop dealt
+ * immediately with the low bits and saved the high bits to
+ * be picked up next time. The last run of the loop used to
+ * leave leftover high bits, which were handled separately.
+ * Instead, this loop runs an additional time with j == b.len.
+ * These changes were made on 2005.01.11.
+ */
for (j = 0, k = i, carryIn = false; j <= b.len; j++, k++) {
/*
- * The body of this loop is very similar to the body of the first loop
- * in `add', except that this loop does a `+=' instead of a `+'.
- */
+ * The body of this loop is very similar to the body of the first loop
+ * in `add', except that this loop does a `+=' instead of a `+'.
+ */
temp = blk[k] + getShiftedBlock(b, j, i2);
carryOut = (temp < blk[k]);
if (carryIn) {
}
/*
-* 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.
-* A better name for this function might be "modWithQuotient", but I would rather
-* not change the name now.
-*/
+ * 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.
+ * A better name for this function might be "modWithQuotient", but I would rather
+ * not change the name now.
+ */
void BigUnsigned::divideWithRemainder(const BigUnsigned &b, BigUnsigned &q) {
/*
* Defending against aliased calls is a bit tricky because we are
}
/*
- * 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.
- */
+ * 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 *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!)
- */
+ * At this point we know *this > b > 0. (Whew!)
+ */
/*
- * Overall method:
- *
- * For each appropriate i and i2, decreasing:
- * Try to subtract (b << (i blocks and i2 bits)) from *this.
- * (`work2' holds the result of this subtraction.)
- * If the result is nonnegative:
- * Turn on bit i2 of block i of the quotient q.
- * Save the result of the subtraction back into *this.
- * Otherwise:
- * Bit i2 of block i remains off, and *this is unchanged.
- *
- * 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.
- * work2[x] corresponds to blk[x], not blk[x+i], since 2005.01.11.
- * If the subtraction is successful, we copy work2 back to blk.
- * (There's no `work1'. In a previous version, when division was
- * coded for a read-only dividend, `work1' played the role of
- * the here-modifiable `*this' and got the remainder.)
- *
- * We never touch the i lowest blocks of either blk or work2 because
- * they are unaffected by the subtraction: we are subtracting
- * (b << (i blocks and i2 bits)), which ends in at least `i' zero blocks.
- */
+ * Overall method:
+ *
+ * For each appropriate i and i2, decreasing:
+ * Try to subtract (b << (i blocks and i2 bits)) from *this.
+ * (`work2' holds the result of this subtraction.)
+ * If the result is nonnegative:
+ * Turn on bit i2 of block i of the quotient q.
+ * Save the result of the subtraction back into *this.
+ * Otherwise:
+ * Bit i2 of block i remains off, and *this is unchanged.
+ *
+ * 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.
+ * work2[x] corresponds to blk[x], not blk[x+i], since 2005.01.11.
+ * If the subtraction is successful, we copy work2 back to blk.
+ * (There's no `work1'. In a previous version, when division was
+ * coded for a read-only dividend, `work1' played the role of
+ * the here-modifiable `*this' and got the remainder.)
+ *
+ * We never touch the i lowest blocks of either blk or work2 because
+ * they are unaffected by the subtraction: we are subtracting
+ * (b << (i blocks and i2 bits)), which ends in at least `i' zero blocks.
+ */
// Variables for the calculation
Index i, j, k;
unsigned int i2;
bool borrowIn, borrowOut;
/*
- * Make sure we have an extra zero block just past the value.
- *
- * When we attempt a subtraction, we might shift `b' so
- * its first block begins a few bits left of the dividend,
- * and then we'll try to compare these extra bits with
- * a nonexistent block to the left of the dividend. The
- * extra zero block ensures sensible behavior; we need
- * an extra block in `work2' for exactly the same reason.
- *
- * See below `divideWithRemainder' for the interesting and
- * amusing story of this section of code.
- */
+ * Make sure we have an extra zero block just past the value.
+ *
+ * When we attempt a subtraction, we might shift `b' so
+ * its first block begins a few bits left of the dividend,
+ * and then we'll try to compare these extra bits with
+ * a nonexistent block to the left of the dividend. The
+ * extra zero block ensures sensible behavior; we need
+ * an extra block in `work2' for exactly the same reason.
+ *
+ * See below `divideWithRemainder' for the interesting and
+ * amusing story of this section of code.
+ */
Index origLen = len; // Save real length.
// 2006.05.03: Copy the number and then change the length!
allocateAndCopy(len + 1); // Get the space.
while (i2 > 0) {
i2--;
/*
- * Subtract b, shifted left i blocks and i2 bits, from *this,
- * and store the answer in work2. In the for loop, `k == i + j'.
- *
- * Compare this to the middle section of `multiply'. They
- * are in many ways analogous. See especially the discussion
- * of `getShiftedBlock'.
- */
+ * Subtract b, shifted left i blocks and i2 bits, from *this,
+ * and store the answer in work2. In the for loop, `k == i + j'.
+ *
+ * Compare this to the middle section of `multiply'. They
+ * are in many ways analogous. See especially the discussion
+ * of `getShiftedBlock'.
+ */
for (j = 0, k = i, borrowIn = false; j <= b.len; j++, k++) {
temp = blk[k] - getShiftedBlock(b, j, i2);
borrowOut = (temp > blk[k]);
work2[k] = blk[k] - 1;
}
/*
- * If the subtraction was performed successfully (!borrowIn),
- * set bit i2 in block i of the quotient.
- *
- * Then, copy the portion of work2 filled by the subtraction
- * back to *this. This portion starts with block i and ends--
- * where? Not necessarily at block `i + b.len'! Well, we
- * increased k every time we saved a block into work2, so
- * the region of work2 we copy is just [i, k).
- */
+ * If the subtraction was performed successfully (!borrowIn),
+ * set bit i2 in block i of the quotient.
+ *
+ * Then, copy the portion of work2 filled by the subtraction
+ * back to *this. This portion starts with block i and ends--
+ * where? Not necessarily at block `i + b.len'! Well, we
+ * increased k every time we saved a block into work2, so
+ * the region of work2 we copy is just [i, k).
+ */
if (!borrowIn) {
q.blk[i] |= (Blk(1) << i2);
while (k > i) {
}
/*
-* The out-of-bounds accesses story:
-*
-* On 2005.01.06 or 2005.01.07 (depending on your time zone),
-* Milan Tomic reported out-of-bounds memory accesses in
-* the Big Integer Library. To investigate the problem, I
-* added code to bounds-check every access to the `blk' array
-* of a `NumberlikeArray'.
-*
-* This gave me warnings that fell into two categories of false
-* positives. The bounds checker was based on length, not
-* capacity, and in two places I had accessed memory that I knew
-* was inside the capacity but that wasn't inside the length:
-*
-* (1) The extra zero block at the left of `*this'. Earlier
-* versions said `allocateAndCopy(len + 1); blk[len] = 0;'
-* but did not increment `len'.
-*
-* (2) The entire digit array in the conversion constructor
-* ``BigUnsignedInABase(BigUnsigned)''. It was allocated with
-* a conservatively high capacity, but the length wasn't set
-* until the end of the constructor.
-*
-* To simplify matters, I changed both sections of code so that
-* all accesses occurred within the length. The messages went
-* away, and I told Milan that I couldn't reproduce the problem,
-* sending a development snapshot of the bounds-checked code.
-*
-* Then, on 2005.01.09-10, he told me his debugger still found
-* problems, specifically at the line `delete [] work2'.
-* It was `work2', not `blk', that was causing the problems;
-* this possibility had not occurred to me at all. In fact,
-* the problem was that `work2' needed an extra block just
-* like `*this'. Go ahead and laugh at me for finding (1)
-* without seeing what was actually causing the trouble. :-)
-*
-* The 2005.01.11 version fixes this problem. I hope this is
-* the last of my memory-related bloopers. So this is what
-* starts happening to your C++ code if you use Java too much!
-*/
+ * The out-of-bounds accesses story:
+ *
+ * On 2005.01.06 or 2005.01.07 (depending on your time zone),
+ * Milan Tomic reported out-of-bounds memory accesses in
+ * the Big Integer Library. To investigate the problem, I
+ * added code to bounds-check every access to the `blk' array
+ * of a `NumberlikeArray'.
+ *
+ * This gave me warnings that fell into two categories of false
+ * positives. The bounds checker was based on length, not
+ * capacity, and in two places I had accessed memory that I knew
+ * was inside the capacity but that wasn't inside the length:
+ *
+ * (1) The extra zero block at the left of `*this'. Earlier
+ * versions said `allocateAndCopy(len + 1); blk[len] = 0;'
+ * but did not increment `len'.
+ *
+ * (2) The entire digit array in the conversion constructor
+ * ``BigUnsignedInABase(BigUnsigned)''. It was allocated with
+ * a conservatively high capacity, but the length wasn't set
+ * until the end of the constructor.
+ *
+ * To simplify matters, I changed both sections of code so that
+ * all accesses occurred within the length. The messages went
+ * away, and I told Milan that I couldn't reproduce the problem,
+ * sending a development snapshot of the bounds-checked code.
+ *
+ * Then, on 2005.01.09-10, he told me his debugger still found
+ * problems, specifically at the line `delete [] work2'.
+ * It was `work2', not `blk', that was causing the problems;
+ * this possibility had not occurred to me at all. In fact,
+ * the problem was that `work2' needed an extra block just
+ * like `*this'. Go ahead and laugh at me for finding (1)
+ * without seeing what was actually causing the trouble. :-)
+ *
+ * The 2005.01.11 version fixes this problem. I hope this is
+ * the last of my memory-related bloopers. So this is what
+ * starts happening to your C++ code if you use Java too much!
+ */
// Bitwise and
void BigUnsigned::bitAnd(const BigUnsigned &a, const BigUnsigned &b) {
/*
-* Matt McCutchen's Big Integer Library
-*/
+ * Matt McCutchen's Big Integer Library
+ */
#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 BigUnsigneds.
-*
-* 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.**
-*
-* 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.
-*/
+ * 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 BigUnsigneds.
+ *
+ * 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.**
+ *
+ * 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 : protected NumberlikeArray<unsigned long> {
bool operator > (const BigUnsigned &x) const { return compareTo(x) == greater; }
/*
- * BigUnsigned and BigInteger both provide three kinds of operators.
- * Here ``big-integer'' refers to BigInteger or BigUnsigned.
- *
- * (1) Overloaded ``return-by-value'' operators:
- * +, -, *, /, %, unary -.
- * Big-integer code using these operators looks identical to
- * code using the primitive integer types. These operators take
- * one or two big-integer inputs and return a big-integer result,
- * which can then be assigned to a BigInteger variable or used
- * in an expression. Example:
- * BigInteger a(1), b = 1;
- * BigInteger c = a + b;
- *
- * (2) Overloaded assignment operators:
- * +=, -=, *=, /=, %=, &=, |=, ^=, ++, --, flipSign.
- * Again, these are used on big integers just like on ints.
- * They take one writable big integer that both provides an
- * operand and receives a result. The first eight also take
- * a second read-only operand. Example:
- * BigInteger a(1), b(1);
- * a += b;
- *
- * (3) ``Put-here'' operations: `add', `subtract', etc.
- * Using a return-by-value or assignment operator generally involves
- * copy constructions and/or assignments. The ``put-here'' operations
- * require none, but they are more of a hassle to use. Most take two
- * read-only operands and save the result in the calling object `*this',
- * whose previous value is ignored. `divideWithRemainder' is an exception.
- * <<< NOTE >>>: Put-here operations do not return a value: they don't need to!!
- * Examples:
- * BigInteger a(43), b(7), c, d;
- * c = a + b; // Now c == 50.
- * c.add(a, b); // Same effect but without the two bulk-copies.
- * c.divideWithRemainder(b, d); // 50 / 7; now d == 7 (quotient) and c == 1 (remainder).
- * a.add(a, b); // ``Aliased'' calls now do the right thing using a
- * // temporary copy, but see note on divideWithRemainder.
- */
+ * BigUnsigned and BigInteger both provide three kinds of operators.
+ * Here ``big-integer'' refers to BigInteger or BigUnsigned.
+ *
+ * (1) Overloaded ``return-by-value'' operators:
+ * +, -, *, /, %, unary -.
+ * Big-integer code using these operators looks identical to
+ * code using the primitive integer types. These operators take
+ * one or two big-integer inputs and return a big-integer result,
+ * which can then be assigned to a BigInteger variable or used
+ * in an expression. Example:
+ * BigInteger a(1), b = 1;
+ * BigInteger c = a + b;
+ *
+ * (2) Overloaded assignment operators:
+ * +=, -=, *=, /=, %=, &=, |=, ^=, ++, --, flipSign.
+ * Again, these are used on big integers just like on ints.
+ * They take one writable big integer that both provides an
+ * operand and receives a result. The first eight also take
+ * a second read-only operand. Example:
+ * BigInteger a(1), b(1);
+ * a += b;
+ *
+ * (3) ``Put-here'' operations: `add', `subtract', etc.
+ * Using a return-by-value or assignment operator generally involves
+ * copy constructions and/or assignments. The ``put-here'' operations
+ * require none, but they are more of a hassle to use. Most take two
+ * read-only operands and save the result in the calling object `*this',
+ * whose previous value is ignored. `divideWithRemainder' is an exception.
+ * <<< NOTE >>>: Put-here operations do not return a value: they don't need to!!
+ * Examples:
+ * BigInteger a(43), b(7), c, d;
+ * c = a + b; // Now c == 50.
+ * c.add(a, b); // Same effect but without the two bulk-copies.
+ * c.divideWithRemainder(b, d); // 50 / 7; now d == 7 (quotient) and c == 1 (remainder).
+ * a.add(a, b); // ``Aliased'' calls now do the right thing using a
+ * // temporary copy, but see note on divideWithRemainder.
+ */
// PUT-HERE OPERATIONS
public:
void subtract(const BigUnsigned &a, const BigUnsigned &b); // Subtraction
void multiply(const BigUnsigned &a, const BigUnsigned &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 differ from the semantics of primitive-type
- * / and % under division by zero.
- * Look in `BigUnsigned.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 differ from the semantics of primitive-type
+ * / and % under division by zero.
+ * Look in `BigUnsigned.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 BigUnsigned &b, BigUnsigned &q);
void divide(const BigUnsigned &a, const BigUnsigned &b) {
BigUnsigned a2(a);
// 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 BigUnsigned BigUnsigned::operator +(const BigUnsigned &x) const {
BigUnsigned ans;
ans.add(*this, x);
/*
-* Matt McCutchen's Big Integer Library
-*/
+ * Matt McCutchen's Big Integer Library
+ */
/*
-* Milan Tomic had trouble compiling this file on Microsoft
-* Visual C++ 6 because, in the libraries that come with
-* Visual C++ 6, the `std::string::push_back' method apparently
-* does not exist. To get around the problem, I rewrote
-* `BigUnsignedInABase::operator std::string' (at the bottom
-* of this file) so it doesn't use `push_back'.
-*/
+ * Milan Tomic had trouble compiling this file on Microsoft
+ * Visual C++ 6 because, in the libraries that come with
+ * Visual C++ 6, the `std::string::push_back' method apparently
+ * does not exist. To get around the problem, I rewrote
+ * `BigUnsignedInABase::operator std::string' (at the bottom
+ * of this file) so it doesn't use `push_back'.
+ */
#include "BigUnsignedInABase.hh"
/*
-* Matt McCutchen's Big Integer Library
-*/
+ * Matt McCutchen's Big Integer Library
+ */
#ifndef BIGUNSIGNEDINABASE
#define BIGUNSIGNEDINABASE
#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.
-*/
+ * 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> {
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.
- */
+ *
+ * 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);
/*
-* Matt McCutchen's Big Integer Library
-*/
+ * Matt McCutchen's Big Integer Library
+ */
/*
-* This mechanism prevents files from being included twice.
-* Each file gets its own `id' (here `NUMBERLIKEARRAY').
-* When `#include'd, this file checks whether its `id' has
-* already been flagged. If not, it flags the `id' and
-* loads the declarations.
-*/
+ * This mechanism prevents files from being included twice.
+ * Each file gets its own `id' (here `NUMBERLIKEARRAY').
+ * When `#include'd, this file checks whether its `id' has
+ * already been flagged. If not, it flags the `id' and
+ * loads the declarations.
+ */
#ifndef NUMBERLIKEARRAY
#define NUMBERLIKEARRAY
#endif
/*
-* A NumberlikeArray<Blk> object holds a dynamically
-* allocated array of Blk. 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;
-*/
+ * A NumberlikeArray<Blk> object holds a dynamically
+ * allocated array of Blk. 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 {
Blk *blk; // Dynamically allocated array of the blocks
/*
- * Change made on 2005.01.06:
- *
- * If a zero-length NumberlikeArray is desired, no array is actually allocated.
- * Instead, `blk' is set to `NULL', and `cap' and `len' are zero as usual.
- *
- * `blk' is never dereferenced if the array has zero length. Furthermore,
- * `delete NULL;' does nothing and causes no error. Therefore, we can use
- * `NULL' as if it were a zero-length array from `new'.
- *
- * 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.
- */
+ * Change made on 2005.01.06:
+ *
+ * If a zero-length NumberlikeArray is desired, no array is actually allocated.
+ * Instead, `blk' is set to `NULL', and `cap' and `len' are zero as usual.
+ *
+ * `blk' is never dereferenced if the array has zero length. Furthermore,
+ * `delete NULL;' does nothing and causes no error. Therefore, we can use
+ * `NULL' as if it were a zero-length array from `new'.
+ *
+ * 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
void allocateAndCopy(Index c); // Ensures the array has at least the indicated capacity, preserving its contents
/*
- * Default constructor.
- *
- * If a class derived from NumberlikeArray knows at initializer time what size array
- * it wants, it can call the first constructor listed above in an initializer.
- *
- * Otherwise, this default constructor will be implicitly invoked, pointing `blk' to
- * `NULL', a fake zero-length block array. The derived class can allocate the desired
- * array itself and overwrite `blk'; it need not `delete [] blk' first.
- *
- * This change fixes a memory leak reported by Milan Tomic on 2005.01.06.
- * Integer-type-to-BigUnsigned (and BigInteger) conversion constructors have always
- * allocated their own array of length 0 or 1 after seeing whether the input is zero.
- * But when the NumberlikeArray transition occurred, these constructors contained an
- * implicit initializer call to the old NumberlikeArray default constructor, which
- * created a real `new'-allocated zero-length array. This array would then be lost,
- * causing a small but annoying memory leak.
- */
+ * Default constructor.
+ *
+ * If a class derived from NumberlikeArray knows at initializer time what size array
+ * it wants, it can call the first constructor listed above in an initializer.
+ *
+ * Otherwise, this default constructor will be implicitly invoked, pointing `blk' to
+ * `NULL', a fake zero-length block array. The derived class can allocate the desired
+ * array itself and overwrite `blk'; it need not `delete [] blk' first.
+ *
+ * This change fixes a memory leak reported by Milan Tomic on 2005.01.06.
+ * Integer-type-to-BigUnsigned (and BigInteger) conversion constructors have always
+ * allocated their own array of length 0 or 1 after seeing whether the input is zero.
+ * But when the NumberlikeArray transition occurred, these constructors contained an
+ * implicit initializer call to the old NumberlikeArray default constructor, which
+ * created a real `new'-allocated zero-length array. This array would then be lost,
+ * causing a small but annoying memory leak.
+ */
NumberlikeArray() : cap(0), len(0) {
blk = NULL;
}
};
/*
-* =================================
-* 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.
-*/
+ * =================================
+ * 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.
+ */
template <class Blk>
const unsigned int NumberlikeArray<Blk>::N = 8 * sizeof(Blk);
/*
-* Matt McCutchen's Big Integer Library
-*
-* Sample program demonstrating the most important features of the Big
-* Integer Library
-*/
+ * Matt McCutchen's Big Integer Library
+ *
+ * Sample program demonstrating the most important features of the Big
+ * Integer Library
+ */
// Standard libraries
#include <string>
a = b; // From int to BigInteger...
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; the `try/catch' construct wrapping all this
- * code is an example of how to do this. Some C++ compilers need
- * a special command-line option to compile code that uses
- * exceptions.
- */
+ * 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; the `try/catch' construct wrapping all this
+ * code is an example of how to do this. Some C++ compilers need
+ * a special command-line option to compile code that uses
+ * exceptions.
+ */
BigInteger c(a); // Copy a BigInteger.
std::cout << f << std::endl;
/*
- * Let's do some math!
- *
- * The Big Integer Library provides lots of overloaded operators
- * and corresponding assignment operators. So you can do `a + b'
- * with BigIntegers just as with normal integers. The named
- * methods `add', `divideWithRemainder', etc. are more advanced
- * ``put-here operations''; see `BigUnsigned.hh' for details.
- */
+ * Let's do some math!
+ *
+ * The Big Integer Library provides lots of overloaded operators
+ * and corresponding assignment operators. So you can do `a + b'
+ * with BigIntegers just as with normal integers. The named
+ * methods `add', `divideWithRemainder', etc. are more advanced
+ * ``put-here operations''; see `BigUnsigned.hh' for details.
+ */
BigInteger g(314159), h(265);
// All five ``return-by-value'' arithmetic operators.
std::cout << (g + h) << '\n' << (g - h) << '\n' << (g * h)
}
/*
- * If you want to experiment with the library,
- * you can add your own test code here.
- */
+ * 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) {
314^9 = 29673367320587092457984
314^10 = 9317437338664347031806976
-*/
+ */
Matt McCutchen's Web Site / bigint / bigint.git / commitdiff