A Class for Representing Large Integers

When you need big numbers, you need big numbers. In that case, even the simplest class for representing large integers can make all the difference.

Introduction

As a long time C and Fortran programmer, I've never been quite convinced that C++ will lead to more code reuse and increased reliability, or that it will otherwise satisfy many of the claims of the OOP evangelists. It has always seemed to me that a library of well written subroutines gives a programmer just as much reliability and code reuse as a class library. However, I must admit that when it comes to defining or extending number systems, the ability to overload operators offers a clear advantage. In this article I will describe a class for operating on very large integers, that is integers that are several hundred or more digits long (hereafter referred to as BigNums). The class will overload the standard operators +, -, *, /, and ^ so that a user of the class will be able to mix BigNums and ints in arithmetic expressions.

For those who believe that operator overloading is nothing more than syntactic sugar, suppose that x, y, and z are each 100-digit numbers, and a, b, and c are short ints. Using the BigNum class defined here, it is possible to have expressions such as (2*x + z + y³ + 4) / b. Obviously this expression is easier to read and use than

divBigShort(addBigShort(
    addBig(addBig(multBigShort(x,
    2),z),powerBigShort(y,3)), 4),b)

which is how you must write the expression in a language where operator overloading isn't allowed. I have used this class for a number of complex calculations, and have found that the operator overloading in this case has saved me from remembering a lot of strange subroutine names. It also freed me from thinking about whether I am operating on BigNums or regular integers in expressions where both may occur.

The BigNum Class

Let's jump right into the addition routine, since it has a theme that recurs in all the other functions. Besides, it illustrates an obvious way to implement BigNums. Suppose we wish to add a + b where a == 478 and b == 341. We can think of these numbers as arrays, with

a[0] == 8  a[1] == 7  a[2] == 4
b[0] == 1  b[1] == 4  and b[2] == 3

Then to compute a + b we merely add the individual components of the array while keeping track of any carries from the previous component. Figure 1 shows a piece of pseudocode that does the trick.

This routine is basically correct, but it overlooks a few details. First, it always assumes that a and b are positive. Dealing with negative numbers just adds some extra bookkeeping that is easily handled in the final version. Another thing to notice is that this addition routine uses base 10 for no apparent reason. It is quite wasteful for each element of an integer array to take on only the values zero through 9. I did this in the example, but in the actual version the array contains integers between zero and BASE, where BASE is less than or equal to 32,767.

I need to make one more observation before defining the structure of the BigNum class. Note that 478 was represented as 4*10² + 7*10¹ + 8*10⁰, since

a[2] == 4  a[1] == 7  a[0] == 8

So it works out that the array index is the exponent to which the base is raised for each digit. With this in mind I define a BigNum as:

int *x;        //an array of ints
char positive; //flag, 1 => number
               //is positive
               // 0 => number is
               //negative.
long exp;      //exponent == array
               //index of the most
               //significant digit

The final addition routine can be found in Listing 2, as can the subtraction routine. The latter is quite similar to the addition routine, except that borrows are generated instead of carries.

Adding an int to a BigNum requires only a simple modification of the BigNum addition routine and is therefore omitted in the listings. The modification is most easily illustrated by examining Figure 1 again. By initializing carry to equal b instead of zero, and skipping to the second for loop, we have a routine for adding a BigNum to an int as required. Alternatively, we could have a routine that converts the int to a BigNum and calls the BigNum addition with no significant loss in performance. Subtraction of BigNums and ints is similar.

Once we've seen the addition routine, multiplication of a BigNum and an integer is now straightforward. We simply multiply each term of the BigNum by the integer and keep track of the carries as in the addition. Multiplying two BigNums is slightly more complicated, but not much. If we again use the example from above with a == 478 and b == 341 in base 10, then the product

p = a * b can be computed as we would do with pencil and paper. That is, first we compute p1 = 1 * 478, then p2 = 4 * 478, and then p3 = 3 * 478. Then p is simply p1 + 10 * p2 + 100 * p3. Note that we compute p2 and p3 instead of 10 * p2 and 100 * p3 but we accomplish the equivalent result by carefully adding to the correct array index (which is equivalent to the shifting one does with pencil and paper multiplication). See Listing 3 for the complete multiplication routine.

It turns out that dividing a BigNum by an integer is rather easy. Simply divide each term of the numerator array (in reverse order, so that i goes from numerator.exp to zero) by the integer denominator. The integer part of the division becomes part of the quotient array, while the fractional part gets multiplied by BASE and added to the previous term of the numerator. The remainder is simply the fractional part of the last division, or (previous Remainder*BASE + numerator[0]) % denominator. See Listing 4. Dividing a BigNum by a BigNum on the other hand is not all that straightforward. The difficulty in long division is that it is not nearly as mechanical as addition, subtraction, or multiplication. In particular each step requires a guess as to what the next digit in the quotient ought to be. Unfortunately, computers aren't terribly well suited to guessing, so this step needs to be better quantified with an example.

It is instructive to revisit the paper and pencil method of division from elementary school. Recall that dividing a five-place number such as 54321 by a two-place number like 59 is computed as a series of simpler divisions. That is, we don't just come up with 920, but first divide 543 by 59 to come up with 9, the first digit of the quotient. Then 9 * 59 == 531 is subtracted from 543 to reduce the problem to computing 1,221 divided by 59, and so on. After two more steps we have 920 as the quotient so far and the new problem of dividing 41 by 59. Since 41 is smaller than 59, 920 must be the entire quotient and the remainder is 41.

Thus to divide an N-digit number by an M-digit number, one only needs to know how to divide a series of M+1-digit numbers by an M-digit number. For the discussion of division I revert back to thinking of Bignums as arrays of single digits, and assume both the numerator and denominator are positive integers. In this simplified case, if a is an N-digit number, then a.exp == N - 1. Also, observe that if q is the quotient of a / b, then q.exp == a.exp - b.exp. From these observations, a basic division algorithm is given in pseudocode in Figure 2. (Note the algorithm assumes the existence of a subroutine guess to find qGuess. For the moment let's just assume we have such a subroutine.)

Note that this snippet of code merely mimics the method described above in dividing 54,321 by 59. For this example, the first iteration sets atemp = 54 and tries to divide it by 59. In this case qGuess is zero, and a isn't reduced at all. However x is reduced by 1 before looping, resulting in atemp = 543 in the second iteration. In the second iteration qGuess becomes 9, and a is reduced to 1,221 before the next iteration.

This is the basic idea, but of course it leaves out several details, including a major one about how to compute qGuess! It turns out that a good qGuess can be made by dividing the two most significant digits of a by the most significant digit of b, that is

(a[a.exp]*BASE + a[a.exp-1])
 /b[b.exp]

If this gives a number bigger than BASE then qGuess = BASE-1 is used instead.

The idea of qGuess comes from Donald Knuth's Seminumerical Algorithms [1]. In the book he proves that qGuess will never be too small, and he gives a way to ensure that qGuess is never more than 1 too large. Thus one can be sure that the while loop in the pseudocode of Figure 2 for adding back will very rarely be entered, and if entered will only require a single iteration.

The only hitch in this qGuess business is that, for qGuess to work, b[b.exp] must be larger than BASE/2. This seems like a rather restrictive detail, but multiplying both a and b by a number d, where d = (b[b.exp] + 1)/BASE, will make b satisfy the requirement. Note that this will not change the quotient since a/b = ad/bd, although we will have to divide the remainder by d as a last step in order to get the correct remainder.

The final version of the division algorithm encompassing all of the above details can be found in Listing 5. A few minor adjustments to this routine yields the % operator routine. Notice that the division algorithm is quite a bit more complicated and hence quite a bit slower than dividing a BigNum by an integer. It is therefore quite useful to create a separate routine for dividing a BigNum by an int, whereas for addition, subtraction, and even multiplication, we can get away with converting the int to a BigNum and passing it to those routines with a very small loss in performance.

The last major routine in the class involves raising BigNums to integer powers. The obvious way of doing this can be improved. For example, since x⁶ = x * (x⁵) it is tempting to use the following:

BigNum operator^(const long n){
 if (n>0)
  return ((*this)*(*this)^(n-1));
 else return 0;
}

But observing that x⁶ = (x³)² can save the computer quite a bit of work. An improved routine looks like this:

BigNum operator^(const long n){
 if (n>0){
  if (n==2)
   return((*this)*(*this));
  if (n%2==0)
   return (((*this)^(n/2))^2);
  else
   return (*this * ((*this)^(n-1)));
 }else
  if (!n)
   return BigNum(1);
  else
   return BigNum(long(0));
}

Other Routines

In this article I've only detailed the main routines to give a flavor of the BigNum class. Listing 6 gives a few more important routines such as the copy constructor and constructors for creating BigNums from strings of digits, etc.

The class contains a number of other useful routines. For example, asl and asr will do an arithmetic shift left and arithmetic shift right on BigNums. (x.asl(n) has the effect of multiplying x by BASE n times, while x.asr(n) is equivalent to dividing x by BASE n times.) random(n) will return a random BigNum between zero and an n-digit number. These routines are fairly simple to implement, and thus have been eliminated from the listings because of space considerations, (They are still listed in the header file of Listing 1 however). The complete BigNum class will be available for download from my web page at about the time you read this.

Design Considerations

It should be mentioned here that speed of the BigNum functions was sacrificed for efficient use of memory. Since the main part of the BigNum is a pointer, I am creating and deleting this pointer in nearly every routine. In fact, I recently tested the BigNum class in calculating pi to 10,000 digits of accuracy, and found that there were 236,271 calls to new and delete.

By basing the BigNum class on a fixed-length array, I could avoid all of the allocating and deallocating of memory and thereby speed up the class. However, the speed gained is probably not worth the price in wasted memory. To test this I rewrote the BigNum routines in C using fixed length arrays as the basis of the BigNums. The aforementioned calculation of pi took just under 10 minutes on a 66 MHz 486 using the fixed-array implementation in C, while the BigNum class shown here took a little over 11 minutes. However to gain this 10% speed savings I used considerably more memory. In the BigNum class with a base of 10,000, each BigNum uses two bytes for every four digits, but in the fixed-array implementation each BigNum uses over 5,000 bytes, whether it is one digit or 10,000 digits.

References

[1] Donald Knuth. The Art of Computer Programming: Semi-Numerical Methods, Second Edition, Addison-Wesley 1981.

Anthony Breitzman is Vice President of CHI Research, Inc. a consulting firm specializing in science and technology indicators. He has a masters degree in mathematics and is currently working on a Ph.D in computer science. He may be reached at [email protected] or via his web page at http://members.aol.com/ breitzchi/homepage/afb1.html.