Can't Copy and Paste this?
Click here for a copy-and-paste friendly version of this code!
//**************************************
//
//INCLUDE files for :Big Num Part #1: Ad
// d, subtract, and multiply BigNum's
//**************************************
//
/* +++Date last modified: 05-Jul-1997 */
/* BIGNUM.H
**
** Header file with definition of BigNum type for Big Number Arithmetic.
**
** Released to the public domain by Clifford Rhodes on June 15, 1995 with
** no guarantees of any sort as to accuracy or fitness of use.
*/
/* Each int in the Big Number array will hold a digit up to MODULUS - 1.
** Choosing 10000 makes testing easy because each digit contains 4 decimal
** places.
*/
#ifndef BIGNUM__H
#define BIGNUM__H
#include "minmax.h"
#define MODULUS 10000 /* Warning: Must be <= USHRT_MAX! */
typedef unsigned short UShort;
typedef unsigned long ULong;
/* The Big Number is contained in a structure that has a length, nlen, and
** an array, n[], of unsigned shorts to hold the 'digits'. The most
** significant digit of the big number is at n[0]. The least significant
** digit is at n[nlen - 1];
*/
typedef struct {
int nlen;/* Number of int's in n */
UShort *n;/* Array of unsigned shorts to hold the number */
} BigNum;
/* Arithmetic function prototypes */
BigNum * BigNumAdd(const BigNum *a, const BigNum *b);
BigNum * BigNumSub(const BigNum *a, const BigNum *b);
BigNum * BigNumMul(const BigNum *a, const BigNum *b);
BigNum * BigNumDiv(const BigNum *a, const BigNum *b, BigNum **c);
BigNum * BigNumAlloc(int nlen);
voidBigNumFree(BigNum *b);
#endif /* BIGNUM__H */
code:
Can't Copy and Paste this?
Click here for a copy-and-paste friendly version of this code!
Terms of Agreement:
By using this code, you agree to the following terms...
1) You may use this code in your own programs (and may compile it into a program and distribute it in compiled format for langauges that allow it) freely and with no charge.
2) You MAY NOT redistribute this code (for example to a web site) without written permission from the original author. Failure to do so is a violation of copyright laws.
3) You may link to this code from another website, but ONLY if it is not wrapped in a frame.
4) You will abide by any additional copyright restrictions which the author may have placed in the code or code's description.
/* +++Date last modified: 05-Jul-1997 */
/* BIGNUM1.C
**
** Routines to do Big Number Arithmetic. These are multi-precision, unsigned
** natural numbers (0, 1, 2, ...). for the storage method, see the BigNum
** typedef in file BIGNUM.H
**
** Released to the public domain by Clifford Rhodes, June 15, 1995, with
** no guarantees of any sort as to accuracy or fitness of use.
*/
#include
#include "bignum.h" /* typedef for BigNum type */
BigNum * BigNumAdd(const BigNum * a, const BigNum * b)
{
/* Big Numbers a and b are added. if successful a pointer to the sum is
** returned. if unsuccessful, a NULL is returned.
** Neither a nor b is changed by the call.
*/
UShort carry = 0;
intsize, la, lb;
long tsum;
BigNum * sum;
/* Allocate memory for Big Number sum to be returned... */
size = max(a->nlen, b->nlen) + 1;
if ((sum = BigNumAlloc(size)) == NULL)
return NULL;
/* Get indexes to last digits in each number (Least significant) */
la = a->nlen - 1;
lb = b->nlen - 1;
size--;
while (la >= 0 && lb >= 0) /* While both a and b have data */
{
tsum = carry + (long) *(a->n + la) + (long) *(b->n + lb);
*(sum->n + size) = (UShort) (tsum % (long) MODULUS);
carry = (tsum / (long) MODULUS) ? 1 : 0;
la--;
lb--;
size--;
}
if (lb < 0) /* Must see if a still has data */
{
while (carry && la >= 0)
{
tsum = carry + (long) *(a->n + la);
*(sum->n + size) = (UShort) (tsum % (long) MODULUS);
carry = (tsum / (long) MODULUS) ? 1 : 0;
la--;
size--;
}
while (la >= 0)
{
*(sum->n + size) = *(a->n + la);
la--;
size--;
}
}
else /* See if b still has data */
{
while (carry && lb >= 0)
{
tsum = carry + (long) *(b->n + lb);
*(sum->n + size) = (UShort) (tsum % (long) MODULUS);
carry = (tsum / (long) MODULUS) ? 1 : 0;
lb--;
size--;
}
while (lb >= 0)
{
*(sum->n + size) = *(b->n + lb);
lb--;
size--;
}
}
*(sum->n + size) = carry;
return sum;
}
BigNum * BigNumSub(const BigNum * a, const BigNum * b)
{
/* Big Numbers a and b are subtracted. a must be >= to b. A pointer to
** the difference (a - b) is returned if successful. If unsuccessful,
** a NULL is returned.
** Neither a nor b is changed by the call.
*/
intsize, la, lb, borrow = 0;
longtdiff;
BigNum * diff;
/* Allocate memory for Big Number difference to be returned... */
if ((diff = BigNumAlloc(a->nlen)) == NULL)
return NULL;
la = a->nlen - 1;
size = la;
lb = b->nlen - 1;
while (lb >= 0)
{
tdiff = (long) *(a->n + la) - (long) *(b->n + lb) - borrow;
if (tdiff < 0)
{
tdiff += (long) (MODULUS - 1);
borrow = 1;
}
else borrow = 0;
*(diff->n + size) = (UShort) tdiff + borrow;
la--;
lb--;
size--;
}
while (la >= 0) /* Must get rest of a->n */
{
tdiff = (long) *(a->n + la) - borrow;
if (tdiff < 0)
{
tdiff += (long) (MODULUS - 1);
borrow = 1;
}
else borrow = 0;
*(diff->n + size) = (UShort) tdiff + borrow;
la--;
size--;
}
if (borrow) /* We've got an underflow here! */
{
BigNumFree(diff);
return NULL;
}
return diff;
}
BigNum * BigNumMul(const BigNum * a, const BigNum * b)
{
/* Big Numbers a and b are multiplied. A pointer to the product
** is returned if successful. If unsuccessful, a NULL is returned.
** Neither a nor b is changed by the call.
*/
intsize, la, lb, apos, bpos, ppos;
UShort carry;
BigNum * product;
/* Allocate memory for Big Number product to be returned... */
size = a->nlen + b->nlen;
if ((product = BigNumAlloc(size)) == NULL)
return NULL;
la = a->nlen - 1;
lb = b->nlen - 1;
size--;
bpos = lb;
while (bpos >= 0)/* We'll multiply by each digit in b */
{
ppos = size + (bpos - lb); /* Position in product */
if (*(b->n + bpos) == 0) /* If zero multiplier, skip this pass */
ppos = ppos - la - 1;
else /* Multiply a by next b digit */
{
apos = la;
carry = 0;
while (apos >= 0) /* Go a digit at a time through a */
{
ULong temp;
temp = (ULong) *(a->n + apos) *
(ULong) *(b->n + bpos) + carry;
/*
** We must add any previous product term in
** this 'column' too
*/
temp += (ULong) *(product->n + ppos);
/* Now update product term, remembering any carry */
*(product->n + ppos) =
(UShort) (temp % (ULong) MODULUS);
carry = (UShort) (temp / (ULong) MODULUS);
apos--;
ppos--;
}
*(product->n + ppos) = carry;
}
bpos--;
}
return product;
}