From: Matt McCutchen Date: Sat, 27 Jan 2007 21:06:15 +0000 (-0500) Subject: Old snapshot `BigIntegerLibrary-2005.01.11'; see the ChangeLog file. X-Git-Tag: v2007.07.07~17 X-Git-Url: https://mattmccutchen.net/bigint/bigint.git/commitdiff_plain/4efbb07622a0aa83db4fe05ca8c17aca406ed928 Old snapshot `BigIntegerLibrary-2005.01.11'; see the ChangeLog file. --- diff --git a/BigInteger.cc b/BigInteger.cc index 471d056..69d2dd7 100644 --- a/BigInteger.cc +++ b/BigInteger.cc @@ -67,7 +67,7 @@ BigInteger::BigInteger(unsigned long x) { sign = zero; // NumberlikeArray did the rest else { cap = 1; - blk2 = new Blk[1]; + blk = new Blk[1]; sign = positive; len = 1; blk[0] = Blk(x); @@ -77,13 +77,13 @@ BigInteger::BigInteger(unsigned long x) { BigInteger::BigInteger(long x) { if (x > 0) { cap = 1; - blk2 = new Blk[1]; + blk = new Blk[1]; sign = positive; len = 1; blk[0] = Blk(x); } else if (x < 0) { cap = 1; - blk2 = new Blk[1]; + blk = new Blk[1]; sign = negative; len = 1; blk[0] = Blk(-x); @@ -96,7 +96,7 @@ BigInteger::BigInteger(unsigned int x) { sign = zero; else { cap = 1; - blk2 = new Blk[1]; + blk = new Blk[1]; sign = positive; len = 1; blk[0] = Blk(x); @@ -106,13 +106,13 @@ BigInteger::BigInteger(unsigned int x) { BigInteger::BigInteger(int x) { if (x > 0) { cap = 1; - blk2 = new Blk[1]; + blk = new Blk[1]; sign = positive; len = 1; blk[0] = Blk(x); } else if (x < 0) { cap = 1; - blk2 = new Blk[1]; + blk = new Blk[1]; sign = negative; len = 1; blk[0] = Blk(-x); @@ -125,7 +125,7 @@ BigInteger::BigInteger(unsigned short x) { sign = zero; else { cap = 1; - blk2 = new Blk[1]; + blk = new Blk[1]; sign = positive; len = 1; blk[0] = Blk(x); @@ -135,13 +135,13 @@ BigInteger::BigInteger(unsigned short x) { BigInteger::BigInteger(short x) { if (x > 0) { cap = 1; - blk2 = new Blk[1]; + blk = new Blk[1]; sign = positive; len = 1; blk[0] = Blk(x); } else if (x < 0) { cap = 1; - blk2 = new Blk[1]; + blk = new Blk[1]; sign = negative; len = 1; blk[0] = Blk(-x); diff --git a/BigInteger.hh b/BigInteger.hh index e206718..4231824 100644 --- a/BigInteger.hh +++ b/BigInteger.hh @@ -15,8 +15,9 @@ * 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 numbers -* were written digit by digit in base 256 ^ sizeof(unsigned long). +* 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 diff --git a/BigUnsigned.cc b/BigUnsigned.cc index 2a61477..4074822 100644 --- a/BigUnsigned.cc +++ b/BigUnsigned.cc @@ -20,7 +20,7 @@ * 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 `blk2 = NULL, cap = len = 0'. +* 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'. */ @@ -30,7 +30,7 @@ BigUnsigned::BigUnsigned(unsigned long x) { ; // NumberlikeArray already did all the work else { cap = 1; - blk2 = new Blk[1]; + blk = new Blk[1]; len = 1; blk[0] = Blk(x); } @@ -41,7 +41,7 @@ BigUnsigned::BigUnsigned(long x) { ; else if (x > 0) { cap = 1; - blk2 = new Blk[1]; + blk = new Blk[1]; len = 1; blk[0] = Blk(x); } else @@ -53,7 +53,7 @@ BigUnsigned::BigUnsigned(unsigned int x) { ; else { cap = 1; - blk2 = new Blk[1]; + blk = new Blk[1]; len = 1; blk[0] = Blk(x); } @@ -64,7 +64,7 @@ BigUnsigned::BigUnsigned(int x) { ; else if (x > 0) { cap = 1; - blk2 = new Blk[1]; + blk = new Blk[1]; len = 1; blk[0] = Blk(x); } else @@ -76,7 +76,7 @@ BigUnsigned::BigUnsigned(unsigned short x) { ; else { cap = 1; - blk2 = new Blk[1]; + blk = new Blk[1]; len = 1; blk[0] = Blk(x); } @@ -87,7 +87,7 @@ BigUnsigned::BigUnsigned(short x) { ; else if (x > 0) { cap = 1; - blk2 = new Blk[1]; + blk = new Blk[1]; len = 1; blk[0] = Blk(x); } else @@ -197,6 +197,28 @@ 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''. +*/ + // Addition void BigUnsigned::add(const BigUnsigned &a, const BigUnsigned &b) { // Block unsafe calls @@ -210,6 +232,7 @@ void BigUnsigned::add(const BigUnsigned &a, const BigUnsigned &b) { operator =(a); return; } + // Some variables... // Carries in and out of an addition stage bool carryIn, carryOut; Blk temp; @@ -270,6 +293,7 @@ void BigUnsigned::subtract(const BigUnsigned &a, const BigUnsigned &b) { return; } else if (a.len < b.len) throw "BigUnsigned::subtract: Negative result in unsigned calculation"; + // Some variables... bool borrowIn, borrowOut; Blk temp; Index i; @@ -307,6 +331,71 @@ void BigUnsigned::subtract(const BigUnsigned &a, const BigUnsigned &b) { zapLeadingZeros(); } +/* +* 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. +*/ +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)); + BigUnsigned::Blk part2 = (x == num.len) ? 0 : (num.blk[x] << y); + return part1 | part2; +} + // Multiplication void BigUnsigned::multiply(const BigUnsigned &a, const BigUnsigned &b) { // Block unsafe calls @@ -317,12 +406,17 @@ void BigUnsigned::multiply(const BigUnsigned &a, const BigUnsigned &b) { len = 0; return; } - // Overall method: this = 0, then for each 1-bit of a, add b - // to this shifted the appropriate amount. + /* + * 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; - Blk aBlk, bHigh, temp; + Blk temp; bool carryIn, carryOut; // Set preliminary length and make room len = a.len + b.len; @@ -333,16 +427,28 @@ void BigUnsigned::multiply(const BigUnsigned &a, const BigUnsigned &b) { // For each block of the first number... for (i = 0; i < a.len; i++) { // For each 1-bit of that block... - for (i2 = 0, aBlk = a.blk[i]; aBlk != 0; i2++, aBlk >>= 1) { - if ((aBlk & 1) == 0) + for (i2 = 0; i2 < N; i2++) { + if ((a.blk[i] & (1 << i2)) == 0) continue; - /* Add b to this, shifted left i blocks and i2 bits. + /* + * 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. - * The low bits of b.blk[j] are shifted and added to blk[k]. - * bHigh is used to carry the high bits to the next addition. */ - bHigh = 0; - for (j = 0, k = i, carryIn = false; j < b.len; j++, k++) { - temp = blk[k] + ((b.blk[j] << i2) | bHigh); + * + * `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 `+'. + */ + temp = blk[k] + getShiftedBlock(b, j, i2); carryOut = (temp < blk[k]); if (carryIn) { temp++; @@ -350,17 +456,9 @@ void BigUnsigned::multiply(const BigUnsigned &a, const BigUnsigned &b) { } blk[k] = temp; carryIn = carryOut; - bHigh = (i2 == 0) ? 0 : b.blk[j] >> (8 * sizeof(Blk) - i2); - } - temp = blk[k] + bHigh; - carryOut = (temp < blk[k]); - if (carryIn) { - temp++; - carryOut |= (temp == 0); } - blk[k] = temp; - carryIn = carryOut; - k++; // Added by Matt 2004.12.23: Move to the next block. It belongs here (and there was a corresponding line in the division routine), but I'm not certain whether it ever matters. + // No more extra iteration to deal with `bHigh'. + // Roll-over a carry as necessary. for (; carryIn; k++) { blk[k]++; carryIn = (blk[k] == 0); @@ -392,14 +490,6 @@ void BigUnsigned::divideWithRemainder(const BigUnsigned &b, BigUnsigned &q) { if (this == &b || &q == &b || this == &q) throw "BigUnsigned::divideWithRemainder: Some two objects involved are the same"; - /*std::cout << "((( divideWithRemainder\n[ Dumps:\n*this:\n"; - dump(); - std::cout << "b:\n"; - b.dump(); - std::cout << "q:\n"; - q.dump(); - std::cout << "]\n";*/ - /* * 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. @@ -427,49 +517,58 @@ void BigUnsigned::divideWithRemainder(const BigUnsigned &b, BigUnsigned &q) { * At this point we know *this > b > 0. (Whew!) */ - /* DEBUG * - std::cout << "divideWithRemainder starting\n" - << "length of dividend: " << len - << "\nlast block of dividend: " << getBlock(0) - << "\nlength of divisor: " << b.len - << "\nlast block of divisor: " << b.getBlock(0) - << std::endl; */ - /* - * Overall method: Subtract b, shifted varying amounts to - * the left, from this, setting the bit in the quotient q - * whenever the subtraction succeeds. Eventually q will contain the entire - * quotient, and this will be left with the remainder. + * 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. - * But we don't even compute the i lowest blocks of the result, - * because they are unaffected (we shift left i places). - * */ + * 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; - Blk bHigh, temp; + Blk temp; bool borrowIn, borrowOut; /* * Make sure we have an extra zero block just past the value. - * A shifted subtraction (for example, subtracting 1 << 2 from 4) - * might stick into this block. * - * In earlier versions, `len' was not increased. But then Milan Tomic - * found out-of-bounds memory accesses. In investigating the problem, - * I got tons of warnings in this routine, which I should have expected. - * I decided to make the extra block logically part of the number so it - * would not cause confusion in the future. + * 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; // original length - len++; // increased to avoid memory management worries - allocateAndCopy(len); - blk[origLen] = 0; + Index origLen = len; // Save real length. + len++; // Increase the length. + allocateAndCopy(len); // Get the space. + blk[origLen] = 0; // Zero the extra block. - // work2 holds part of the result of a subtraction. - // (There's no work1. The name work2 is from a previous version.) - Blk *work2 = new Blk[origLen]; + // work2 holds part of the result of a subtraction; see above. + Blk *work2 = new Blk[len]; // Set preliminary length for quotient and make room q.len = origLen - b.len + 1; @@ -483,52 +582,51 @@ void BigUnsigned::divideWithRemainder(const BigUnsigned &b, BigUnsigned &q) { while (i > 0) { i--; // For each possible left-shift of b in bits... + // (Remember, N is the number of bits in a Blk.) q.blk[i] = 0; - i2 = 8 * sizeof(Blk); + i2 = N; while (i2 > 0) { i2--; /* - * Subtract b, shifted left i blocks and i2 bits, from this. - * and store the answer in work2. + * 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. + * are in many ways analogous. See especially the discussion + * of `getShiftedBlock'. */ - bHigh = 0; - for (j = 0, k = i, borrowIn = false; j < b.len; j++, k++) { - temp = blk[k] - ((b.blk[j] << i2) | bHigh); + for (j = 0, k = i, borrowIn = false; j <= b.len; j++, k++) { + temp = blk[k] - getShiftedBlock(b, j, i2); borrowOut = (temp > blk[k]); if (borrowIn) { borrowOut |= (temp == 0); temp--; } - work2[j] = temp; + // Since 2005.01.11, indices of `work2' directly match those of `blk', so use `k'. + work2[k] = temp; borrowIn = borrowOut; - bHigh = (i2 == 0) ? 0 : b.blk[j] >> (8 * sizeof(Blk) - i2); } - temp = blk[k] - bHigh; - borrowOut = (temp > blk[k]); - if (borrowIn) { - borrowOut |= (temp == 0); - temp--; - } - work2[j] = temp; - borrowIn = borrowOut; - j++; - k++; - for (; k < origLen && borrowIn; j++, k++) { + // No more extra iteration to deal with `bHigh'. + // Roll-over a borrow as necessary. + for (; k < origLen && borrowIn; k++) { borrowIn = (blk[k] == 0); - work2[j] = blk[k] - 1; + work2[k] = blk[k] - 1; } - /* If the subtraction was performed successfully (!borrowIn), set bit i2 - * in block i of the quotient, and copy the changed portion of - * work2 back to this. Otherwise, reset that bit and move on. */ + /* + * 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] |= (1 << i2); - while (j > 0) { - j--; + while (k > i) { k--; - blk[k] = work2[j]; + blk[k] = work2[k]; } } } @@ -542,22 +640,47 @@ void BigUnsigned::divideWithRemainder(const BigUnsigned &b, BigUnsigned &q) { // (Thanks to Brad Spencer for noticing my accidental omission of this!) delete [] work2; - /* DEBUG * - std::cout << "divideWithRemainder complete\n" - << "length of quotient: " << q.len - << "\nlast block of quotient: " << q.getBlock(0) - << "\nlength of remainder: " << len - << "\nlast block of remainder: " << getBlock(0) - << std::endl; - - std::cout << "[ Dumps:\n*this:\n"; - dump(); - std::cout << "b:\n"; - b.dump(); - std::cout << "q:\n"; - q.dump(); - std::cout << "]\ndivideWithRemainder )))\n"; */ } +/* +* 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 101f697..72513af 100644 --- a/BigUnsigned.hh +++ b/BigUnsigned.hh @@ -15,8 +15,9 @@ * and many math operations are defined on BigUnsigneds. * * The number is stored as a series of blocks in a -* dynamically allocated array. It is as if the numbers -* were written digit by digit in base 256 ^ sizeof(unsigned long). +* 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. @@ -32,6 +33,7 @@ class BigUnsigned : protected NumberlikeArray { enum CmpRes { less = -1, equal = 0, greater = 1 }; // Enumeration for the result of a comparison typedef unsigned long Blk; // The number block type that BigUnsigneds are built from typedef NumberlikeArray::Index Index; // (NlA) Type for the index of a block in the array + NumberlikeArray::N; // Number of bits in a Blk /* // FIELDS @@ -185,6 +187,8 @@ class BigUnsigned : protected NumberlikeArray { void operator --( ); // Prefix increment void operator --(int); // Postfix decrement + // Helper function that needs access to BigUnsigned internals + friend Blk getShiftedBlock(const BigUnsigned &num, Index x, unsigned int y); }; // NORMAL OPERATORS diff --git a/BigUnsignedInABase.cc b/BigUnsignedInABase.cc index 8852575..7745adb 100644 --- a/BigUnsignedInABase.cc +++ b/BigUnsignedInABase.cc @@ -13,7 +13,6 @@ */ #include "BigUnsignedInABase.hh" -#include namespace { unsigned int bitLen(unsigned int x) { @@ -28,9 +27,7 @@ namespace { return (a + b - 1) / b; } } - /*std::cout << "((( BigUnsigned ==> BigUnsignedInABase\n"; - std::cout << "[ Parameter BigUnsigned @ " << (void *)(NumberlikeArray *)(&x) - << ",\nresulting BigUnsignedInABase @ " << (void *)(NumberlikeArray *)(this) << "]" << std::endl;*/ + BigUnsignedInABase::BigUnsignedInABase(const BigUnsigned &x, Base base) { // Check the base @@ -41,7 +38,7 @@ BigUnsignedInABase::BigUnsignedInABase(const BigUnsigned &x, Base base) { this->base = base; // Get an upper bound on how much space we need - int maxBitLenOfX = x.getLength() * 8 * sizeof(BigUnsigned::Blk); + int maxBitLenOfX = x.getLength() * BigUnsigned::N; int minBitsPerDigit = bitLen(base) - 1; int maxDigitLenOfX = ceilingDiv(maxBitLenOfX, minBitsPerDigit); len = maxDigitLenOfX; // Another change to comply with `staying in bounds'; see `BigUnsigned::divideWithRemainder'. @@ -62,7 +59,6 @@ BigUnsignedInABase::BigUnsignedInABase(const BigUnsigned &x, Base base) { // Save the actual length. len = digitNum; - /*std::cout << "BigUnsigned ==> BigUnsignedInABase )))\n";*/ } BigUnsignedInABase::operator BigUnsigned() const { @@ -84,7 +80,9 @@ BigUnsignedInABase::BigUnsignedInABase(const std::string &s, Base base) { // This pattern is seldom seen in C++, but the analogous ``this.'' is common in Java. this->base = base; - len = s.length(); + // `s.length()' is a `size_t', while `len' is a `NumberlikeArray::Index', + // also known as an `unsigned int'. Some compilers warn without this cast. + len = Index(s.length()); allocate(len); Index digitNum, symbolNumInString; @@ -104,7 +102,6 @@ BigUnsignedInABase::BigUnsignedInABase(const std::string &s, Base base) { } BigUnsignedInABase::operator std::string() const { - //std::cout << "((( BigUnsignedInABase ==> std::string\n"; if (base > 36) throw "BigUnsignedInABase ==> std::string: The default string conversion routines use the symbol set 0-9, A-Z and therefore support only up to base 36. You tried a conversion with a base over 36; write your own string conversion routine."; if (len == 0) @@ -122,6 +119,5 @@ BigUnsignedInABase::operator std::string() const { } std::string s2(s); delete s; - //std::cout << "BigUnsignedInABase ==> std::string )))\n"; return s2; } diff --git a/NumberlikeArray.hh b/NumberlikeArray.hh index 4fe2a42..3b018a4 100644 --- a/NumberlikeArray.hh +++ b/NumberlikeArray.hh @@ -20,8 +20,8 @@ #endif /* -* A NumberlikeArray object holds a dynamically -* allocated array of Blocks. It provides certain basic +* 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. * @@ -37,56 +37,17 @@ * NumberlikeArray< whatever >::getLength; */ -/*debug*/ -#include - template class NumberlikeArray { public: typedef unsigned int Index; // Type for the index of a block in the array + static const unsigned int N; // The number of bits in a block, defined below. // FIELDS Index cap; // The current allocated capacity of this NumberlikeArray (in blocks) Index len; // The actual length of the value stored in this NumberlikeArray (in blocks) - Blk *blk2; // Dynamically allocated array of the blocks - - static Blk x; // trash that [] can return for out-of-range requests - - void dump() const { - std::cout << "Dumping NumberlikeArray @ " << (void *)(this) << '\n'; - std::cout << "Length " << (len) << ", capacity " << (cap) << '\n'; - for (unsigned int i = 0; i < len; i++) { - std::cout << "Block " << i << ":" << blk2[i] << '\n'; - } - } - - struct BoundsCheckingBlk { - const NumberlikeArray *na; - BoundsCheckingBlk(NumberlikeArray *na) { - this->na = na; - } - Blk & operator [](Index index) const { - if (index >= na->len) { - std::cout << "== Out-of-bounds access to block " << index << ". Affected NumberlikeArray: ==\n"; - na->dump(); - std::cout << "== End of dump. ==" << std::endl; - return x; - } else - return na->blk2[index]; - } // dangerous because it allows ``always writable'', but OK for now - /*const Blk & operator [](Index index) const { - if (index >= na->len) - std::cout << "OUT OF BOUNDS! Length " << (na->len) << ", accessed " << index << std::endl; - else - return na->blk[index]; - }*/ - /*operator Blk * () { - return na->blk2; - }*/ - }; - - BoundsCheckingBlk blk; + Blk *blk; // Dynamically allocated array of the blocks /* * Change made on 2005.01.06: @@ -103,8 +64,8 @@ class NumberlikeArray { */ // MANAGEMENT - NumberlikeArray(Index c) : cap(c), len(0), blk(this) { // Creates a NumberlikeArray with a capacity - blk2 = (cap > 0) ? (new Blk[cap]) : NULL; + NumberlikeArray(Index c) : cap(c), len(0) { // Creates a NumberlikeArray with a capacity + blk = (cap > 0) ? (new Blk[cap]) : NULL; } void allocate(Index c); // Ensures the array has at least the indicated capacity, maybe discarding contents void allocateAndCopy(Index c); // Ensures the array has at least the indicated capacity, preserving its contents @@ -127,14 +88,14 @@ class NumberlikeArray { * 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(this) { - blk2 = NULL; + NumberlikeArray() : cap(0), len(0) { + blk = NULL; } NumberlikeArray(const NumberlikeArray &x); // Copy constructor void operator=(const NumberlikeArray &x); // Assignment operator NumberlikeArray(const Blk *b, Index l); // Constructor from an array of blocks ~NumberlikeArray() { // Destructor - delete [] blk2; // Does nothing and causes no error if `blk' is null. + delete [] blk; // Does nothing and causes no error if `blk' is null. } // PICKING APART @@ -169,7 +130,7 @@ class NumberlikeArray { */ template -Blk NumberlikeArray::x = 0; +const unsigned int NumberlikeArray::N = 8 * sizeof(Blk); // MANAGEMENT @@ -180,10 +141,10 @@ void NumberlikeArray::allocate(Index c) { // If the requested capacity is more than the current capacity... if (c > cap) { // Delete the old number array - delete [] blk2; + delete [] blk; // Allocate the new array cap = c; - blk2 = new Blk[cap]; + blk = new Blk[cap]; } } @@ -193,10 +154,10 @@ template void NumberlikeArray::allocateAndCopy(Index c) { // If the requested capacity is more than the current capacity... if (c > cap) { - Blk *oldBlk = blk2; + Blk *oldBlk = blk; // Allocate the new number array cap = c; - blk2 = new Blk[cap]; + blk = new Blk[cap]; // Copy number blocks Index i; for (i = 0; i < len; i++) @@ -208,10 +169,10 @@ void NumberlikeArray::allocateAndCopy(Index c) { // Copy constructor template -NumberlikeArray::NumberlikeArray(const NumberlikeArray &x) : len(x.len), blk(this) { +NumberlikeArray::NumberlikeArray(const NumberlikeArray &x) : len(x.len) { // Create array cap = len; - blk2 = new Blk[cap]; + blk = new Blk[cap]; // Copy blocks Index i; for (i = 0; i < len; i++) @@ -236,9 +197,9 @@ void NumberlikeArray::operator=(const NumberlikeArray &x) { // Constructor from an array of blocks template -NumberlikeArray::NumberlikeArray(const Blk *b, Index l) : cap(l), len(l), blk(this) { +NumberlikeArray::NumberlikeArray(const Blk *b, Index l) : cap(l), len(l) { // Create array - blk2 = new Blk[cap]; + blk = new Blk[cap]; // Copy blocks Index i; for (i = 0; i < len; i++) diff --git a/README b/README index b201725..0c82f66 100644 --- a/README +++ b/README @@ -22,6 +22,14 @@ for more information and the latest version. Change Log: =========== +2005.01.11 version: +A fix to some out-of-bounds accesses reported by Milan Tomic (see the comment under `BigUnsigned::divideWithRemainder'). `BigUnsigned::multiply' and `BigUnsigned::divideWithRemainder' implementations neatened up a bit with the help of a function `getShiftedBlock'. I (finally!) introduced a constant `BigUnsigned::N', the number of bits in a `BigUnsigned::Blk', which varies depending on machine word size. In both code and comments, it replaces the much clunkier `8*sizeof(Blk)'. Numerous other small changes. + +I have inserted a significant number of new comments. Most explain unobvious aspects of the code. + +2005.01.06 version: +Some changes to the way zero-length arrays are handled by `NumberlikeArray', which fixed a memory leak reported by Milan Tomic. + 2004.12.24.2 version: I tied down a couple of loose ends involving division/modulo. I added an explanation of put-here vs. overloaded operators in the sample program; this has confused too many people. Miscellaneous other improvements. diff --git a/sample.cc b/sample.cc index a9e4d46..3779ef4 100644 --- a/sample.cc +++ b/sample.cc @@ -42,30 +42,20 @@ int main() { BigInteger c(a); // Copy a BigInteger. - std::cout << "here 0" << std::endl; - BigInteger d(-314159265); // c is -314159265. The `int' literal is converted to a BigInteger. // Ahem: that's too big to be an `int' literal (or even a `long' literal)! // Disillusion yourself now -- this won't compile. //BigInteger e(3141592653589793238462643383279); - std::cout << "here 1" << std::endl; - std::string s("3141592653589793238462643383279"); BigInteger f = easyStringToBI(s); // Ah. The string is converted to a BigInteger, and strings can be as long as you want. - std::cout << "here 2" << std::endl; - std::string s2 = easyBItoString(f); // You can convert the other way too. - std::cout << "here 3" << std::endl; - std::cout << f << std::endl; // f is stringified and send to std::cout. - std::cout << "here 4" << std::endl; - /* * Let's do some math! * @@ -99,15 +89,11 @@ int main() { std::cout << (g + h) << '\n' << (g - h) << '\n' << (g * h) << '\n' << (g / h) << '\n' << (g % h) << std::endl; - std::cout << "here 5" << std::endl; - BigInteger i(5), j(10), k; // These two lines do the same thing: k is set to a BigInteger containing 15. k = i + j; k.add(i, j); - std::cout << "here 6" << std::endl; - // Let's do some heavy lifting. std::cout << "Powers of 3" << std::endl; std::cout << "How many do you want?" << std::endl;