BN.c: Performing arithmetic on arbitrarily long integers

Mark Baranowski markb at giga.slc.unisys.com
Wed Aug 22 07:57:15 AEST 1990


echo x - README
sed 's/^X//' >README <<'*-*-END-of-README-*-*'
XOverview:
X
X	This library is a collection of routines that allows you to
X	add, subtract, multiply, and divide arbitrarily long integers
X	(BigNums).  This library also contains routines for converting
X	ascii strings to BigNums, converting BigNums to ascii strings,
X	and comparing two BigNums against each other.
X
X
XFeatures:
X
X	Input/output, multiplication, division, addition, subtraction,
X	and comparison (i.e. <, <=, >, >=, !=, ==).
X
X	Arbitrarily long integers are obtainable by adjusting the
X	constant BN_SIZE in the file BN.h to the number of 32-bit
X	chunks desired and then recompiling.  This size may be from 1
X	up to any desired maximum.
X
X	Overflow is detected for multiplication, addition, and
X	subtraction.  The global variable BN_overflow is set to TRUE
X	if an overflow occurs and remains TRUE until reset by the
X	user.  It is up to the user whether or not to ignore
X	BN_overflow.
X
X	The remainder is available immediately following any division
X	via the global variable BN_remainder.  This variable is valid
X	only until the next BigNum operation.
X
X	All arguments are passed by value and the result is returned
X	by value.  Although this slightly increases the overhead, the
X	user interface is simplified.
X
X
XSynopsis:
X
X	#include "BN.h"
X
X
X	/* Remainder following division: */
X	BN BN_remainder;	/* Valid only until next operation */
X
X
X	/* Overflow condition following add, sub, or mult: */
X	Boolean BN_overflow;	/* Valid until reset by the user */
X
X
X	/* Convert an ascii string to a BigNum.
X	   User is notified and BN_overflow is set if any overflow occurs. */
X	BN atoBN(str)
X	     char *str;
X
X
X	/* Convert a BigNum to an ascii string. */
X	int BNtoa(bignum,str)
X	     BN bignum;
X	     char *str;
X
X
X	/* Convert a 32 bit integer to a BigNum. */
X	BN itoBN(num)
X	     int num;
X
X
X	/* Convert a BigNum to a 32 bit integer.
X	   User is warned if any truncation occurs. */
X	int BNtoi(bignum)
X	     BN bignum;
X
X
X	/* Multiply two BigNums.
X	   BN_overflow is set if any overflow occurs. */
X	BN BN_mult(multiplicand,multiplier)
X	     BN multiplicand,multiplier;
X
X
X	/* Divide the dividend by the divisor.
X	   The User is notified and program terminated if division by
X	   0 occurs.  The global variable BN_remainder contains the
X	   remainder of the most recent division. */
X	BN BN_div(dividend,divisor)
X	     BN dividend,divisor;
X
X
X	/* Subtract arg2 from arg1.
X	   BN_overflow is set if any overflow occurs. */
X	BN BN_sub(arg1,arg2)
X	     BN arg1,arg2;
X
X
X	/* Add two BigNums.
X	   BN_overflow is set if any overflow occurs. */
X	BN BN_add(arg1,arg2)
X	     BN arg1,arg2;
X
X
X	/* Negate a BigNum. */
X	BN BN_neg(arg)
X	     BN arg;
X
X
X	/* Test if arg1 is greater than or equal to arg2. */
X	Boolean BN_ge(arg1,arg2)
X	     BN arg1,arg2;
X
X
X	/* Test if arg1 is less than or equal to arg2. */
X	Boolean BN_le(arg1,arg2)
X	     BN arg1,arg2;
X
X
X	/* Test if arg1 is greater than arg2. */
X	Boolean BN_gt(arg1,arg2)
X	     BN arg1,arg2;
X
X
X	/* Test if arg1 is less than arg2. */
X	Boolean BN_lt(arg1,arg2)
X	     BN arg1,arg2;
X
X
X	/* Test if arg1 is not equal to arg2. */
X	Boolean BN_ne(arg1,arg2)
X	     BN arg1,arg2;
X
X
X	/* Test if arg1 is equal to arg2. */
X	Boolean BN_eq(arg1,arg2)
X	     BN arg1,arg2;
X
X
XExample:
X	
X	/**************************/
X	/* Using 32-bit integers: */
X	
X	main()
X	{
X	    int i,j,n;
X	
X	    j = 10000000000000000;
X	
X	    /* Find first factorial greater than j: */
X	    i = 1;
X	    n = 1;
X	    while (i <= j)
X	    {
X		i = i * n;
X		n++;
X	    }
X	    printf("%d\n", i);
X	}
X	
X		
X	/******************/
X	/* Using BigNums: */
X	
X	#include "BN.h"
X	main()
X	{
X	    BN i,j,n;
X	    char str[11*BN_SIZE];
X	
X	    j = atoBN("10000000000000000");
X	
X	    /* Find first factorial greater than j: */
X	    i = itoBN(1);
X	    n = itoBN(1);
X	    while (BN_le (i, j))
X	    {
X		i = BN_mult(i, n);
X		n = BN_add (n, itoBN(1));
X	
X		/* Check for overflow: */
X		if (BN_overflow)
X		{
X		    printf("BigNum overflow\n");
X		    exit (1);
X		}
X	    }
X	
X	    BNtoa(i,str);
X	    printf("%s\n", str);
X	}
X
X
X
XTo compile:
X
X	cc yourprogram.c BN.c
X
X
XRanges:
X
X	Different ranges can be obtained by changing the constant
X	BN_SIZE in "BN.h".  The following table gives the maximum
X	power of 10 and the maximum factorial obtainable for a given
X	BN_SIZE:
X
X
X	BN_SIZE		10^N		N!
X	-------		----		--
X	   1		 10		12
X	   2		 19		20
X	   5		 48		39
X	  10		 97		67
X	  20		193	       116
X	  50		482	       245
*-*-END-of-README-*-*
echo x - BN.c
sed 's/^X//' >BN.c <<'*-*-END-of-BN.c-*-*'
X/******************************************************************************
X  BN.c -- A library for performing arithmetic operations on arbitrarily
X  	  long integers.
X
X  Author: Mark Baranowski (markb at signus.utah.edu)
X
X  Version: 1.0
X  Date: Aug. 20, 1990
X
X  This program is provided "as is" without any warranty of its
X  correctness or of its fitness for a particular purpose.  You may
X  freely distribute and modify this program as long as this header
X  remains intact.
X
X *****************************************************************************/
X
X#include "BN.h"
X
Xtypedef void Nil;
X#define Local static
X
X/* Globally accessable remainder following division: */
XBN BN_remainder;		/* Valid only until next operation */
X
X/* Globally accessable overflow condition following add, sub, or mult: */
XBoolean BN_overflow;		/* Valid until reset by the user */
X
X/* Locally defined functions: */
XLocal Nil lshift1(/* BN *arg */);
XLocal Nil rshift1(/* BN *arg */);
X
X/* Locally defined BigNum Constants: */
XLocal BN BN_0  = { 0, /* 0, 0, ..., 0 */};
XLocal BN BN_1  = { 1, /* 0, 0, ..., 0 */};
XLocal BN BN_10 = {10, /* 0, 0, ..., 0 */};
X
X#define MASKSIGN(bignum)  (bignum.N[BN_SIZE-1] & 0x80000000)
X
Xextern void exit();
X
X/******************************************************************************
X
X  atoBN -- Convert an ascii string to a BigNum.
X
X  User is notified and BN_overflow is set if any overflow occurs.
X
X *****************************************************************************/
X
XBN atoBN(str)
X     char *str;
X{
X  BN bignum;
X  Boolean negate;
X  Boolean save_overflow;
X
X  /* Make sure we don't confuse a pre-existing overflow for an overflow that
X     might occur here: */
X  save_overflow = BN_overflow;
X  BN_overflow = FALSE;
X
X  /* Build bignum: */
X
X  if (str[0] == '-')
X  {
X    str++;
X    negate = TRUE;
X  }
X  else
X  {
X    negate = FALSE;
X  }
X
X  bignum = BN_0;
X  while (*str)
X  {
X    if (*str < '0' || *str > '9')
X    {
X      (void)printf ("atoBN: non-numeric character in constant\n");
X      exit (1);
X    }
X    bignum = BN_add(BN_mult(BN_10,bignum), itoBN(*str++ - '0'));
X  }
X  if (negate) bignum = BN_neg(bignum);
X
X  /* Notify user of any overflows and restore overflow condition if it
X     existed previously: */
X  if (BN_overflow) (void)printf("atoBN: string overflowed bignum\n");
X  BN_overflow = BN_overflow || save_overflow;
X
X  return (bignum);
X}
X
X
X/******************************************************************************
X
X  BNtoa -- Convert a BigNum to an ascii string.
X
X *****************************************************************************/
X
Xint BNtoa(bignum,str)
X     BN bignum;
X     char *str;
X{
X  register int i,j,k;
X  register char tmp;
X
X  /* If negative then output '-' and change to a positive number: */
X  if (MASKSIGN(bignum))
X  {
X    *str++ = '-';
X    bignum = BN_neg(bignum);
X  }
X
X  /* Strip off numbers in reverse order: */
X  i = 0;
X  do
X  {
X    bignum = BN_div(bignum, BN_10);
X    str[i++] = '0' + BN_remainder.N[0];
X  } while (BN_gt(bignum, BN_0));
X  str[i] = '\0';
X
X  /* Reverse the order of output string: */
X  j = 0;
X  k = i - 1;
X  while (j < k)
X  {
X    tmp = str[j];
X    str[j++] = str[k];
X    str[k--] = tmp;
X  }
X
X  /* Return the string size: */
X  return (i);
X}
X
X
X/******************************************************************************
X
X  itoBN -- Convert a 32 bit integer to a BigNum.
X
X *****************************************************************************/
X
XBN itoBN(num)
X     int num;
X{
X  BN bignum;
X  int i, filler;
X
X  /* Assign num to first 32 bits of bignum and add the appropriate
X     filler for the remaining bits depending on the sign: */
X
X  bignum.N[0] = num;
X  if (num < 0)
X    filler = -1;
X  else
X    filler = 0;
X
X  for (i = 1; i < BN_SIZE; i++)
X    bignum.N[i] = filler;
X
X  return (bignum);
X}
X
X
X/******************************************************************************
X
X  BNtoi -- Convert a BigNum to a 32 bit integer.
X
X  User is warned if any truncation occurs.
X
X *****************************************************************************/
X
Xint BNtoi(bignum)
X     BN bignum;
X{
X# define  BN_abs(bn)  (MASKSIGN(bn) ? BN_neg(bn) : bn)
X
X  if (BN_gt (BN_abs(bignum), itoBN(0x7fffffff)))
X    (void)printf ("BNtoi: integer truncated\n");
X
X  /* Return the lowest 32 bits of a bignum: */
X  return ((int)bignum.N[0]);
X}
X
X
X/******************************************************************************
X
X  BN_mult -- Multiply two BigNums.
X
X  BN_overflow is set if any overflow occurs.
X
X *****************************************************************************/
X
XBN BN_mult(multiplicand,multiplier)
X     BN multiplicand,multiplier;
X{
X  BN result;
X  Boolean s1,s2;
X  register Boolean danger;
X  register int i,j;
X
X  /* Note whether either argument is negative and make sure both of them
X     are positive: */
X  s1 = MASKSIGN(multiplicand);
X  s2 = MASKSIGN(multiplier);
X  if (s1) multiplicand = BN_neg(multiplicand);
X  if (s2) multiplier = BN_neg(multiplier);
X
X  /* Perform multiplication by shifting the multiplicand and performing an
X     addition whenever a '1' appears in the multiplier: */
X  danger = FALSE;
X  result = BN_0;
X  for (i = 0; i < BN_SIZE; i++)
X  {
X    for (j = 0; j < 32; j++)
X    {
X      if (BN_eq (multiplier, BN_0)) break;
X      if (multiplier.N[0] & 1)
X      {
X	/* BN_add also detects certain overflows. */
X	result = BN_add(result,multiplicand);
X	/* Overflow occurs either by addition or by adding the multiplicand
X	   after shifting it out of range. */
X	BN_overflow = BN_overflow || danger;
X      }
X      lshift1(&multiplicand);
X      rshift1(&multiplier);
X      danger = danger || (MASKSIGN(multiplicand) ? TRUE : FALSE);
X    }
X  }
X
X  /* Ensure the result has the appropriate sign: */
X  if (s1 != s2) result = BN_neg(result);
X
X  return (result);
X}
X
X
X/******************************************************************************
X
X  BN_div -- Divide the dividend by the divisor.
X
X  The User is notified and program terminated if division by 0 occurs.
X  The global variable BN_remainder contains the remainder of the most
X  recent division.
X
X *****************************************************************************/
X
XBN BN_div(dividend,divisor)
X     BN dividend,divisor;
X{
X  BN result,power;
X  register int nshifts;
X  Boolean s1,s2;
X
X  if (BN_eq(divisor, BN_0))
X  {
X    (void)printf("BN_div: division by 0\n");
X    exit (1);
X  }
X
X  /* Note whether either argument is negative and make sure both of them
X     are positive: */
X  s1 = MASKSIGN(dividend);
X  s2 = MASKSIGN(divisor);
X  if (s1) dividend = BN_neg(dividend);
X  if (s2) divisor = BN_neg(divisor);
X
X  /* Perform division by shifting the divisor up by powers of two until
X     it is greater than the dividend.  Next shift the divisor down in
X     powers of two--each time the dividend can be divided by the divisor
X     tally the current power of two and reduce the dividend accordingly: */
X  power = BN_1;
X  nshifts = 0;
X  while (MASKSIGN(divisor) == 0 && BN_ge(dividend,divisor))
X  {
X    lshift1(&divisor);
X    lshift1(&power);
X    nshifts++;
X  }
X  result = BN_0;
X  while (nshifts > 0)
X  {
X    rshift1(&divisor);
X    rshift1(&power);
X    nshifts--;
X    if (BN_ge(dividend,divisor))
X    {
X      result = BN_add(result,power);
X      dividend = BN_sub(dividend,divisor);
X    }
X  }
X  
X  /* Ensure the result has the appropriate sign and make the remainder
X     globally available: */
X  if (s1 != s2) result = BN_neg(result);
X  BN_remainder = dividend;
X
X  return (result);
X}
X
X
X/******************************************************************************
X
X  BN_sub -- Subtract arg2 from arg1.
X
X  BN_overflow is set if any overflow occurs.
X
X *****************************************************************************/
X
XBN BN_sub(arg1,arg2)
X     BN arg1,arg2;
X{
X  /* Perform subtraction by negating the subtrahend and then adding
X     both numbers: */
X  return (BN_add(arg1,BN_neg(arg2)));
X}
X
X
X/******************************************************************************
X
X  BN_add -- Add two BigNums.
X
X  BN_overflow is set if any overflow occurs.
X
X *****************************************************************************/
X
XBN BN_add(arg1,arg2)
X     BN arg1,arg2;
X{
X  BN result;
X  register int i;
X  register int ssum;
X  register int a1,a2,carry;
X  int criterion;
X
X  /* Perform addition in 32 bit chunks by first striping off the sign
X     bits of each chunk, adding the numbers, manually appending the
X     sign bit, and then generating a carry if necessary: */
X
X  carry = 0;
X  for (i = 0; i < BN_SIZE; i++)
X  {
X    a1 = arg1.N[i] & 0x7fffffff;
X    a2 = arg2.N[i] & 0x7fffffff;
X    result.N[i] = a1 + a2 + carry;
X
X    ssum = 0;
X    if (arg1.N[i] & 0x80000000) ssum++;
X    if (arg2.N[i] & 0x80000000) ssum++;
X    if (result.N[i] & 0x80000000) ssum++;
X
X    if (ssum == 0)
X    {
X      carry = 0;
X    }
X    else if (ssum == 1)
X    {
X      result.N[i] |= 0x80000000;
X      carry = 0;
X    }
X    else if (ssum == 2)
X    {
X      result.N[i] &= 0x7fffffff;
X      carry = 1;
X    }
X    else /* (ssum == 3) */
X    {
X      carry = 1;
X    }
X  }
X
X  /* Check for overflow.  The overflow "criterion" is always an even
X     number unless an overflow occurs: */
X  criterion = ((MASKSIGN(arg1) ? 1 : 0) +
X	       (MASKSIGN(arg2) ? 1 : 0) +
X	       (MASKSIGN(result) ? 1 : 0) +
X	       carry);
X  BN_overflow = BN_overflow || (criterion == 1 || criterion == 3);
X
X  return (result);
X}
X
X
X/******************************************************************************
X
X  BN_neg -- Negate a BigNum.
X
X *****************************************************************************/
X
XBN BN_neg(arg)
X     BN arg;
X{
X  register int i;
X
X  /* Perform negation a la two's complement (i.e. perform a bitwise
X     complement and then add 1): */
X
X  for (i = 0; i < BN_SIZE; i++)
X    arg.N[i] = ~arg.N[i];
X
X  return (BN_add(arg,BN_1));
X}
X
X
X/******************************************************************************
X
X  BN_ge --  Test if arg1 is greater than or equal to arg2.
X
X *****************************************************************************/
X
XBoolean BN_ge(arg1,arg2)
X     BN arg1,arg2;
X{
X  return (!BN_lt(arg1,arg2));
X}
X
X
X/******************************************************************************
X
X  BN_le --  Test if arg1 is less than or equal to arg2.
X
X *****************************************************************************/
X
XBoolean BN_le(arg1,arg2)
X     BN arg1,arg2;
X{
X  return (BN_lt(arg1,arg2) || BN_eq(arg1,arg2));
X}
X
X
X/******************************************************************************
X
X  BN_gt --  Test if arg1 is greater than arg2.
X
X *****************************************************************************/
X
XBoolean BN_gt(arg1,arg2)
X     BN arg1,arg2;
X{
X  return (!BN_lt(arg1,arg2) && !BN_eq(arg1,arg2));
X}
X
X
X/******************************************************************************
X
X  BN_lt --  Test if arg1 is less than arg2.
X
X *****************************************************************************/
X
XBoolean BN_lt(arg1,arg2)
X     BN arg1,arg2;
X{
X  Boolean s1,s2;
X  register int i;
X
X  /* Test if arg1 is less than arg2 by first comparing signs.  If both
X     signs are different, then the rest is easy.  If both signs are the
X     same then begin looking from the high order bits down to the low
X     order bits until a difference is detected: */
X
X  s1 = (MASKSIGN(arg1) ? TRUE : FALSE);
X  s2 = (MASKSIGN(arg2) ? TRUE : FALSE);
X
X  if (s1 && !s2)
X    return (TRUE);
X  else if (!s1 && s2)
X    return (FALSE);
X  else
X    for (i = BN_SIZE-1; i >= 0; i--)
X      if (arg1.N[i] != arg2.N[i])
X      {
X	if (arg1.N[i] < arg2.N[i])
X	  return (TRUE);
X	else /* (arg1.N[i] > arg2.N[i]) */
X	  return (FALSE);
X      }
X  return (FALSE);
X}
X
X
X/******************************************************************************
X
X  BN_ne --  Test if arg1 is not equal to arg2.
X
X *****************************************************************************/
X
XBoolean BN_ne(arg1,arg2)
X     BN arg1,arg2;
X{
X  return(!BN_eq(arg1,arg2));
X}
X
X
X/******************************************************************************
X
X  BN_eq --  Test if arg1 is equal to arg2.
X
X *****************************************************************************/
X
XBoolean BN_eq(arg1,arg2)
X     BN arg1,arg2;
X{
X  register int i;
X
X  for (i = 0; i < BN_SIZE; i++)
X    if (arg1.N[i] != arg2.N[i]) return (FALSE);
X
X  return (TRUE);
X}
X
X
X/******************************************************************************
X
X  lshift1 -- Perform a logical left shift one bit possition.
X
X *****************************************************************************/
X
XLocal Nil lshift1(arg)
X     register BN *arg;
X{
X  register int i;
X
X  for (i = BN_SIZE - 1; i > 0; i--)
X  {
X    arg->N[i] = arg->N[i] << 1;
X    if (arg->N[i-1] & 0x80000000)
X      arg->N[i] |= 1;
X  }
X
X  arg->N[0] = arg->N[0] << 1;
X
X  return;
X}
X
X
X/******************************************************************************
X
X  rshift1 -- Perform a logical right shift one bit possition.
X
X *****************************************************************************/
X
XLocal Nil rshift1(arg)
X     register BN *arg;
X{
X  register int i;
X
X  for (i = 0; i < BN_SIZE - 1; i++)
X  {
X    arg->N[i] = arg->N[i] >> 1;
X    if (arg->N[i+1] & 1)
X      arg->N[i] |= 0x80000000;
X  }
X
X  arg->N[BN_SIZE-1] = arg->N[BN_SIZE-1] >> 1;
X
X  return;
X}
*-*-END-of-BN.c-*-*
echo x - BN.h
sed 's/^X//' >BN.h <<'*-*-END-of-BN.h-*-*'
X/******************************************************************************
X  BN.h -- A library for performing arithmetic operations on arbitrarily
X  	  long integers.
X
X  Author: Mark Baranowski (markb at signus.utah.edu)
X
X  Version: 1.0
X  Date: Aug. 20, 1990
X
X  This program is provided "as is" without any warranty of its
X  correctness or of its fitness for a particular purpose.  You may
X  freely distribute and modify this program as long as this header
X  remains intact.
X
X *****************************************************************************/
X
X/* Number of 32 bit chunks used by BigNum--BN_SIZE must be at least 1 and
X   can be any desired maximum: */
X#define BN_SIZE 5
X
X/* BN data structure: */
Xstruct BN
X{
X  unsigned int N[BN_SIZE];
X};
Xtypedef struct BN BN;
X
Xtypedef int Boolean;
X#define TRUE 1
X#define FALSE 0
X
X/* BigNum remainder following division: */
Xextern BN BN_remainder;		/* Valid only until next operation */
X
X/* BigNum overflow condition following add, subtract, or multiply: */
Xextern Boolean BN_overflow;	/* Valid until reset by the user */
X
X/* Globally defined funtions: */
Xextern BN  atoBN (/* char *str */);
Xextern int BNtoa (/* BN bignum, char *str */);
Xextern BN  itoBN (/* int num */);
Xextern int BNtoi (/* BN bignum */);
X
Xextern BN BN_mult(/* BN arg1, BN arg2 */);
Xextern BN BN_div (/* BN arg1, BN arg2 */);
Xextern BN BN_sub (/* BN arg1, BN arg2 */);
Xextern BN BN_add (/* BN arg1, BN arg2 */);
Xextern BN BN_neg (/* BN arg1 */);
X
Xextern Boolean BN_ge(/* BN arg1, BN arg2 */);
Xextern Boolean BN_le(/* BN arg1, BN arg2 */);
Xextern Boolean BN_gt(/* BN arg1, BN arg2 */);
Xextern Boolean BN_lt(/* BN arg1, BN arg2 */);
Xextern Boolean BN_ne(/* BN arg1, BN arg2 */);
Xextern Boolean BN_eq(/* BN arg1, BN arg2 */);
*-*-END-of-BN.h-*-*
exit


-- 
Internet: markb at slc.unisys.com			uucp: ...!giga!markb
	  markb at signus.utah.edu
Brought to you by the Great State of Utah: Home of Gary Gilmore, Syncrete,
Cold Fusion, Mark Hoffman, Sonja Johnson, John Singer, and Sen. Orrin Hatch.



More information about the Alt.sources mailing list