Page 1 of 1

Arbitrary Precision Arithmatic : BigInteger Algorithm

Posted: Wed Nov 13, 2002 12:57 am
by suman
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

Posted: Thu Nov 14, 2002 9:14 pm
by Moni
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 space-time complexity of you algorithms.

But your attempt is appriciatable!!!

Thanks for the inspiration

Posted: Sat Nov 16, 2002 5:18 pm
by suman
Hi,
Thanks for inspiring me that way, :D .

USE
-----
As easy as using built-in 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[i-1].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[i-1] << 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[n-1] + fb[n-2];
// cout << fb[n] << endl;
}

while(scanf("%d",&n)==1) cout << fb[n] << endl;

return 0;
}

[/cpp]


Thanks.

- Suman

Posted: Mon Nov 25, 2002 3:00 am
by Adrian Kuegel
There is a faster method for finding the squareroot (at least faster for really big numbers).
http://home.earthlink.net/~usondermann/square.html

I am working on it

Posted: Tue Nov 26, 2002 10:51 pm
by suman
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

Bug

Posted: Wed Jan 29, 2003 6:20 pm
by Shahriar Nirjon
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?
:o

Posted: Tue Feb 04, 2003 9:41 pm
by Moni
Suman have you read the thread in the C++ about "Bigint" of mine?
What's your opinion???

About BUG : To Nirjon

Posted: Wed Feb 05, 2003 10:05 pm
by suman
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

To Moni

Posted: Wed Feb 05, 2003 10:13 pm
by suman
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

THE BIGinteger class

Posted: Sun Sep 24, 2006 9:32 pm
by altaf hussain(sust_2002)
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? :cry: :cry:
so, is it right to use it for solving problem rather using manual string operation.
altaf