Arbitrary Precision Arithmatic : BigInteger Algorithm
Moderator: Board moderators
Arbitrary Precision Arithmatic : BigInteger Algorithm
Hi,
Followed from the previous mail this is my first posting on sharing algorithms. As lot of problems involves operation on arbitrary precision integer I am starting with this one.
Here is the BigInteger class, as named in Java library. I created this a lot many times in different way. This version is not completed fully. I would like to see comments and improvement suggestion on it. The algorithm on addition, subtraction, multiplication and division are from chapter 4.3 of
Followed from the previous mail this is my first posting on sharing algorithms. As lot of problems involves operation on arbitrary precision integer I am starting with this one.
Here is the BigInteger class, as named in Java library. I created this a lot many times in different way. This version is not completed fully. I would like to see comments and improvement suggestion on it. The algorithm on addition, subtraction, multiplication and division are from chapter 4.3 of
Last edited by suman on Wed Nov 20, 2002 2:08 pm, edited 1 time in total.
 Moni
 Experienced poster
 Posts: 202
 Joined: Fri Mar 22, 2002 2:00 am
 Location: Chittagong. CSE  CUET
 Contact:
Hi! Suman!
It's fine! Your implementation is nice! You have also shown a good example. But as a part of GNU or GPL you need to provide us with a very good documentation. Can't you give some explanations and also limitations of your program. You can also give spacetime complexity of you algorithms.
But your attempt is appriciatable!!!
It's fine! Your implementation is nice! You have also shown a good example. But as a part of GNU or GPL you need to provide us with a very good documentation. Can't you give some explanations and also limitations of your program. You can also give spacetime complexity of you algorithms.
But your attempt is appriciatable!!!
We are all in a circular way, no advances, only moving and moving!
Thanks for the inspiration
Hi,
Thanks for inspiring me that way, .
USE

As easy as using builtin Integers.
DOC

No doc right now, sorry.
Limitation

Lots , heres few
> Implementation of << (or >>) as indicated in the source code is not done.
> Full use of 32 bit integer is not done, this would make much faster.
> Fastest algorithm for multiplication is not implemented
> Division function is not fully debugged.
COMPLEXITY

See D.E. Knuth Volume 2, seminumerical algorithm.
I think posting solutions is not a good way. But I have no other alternative to have show use.
Here goes some examples :
Problem 10303

[cpp]
/*
Catalan Numbers
result = (2nCn) / (n+1)
*/
using namespace BigMath;
int main()
{
#ifndef ONLINE_JUDGE
freopen("e:\\cppfile\\in\\acm10303.in","rt",stdin);
freopen("e:\\cppfile\\out\\acm10303.out","wt",stdout);
#endif
DATATYPE i;
DATATYPE j;
DATATYPE temp;
BigInteger a[1001] = { 1, 2, 5, 14, 42 };
for(i=5;i<=1000;i++)
{
BigInteger& up = *new BigInteger(2*(i+1));
for(j = 2*i+1; j>2*i; j)
up = up.Multiply(j);
up = a[i1].Multiply(up);
up = up.DivideAndRemainder(i+1,temp,true);
up = up.DivideAndRemainder(i+2,temp,true);
a = up;
}
while(true)
{
cin >> i;
if(cin.eof()) break;
cout << a[i1] << endl;
}
return 0;
}
[/cpp]
Problem 10334

[cpp]
using namespace BigMath;
int main()
{
#ifndef ONLINE_JUDGE
// freopen("e:\\cppfile\\in\\acm10334.in","rt",stdin);
// freopen("e:\\cppfile\\out\\acm10334.out","wt",stdout);
#endif
BigInteger fb[1001] = { 1, 2};
int n;
for(n=2;n<=1000;n++) {
fb[n] = fb[n1] + fb[n2];
// cout << fb[n] << endl;
}
while(scanf("%d",&n)==1) cout << fb[n] << endl;
return 0;
}
[/cpp]
Thanks.
 Suman
Thanks for inspiring me that way, .
USE

As easy as using builtin Integers.
DOC

No doc right now, sorry.
Limitation

Lots , heres few
> Implementation of << (or >>) as indicated in the source code is not done.
> Full use of 32 bit integer is not done, this would make much faster.
> Fastest algorithm for multiplication is not implemented
> Division function is not fully debugged.
COMPLEXITY

See D.E. Knuth Volume 2, seminumerical algorithm.
I think posting solutions is not a good way. But I have no other alternative to have show use.
Here goes some examples :
Problem 10303

[cpp]
/*
Catalan Numbers
result = (2nCn) / (n+1)
*/
using namespace BigMath;
int main()
{
#ifndef ONLINE_JUDGE
freopen("e:\\cppfile\\in\\acm10303.in","rt",stdin);
freopen("e:\\cppfile\\out\\acm10303.out","wt",stdout);
#endif
DATATYPE i;
DATATYPE j;
DATATYPE temp;
BigInteger a[1001] = { 1, 2, 5, 14, 42 };
for(i=5;i<=1000;i++)
{
BigInteger& up = *new BigInteger(2*(i+1));
for(j = 2*i+1; j>2*i; j)
up = up.Multiply(j);
up = a[i1].Multiply(up);
up = up.DivideAndRemainder(i+1,temp,true);
up = up.DivideAndRemainder(i+2,temp,true);
a = up;
}
while(true)
{
cin >> i;
if(cin.eof()) break;
cout << a[i1] << endl;
}
return 0;
}
[/cpp]
Problem 10334

[cpp]
using namespace BigMath;
int main()
{
#ifndef ONLINE_JUDGE
// freopen("e:\\cppfile\\in\\acm10334.in","rt",stdin);
// freopen("e:\\cppfile\\out\\acm10334.out","wt",stdout);
#endif
BigInteger fb[1001] = { 1, 2};
int n;
for(n=2;n<=1000;n++) {
fb[n] = fb[n1] + fb[n2];
// cout << fb[n] << endl;
}
while(scanf("%d",&n)==1) cout << fb[n] << endl;
return 0;
}
[/cpp]
Thanks.
 Suman

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany
There is a faster method for finding the squareroot (at least faster for really big numbers).
http://home.earthlink.net/~usondermann/square.html
http://home.earthlink.net/~usondermann/square.html
I am working on it
Hi,
The post is viewed for about 200 times, but only one improvement suggestion from Adrian. Thanks Adrian. I am working on the improvement. But I am little busy with something. So can't say when that will be ready. Thanks again for the suggestion.
 Suman
The post is viewed for about 200 times, but only one improvement suggestion from Adrian. Thanks Adrian. I am working on the improvement. But I am little busy with something. So can't say when that will be ready. Thanks again for the suggestion.
 Suman

 New poster
 Posts: 16
 Joined: Tue Dec 03, 2002 9:44 pm
Bug
Sumon Bhai,
Your Class gives wrong out put for division:
[cpp]BigInteger a("3024"), b("24");
cout << a / b << " ????";[/cpp]
Your Output : 125 ????
How can it be?
Your Class gives wrong out put for division:
[cpp]BigInteger a("3024"), b("24");
cout << a / b << " ????";[/cpp]
Your Output : 125 ????
How can it be?
About BUG : To Nirjon
About BUG : To Nirjon
Hi Nirjon,
Thanks for locating the BUG for me. I am amazed at the error. I checked the code again and again. It seems to be ok. But I am not getting any reason. If you can find pls tell me.
Previously I had not undergone any test over the correctness of "division" algorithm . Now I have tested with about 1300 test cases , all is ok. But interstingly your test is failed. I will test with more datas. I need help in this stage.
 Suman
Hi Nirjon,
Thanks for locating the BUG for me. I am amazed at the error. I checked the code again and again. It seems to be ok. But I am not getting any reason. If you can find pls tell me.
Previously I had not undergone any test over the correctness of "division" algorithm . Now I have tested with about 1300 test cases , all is ok. But interstingly your test is failed. I will test with more datas. I need help in this stage.
 Suman
To Moni
To Moni:
Hi Moni,
Yes, I have read that post. But that post is a long one. Can you be a little more specific on which you are focussing? Thanks.
 Suman
Hi Moni,
Yes, I have read that post. But that post is a long one. Can you be a little more specific on which you are focussing? Thanks.
 Suman

 New poster
 Posts: 10
 Joined: Sat Aug 19, 2006 7:23 pm
 Location: bangladesh
 Contact:
THE BIGinteger class
if i solve any problem by BIGint class then i have to send it with the class to the judge.
will any one tell me that in a real time contest, how i can afford to solve a problem using BIGint class of mr. sumon ( i appritiate him as i like the class) .
so, if i hv to write in the contest time the how it is possible to use?
so, is it right to use it for solving problem rather using manual string operation.
altaf
will any one tell me that in a real time contest, how i can afford to solve a problem using BIGint class of mr. sumon ( i appritiate him as i like the class) .
so, if i hv to write in the contest time the how it is possible to use?
so, is it right to use it for solving problem rather using manual string operation.
altaf