Big Numbers

Jon Bently writes a column called “Software Explorations” for the magazine Unix Review. In the November 1994 issue, Jon discusses how to handle big digit numbers. He starts off by discussing how to store the number, in decimal or binary. He opts for decimal storage and the use of a simple array to store the number in.

Jon writes up a few simple routines to handle big numbers. They are:

• pow2 – raises 2 to the power of X.
• bnset1 – sets the global array that holds the number
• being created.
• bnmult – multiply the number with a constant.
• bnprint – print the big number.

All of these routines us a global array that stores the number as it is being worked on. You could adapt them to pass the array to each function.

The article goes on to refine some of the routines listed above. Plus, Jon mentions that a real big number library would have a lot more routines than the ones listed above. Bnadd, bnsub, bndiv, and bncomp would round out a library.

In porting this program to the QL using Small-C, I opted to make the variables INT and not LONG as all of the example programs Jon created used. This would only affect the size of the big numbers that this port could use. Using C68 and LONG would solve this problem.

Below is the code from the article, with an example main() to test it with. I’m sure this code is very simple and is only a start for those interested in seriously handling large numbers.

#include <stdio_h>
   
int x[1000];  /* global array for storage
                 of resultant number */
int topdig;
      
main()
{
   int c;
   
pow2(100);
bnprint();

 while ( ( c = getchar() ) == "" )
          ;  /* pause screen */
   
}
   
pow2 ( n )
   int n;
{
   bnset1( 1 + n/3);
   while ( n -- > 0 )
      bnmult(2);
}
   
bnset1(maxdig)
   int maxdig;
{
   int i;
   
   topdig = maxdig;
   for ( i = 0; i < topdig; i++)
      x[i] = 0;
   
   x[0] = 1;
}
   
bnmult( a )
   int a;

   int i, carry;

   carry = 0;
   for ( i = 0; i < topdig; i++ ) {
      x[i] = a * x[i] + carry;
      carry = 0;
      if ( x[i] >= 10 ) {
         x[i] -= 10;
         carry = 1;
      }
   }
   if (carry)
      x[topdig++] = carry;
}
   
bnprint ()
{
   int i;

   for ( i = topdig-1; i >= 0; i--)
      printf("%d", x[i]);
   printf("\n");

}