_BASIC ARITHMETIC WITH INFINITE INTEGERS_
by Jeffrey W. Hamilton
   

Listing One

/* Infinite Integer Definitions -- by Jeffrey W. Hamilton, 1993
** NOTE: This code assumes that a 'short int' is two bytes
**       and a 'long int' is four bytes.
*/
#ifndef BIGNUM_DEFINES
#define BIGNUM_DEFINES
typedef struct BigNum {
   unsigned short int length;     /* Left most bit is used for the sign of the number */
   unsigned short int element[1]; /* Minimum of one element */
} *bignum;

/* Convience Routines */
#define NEGATIVE 0x8000
#define POSITIVE 0
#define BIGNUM(sign, value) { (sign) | 1, (value) }
#define BIGNUM_SIZE(b) ((b)->length & ~NEGATIVE)
#define BIGNUM_SIGN(b) ((b)->length & NEGATIVE)
#define BIGNUM_SIZEOF(len) (sizeof(struct BigNum) + (((len)-1) * 
                                                      sizeof(unsigned short)))
#define FORCE_POSITIVE(b) ((b)->length &= ~NEGATIVE)
#define FORCE_NEGATIVE(b) ((b)->length |= NEGATIVE)
#define FORCE_INVERT(b)   ((b)->length = (BIGNUM_SIGN(b) ^ NEGATIVE) | 
                                                               BIGNUM_SIZE(b))

/* Error Conditions */
#define BIGNUM_BADARG  22
#define BIGNUM_NOSPACE 12
#define BIGNUM_ZERO    1

#ifndef max
#define max(x,y) (((x) < (y)) ? (y) : (x))
#endif

bignum new_bignum(short int size);
void   destroy_bignum(bignum);
bignum copy_bignum(bignum);
bignum ltobig(long int number);
double bigtod(bignum);
bignum dtobig(double);
bignum strtobig(char *string, char **endPoint, int radix);
char * bigtostr(bignum number, char *target, int maxLength, int radix);
bignum reduce_bignum(bignum);
bignum add_bignum(bignum, bignum);
bignum sub_bignum(bignum, bignum);
bignum neg_bignum(bignum);
bignum mult_bignum(bignum, bignum);
bignum div_bignum(bignum, bignum, bignum *);
bignum shiftl_bignum(bignum, unsigned long);
bignum shiftr_bignum(bignum, unsigned long);
bignum or_bignum(bignum, bignum);
bignum xor_bignum(bignum, bignum);
bignum and_bignum(bignum, bignum);
bignum not_bignum(bignum);
bignum set_bit_bignum(bignum, unsigned long, int value);
int    test_bit_bignum(bignum, unsigned long);
#endif



Listing Two

/* Infinite Integer Conversion Facility -- by Jeffrey W. Hamilton, 1993 */
#include <stdlib.h>
#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <math.h>
#include <errno.h>
#include "bignum.h"

/* Allocate space for a bignum, but does not intialize it.
** Input: Number of elements to allocate. Must be greater than 0.
** Output: The allocated space
** Error: Returns NULL with errno set to one of the following:
**        BIGNUM_BADARG  - Size if less than 1
**        BIGNUM_NOSPACE - No enough memory available to allocate the number
*/
bignum new_bignum(short int size)
{
   bignum temp;

   if (size <= 0) {
      errno = BIGNUM_BADARG;
      return NULL;
   }
   if ((temp = malloc(BIGNUM_SIZEOF(size))) == NULL) {
      errno = BIGNUM_NOSPACE;
   }
   temp->length = size;
   return temp;
}
/* Release the space occupied by a bignum 
** Input: Number to be released.
*/
void destroy_bignum(bignum temp)
{
   free(temp);
}
/* Create a duplicate copy of a bignum
** Input: Number to be copied.
** Output: Copy of the number
** Error: Returns NULL with errno set to one of the following:
**        BIGNUM_NOSPACE - No enough memory available to allocate the number
*/
bignum copy_bignum(bignum temp)
{
   int size;
   bignum result;

   size = BIGNUM_SIZE(temp);
   if ((result = new_bignum(size)) == NULL) return NULL;
   memcpy(result, temp, BIGNUM_SIZEOF(size));
   return result;
}
/* Convert a long int to a bignum
** Input: A long integer number to be converted.
** Output: The equivalent value in bignum format
** Error: Returns NULL and errno will be set to:
**        BIGNUM_NOSPACE - Not enough space to hold the number in memory.
*/
bignum ltobig(long temp)
{
   int sign;
   bignum result;

   /* Determine the sign of the number and put the value in absolute form */
   if (temp < 0) {
      sign = NEGATIVE;
      temp = -temp;
   } else {
      sign = POSITIVE;
   }
   /* Try to allocate the minimum space needed */
   if ((temp & 0xFFFF0000L) == 0) {
      /* Number will fit in one element */
      if ((result = new_bignum(1)) == NULL) return NULL;
      result->element[0] = (unsigned short) temp;
   } else {
      /* Number needs two elements */
      if ((result = new_bignum(2)) == NULL) return NULL;
      result->element[0] = (unsigned short) temp;
      result->element[1] = (unsigned short) (temp >> 16);
   }
   /* Record the correct sign */
   result->length |= sign;
   return result;
}
/* Convert an unsigned long int to a bignum
** Input: A long integer number to be converted.
** Output: The equivalent value in bignum format
** Error: Returns NULL and errno will be set to:
**        BIGNUM_NOSPACE - Not enough space to hold the number in memory.
*/
bignum ultobig(unsigned long temp)
{
   bignum result;

   /* Try to allocate the minimum space needed */
   if ((temp & 0xFFFF0000L) == 0) {
      /* Number will fit in one element */
      if ((result = new_bignum(1)) == NULL) return NULL;
      result->element[0] = (unsigned short) temp;
   } else {
      /* Number needs two elements */
      if ((result = new_bignum(2)) == NULL) return NULL;
      result->element[0] = (unsigned short) temp;
      result->element[1] = (unsigned short) (temp >> 16);
   }
   return result;
}
/* Convert a bignum to a long
** Input: A bignum to be converted.
** Output: The equivalent value as a long.
** Error: Returns NULL and errno will be set to:
**        BIGNUM_NOSPACE - Not enough space to hold the number in a long.
*/
int bigtol(bignum num, long *temp)
{
   if (BIGNUM_SIZE(num) > 2) {
      /* Two many significant bits */
      errno = BIGNUM_NOSPACE;
      return -1;
   } else if (BIGNUM_SIZE(num) == 2) {
      if (num->element[1] & NEGATIVE) {
         /* The number contains more than 31 significant bits */
         errno = BIGNUM_NOSPACE;
         return -1;
      }
      *temp = ((long) num->element[1] << 16) | num->element[0];
   } else {
      *temp = num->element[0];
   }
   if (BIGNUM_SIGN(num) == NEGATIVE) *temp = -*temp;
   return 0;
}
/* Convert a bignum to an unsigned long
** Input: A bignum to be converted.
** Output: The equivalent value as a long.
** Error: Returns NULL and errno will be set to:
**        BIGNUM_NOSPACE - Not enough space to hold the number in a long.
*/
int bigtoul(bignum num, unsigned long *temp)
{
   if (BIGNUM_SIZE(num) > 2) {
      /* Two many significant bits */
      errno = BIGNUM_NOSPACE;
      return -1;
   } else if (BIGNUM_SIZE(num) == 2) {
      *temp = ((unsigned long) num->element[1] << 16) | num->element[0];
   } else {
      *temp = num->element[0];
   }
   if (BIGNUM_SIGN(num) == NEGATIVE) *temp = -*temp;
   return 0;
}


Listing Three

/* Infinite Integers Logic Facility -- by Jeffrey W. Hamilton, 1993 */
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <errno.h>
#include "bignum.h"

/* Compare first bignum to the second
** Input: Two bignums
** Output: Returns  -1 if first is less than second
**                   0 if first equals second
**                  +1 if first is greater than second
*/
int cmp_bignum(bignum num1, bignum num2)
{
   int isNegative;
   int i;

   /* Quick check based on sign */
   if (BIGNUM_SIGN(num1) != BIGNUM_SIGN(num2)) {
      if (BIGNUM_SIGN(num1) == NEGATIVE) return -1;
      return 1;
   }
   /* Use a flag to compensate for positive / negative numbers */
   isNegative = (BIGNUM_SIGN(num1) == NEGATIVE) ? 1 : 0;

   /* Quick check based on length */
   if (BIGNUM_SIZE(num1) < BIGNUM_SIZE(num2)) {
      return (isNegative) ? 1 : -1;
   } else if (BIGNUM_SIZE(num1) > BIGNUM_SIZE(num2)) {
      return (isNegative) ? -1 : 1;
   }
   /* It looks like we have to be more thorough */
   for (i = BIGNUM_SIZE(num1) - 1; i >=0; i--) {
      if (num1->element[i] < num2->element[i]) {
         return (isNegative) ? 1 : -1;
      } else if (num1->element[i] > num2->element[i]) {
         return (isNegative) ? -1 : 1;
      }
   }
   /* They are equal */
   return 0;
}


Listing Four

/* Infinite Integers Math Facility -- by Jeffrey W. Hamilton, 1993 */
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <errno.h>
#include "bignum.h"

/* Reduce a bignum to occupy the minimum space required
** Input: bignum to be reduced
** Output: reduced bignum
*/
bignum reduce_bignum(bignum number)
{
  register int j;

  /* Remove leading zero values from the high end of the number */
  for (j = BIGNUM_SIZE(number); (j > 1) && (number->element[j-1] == 0); j--);

  /* Special case: We don't allow a negative zero */
  if ((j == 1) && (number->element[0] == 0)) {
      FORCE_POSITIVE(number);
  }
  /* If the number is already at a minimal size, return it */
  if (j == BIGNUM_SIZE(number)) return number;

  /* Reallocate the number at a smaller size. In theory realloc could fail, 
  ** but since we are always reducing the space we are occupying, a failure
  ** would be a sign of a VERY poor memory manager.
  */
  number->length = BIGNUM_SIGN(number) | j;
  return realloc(number, BIGNUM_SIZEOF(j));
}
/* Add two bignums
** Input: numbers to add
** Output: a bignum that is the sum
** Errors: Returns NULL with errno set to one of the following:
**         BIGNUM_BADARG  - Size if less than 1
**         BIGNUM_NOSPACE - No enough memory available to allocate the results
*/
bignum add_bignum(bignum num1, bignum num2)
{
  long carry;
  int size, size1, size2;
  int sign1, sign2;
  register int i;
  bignum result;

  carry = 0;

  /* Insure sum can hold the results */
  size1 = BIGNUM_SIZE(num1);
  size2 = BIGNUM_SIZE(num2);
  size = max(size1, size2) + 1;
  if ((result = new_bignum(size)) == NULL) return NULL;

  sign1 = BIGNUM_SIGN(num1);
  sign2 = BIGNUM_SIGN(num2);

  /* Add the numbers */
  for (i = 0; i < size; i++) {
     if (i < size1) {
        /* We still have elements of num1 to process */
          if ((unsigned) sign1 == NEGATIVE) {
           carry -= num1->element[i];
        } else {
           carry += num1->element[i];
        }
     }
     if (i < size2) {
        /* We still have elements of num2 to process */
          if ((unsigned)sign2 == NEGATIVE) {
           carry -= num2->element[i];
        } else {
           carry += num2->element[i];
        }
     }
     result->element[i] = (unsigned short) carry;
     carry >>= 16;
  }
  /* Adjust the sign of the results */
  if (carry < 0) {
     /* Complement the answer */
     carry = 0;
     for (i = 0; i < size; i++) {
        carry -= result->element[i];
        result->element[i] = (unsigned short) carry;
        carry >>= 16;
     }
     FORCE_NEGATIVE(result);
  }
  return reduce_bignum(result);
}
/* Subtract the second bignum from the first.
** Input: numbers to subtract.
** Output: a bignum that is the subtraction
** Errors: Returns NULL with errno set to one of the following:
**         BIGNUM_BADARG  - Size if less than 1
**         BIGNUM_NOSPACE - No enough memory available to allocate the results
*/
bignum sub_bignum(bignum num1, bignum num2)
{
   long carry;
   int size, size1, size2;
   int sign1, sign2;
   register int i;
   bignum result;

   carry = 0;

   /* Insure sum can hold the results */
   size1 = BIGNUM_SIZE(num1);
   size2 = BIGNUM_SIZE(num2);
   size = max(size1, size2) + 1;
   if ((result = new_bignum(size)) == NULL) return NULL;

   sign1 = BIGNUM_SIGN(num1);
   /* Invert the sign for subtraction */
   sign2 = (BIGNUM_SIGN(num2) == NEGATIVE) ? POSITIVE : NEGATIVE;

   /* Do a normal add with the inverted second number */
   for (i = 0; i < size; i++) {
      if (i < size1) {
         /* We still have elements of num1 to process */
            if ((unsigned)sign1 == NEGATIVE) {
            carry -= num1->element[i];
         } else {
            carry += num1->element[i];
         }
      }
      if (i < size2) {
         /* We still have elements of num2 to process */
         if ((unsigned)sign2 == NEGATIVE) {
           carry -= num2->element[i];
        } else {
           carry += num2->element[i];
        }
      }
      result->element[i] = (unsigned short int) carry;
      carry >>= 16;
   }
   /* Adjust the sign of the results */
   if (carry < 0) {
      /* Complement the answer */
      carry = 0;
      for (i = 0; i < size; i++) {
         carry -= result->element[i];
         result->element[i] = (unsigned short) carry;
         carry >>= 16;
      }
      FORCE_NEGATIVE(result);
   }
   return reduce_bignum(result);
}
/* Compute the negative of a bignum
** Input: number to negate
** Output: a negated copy of the number
** Errors: Returns NULL with errno set to one of the following:
**         BIGNUM_BADARG  - Size if less than 1
**         BIGNUM_NOSPACE - No enough memory available to allocate the results
*/
bignum neg_bignum(bignum number)
{
   bignum result;

   if ((result = copy_bignum(number)) == NULL) return NULL;
   FORCE_INVERT(result);
   return result;
}