From b3fe29df9a21e6ade45c470b9b2632e9f75a7aaa Mon Sep 17 00:00:00 2001 From: Matt McCutchen Date: Sat, 27 Jan 2007 16:06:12 -0500 Subject: [PATCH] Old snapshot `BigIntegerLibrary-2005.01.06'; see the ChangeLog file. --- BigInteger.cc | 50 +++++++++++----------------------- BigUnsigned.cc | 63 ++++++++++++++++++++----------------------- BigUnsignedInABase.cc | 19 +++++++++---- Makefile | 13 +-------- NumberlikeArray.hh | 54 +++++++++++++++++++++++++++++++++---- README | 11 ++++---- sample.cc | 23 +++++++++------- 7 files changed, 129 insertions(+), 104 deletions(-) diff --git a/BigInteger.cc b/BigInteger.cc index 34a4e17..15173b1 100644 --- a/BigInteger.cc +++ b/BigInteger.cc @@ -57,15 +57,15 @@ BigInteger::BigInteger(const BigUnsigned &x, Sign s) : BigUnsigned(x) { * 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) { - cap = 0; - blk = new Blk[0]; - sign = zero; - len = 0; - } else { + if (x == 0) + sign = zero; // NumberlikeArray did the rest + else { cap = 1; blk = new Blk[1]; sign = positive; @@ -87,21 +87,14 @@ BigInteger::BigInteger(long x) { sign = negative; len = 1; *blk = Blk(-x); - } else { - cap = 0; - blk = new Blk[0]; - sign = zero; - len = 0; - } + } else + sign = zero; } BigInteger::BigInteger(unsigned int x) { - if (x == 0) { - cap = 0; - blk = new Blk[0]; + if (x == 0) sign = zero; - len = 0; - } else { + else { cap = 1; blk = new Blk[1]; sign = positive; @@ -123,21 +116,14 @@ BigInteger::BigInteger(int x) { sign = negative; len = 1; *blk = Blk(-x); - } else { - cap = 0; - blk = new Blk[0]; - sign = zero; - len = 0; - } + } else + sign = zero; } BigInteger::BigInteger(unsigned short x) { - if (x == 0) { - cap = 0; - blk = new Blk[0]; + if (x == 0) sign = zero; - len = 0; - } else { + else { cap = 1; blk = new Blk[1]; sign = positive; @@ -159,12 +145,8 @@ BigInteger::BigInteger(short x) { sign = negative; len = 1; *blk = Blk(-x); - } else { - cap = 0; - blk = new Blk[0]; - sign = zero; - len = 0; - } + } else + sign = zero; } // CONVERTERS diff --git a/BigUnsigned.cc b/BigUnsigned.cc index f70560a..712db98 100644 --- a/BigUnsigned.cc +++ b/BigUnsigned.cc @@ -5,7 +5,7 @@ #include "BigUnsigned.hh" -// The "management" routines that used to be here are now in NumberlikeArray.cpp. +// The "management" routines that used to be here are now in NumberlikeArray.hh. /* * The steps for construction of a BigUnsigned @@ -16,14 +16,19 @@ * 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) { - cap = 0; - blk = new Blk[0]; - len = 0; - } else { + if (x == 0) + ; // NumberlikeArray already did all the work + else { cap = 1; blk = new Blk[1]; len = 1; @@ -32,25 +37,21 @@ BigUnsigned::BigUnsigned(unsigned long x) { } BigUnsigned::BigUnsigned(long x) { - if (x == 0) { - cap = 0; - blk = new Blk[0]; - len = 0; - } else if (x > 0) { + if (x == 0) + ; + else if (x > 0) { cap = 1; blk = new Blk[1]; len = 1; blk[0] = Blk(x); } else - throw "BigUnsigned::BigUnsigned(long): Cannot construct a BigUnsigned from a negative number"; + throw "BigUnsigned::BigUnsigned(long): Cannot construct a BigUnsigned from a negative number"; } BigUnsigned::BigUnsigned(unsigned int x) { - if (x == 0) { - cap = 0; - blk = new Blk[0]; - len = 0; - } else { + if (x == 0) + ; + else { cap = 1; blk = new Blk[1]; len = 1; @@ -59,25 +60,21 @@ BigUnsigned::BigUnsigned(unsigned int x) { } BigUnsigned::BigUnsigned(int x) { - if (x == 0) { - cap = 0; - blk = new Blk[0]; - len = 0; - } else if (x > 0) { + if (x == 0) + ; + else if (x > 0) { cap = 1; blk = new Blk[1]; len = 1; blk[0] = Blk(x); } else - throw "BigUnsigned::BigUnsigned(int): Cannot construct a BigUnsigned from a negative number"; + throw "BigUnsigned::BigUnsigned(int): Cannot construct a BigUnsigned from a negative number"; } BigUnsigned::BigUnsigned(unsigned short x) { - if (x == 0) { - cap = 0; - blk = new Blk[0]; - len = 0; - } else { + if (x == 0) + ; + else { cap = 1; blk = new Blk[1]; len = 1; @@ -86,17 +83,15 @@ BigUnsigned::BigUnsigned(unsigned short x) { } BigUnsigned::BigUnsigned(short x) { - if (x == 0) { - cap = 0; - blk = new Blk[0]; - len = 0; - } else if (x > 0) { + if (x == 0) + ; + else if (x > 0) { cap = 1; blk = new Blk[1]; len = 1; blk[0] = Blk(x); } else - throw "BigUnsigned::BigUnsigned(short): Cannot construct a BigUnsigned from a negative number"; + throw "BigUnsigned::BigUnsigned(short): Cannot construct a BigUnsigned from a negative number"; } // CONVERTERS diff --git a/BigUnsignedInABase.cc b/BigUnsignedInABase.cc index b668c58..a450cf0 100644 --- a/BigUnsignedInABase.cc +++ b/BigUnsignedInABase.cc @@ -3,6 +3,15 @@ * http://mysite.verizon.net/mccutchen/bigint/ */ +/* +* 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" namespace { @@ -93,16 +102,16 @@ BigUnsignedInABase::operator std::string() const { 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) return std::string("0"); - std::string s; - s.reserve(len); + char *s = new char[len + 1]; + s[len] = '\0'; Index digitNum, symbolNumInString; for (symbolNumInString = 0; symbolNumInString < len; symbolNumInString++) { digitNum = len - 1 - symbolNumInString; Digit theDigit = blk[digitNum]; if (theDigit < 10) - s.push_back(char('0' + theDigit)); + s[symbolNumInString] = char('0' + theDigit); else - s.push_back(char('A' + theDigit - 10)); + s[symbolNumInString] = char('A' + theDigit - 10); } - return s; + return std::string(s); } diff --git a/Makefile b/Makefile index 5ad430e..3a36e94 100644 --- a/Makefile +++ b/Makefile @@ -1,18 +1,7 @@ # # Matt McCutchen's Big Integer Library +# http://mysite.verizon.net/mccutchen/bigint/ # -# Please see the project Web site at -# http://mysite.verizon.net/mccutchen/bigint/ -# for more information and the latest version. -# -# December 23, 2004 development version -# -# NEWS: -# We're now using array indexes instead of pointers. -# After having used pointers for faster speed, I decided -# that they detracted too much from the readability of -# the program and that a good optimizing compiler should -# be able to produce as efficient code. # The implicit rules we need %.tag : % diff --git a/NumberlikeArray.hh b/NumberlikeArray.hh index 10b7262..79d46df 100644 --- a/NumberlikeArray.hh +++ b/NumberlikeArray.hh @@ -3,9 +3,22 @@ * http://mysite.verizon.net/mccutchen/bigint/ */ +/* +* 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 +// An essential memory-management constant. +// I wish this were built into C++ just as it is in Java. +#ifndef NULL +#define NULL 0 +#endif + /* * A NumberlikeArray object holds a dynamically * allocated array of Blocks. It provides certain basic @@ -34,22 +47,53 @@ class NumberlikeArray { 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: + * + * 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 file. + */ // MANAGEMENT - NumberlikeArray(int, Index c) : cap(c), len(0) { // Creates a NumberlikeArray with a capacity - blk = new Blk[cap]; + 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 - NumberlikeArray() : cap(0), len(0) { // Default constructor (empty array) - blk = new Blk[0]; + /* + * 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; } 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 [] blk; + delete [] blk; // Does nothing and causes no error if `blk' is null. } // PICKING APART diff --git a/README b/README index d3503ca..b201725 100644 --- a/README +++ b/README @@ -1,8 +1,9 @@ -================================================================= -Matt McCutchen's Big Integer Library -A C++ library that does arithmetic on integers of unlimited size. -================================================================= -Version 2004.12.24.2 ++===================================================================+ +| Matt McCutchen's Big Integer Library | +| A C++ library that does arithmetic on integers of unlimited size. | ++===================================================================+ + +Version 2005.01.06. This library contains two classes, BigUnsigned and BigInteger, that represent nonnegative integers and integers, respectively. Each provides the operations listed below and possibly others: +, -, *, /, %, unary - diff --git a/sample.cc b/sample.cc index 58023a6..3779ef4 100644 --- a/sample.cc +++ b/sample.cc @@ -15,28 +15,32 @@ * GO FORTH and play with many-digit numbers! (c.f. The TeXbook.) */ -#include "BigUnsigned.hh" -#include "BigInteger.hh" -#include "BigIntegerUtils.hh" - +// Standard libraries #include #include +// For the BigInteger class itself. +#include "BigInteger.hh" + +// For the 4 routines `easy BI/BU <=> string' and `iostream' integration. +#include "BigIntegerUtils.hh" + int main() { try { BigInteger a; // a is 0 int b = 535; - a = b; // From int to BigUnsigned... + 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. Some C++ compilers need a special command-line option to compile - * code that uses throw/catch. + * 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 them. + BigInteger c(a); // Copy a BigInteger. BigInteger d(-314159265); // c is -314159265. The `int' literal is converted to a BigInteger. @@ -104,10 +108,11 @@ int main() { std::cout << "There you go. Goodbye." << std::endl; - } catch(char const* err){ + } catch(char const* err) { std::cout << "Sorry, the library threw an exception:\n" << err << std::endl; } + return 0; } -- 2.34.1