From 6e1e0f2f3c2fee3e1e9df39c6d4816566c10aafb Mon Sep 17 00:00:00 2001 From: Matt McCutchen Date: Thu, 17 Jan 2008 22:45:02 -0500 Subject: [PATCH] Indent comments an extra space so the stars line up. --- BigInteger.cc | 150 ++++++------- BigInteger.hh | 60 +++--- BigIntegerLibrary.hh | 4 +- BigIntegerUtils.cc | 12 +- BigIntegerUtils.hh | 42 ++-- BigUnsigned.cc | 488 +++++++++++++++++++++--------------------- BigUnsigned.hh | 130 +++++------ BigUnsignedInABase.cc | 18 +- BigUnsignedInABase.hh | 84 ++++---- NumberlikeArray.hh | 136 ++++++------ sample.cc | 50 ++--- 11 files changed, 587 insertions(+), 587 deletions(-) diff --git a/BigInteger.cc b/BigInteger.cc index 00074cf..11ac841 100644 --- a/BigInteger.cc +++ b/BigInteger.cc @@ -1,6 +1,6 @@ /* -* Matt McCutchen's Big Integer Library -*/ + * Matt McCutchen's Big Integer Library + */ #include "BigInteger.hh" @@ -44,22 +44,22 @@ BigInteger::BigInteger(const BigUnsigned &x, Sign s) : BigUnsigned(x) { } /* -* 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) @@ -150,23 +150,23 @@ BigInteger::BigInteger(short x) { // 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 @@ -412,27 +412,27 @@ void BigInteger::multiply(const BigInteger &a, const BigInteger &b) { } /* -* 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 . @@ -469,25 +469,25 @@ void BigInteger::divideWithRemainder(const BigInteger &b, BigInteger &q) { // 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. diff --git a/BigInteger.hh b/BigInteger.hh index 1605975..8aa65ed 100644 --- a/BigInteger.hh +++ b/BigInteger.hh @@ -1,6 +1,6 @@ /* -* Matt McCutchen's Big Integer Library -*/ + * Matt McCutchen's Big Integer Library + */ #ifndef BIGINTEGER #define BIGINTEGER @@ -8,22 +8,22 @@ #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 { @@ -91,21 +91,21 @@ 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); @@ -163,8 +163,8 @@ inline BigInteger::Sign BigInteger::getSign() const { return sign; } // 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); diff --git a/BigIntegerLibrary.hh b/BigIntegerLibrary.hh index 2f01a3b..27e5198 100644 --- a/BigIntegerLibrary.hh +++ b/BigIntegerLibrary.hh @@ -1,6 +1,6 @@ /* -* Matt McCutchen's Big Integer Library -*/ + * Matt McCutchen's Big Integer Library + */ // This header file includes all the other header files. diff --git a/BigIntegerUtils.cc b/BigIntegerUtils.cc index ea00ed2..c8f4df2 100644 --- a/BigIntegerUtils.cc +++ b/BigIntegerUtils.cc @@ -1,15 +1,15 @@ /* -* 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)); diff --git a/BigIntegerUtils.hh b/BigIntegerUtils.hh index dfbdee3..42f2ed6 100644 --- a/BigIntegerUtils.hh +++ b/BigIntegerUtils.hh @@ -1,6 +1,6 @@ /* -* Matt McCutchen's Big Integer Library -*/ + * Matt McCutchen's Big Integer Library + */ #ifndef BIGINTEGERUTILS #define BIGINTEGERUTILS @@ -10,10 +10,10 @@ #include /* -* 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); @@ -33,23 +33,23 @@ std::ostream &operator <<(std::ostream &os, 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 BigInteger easyDataToBI(const T* data, BigInteger::Index length, BigInteger::Sign sign) { // really ceiling(numBytes / sizeof(BigInteger::Blk)) diff --git a/BigUnsigned.cc b/BigUnsigned.cc index f6a925c..f2f5dfa 100644 --- a/BigUnsigned.cc +++ b/BigUnsigned.cc @@ -1,28 +1,28 @@ /* -* 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) @@ -95,15 +95,15 @@ BigUnsigned::BigUnsigned(short x) { // 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 @@ -197,26 +197,26 @@ BigUnsigned::CmpRes BigUnsigned::compareTo(const BigUnsigned &x) const { // 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 @@ -355,63 +355,63 @@ void BigUnsigned::subtract(const BigUnsigned &a, const BigUnsigned &b) { } /* -* 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)); @@ -428,12 +428,12 @@ void BigUnsigned::multiply(const BigUnsigned &a, const BigUnsigned &b) { 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; @@ -452,23 +452,23 @@ void BigUnsigned::multiply(const BigUnsigned &a, const BigUnsigned &b) { 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) { @@ -492,22 +492,22 @@ void BigUnsigned::multiply(const BigUnsigned &a, const BigUnsigned &b) { } /* -* 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 @@ -529,58 +529,58 @@ void BigUnsigned::divideWithRemainder(const BigUnsigned &b, BigUnsigned &q) { } /* - * 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; @@ -588,18 +588,18 @@ void BigUnsigned::divideWithRemainder(const BigUnsigned &b, BigUnsigned &q) { 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. @@ -627,13 +627,13 @@ void BigUnsigned::divideWithRemainder(const BigUnsigned &b, BigUnsigned &q) { 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]); @@ -652,15 +652,15 @@ void BigUnsigned::divideWithRemainder(const BigUnsigned &b, BigUnsigned &q) { 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) { @@ -681,45 +681,45 @@ void BigUnsigned::divideWithRemainder(const BigUnsigned &b, BigUnsigned &q) { } /* -* 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) { diff --git a/BigUnsigned.hh b/BigUnsigned.hh index 50fca2f..8ce1767 100644 --- a/BigUnsigned.hh +++ b/BigUnsigned.hh @@ -1,6 +1,6 @@ /* -* Matt McCutchen's Big Integer Library -*/ + * Matt McCutchen's Big Integer Library + */ #ifndef BIGUNSIGNED #define BIGUNSIGNED @@ -8,22 +8,22 @@ #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 { @@ -117,43 +117,43 @@ class BigUnsigned : protected NumberlikeArray { 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: @@ -162,14 +162,14 @@ class BigUnsigned : protected NumberlikeArray { 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); @@ -243,8 +243,8 @@ class BigUnsigned : protected NumberlikeArray { // 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); diff --git a/BigUnsignedInABase.cc b/BigUnsignedInABase.cc index b423ca2..c9b2906 100644 --- a/BigUnsignedInABase.cc +++ b/BigUnsignedInABase.cc @@ -1,15 +1,15 @@ /* -* 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" diff --git a/BigUnsignedInABase.hh b/BigUnsignedInABase.hh index 3712907..737d877 100644 --- a/BigUnsignedInABase.hh +++ b/BigUnsignedInABase.hh @@ -1,6 +1,6 @@ /* -* Matt McCutchen's Big Integer Library -*/ + * Matt McCutchen's Big Integer Library + */ #ifndef BIGUNSIGNEDINABASE #define BIGUNSIGNEDINABASE @@ -10,31 +10,31 @@ #include /* -* 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 { @@ -80,21 +80,21 @@ class BigUnsignedInABase : protected NumberlikeArray { 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); diff --git a/NumberlikeArray.hh b/NumberlikeArray.hh index d884d37..971c75f 100644 --- a/NumberlikeArray.hh +++ b/NumberlikeArray.hh @@ -1,14 +1,14 @@ /* -* 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 @@ -19,22 +19,22 @@ #endif /* -* A NumberlikeArray 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 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 NumberlikeArray { @@ -49,18 +49,18 @@ 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 @@ -70,23 +70,23 @@ class NumberlikeArray { 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; } @@ -113,21 +113,21 @@ class NumberlikeArray { }; /* -* ================================= -* 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 const unsigned int NumberlikeArray::N = 8 * sizeof(Blk); diff --git a/sample.cc b/sample.cc index 58e5a42..008f400 100644 --- a/sample.cc +++ b/sample.cc @@ -1,9 +1,9 @@ /* -* 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 @@ -23,14 +23,14 @@ int main() { 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. @@ -53,14 +53,14 @@ int main() { 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) @@ -82,9 +82,9 @@ int main() { } /* - * 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) { @@ -121,4 +121,4 @@ Running the sample program produces this output: 314^9 = 29673367320587092457984 314^10 = 9317437338664347031806976 -*/ + */ -- 2.34.1