From 5ff40cf5d6e822051da902b041ae7ae8f545123e Mon Sep 17 00:00:00 2001 From: Matt McCutchen Date: Thu, 17 Jan 2008 22:15:13 -0500 Subject: [PATCH] I decided to delete whitespace from otherwise empty lines. --- BigInteger.cc | 16 ++++++++-------- BigInteger.hh | 22 +++++++++++----------- BigIntegerUtils.hh | 10 +++++----- BigUnsigned.cc | 18 +++++++++--------- BigUnsigned.hh | 36 ++++++++++++++++++------------------ BigUnsignedInABase.cc | 12 ++++++------ BigUnsignedInABase.hh | 28 ++++++++++++++-------------- NumberlikeArray.hh | 16 ++++++++-------- sample.cc | 26 +++++++++++++------------- 9 files changed, 92 insertions(+), 92 deletions(-) diff --git a/BigInteger.cc b/BigInteger.cc index ba49180..3873e15 100644 --- a/BigInteger.cc +++ b/BigInteger.cc @@ -443,7 +443,7 @@ void BigInteger::divideWithRemainder(const BigInteger &b, BigInteger &q) { divideWithRemainder(tmpB, q); return; } - + // Division by zero gives quotient 0 and remainder *this if (b.sign == zero) { q.len = 0; @@ -456,9 +456,9 @@ void BigInteger::divideWithRemainder(const BigInteger &b, BigInteger &q) { q.sign = zero; return; } - + // Here *this != 0, b != 0. - + // Do the operands have the same sign? if (sign == b.sign) { // Yes: easy case. Quotient is zero or positive. @@ -489,10 +489,10 @@ void BigInteger::divideWithRemainder(const BigInteger &b, BigInteger &q) { * Find r = (b - 1) - R and give it the desired sign. */ } - + // Divide the magnitudes. BigUnsigned::divideWithRemainder(b, q); - + if (sign != b.sign) { // More for the harder case (as described): // Increase the magnitude of the quotient by one. @@ -502,16 +502,16 @@ void BigInteger::divideWithRemainder(const BigInteger &b, BigInteger &q) { BigUnsigned::subtract(b, temp); BigUnsigned::operator --(); } - + // Sign of the remainder is always the sign of the divisor b. sign = b.sign; - + // Set signs to zero as necessary. (Thanks David Allen!) if (len == 0) sign = zero; if (q.len == 0) q.sign = zero; - + // WHEW!!! } diff --git a/BigInteger.hh b/BigInteger.hh index 7319168..1605975 100644 --- a/BigInteger.hh +++ b/BigInteger.hh @@ -26,15 +26,15 @@ */ class BigInteger : public BigUnsigned { - + // TYPES & CONSTANTS public: enum Sign { negative = -1, zero = 0, positive = 1 }; // Enumeration for the sign of a BigInteger - + // FIELDS protected: Sign sign; // The sign of this BigInteger - + // MANAGEMENT protected: BigInteger(Sign s, Index c) : BigUnsigned(0, c), sign(s) {}; // Creates a BigInteger with a sign and capacity @@ -60,7 +60,7 @@ class BigInteger : public BigUnsigned { BigInteger( short x); // Note that a BigInteger can be converted to a BigUnsigned // automatically; this takes its absolute value. - + // CONVERTERS to integral types public: operator unsigned long () const; @@ -69,12 +69,12 @@ class BigInteger : public BigUnsigned { operator int () const; operator unsigned short() const; operator short() const; - + // PICKING APART // These accessors can be used to get the pieces of the number public: Sign getSign() const; - + // COMPARISONS public: // Compares this to x like Perl's <=> @@ -88,7 +88,7 @@ class BigInteger : public BigUnsigned { bool operator <=(const BigInteger &x) const { return compareTo(x) != greater; } bool operator >=(const BigInteger &x) const { return compareTo(x) != less ; } bool operator > (const BigInteger &x) const { return compareTo(x) == greater; } - + // PUT-HERE OPERATIONS /* These store the result of the operation on the arguments into this. * a.add(b, c) is equivalent to, but faster than, a = b + c. @@ -125,7 +125,7 @@ class BigInteger : public BigUnsigned { // redefined for BigIntegers. Calling one of these on // a BigInteger will convert it to a BigUnsigned, // which takes its absolute value. - + // NORMAL OPERATORS // These perform the operation on this (to the left of the operator) // and x (to the right of the operator) and return a new BigInteger with the result. @@ -136,7 +136,7 @@ class BigInteger : public BigUnsigned { BigInteger operator /(const BigInteger &x) const; // Division BigInteger operator %(const BigInteger &x) const; // Modular reduction BigInteger operator -( ) const; // Negative - + // ASSIGNMENT OPERATORS // These perform the operation on this and x, storing the result into this. public: @@ -146,7 +146,7 @@ class BigInteger : public BigUnsigned { void operator /=(const BigInteger &x); // Division void operator %=(const BigInteger &x); // Modular reduction void flipSign(); // Negative - + // INCREMENT/DECREMENT OPERATORS // These increase or decrease the number by 1. To discourage side effects, // these do not return *this, so prefix and postfix behave the same. @@ -155,7 +155,7 @@ class BigInteger : public BigUnsigned { void operator ++(int); // Postfix decrement void operator --( ); // Prefix increment void operator --(int); // Postfix decrement - + }; // PICKING APART diff --git a/BigIntegerUtils.hh b/BigIntegerUtils.hh index 118179b..dfbdee3 100644 --- a/BigIntegerUtils.hh +++ b/BigIntegerUtils.hh @@ -56,12 +56,12 @@ BigInteger easyDataToBI(const T* data, BigInteger::Index length, BigInteger::Sig unsigned int pieceSizeInBits = 8 * sizeof(T); unsigned int piecesPerBlock = sizeof(BigInteger::Blk) / sizeof(T); unsigned int numBlocks = (length + piecesPerBlock - 1) / piecesPerBlock; - + // Allocate our block array BigInteger::Blk *blocks = new BigInteger::Blk[numBlocks]; - + BigInteger::Index blockNum, pieceNum, pieceNumHere; - + // Convert for (blockNum = 0, pieceNum = 0; blockNum < numBlocks; blockNum++) { BigInteger::Blk curBlock = 0; @@ -70,10 +70,10 @@ BigInteger easyDataToBI(const T* data, BigInteger::Index length, BigInteger::Sig curBlock |= (BigInteger::Blk(data[pieceNum]) << (pieceSizeInBits * pieceNumHere)); blocks[blockNum] = curBlock; } - + // Create the BigInteger. BigInteger x(blocks, numBlocks, sign); - + delete blocks; return x; } diff --git a/BigUnsigned.cc b/BigUnsigned.cc index 3c9a1d7..f6a925c 100644 --- a/BigUnsigned.cc +++ b/BigUnsigned.cc @@ -527,7 +527,7 @@ void BigUnsigned::divideWithRemainder(const BigUnsigned &b, BigUnsigned &q) { divideWithRemainder(tmpB, q); return; } - + /* * Note that the mathematical definition of mod (I'm trusting Knuth) is somewhat * different from the way the normal C++ % operator behaves in the case of division by 0. @@ -541,7 +541,7 @@ void BigUnsigned::divideWithRemainder(const BigUnsigned &b, BigUnsigned &q) { 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). @@ -550,11 +550,11 @@ void BigUnsigned::divideWithRemainder(const BigUnsigned &b, BigUnsigned &q) { q.len = 0; return; } - + /* * At this point we know *this > b > 0. (Whew!) */ - + /* * Overall method: * @@ -586,7 +586,7 @@ void BigUnsigned::divideWithRemainder(const BigUnsigned &b, BigUnsigned &q) { unsigned int i2; Blk temp; bool borrowIn, borrowOut; - + /* * Make sure we have an extra zero block just past the value. * @@ -605,17 +605,17 @@ void BigUnsigned::divideWithRemainder(const BigUnsigned &b, BigUnsigned &q) { allocateAndCopy(len + 1); // Get the space. len++; // Increase the length. blk[origLen] = 0; // Zero the extra block. - + // work2 holds part of the result of a subtraction; see above. Blk *work2 = new Blk[len]; - + // Set preliminary length for quotient and make room q.len = origLen - b.len + 1; q.allocate(q.len); // Zero out the quotient for (i = 0; i < q.len; i++) q.blk[i] = 0; - + // For each possible left-shift of b in blocks... i = q.len; while (i > 0) { @@ -678,7 +678,7 @@ void BigUnsigned::divideWithRemainder(const BigUnsigned &b, BigUnsigned &q) { // Deallocate temporary array. // (Thanks to Brad Spencer for noticing my accidental omission of this!) delete [] work2; - + } /* * The out-of-bounds accesses story: diff --git a/BigUnsigned.hh b/BigUnsigned.hh index 61fcb90..50fca2f 100644 --- a/BigUnsigned.hh +++ b/BigUnsigned.hh @@ -26,14 +26,14 @@ */ class BigUnsigned : protected NumberlikeArray { - + // TYPES & CONSTANTS public: enum CmpRes { less = -1, equal = 0, greater = 1 }; // Enumeration for the result of a comparison typedef unsigned long Blk; // The number block type that BigUnsigneds are built from typedef NumberlikeArray::Index Index; // (NlA) Type for the index of a block in the array NumberlikeArray::N; // Number of bits in a Blk - + /* // FIELDS protected: @@ -41,34 +41,34 @@ class BigUnsigned : protected NumberlikeArray { Index len; // (NlA) The actual length of the number stored in this BigUnsigned (in blocks) Blk *blk; // (NlA) Dynamically allocated array of the number blocks */ - + // MANAGEMENT protected: // These members generally defer to those in NumberlikeArray, possibly with slight changes. // It might be nice if one could request that constructors be inherited in C++. - + BigUnsigned(int, Index c) : NumberlikeArray(0, c) {} // Creates a BigUnsigned with a capacity - + void zapLeadingZeros() { // Decreases len to eliminate leading zeros while (len > 0 && blk[len - 1] == 0) len--; } - + //void allocate(Index c); // (NlA) Ensures the number array has at least the indicated capacity, maybe discarding contents //void allocateAndCopy(Index c); // (NlA) Ensures the number array has at least the indicated capacity, preserving its contents - + public: BigUnsigned() : NumberlikeArray() {} // Default constructor (value is 0) BigUnsigned(const BigUnsigned &x) : NumberlikeArray(x) {} // Copy constructor - + void operator=(const BigUnsigned &x) { // Assignment operator NumberlikeArray::operator =(x); } - + BigUnsigned(const Blk *b, Index l) : NumberlikeArray(b, l) { // Constructor from an array of blocks zapLeadingZeros(); } - + // Constructors from integral types BigUnsigned(unsigned long x); BigUnsigned( long x); @@ -77,7 +77,7 @@ class BigUnsigned : protected NumberlikeArray { BigUnsigned(unsigned short x); BigUnsigned( short x); ~BigUnsigned() {} // Destructor - + // CONVERTERS to integral types public: operator unsigned long () const; @@ -86,7 +86,7 @@ class BigUnsigned : protected NumberlikeArray { operator int () const; operator unsigned short() const; operator short() const; - + // PICKING APART // These accessors can be used to get the pieces of the number public: @@ -97,7 +97,7 @@ class BigUnsigned : protected NumberlikeArray { Blk getBlock(Index i) const { return i >= len ? 0 : blk[i]; } // Note how we replace one level of abstraction with another. Isn't that neat? bool isZero() const { return NumberlikeArray::isEmpty(); } // Often convenient for loops - + // COMPARISONS public: // Compares this to x like Perl's <=> @@ -154,7 +154,7 @@ class BigUnsigned : protected NumberlikeArray { * a.add(a, b); // ``Aliased'' calls now do the right thing using a * // temporary copy, but see note on divideWithRemainder. */ - + // PUT-HERE OPERATIONS public: /* These 3: Two read-only operands as arguments. Result left in *this. */ @@ -192,7 +192,7 @@ class BigUnsigned : protected NumberlikeArray { void bitXor(const BigUnsigned &a, const BigUnsigned &b); // Bitwise XOR void bitShiftLeft(const BigUnsigned &a, unsigned int b); // Bitwise left shift void bitShiftRight(const BigUnsigned &a, unsigned int b); // Bitwise right shift - + // NORMAL OPERATORS // These perform the operation on this (to the left of the operator) // and x (to the right of the operator) and return a new BigUnsigned with the result. @@ -210,7 +210,7 @@ class BigUnsigned : protected NumberlikeArray { // Additional operators in an attempt to avoid overloading tangles. BigUnsigned operator <<(int b) const; BigUnsigned operator >>(int b) const; - + // ASSIGNMENT OPERATORS // These perform the operation on this and x, storing the result into this. public: @@ -227,7 +227,7 @@ class BigUnsigned : protected NumberlikeArray { // Additional operators in an attempt to avoid overloading tangles. void operator <<=(int b); void operator >>=(int b); - + // INCREMENT/DECREMENT OPERATORS // These increase or decrease the number by 1. To discourage side effects, // these do not return *this, so prefix and postfix behave the same. @@ -236,7 +236,7 @@ class BigUnsigned : protected NumberlikeArray { void operator ++(int); // Postfix decrement void operator --( ); // Prefix increment void operator --(int); // Postfix decrement - + // Helper function that needs access to BigUnsigned internals friend Blk getShiftedBlock(const BigUnsigned &num, Index x, unsigned int y); }; diff --git a/BigUnsignedInABase.cc b/BigUnsignedInABase.cc index 4692a0a..b423ca2 100644 --- a/BigUnsignedInABase.cc +++ b/BigUnsignedInABase.cc @@ -35,17 +35,17 @@ BigUnsignedInABase::BigUnsignedInABase(const BigUnsigned &x, Base base) { // Save the base. // This pattern is seldom seen in C++, but the analogous ``this.'' is common in Java. this->base = base; - + // Get an upper bound on how much space we need int maxBitLenOfX = x.getLength() * BigUnsigned::N; int minBitsPerDigit = bitLen(base) - 1; int maxDigitLenOfX = ceilingDiv(maxBitLenOfX, minBitsPerDigit); len = maxDigitLenOfX; // Another change to comply with `staying in bounds'; see `BigUnsigned::divideWithRemainder'. allocate(len); // Get the space - + BigUnsigned x2(x), buBase(base); Index digitNum = 0; - + while (!x2.isZero()) { // Get last digit. This is like `lastDigit = x2 % buBase, x2 /= buBase'. BigUnsigned lastDigit(x2); @@ -55,7 +55,7 @@ BigUnsignedInABase::BigUnsignedInABase(const BigUnsigned &x, Base base) { // Move on. We can't run out of room: we figured it out above. digitNum++; } - + // Save the actual length. len = digitNum; } @@ -78,12 +78,12 @@ BigUnsignedInABase::BigUnsignedInABase(const std::string &s, Base base) { // Save the base. // This pattern is seldom seen in C++, but the analogous ``this.'' is common in Java. this->base = base; - + // `s.length()' is a `size_t', while `len' is a `NumberlikeArray::Index', // also known as an `unsigned int'. Some compilers warn without this cast. len = Index(s.length()); allocate(len); - + Index digitNum, symbolNumInString; for (digitNum = 0; digitNum < len; digitNum++) { symbolNumInString = len - 1 - digitNum; diff --git a/BigUnsignedInABase.hh b/BigUnsignedInABase.hh index 4096907..3712907 100644 --- a/BigUnsignedInABase.hh +++ b/BigUnsignedInABase.hh @@ -37,48 +37,48 @@ */ class BigUnsignedInABase : protected NumberlikeArray { - + // TYPES public: typedef unsigned short Digit; // The digit type that BigUnsignedInABases are built from typedef Digit Base; - + // FIELDS protected: Base base; // The base of this BigUnsignedInABase - + // MANAGEMENT protected: // These members generally defer to those in NumberlikeArray, possibly with slight changes. // It might be nice if one could request that constructors be inherited in C++. - + BigUnsignedInABase(int, Index c) : NumberlikeArray(0, c) {} // Creates a BigUnsignedInABase with a capacity - + void zapLeadingZeros() { // Decreases len to eliminate leading zeros while (len > 0 && blk[len - 1] == 0) len--; } - + //void allocate(Index c); // (NlA) Ensures the number array has at least the indicated capacity, maybe discarding contents //void allocateAndCopy(Index c); // (NlA) Ensures the number array has at least the indicated capacity, preserving its contents - + public: BigUnsignedInABase() : NumberlikeArray(), base(2) {} // Default constructor (value is 0 in base 2) BigUnsignedInABase(const BigUnsignedInABase &x) : NumberlikeArray(x), base(x.base) {} // Copy constructor - + void operator =(const BigUnsignedInABase &x) { // Assignment operator NumberlikeArray::operator =(x); base = x.base; } - + BigUnsignedInABase(const Digit *d, Index l) : NumberlikeArray(d, l) { // Constructor from an array of digits zapLeadingZeros(); } - + // LINKS TO BIGUNSIGNED BigUnsignedInABase(const BigUnsigned &x, Base base); operator BigUnsigned() const; - + /* LINKS TO STRINGS * * These use the symbols ``0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ'' to represent @@ -97,7 +97,7 @@ class BigUnsignedInABase : protected NumberlikeArray { */ operator std::string() const; BigUnsignedInABase(const std::string &s, Base base); - + // PICKING APART // These accessors can be used to get the pieces of the number public: @@ -109,7 +109,7 @@ class BigUnsignedInABase : protected NumberlikeArray { Digit getDigit(Index i) const { return i >= len ? 0 : blk[i]; } // Note how we replace one level of abstraction with another. bool isZero() const { return NumberlikeArray::isEmpty(); } // Often convenient for loops - + // EQUALITY TEST public: // Equality test @@ -117,7 +117,7 @@ class BigUnsignedInABase : protected NumberlikeArray { return base == x.base && NumberlikeArray::operator ==(x); } bool operator !=(const BigUnsignedInABase &x) const { return !operator ==(x); } - + }; #endif diff --git a/NumberlikeArray.hh b/NumberlikeArray.hh index ab0aae0..d884d37 100644 --- a/NumberlikeArray.hh +++ b/NumberlikeArray.hh @@ -39,15 +39,15 @@ 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 *blk; // Dynamically allocated array of the blocks - + /* * Change made on 2005.01.06: * @@ -61,14 +61,14 @@ class NumberlikeArray { * This is a great convenience because the only code that need be changed * is the array allocation code. All other code will still work fine. */ - + // MANAGEMENT NumberlikeArray(Index c) : cap(c), len(0) { // Creates a NumberlikeArray with a capacity blk = (cap > 0) ? (new Blk[cap]) : NULL; } void allocate(Index c); // Ensures the array has at least the indicated capacity, maybe discarding contents void allocateAndCopy(Index c); // Ensures the array has at least the indicated capacity, preserving its contents - + /* * Default constructor. * @@ -96,20 +96,20 @@ class NumberlikeArray { ~NumberlikeArray() { // Destructor delete [] blk; // Does nothing and causes no error if `blk' is null. } - + // PICKING APART // These accessors can be used to get the pieces of the value Index getCapacity() const { return cap; } Index getLength() const { return len; } Blk getBlock(Index i) const { return blk[i]; }; bool isEmpty() const { return len == 0; } - + // Equality comparison: checks if arrays have same length and matching values // Derived classes may wish to override these if differing arrays can // sometimes be considered equivalent. bool operator ==(const NumberlikeArray &x) const; bool operator !=(const NumberlikeArray &x) const { return !operator ==(x); } - + }; /* diff --git a/sample.cc b/sample.cc index f52a7e1..58e5a42 100644 --- a/sample.cc +++ b/sample.cc @@ -19,7 +19,7 @@ int main() { try { BigInteger a; // a is 0 int b = 535; - + a = b; // From int to BigInteger... b = a; // ...and back, no casts required! /* @@ -31,27 +31,27 @@ int main() { * a special command-line option to compile code that uses * exceptions. */ - + BigInteger c(a); // Copy a BigInteger. - + // d is -314159265. The `int' literal is converted to a // BigInteger. BigInteger d(-314159265); - + // This won't compile because the number is too big to be an // integer literal. //BigInteger e(3141592653589793238462643383279); - + // Instead you can convert the number from a string. std::string s("3141592653589793238462643383279"); BigInteger f = easyStringToBI(s); - + // You can convert the other way too. std::string s2 = easyBItoString(f); - + // f is stringified and send to std::cout. std::cout << f << std::endl; - + /* * Let's do some math! * @@ -65,14 +65,14 @@ int main() { // All five ``return-by-value'' arithmetic operators. std::cout << (g + h) << '\n' << (g - h) << '\n' << (g * h) << '\n' << (g / h) << '\n' << (g % h) << std::endl; - + BigUnsigned i(0xFF0000FF), j(0x0000FFFF); // All five ``return-by-value'' bitwise operators. std::cout.flags(std::ios::hex | std::ios::showbase); std::cout << (i & j) << '\n' << (i | j) << '\n' << (i ^ j) << '\n' << (j << 21) << '\n' << (j >> 10) << '\n'; std::cout.flags(std::ios::dec); - + // Let's do some heavy lifting and calculate powers of 314. int maxPower = 10; BigUnsigned x(1), big314(314); @@ -80,18 +80,18 @@ int main() { std::cout << "314^" << power << " = " << x << std::endl; x *= big314; // A BigInteger assignment operator } - + /* * If you want to experiment with the library, * you can add your own test code here. */ // std::cout << "Beginning of custom test code:" << std::endl; - + } catch(char const* err) { std::cout << "The library threw an exception:\n" << err << std::endl; } - + return 0; } -- 2.34.1