Chittagong University of Enginnering and Technology, Bangladesh

ACMBEGINNER

 

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)

return add_bignum(b,a,c);

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;

n_borrow = add_bignum(a,b,c);

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);

      add_bignum(n3,&b,&temp);

      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);

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

      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");

}

}

 

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

  http://www.amazon.com/exec/obidos/ASIN/0387001638/thealgorithmrepo/

 

Copyright 2003 M H Rasel
[
Webmaster]
Last modified

1