Home\ Tutorial \ Bignum Version 2.0
 BIG INTEGER

/*

bignum.cpp

Implementation of large integer arithmetic: addition, subtraction, multiplication,and division.

Compiled : CYGNU & Microsoft Visual C++ 6.0

Copyright 2003 by M H Rasel & CUET Old Sailor ; all rights reserved.

Permission is granted for use in non-commerical applications provided this copyrightnotice remains intact and

unchanged.

*/

#include <stdio.h>

#include<string.h>

#include<math.h>

#define   MAXDIGITS   100    /* maximum length bignum */

#define PLUS     1           /* positive sign bit */

#define MINUS    -1          /* negative sign bit */

#define max(a,b) ((a>b)?a:b)

typedef struct {

char digits[MAXDIGITS]; /* represent the number */

int signbit;            /* 1 if positive, -1 if negative */

int lastdigit;          /* index of high-order digit */

} bignum;

print_bignum(bignum *n);

int_to_bignum(int s, bignum *n);

initialize_bignum(bignum *n);

int add_bignum(bignum *a, bignum *b, bignum *c);

int subtract_bignum(bignum *a, bignum *b, bignum *c);

zero_justify(bignum *n);

compare_bignum(bignum *a, bignum *b);

/* ************************************** */

/*      print a Big integer               */

/*      Input : A big integer pointer     */

/*      Return : None                     */

/* ************************************** */

print_bignum(bignum *n)

{

int i;

if (n->signbit == MINUS) printf("- ");

printf(n->digits);

//   printf("\n");

}

/* *********************************************** */

/*      Convert an integer into big integer        */

/*      Input : A integer and a big integer        */

/*              pointer                            */

/*      Return : None                              */

/* *********************************************** */

int_to_bignum(int s, bignum *n)

{

if (s >= 0) n->signbit = PLUS;

else n->signbit = MINUS;

int t = abs(s);

sprintf(n->digits,"%d",t);

n->lastdigit=strlen(n->digits);

}

/* ************************************************ */

/*      Convert an char array into big integer      */

/*      Input : A string  and a big integer         */

/*              pointer                             */

/*      Return : None                               */

/* ************************************************ */

int_to_bignum(char *s, bignum *n)

{

int i;

if (s[0] != -1)

{

n->signbit = PLUS;

i = 0;

}

else

{  i = 1;

n->signbit = MINUS;

}

strcpy(n->digits,&s[i]);

n->lastdigit = strlen(n->digits);

}

/* **************************************** */

/*      Inatilize a zero integer            */

/*      Input : A big integer pointer       */

/*      Return : None                       */

/* **************************************** */

initialize_bignum(bignum *n)

{   int_to_bignum(0,n);    }

/* *********************************************************** */

/*      Add two big integer                                    */

/*      Input : Three big integer pointer a,b,c                */

/*              where a & b is argument of addition            */

/*              and c is the result. c = a + b                 */

/*      Return : Number of carry                               */

/* *********************************************************** */

int add_bignum(bignum *a, bignum *b, bignum *c)

{

int carry;                /* carry digit */

int i,j,op=0;;            /* counter */

int n_carry,temp;

initialize_bignum(c);

if (a->signbit == b->signbit)

c->signbit = a->signbit;

else

{

if (a->signbit == MINUS)

{

a->signbit = PLUS;

n_carry = subtract_bignum(b,a,c);

a->signbit = MINUS;

}

else

{

b->signbit = PLUS;

n_carry = subtract_bignum(a,b,c);

b->signbit = MINUS;

}

return n_carry;

}

if(a->lastdigit < b->lastdigit)

int k = c->lastdigit = a->lastdigit+1;

c->digits[k--]='\0';

carry = 0;

n_carry = 0;

for(i=b->lastdigit-1,j=a->lastdigit-1;i>=0;i--,j--)

{

carry = b->digits[i]-'0'+a->digits[j]-'0'+carry;

c->digits[k--]= (carry%10)+'0';

carry=carry/10;

if(carry)

n_carry++;

}

for(;j>=0;j--)

{

carry = a->digits[j]-'0'+carry;

c->digits[k--] = (carry % 10)+'0';

carry = carry/10;

if(carry)

n_carry++;

}

if(carry)

c->digits[k]=carry+'0';

else

{

char string[MAXDIGITS];

strcpy(string,&c->digits[1]);

strcpy(c->digits,string);

c->lastdigit=c->lastdigit - k - 1;

}

return n_carry;

}

/* ************************************************************ */

/*      Subtract two big integer                                */

/*      Input : Three big integer pointer a,b,c                 */

/*              where a & b is argument of subtraction          */

/*            and c is the result.                              */

/*      Return : Number of borrow                               */

/* ************************************************************ */

int subtract_bignum(bignum *a, bignum *b, bignum *c)

{

int borrow;                      /* has anything been borrowed? */

int v;                           /* placeholder digit */

register int i,j,op=0;           /* counter */

int n_borrow;

int temp;

c->signbit = PLUS;

if ((a->signbit == MINUS) || (b->signbit == MINUS))

{

b->signbit = -1 * b->signbit;

b->signbit = -1 * b->signbit;

return n_borrow;

}

if (compare_bignum(a,b) == PLUS)

{

n_borrow = subtract_bignum(b,a,c);

c->signbit = MINUS;

return n_borrow;

}

int k = c->lastdigit = max(a->lastdigit,b->lastdigit);

n_borrow=0;

c->digits[k--]='\0';

for(i=a->lastdigit-1,j=b->lastdigit-1;j>=0;i--,j--)

{

temp = a->digits[i]-'0'-( b->digits[j]-'0'+op);

if(temp < 0)

{

temp += 10;

op=1;

n_borrow++;

}

else op=0;

c->digits[k--]= temp+'0';

}

while(op)

{

temp = a->digits[i--]-op-'0';

if(temp < 0)

{

temp += 10;

op=1;

n_borrow++;

}

else op=0;

c->digits[k--]= temp+'0';

}

for(;i>=0;i--)

c->digits[k--]=a->digits[i];

for(i=0;!(c->digits[i]-'0');i++);

c->lastdigit = c->lastdigit - i;

if(i==a->lastdigit)

strcpy(c->digits,"0");

else

{

char string[MAXDIGITS];

strcpy(string,&c->digits[i]);

strcpy(c->digits,string);

}

return n_borrow;

}

/* **************************************************** */

/*      Compare two big integer                         */

/*      Input : Two big integer pointer a,b             */

/*      Return : 0,1 or -1,                             */

/*               0 for a=b                              */

/*               1 for a < b                            */

/*               -1 for a>b                             */

/* **************************************************** */

compare_bignum(bignum *a, bignum *b)

{

int i;           /* counter */

if ((a->signbit == MINUS) && (b->signbit == PLUS)) return(PLUS);

if ((a->signbit == PLUS) && (b->signbit == MINUS)) return(MINUS);

if (b->lastdigit > a->lastdigit) return (PLUS * a->signbit);

if (a->lastdigit > b->lastdigit) return (MINUS * a->signbit);

for (i = 0;  i < a->lastdigit; i++ )

{

if (a->digits[i] > b->digits[i]) return(MINUS * a->signbit);

if (b->digits[i] > a->digits[i]) return(PLUS * a->signbit);

}

return(0);

}

/* *************************************************************** */

/*      Multiply two big integer                                   */

/*      Input : Three big integer pointer a,b,c                    */

/*              where a & b is argument of multiplication          */

/*            and c is the result.                                 */

/*      Return : Number of borrow                                  */

/* *************************************************************** */

multiply_bignum(bignum *a, bignum *b, bignum *c)

{

long int n_d;

register long int i,j,k;

short int num1[MAXDIGITS],num2[MAXDIGITS],of=0,res[MAXDIGITS]={0};

n_d=(a->lastdigit<b->lastdigit)?b->lastdigit:a->lastdigit;

n_d++         ;

for(i=0,j= a->lastdigit-1;i< a->lastdigit ;i++,j--)

num1[i]=a->digits[j]-48;

for(i=0,j= b->lastdigit-1;i< b->lastdigit ;j--,i++)

num2[i]=b->digits[j]-48;

res[0]=0;

for(j=0;j< b ->lastdigit;j++)

{   for(i=0,k=j;i< a->lastdigit || of;k++,i++)

{   if(i<a->lastdigit)

res[k] += num1[i] * num2[j] + of;

else   res[k] += of;

of=res[k]/10;

res[k]=res[k]%10;

}

}

for(i=k-1,j=0;i>=0;i--,j++)

c->digits[j]=res[i]+48;

c->digits[j]='\0';

c->lastdigit=k;

c->signbit = a->signbit*b->signbit;

}

/* ******************************************************* */

/*      Copy one big integer into another                  */

/*      Input : Two big integer pointer a,b                */

/*              where a is destinition & b source          */

/*      Return : None                                      */

/* ******************************************************* */

copy(bignum *a, bignum *b)

{

a->lastdigit=b->lastdigit;

a->signbit = b->signbit;

strcpy(a->digits,b->digits);

}

/* **************************************************************** */

/*      Divide two big integer                                      */

/*      Input : FOur big integer pointer n1,n2,n3,n4                */

/*              where n1 & n2 is argument of dividition,              */

/*              n3 is the result and n4 is module                     */

/*      Return : None                                               */

/* **************************************************************** */

divide_bignum(bignum *n1,bignum *n2,bignum *n3,bignum *n4)

{

initialize_bignum(n3);

bignum a,b,temp;

a.signbit=b.signbit=temp.signbit=PLUS;

int asign = n1->signbit;

n1->signbit = PLUS;

int bsign = n2->signbit;

n2->signbit = PLUS;

temp.lastdigit=0;

int_to_bignum(1,&b);

copy(&a,n1);

while(compare_bignum(&a,n2)<1)

{

subtract_bignum(&a,n2,n4);

copy(&a,n4);

copy(n3,&temp);

}

n1->signbit = asign;

n2->signbit = bsign;

n3->signbit = n1->signbit * n2->signbit;

if(n4->digits[0] !='0')

n4->signbit = asign;

}

/* A Sample Main Function */

main()

{

int a,b;

bignum n1,n2,n3,zero,n4;

while (scanf("%d%d",&a,&b) != EOF)

{

printf("a = %d    b = %d\n",a,b);

int_to_bignum(a,&n1);

int_to_bignum(b,&n2);

print_bignum(&n1);

putchar('\n');

print_bignum(&n2);

printf("addition -- \n carry = %d\n res = ",a);

print_bignum(&n3);

printf("compare_bignum a ? b = %d\n",compare_bignum(&n1, &n2));

a = subtract_bignum(&n1,&n2,&n3);

printf("subtraction -- ");

printf("\nborrow %d \nres ",a);

print_bignum(&n3);

multiply_bignum(&n1,&n2,&n3);

printf("multiplication -- ");

print_bignum(&n3);

putchar('\n');

int_to_bignum(0,&zero);

if (compare_bignum(&zero, &n2) == 0)

printf("division -- NaN \n");

else

{

divide_bignum(&n1,&n2,&n3,&n4);

printf("division -- ");

print_bignum(&n3);

putchar('\n');

print_bignum(&n4);

}

printf("\n--------------------------\n");

}

}

 Related Problems 324 Factorial Frequencies 424 Integer Inquiry 623 500! 713 Adding Reversed Numbers 10013 Super long sums 10018 Reverse and Add 10035 Primary Arithmetic 10106 Product 10220 I Love Big Numbers ! 10015 Powers Et Al.

You can also get a big help about the big integer from the book "Programming Challenges: The Programming Contest Training Manual" by Steven Skiena and Miguel Revilla, Springer-Verlag, New York 2003. See its website www.programming-challenges.com for additional information. This book can be ordered from Amazon.com at

 ProblemSet Tricks | Reference | Tutorial FAQ|Index|Info Credits|Guestbook|Update