markb@giga.slc.unisys.com (Mark Baranowski) (08/22/90)
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@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@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@slc.unisys.com uucp: ...!giga!markb
markb@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.