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);
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);
sign = zero;
else {
cap = 1;
- blk2 = new Blk[1];
+ blk = new Blk[1];
sign = positive;
len = 1;
blk[0] = Blk(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);
sign = zero;
else {
cap = 1;
- blk2 = new Blk[1];
+ blk = new Blk[1];
sign = positive;
len = 1;
blk[0] = Blk(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);
--- /dev/null
+/*
+* Matt McCutchen's Big Integer Library
+* http://mysite.verizon.net/mccutchen/bigint/
+*/
+
+// This header file includes all the other header files.
+
+#include "NumberlikeArray.hh"
+#include "BigUnsigned.hh"
+#include "BigInteger.hh"
+#include "BigUnsignedInABase.hh"
+#include "BigIntegerUtils.hh"
BigUnsigned easyStringToBU(const std::string &s);
BigInteger easyStringToBI(const std::string &s);
+// Creates a BigInteger from data such as `char's; read below for details.
+template <class T>
+BigInteger easyDataToBI(const T* data, BigInteger::Index length, BigInteger::Sign sign);
+
// Outputs x to os, obeying the flags `dec', `hex', `bin', and `showbase'.
std::ostream &operator <<(std::ostream &os, const BigUnsigned &x);
// My somewhat arbitrary policy: a negative sign comes before a base indicator (like -0xFF).
std::ostream &operator <<(std::ostream &os, const BigInteger &x);
+/*
+* =================================
+* 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.
+*/
+template <class T>
+BigInteger easyDataToBI(const T* data, BigInteger::Index length, BigInteger::Sign sign) {
+ // really ceiling(numBytes / sizeof(BigInteger::Blk))
+ unsigned int pieceSizeInBits = 8 * sizeof(T);
+ unsigned int piecesPerBlock = sizeof(BigInteger::Blk) / sizeof(T);
+ unsigned int numBlocks = (length + piecesPerBlock - 1) / piecesPerBlock;
+ std::cout << pieceSizeInBits << ' ' << piecesPerBlock << ' ' << numBlocks << std::endl;
+
+ // Allocate our block array
+ BigInteger::Blk *blocks = new BigInteger::Blk[numBlocks];
+
+ BigInteger::Index blockNum, pieceNum, pieceNumHere;
+
+ // Convert
+ for (BigInteger::Index blockNum = 0, pieceNum = 0; blockNum < numBlocks; blockNum++) {
+ BigInteger::Blk curBlock = 0;
+ for (unsigned int pieceNumHere = 0; pieceNumHere < piecesPerBlock && pieceNum < length;
+ pieceNumHere++, pieceNum++)
+ curBlock |= (BigInteger::Blk(data[pieceNum]) << (pieceSizeInBits * pieceNumHere));
+ blocks[blockNum] = curBlock;
+ std::cout << curBlock << std::endl;
+ }
+
+ // Create the BigInteger.
+ BigInteger x(blocks, numBlocks, sign);
+
+ delete blocks;
+ return x;
+}
+
#endif
* 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'.
*/
; // NumberlikeArray already did all the work
else {
cap = 1;
- blk2 = new Blk[1];
+ blk = new Blk[1];
len = 1;
blk[0] = Blk(x);
}
;
else if (x > 0) {
cap = 1;
- blk2 = new Blk[1];
+ blk = new Blk[1];
len = 1;
blk[0] = Blk(x);
} else
;
else {
cap = 1;
- blk2 = new Blk[1];
+ blk = new Blk[1];
len = 1;
blk[0] = Blk(x);
}
;
else if (x > 0) {
cap = 1;
- blk2 = new Blk[1];
+ blk = new Blk[1];
len = 1;
blk[0] = Blk(x);
} else
;
else {
cap = 1;
- blk2 = new Blk[1];
+ blk = new Blk[1];
len = 1;
blk[0] = Blk(x);
}
;
else if (x > 0) {
cap = 1;
- blk2 = new Blk[1];
+ blk = new Blk[1];
len = 1;
blk[0] = Blk(x);
} else
bool operator <=(const BigUnsigned &x) const { return compareTo(x) != greater; }
bool operator >=(const BigUnsigned &x) const { return compareTo(x) != less ; }
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); // Unsafe ``aliased'' call; causes a runtime error.
+ */
// 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.
- * Calls like a.operation(a, b) are unsafe and not allowed. */
public:
- // Easy 3
- void add (const BigUnsigned &a, const BigUnsigned &b); // Addition
- void subtract (const BigUnsigned &a, const BigUnsigned &b); // Subtraction
- void multiply (const BigUnsigned &a, const BigUnsigned &b); // Multiplication
+ /* These 3: Two read-only operands as arguments. Result left in *this. */
+ void add(const BigUnsigned &a, const BigUnsigned &b); // Addition
+ 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 %,
*/
void divideWithRemainder(const BigUnsigned &b, BigUnsigned &q);
void divide(const BigUnsigned &a, const BigUnsigned &b) {
- // Division, deprecated and provided for compatibility
+ // Division, deprecated and provided for backward compatibility
BigUnsigned a2(a);
a2.divideWithRemainder(b, *this);
// quotient now in *this
// don't care about remainder left in a2
}
void modulo(const BigUnsigned &a, const BigUnsigned &b) {
- // Modular reduction, deprecated and provided for compatibility
+ // Modular reduction, deprecated and provided for backward compatibility
*this = a;
BigUnsigned q;
divideWithRemainder(b, q);
// remainder now in *this
// don't care about quotient left in q
}
- // Bitwise
- void bitAnd (const BigUnsigned &a, const BigUnsigned &b); // Bitwise AND
- void bitOr (const BigUnsigned &a, const BigUnsigned &b); // Bitwise OR
- void bitXor (const BigUnsigned &a, const BigUnsigned &b); // Bitwise XOR
+ // Bitwise operations. Two read-only operands as arguments. Result left in *this.
+ // These are not provided for BigIntegers; I think that using them on BigIntegers
+ // will discard the sign first.
+ void bitAnd(const BigUnsigned &a, const BigUnsigned &b); // Bitwise AND
+ void bitOr(const BigUnsigned &a, const BigUnsigned &b); // Bitwise OR
+ void bitXor(const BigUnsigned &a, const BigUnsigned &b); // Bitwise XOR
// These functions are declared but not defined. (Sorry.)
// Trying to call either will result in a link-time error.
- void bitShiftLeft (const BigUnsigned &a, unsigned int b); // Bitwise left shift
+ void bitShiftLeft(const BigUnsigned &a, unsigned int b); // Bitwise left shift
void bitShiftRight(const BigUnsigned &a, unsigned int b); // Bitwise right shift
// NORMAL OPERATORS
*/
#include "BigUnsignedInABase.hh"
-#include <iostream>
namespace {
unsigned int bitLen(unsigned int x) {
return (a + b - 1) / b;
}
}
- /*std::cout << "((( BigUnsigned ==> BigUnsignedInABase\n";
- std::cout << "[ Parameter BigUnsigned @ " << (void *)(NumberlikeArray<BigUnsigned::Blk> *)(&x)
- << ",\nresulting BigUnsignedInABase @ " << (void *)(NumberlikeArray<Digit> *)(this) << "]" << std::endl;*/
+
BigUnsignedInABase::BigUnsignedInABase(const BigUnsigned &x, Base base) {
// Check the base
// Save the actual length.
len = digitNum;
- /*std::cout << "BigUnsigned ==> BigUnsignedInABase )))\n";*/
}
BigUnsignedInABase::operator BigUnsigned() const {
// 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;
}
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)
}
std::string s2(s);
delete s;
- //std::cout << "BigUnsignedInABase ==> std::string )))\n";
return s2;
}
--- /dev/null
+=====================================================================
+Matt McCutchen's Big Integer Library
+http://mysite.verizon.net/mccutchen/bigint/
+
+Change Log
+==========
+These entries tell you what was added, fixed, or improved in each version as compared to the previous one. In case you haven't noticed, a version number roughly corresponds to the release date of that version in `YYYY.MM.DD[.N]' format, where `.N' goes `.2', `.3', etc. if there are multiple versions on the same day.
+
+2005.01.11
+----------
+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
+----------
+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
+------------
+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.
+
+I believe that, at this point, the Big Integer Library makes no assumptions about the word size of the machine it is using. `BigUnsigned::Blk' is always an `unsigned long', whatever that may be, and its size is computed with `sizeof' when necessary. However, just in case, I would be interested to have someone test the library on a non-32-bit machine to see if it works.
+
+2004.12.24
+----------
+This is a _major_ upgrade to the library. Among the things that have changed:
+
+I wrote the original version of the library, particularly the four ``classical algorithms'' in `BigUnsigned.cc', using array indexing. Then I rewrote it to use pointers because I thought that would be faster. But recently, I revisited the code in `BigUnsigned.cc' and found that I could not begin to understand what it was doing.
+
+I have decided that the drawbacks of pointers, increased coding difficulty and reduced code readability, far outweigh their speed benefits. Plus, any modern optimizing compiler should produce fast code either way. Therefore, I rewrote the library to use array indexing again. (Thank goodness for regular-expression find-and-replace. It saved me a lot of time.)
+
+The put-here operations `divide' and `modulo' of each of `BigUnsigned' and `BigInteger' have been supplanted by a single operation `divideWithRemainder'. Read the profuse comments for more information on its exact behavior.
+
+There is a new class `BigUnsignedInABase' that is like `BigUnsigned' but uses a user-specified, small base instead of `256 ^ sizeof(unsigned long)'. Much of the code common to the two has been factored out into `NumberlikeArray'.
+
+`BigUnsignedInABase' facilitates conversion between `BigUnsigned's and digit-by-digit string representations using `std::string'. Convenience routines to do this conversion are in `BigIntegerUtils.hh'. `iostream' compatibility has been improved.
+
+I would like to thank Chris Morbitzer for the e-mail message that catalyzed this major upgrade. He wanted a way to convert a string to a BigInteger. One thing just led to another, roughly in reverse order from how they are listed here.
+
+2004.1216
+---------
+Brad Spencer pointed out a memory leak in `BigUnsigned::divide'. It is fixed in the December 16, 2004 version.
+
+2004.1205
+---------
+After months of inactivity, I fixed a bug in the `BigInteger' division routine; thanks to David Allen for reporting the bug. I also added simple routines for decimal output to `std::ostream's, and there is a demo that prints out powers of 3.
+
+=====================================================================
\ No newline at end of file
g++ -c -O -Wall -Wextra -pedantic $<
# Default target
-library : NumberlikeArray.hh.tag BigUnsigned.o BigInteger.o BigUnsignedInABase.o BigIntegerUtils.o
+all : library sample
-# Extra `include' dependencies
+library : BigUnsigned.o BigInteger.o BigUnsignedInABase.o BigIntegerUtils.o
+
+# Extra dependencies from `#include'
BigUnsigned.hh.tag : NumberlikeArray.hh.tag
BigUnsigned.o : BigUnsigned.hh.tag
BigInteger.hh.tag : BigUnsigned.hh.tag
clean :
rm -f *.tag *.o sample
-# The ``.tag'' mechanism allows for proper recompilation when a header file
+# The `.tag' mechanism allows for proper recompilation when a header file
# changes, considering that some header files may include others.
#
# If a header file X includes other header
* NumberlikeArray< whatever >::getLength;
*/
-/*debug*/
-#include <iostream>
-
template <class Blk>
class NumberlikeArray {
public:
// 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:
*/
// 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
* 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<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 [] 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
};
/*
+* =================================
* BELOW THIS POINT are template definitions; above are declarations.
*
* Definitions would ordinarily belong in a file NumberlikeArray.cc so that they would
* so other files including NumberlikeArray will be able to generate real definitions.
*/
-template <class Blk>
-Blk NumberlikeArray<Blk>::x = 0;
-
template <class Blk>
const unsigned int NumberlikeArray<Blk>::N = 8 * sizeof(Blk);
// 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];
}
}
void NumberlikeArray<Blk>::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++)
// Copy constructor
template <class Blk>
-NumberlikeArray<Blk>::NumberlikeArray(const NumberlikeArray<Blk> &x) : len(x.len), blk(this) {
+NumberlikeArray<Blk>::NumberlikeArray(const NumberlikeArray<Blk> &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++)
// Constructor from an array of blocks
template <class Blk>
-NumberlikeArray<Blk>::NumberlikeArray(const Blk *b, Index l) : cap(l), len(l), blk(this) {
+NumberlikeArray<Blk>::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++)
+===================================================================+
-| Matt McCutchen's Big Integer Library |
+| Big Integer Library |
| A C++ library that does arithmetic on integers of unlimited size. |
+| Version 2005.01.16 |
++-------------------------------------------------------------------+
+| By Matt McCutchen |
+| E-mail: hashproduct@verizon.net |
+| Project Web site: http://mysite.verizon.net/mccutchen/bigint/ |
+===================================================================+
-Version 2005.01.06.
+What the Big Integer Library provides
+=====================================
+This library contains two classes, BigUnsigned and BigInteger, that represent nonnegative integers and integers, respectively, of size limited only by your computer's memory. Their capabilities include these operators:
+ Math: + - * / % & | ^ unary-
+ Assignment: = += -= *= /= %= &= |= ^= ++ --
+ Comparison: == != < <= > >=
+In the works are the << and >> operators, integer algorithms like `gcd', and possibly a working implementation of RSA using the library.
-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 -
-+=, -=, *=, /=, %=, ++, --
-==, !=, <, <=, >, >=
-&, |, ^
+Using the features of the library
+=================================
+The file `sample.cc' explains and demonstrates the most important features of the library. I recommend that you read `sample.cc' and then run the sample program it contains. If you want to do something not shown in `sample.cc' or want more detail, read the actual header and source files, which are extensively commented.
-To get started using this library, look at the code in `sample.cc'. Type `make sample' to compile the sample program in `sample.cc' so you can see what it does.
+Compiling programs with the library
+===================================
+The library consists of a folder full of header files (`.hh') and source files (`.cc'). `#include' header files and compile with source files as necessary for your own programs. For those who use `make', a `Makefile' is included that compiles the source code to object files (`.o') and compiles the sample program.
-This library includes a makefile. To compile it, just type `make'; you'll get some `.o' files. Include `.hh' files and link with `.o' files as necessary for your programming projects.
+Bugs
+====
+The library has been tested by myself and others but is by no means bug-free. The programs you write using the library will be the best test of its correctness. I urge you to report any problems that you find, whether they come in the form of compiling trouble, mathematically inaccurate results, or runtime memory-management bloopers (which, since I use Java, are altogether too common in my C++).
-Please see the project Web site at
- http://mysite.verizon.net/mccutchen/bigint/
-for more information and the latest version.
+Keep in touch
+=============
+Feel free to e-mail me at `hashproduct@verizon.net' to report bugs or request features. When I fix the bug or add the feature, you will generally be credited by name in the source code and/or the Change Log unless you request otherwise. I am also curious as to what uses you find for the library. If you would like an e-mail whenever a new version of the library is released, e-mail me to join my informal mailing list. New versions of the library will be available at the project Web site at `http://mysite.verizon.net/mccutchen/bigint/'.
-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.
-
-I believe that, at this point, the Big Integer Library makes no assumptions about the word size of the machine it is using. `BigUnsigned::Blk' is always an `unsigned long', whatever that may be, and its size is computed with `sizeof' when necessary. However, just in case, I would be interested to have someone test the library on a non-32-bit machine to see if it works.
-
-2004.12.24 version:
-This is a _major_ upgrade to the library. Among the things that have changed:
-
-I wrote the original version of the library, particularly the four ``classical algorithms'' in `BigUnsigned.cc', using array indexing. Then I rewrote it to use pointers because I thought that would be faster. But recently, I revisited the code in `BigUnsigned.cc' and found that I could not begin to understand what it was doing.
-
-I have decided that the drawbacks of pointers, increased coding difficulty and reduced code readability, far outweigh their speed benefits. Plus, any modern optimizing compiler should produce fast code either way. Therefore, I rewrote the library to use array indexing again. (Thank goodness for regular-expression find-and-replace. It saved me a lot of time.)
-
-The put-here operations `divide' and `modulo' of each of `BigUnsigned' and `BigInteger' have been supplanted by a single operation `divideWithRemainder'. Read the profuse comments for more information on its exact behavior.
-
-There is a new class `BigUnsignedInABase' that is like `BigUnsigned' but uses a user-specified, small base instead of `256 ^ sizeof(unsigned long)'. Much of the code common to the two has been factored out into `NumberlikeArray'.
-
-`BigUnsignedInABase' facilitates conversion between `BigUnsigned's and digit-by-digit string representations using `std::string'. Convenience routines to do this conversion are in `BigIntegerUtils.hh'. `iostream' compatibility has been improved.
-
-I would like to thank Chris Morbitzer for the e-mail message that catalyzed this major upgrade. He wanted a way to convert a string to a BigInteger. One thing just led to another, roughly in reverse order from how they are listed here.
-
-2004.1216 version:
-Brad Spencer pointed out a memory leak in `BigUnsigned::divide'. It is fixed in the December 16, 2004 version.
-
-2004.1205 version:
-After months of inactivity, I fixed a bug in the `BigInteger' division routine; thanks to David Allen for reporting the bug. I also added simple routines for decimal output to `std::ostream's, and there is a demo that prints out powers of 3.
-
-===================
\ No newline at end of file
+=====================================================================
\ No newline at end of file
*/
/*
-* This sample file demonstrates the most important features of the Big Integer Library.
+* This sample program demonstrates the most important features of the Big Integer Library.
+* To get started quickly, read the code and explanations below. Then try the program out.
*
-* To get started quickly with the library, imitate the code in `main' below.
-*
-* If you want more detail or more speed or can't find a feature here,
-* look in the appropriate source file. This file shows only the more ``user-friendly'' features;
+* If you want more detail or more speed or can't find a feature here, look in the
+* appropriate source file. This file shows only the more ``user-friendly'' features;
* the other features are messier but worth learning eventually.
*
* GO FORTH and play with many-digit numbers! (c.f. The TeXbook.)
int main() {
try {
+ std::cout << "=====\nBig Integer Library Demonstration" << std::endl;
+
BigInteger a; // a is 0
int b = 535;
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!
*
- * The Big Integer Library provides three kinds of operators:
- *
- * (1) Overloaded ``value'' operators: +, -, *, /, %, unary -.
- * Big-integer code using these operators looks identical to
- * code using the primitive integer types. The operator takes
- * one or two BigInteger inputs and returns a BigInteger result,
- * which can then be assigned to a BigInteger variable or used
- * in an expression.
- *
- * (2) Overloaded assignment operators: +=, -=, *=, /=, %=,
- * ++, --, flipSign.
- * Again, these are used on BigIntegers just like on ints.
- * They take one writable BigInteger that both provides an
- * operand and receives a result. The first five also take
- * a second read-only operand.
- *
- * (3) ``Put-here'' operations: `add', `subtract', etc.
- * Use these if and only if you are concerned about performance.
- * They require fewer BigInteger copy-constructions and assignments
- * than do operators in (1) or (2). Most take two read-only operands
- * and save the result in the invoked object `*this', whose previous
- * value is irrelevant. `divideWithRemainder' is an exception.
- * <<< NOTE >>>: Put-here operations do not return a value: they don't need to!!
+ * The Big Integer Library provides lots of overloaded operators
+ * and corresponding assignment operators. So you can do `a + b'
+ * with big integers 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 ``value'' operators
+ // All five ``return-by-value'' operators.
std::cout << (g + h) << '\n' << (g - h) << '\n' << (g * h)
<< '\n' << (g / h) << '\n' << (g % h) << std::endl;
- std::cout << "here 5" << std::endl;
+ std::cout << "=====\nTest code" << 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);
+ /*
+ * If you want to experiment with the library,
+ * put your own test code here.
+ */
- std::cout << "here 6" << std::endl;
+ /*
+ * (End of test code)
+ */
// Let's do some heavy lifting.
- std::cout << "Powers of 3" << std::endl;
+ std::cout << "=====\nPowers of 3" << std::endl;
std::cout << "How many do you want?" << std::endl;
int maxPower;
std::cin >> maxPower;
x *= three; // A BigInteger assignment operator
}
- std::cout << "There you go. Goodbye." << std::endl;
+ std::cout << "There you go. Goodbye.\n=====" << std::endl;
} catch(char const* err) {
- std::cout << "Sorry, the library threw an exception:\n"
+ std::cout << "=====\nSorry, the library threw an exception:\n"
<< err << std::endl;
}
Matt McCutchen's Web Site / bigint / bigint.git / commitdiff