Source Code 1992 March/Source_Code_CD-ROM_Walnut_Creek_March_1992.iso/usenet/altsrcs/1/1712

Internet Message Format | 1990-12-28 | 20.4 KB

From: [e-mail] (Mark Baranowski)
Newsgroups: alt.sources
Subject: BN.c: Performing arithmetic on arbitrarily long integers
Message-ID: <[e-mail]>
Date: 21 Aug 90 21:57:15 GMT


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 ([e-mail])
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 ([e-mail])
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: [e-mail]            uucp: ...!giga!markb
      [e-mail]
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.