OJ Board

Hi

How can I deal with *huge* integers (more than 10^50 for example, see 10007th problem) ? I've heard of <openssl/bn.h>, but I don't know if it is allowed in ACM.
Otherwise, do you think it is light enough to dynamically store the integers in decimal form in a char*, and to implement addition and multiplication the same way one does with a paper and a pen ?

All advices are welcome
Thanks
Julien

Well, openssl/bn.h is not part of ANSI C, so it's most likely either forbidden or not accessible at all.

The do-it-yourself method with arrays is the usual way, yes. And if you want to make it faster, use int[] and base 10000 instead of char[] and base 10.

You can also look at the sourcecode of java.math.BigInteger...

Stefan

Okay

Thank you very much for your answer

I have a problem in big integer too.
See problem 113
And i don't have java so i can't see the java.math

Can you explained a little more about int[] and 10000 base

Thank you

You may find StrAdd and StrMul useful.
StrAdd adds two positive integers (<=8000 digits) and returns the result as a string.
StrMul multiplies two positive integers (<=2000 digits) and returns the result as a string.

If there are bugs, let me know.
[c]
int StrToInt(char *p, long *a, int ndigit)
{
int len = strlen(p);
int i, j=0, k = 0;
char t[9];
int q = len/ndigit, r = len%ndigit;

for(i=0; i<r; i++)
t = p;
t = 0;

if(i>0)
{
j = q;
a[j--] = atol(t);
}
else j = q-1;

for(i=0; i<q; i++)
{
for(k=0; k<ndigit; k++)
t[k] = p[r+i*ndigit+k];
t[k] = 0;
a[j--] = atol(t);
}
return (q + ((r==0)?0:1));
}
char * ltoa(long x, int zero, int ndigit)
{
char s[100], t[100];
int i = 0, j = 0, k;
while(x) { s[i++] = x%10+'0'; x/=10; }
if(zero) for(j=0; j<ndigit-i; j++) t[j] = '0';
for(k=j, --i; i>=0; k++, i--)
t[k] = s;
t[k] = 0;
return t;
}

char * StrAdd(char * p1, char * p2)
{
long A[1000], B[1000], C[1000];
int i, j; long carry = 0;
for(i=0; i<1000; i++) A=B=C=0;
int n1 = StrToInt(p1, A, 8);
int n2 = StrToInt(p2, B, 8);
for(i=0; i < ((n1>n2) ? n1 : n2); i++)
{
C = (A+B+carry)%100000000L;
carry = (A[i]+B[i]+carry)/100000000L;
}
if(carry) C[i++] = carry;
char Str[4000] = "";
strcat(Str, ltoa(C[i-1], 0, 8));
for(j=i-2; j>=0; j--)
strcat(Str, ltoa(C[j], 1, 8));
return Str;
}

int AllZero(char *p)
{
for(int i=0; i<strlen(p); i++)
if(p[i]!='0') return 0;
return 1;
}

char * StrMul(char * p1, char * p2)
{
long A[500], B[500], C[500];
int i, j, k; long carry = 0;
int n1 = StrToInt(p1, A, 4);
int n2 = StrToInt(p2, B, 4);
char Prev[4000] = "0";
for(i=0; i < n1; i++)
{
carry = 0;
for(j=0; j<n2; j++)
{
C[j] = (A[i]*B[j]+carry)%10000L;
carry = (A[i]*B[j]+carry)/10000L;
}
if(carry) C[j++] = carry;
char Str[4000] = "";
strcat(Str, ltoa(C[j-1], 0, 4));
for(k=j-2; k>=0; k--)
strcat(Str, ltoa(C[k], 1, 4));
for(k=0; k<i; k++) strcat(Str, "0000");
char t[4000];
strcpy(t, StrAdd(Prev, Str));
strcpy(Prev, t);
}
if(AllZero(Prev)) return "0";
else return Prev;
}
[/c]

String Division or Remainder? Can you provide that?

113 is slightly different... the numbers are big, but not so big that there's no variable type to hold the answer. Think double

Can any body paste a pure, error free, readable and fast string arithmatic routines ?