* 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;
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;
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;
sign = negative;
len = 1;
*blk = Blk(-x);
- } else {
- cap = 0;
- blk = new Blk[0];
- sign = zero;
- len = 0;
- }
+ } else
+ sign = zero;
}
// CONVERTERS
#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
* 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;
}
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;
}
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;
}
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
* 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 {
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);
}
#
# 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 : %
* 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<Block> object holds a dynamically
* allocated array of Blocks. It provides certain basic
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<Blk> &x); // Copy constructor
void operator=(const NumberlikeArray<Blk> &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
-=================================================================
-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 -
* GO FORTH and play with many-digit numbers! (c.f. The TeXbook.)
*/
-#include "BigUnsigned.hh"
-#include "BigInteger.hh"
-#include "BigIntegerUtils.hh"
-
+// Standard libraries
#include <string>
#include <iostream>
+// 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.
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;
}
Matt McCutchen's Web Site / bigint / bigint.git / commitdiff