------------------ Purenum 0.4d alpha ------------------ purenum.txt ------------------ AUTHOR Original Author: Shawn Yarbrough Contributing Authors: (none) Web Site: http://www.nailstorm.com/products/purenum/ Email: info@nailstorm.com (subject: Purenum) Original Creation Date: July 19, 1998 Original Release Date: August 15, 2000 This Version Date: July 10, 2001 ALPHA VERSION Some features may not work at all or may not work properly, even if they are described later in this document as working properly. INTRODUCTION TO PURENUM Purenum is a C++ bignum library for programmers. Its unlimited-width Integer type works with all of the C++ math operators (+ and / and *= etc.) but unlike the int type there can never be overflow errors. Division by zero and running out of memory are catchable exceptions. Optimized inline code is used and the software Integer operations for single-width values run almost as quickly as hardware int operations do. An Array type provides for resizeable arrays of bignums. BIGNUMS A simple bignum example: the number 1,234,567,890 easily fits within a 32-bit unsigned integer value. But multiply it by ten and a 32-bit computer chokes because it can't handle numbers higher than 4,294,967,295 (which is about 2 to the 32nd power). Most computers today (as of Jun 2001) would "overflow" the correct answer of 12,345,678,900 resulting in a wrong answer of 3,755,744,308. It's wrong, but it's less than 4,294,967,295 so a 32-bit computer is happy. Yes, this probably means your computer. Each program, and the entire operating system, must be carefully designed to avoid these overflow errors. Overflow errors are bad for four reasons: 1. the overflowed answer is wrong 2. the overflow error is silent, and processing continues 3. programmers must carefully avoid these overflow errors 4. programmers make mistakes If a program has a rare overflow bug it can often go undetected by the programmer. Users will sometimes end up with corrupted data but only the rare crash will signal that something is really wrong. By the way, this is only one of the many problems with modern computer designs that can cause mysterious crashes. Bignum software fixes the overflow problem by teaching the computer in software how to overcome it's hardware limitations. Programs based on bignum math always "do the right thing". They give the right answers without ever overflowing. This increased reliability comes at the price of slower speed. PURENUM The Purenum library provides bignums with a minimal slowdown. Other bignum projects spend much design effort trying to make really huge numbers be processed efficiently. That's great for scientists and mathematicians but most programs rarely use numbers over the low billions. The problem for most programmers is the occasional unnoticed overflow, not the exact diameter of the galaxy measured in centimeters. Purenum provides bignums whenever they are needed (at any speed) but it runs it's absolute fastest while processing those common smaller numbers used by most programs most of the time. An existing program converted to use Purenum will run almost as quickly as it did in the first place... AND all of it's subtle overflow bugs will automatically be fixed. Another advantage of Purenum is program portability between different kinds of computers. A Purenum-based C++ program should recompile and run on 16-bit, 32-bit, 64-bit, and other kinds of CPUs with no integer code changes. Extra CPU power will be taken advantage of where it is available. The program will work everywhere, even on slow, obsolete hardware. Hardware independence is a wonderful thing! C++ CLASS INT class Int // unlimited-width bignum integer type { // (summary, for exact definition see file 'integer.h') public: Int(); // default constructor Int(int); // construct from a signed hardware int Int(unsigned int); // construct from an unsigned hardware int Int(char *); // construct from a number in an ASCIIZ string operator++(); // increment operator--(); // decrement operator+=(Int &); // add operator-=(Int &); // subtract operator*=(Int &); // multiply operator/=(Int &); // divide operator%=(Int &); // remainder // ...all the other standard C++ operators are also provided class exception { }; // math errors cause throws class divisionbyzero : public exception { }; // bad division attempted class outofmemory : public exception { }; // value too large for memory class outofrange : public exception { }; // bad conversion attempted class badstring : public exception { }; // corruptly formatted string private: unsigned int memorysize; // integer size limited only by available memory unsigned int *memory; // array for storing the unlimited-width value }; By default the Int class (defined by int.h) is actually just another name for the very portable Integer class (located in integer.h and integer.c). This default can be changed in the makefile. There are several different bignum classes to choose from, each of which provides a different level of efficiency. Each of these classes provides the same Purenum Int interface: Integer most portable Int, least optimized, should work everywhere Integer_2C an Int optimized for most computers (w/two's-complement) ** Integer_GMP an Int based on the GNU Multi-Precision library (GMP) * Integer_x86 well-optimzed Int for Intel-compatible computers only ** Integer_68K well-optimzed Int for Motorola-compatible computers only ** Integer_fat optimized at expense of size (absolutely all code inline) ** Integer_std same as Integer but using the C++ standard library more ** Integer_fake NOT A BIGNUM: a regular 'signed int' with an Int interface Integer_fakeu NOT A BIGNUM: a regular 'unsigned int' with an Int interface * GMP is a C bignum library for scientists and mathematicians (Integer_GMP is over 10 times slower than Integer, for smallnums) see for more info: http://www.swox.com/gmp/ ** not yet available -- this is an alpha release! (don't worry, even the plain Integer class is really fast for smallnums) Programs using Purenum's different bignum classes may choose to use the Int type and then set the default bignum implementation for Int in the makefile. The chosen version will then automatically be substituted for Int. As an alternative, the different bignum versions may be used directly thru the names listed above. FREQUENTLY ASKED QUESTIONS Q: Why bother with bignums? A: Bignums are easier to use, more reliable, and more portable. Design for correctness first. Design for efficiency last. Purenum makes this easy. And you can always subsitute in Integer_Fake later for a small speed increase if you are confident that your program has no overflow bugs. ;) PURENUM'S DESIGN PRIORITIES 1. portability 2. ease-of-use 3. execution speed 4. memory size 5. compilation speed KNOWN PROBLEMS Bitwise operations do not behave the same with software integers as they do with hardware integers. For example, a bit in a hardware integer can never possibly be shifted in one direction more than 31 times consecutively on a 32-bit processor. But in a software integer the bit can be shifted over and over, probably thousands or millions of times or more, until finally producing a number so large that memory runs out. This behavor is correct but will break programs which depend on the physical size (in memory) of an integer when those programs are converted to use class Integer. The whole point of class Integer is to protect programmers from low- level hardware details such as this, so this is a good thing. Bitwise operations only affect the absolute value (magnitude) of an Integer. The sign is considered to be a seperate value, regardless of the underlying implementation of the sign. Different Int versions can be mixed in the same program with no conflicts, however they can NOT directly interact with each other. Polymorphism was sacrificed for efficiency in the Purenum design. For example, an Integer_x86 is not an Integer as far as the compiler knows. In reality this should rarely be a problem. Programs seriously needing to convert between different kinds of Integer values could use string integers as an intermediate type.