Arbitrary Precision Arithmatic : BigInteger Algorithm

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
suman
New poster
Posts: 45
Joined: Fri Oct 19, 2001 2:00 am
Contact:

Arbitrary Precision Arithmatic : BigInteger Algorithm

Post by suman » Wed Nov 13, 2002 12:57 am

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
Last edited by suman on Wed Nov 20, 2002 2:08 pm, edited 1 time in total.

User avatar
Moni
Experienced poster
Posts: 202
Joined: Fri Mar 22, 2002 2:00 am
Location: Chittagong. CSE - CUET
Contact:

Post by Moni » Thu Nov 14, 2002 9:14 pm

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!!!
ImageWe are all in a circular way, no advances, only moving and moving!

suman
New poster
Posts: 45
Joined: Fri Oct 19, 2001 2:00 am
Contact:

Thanks for the inspiration

Post by suman » Sat Nov 16, 2002 5:18 pm

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

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Mon Nov 25, 2002 3:00 am

There is a faster method for finding the squareroot (at least faster for really big numbers).
http://home.earthlink.net/~usondermann/square.html

suman
New poster
Posts: 45
Joined: Fri Oct 19, 2001 2:00 am
Contact:

I am working on it

Post by suman » Tue Nov 26, 2002 10:51 pm

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

Shahriar Nirjon
New poster
Posts: 16
Joined: Tue Dec 03, 2002 9:44 pm

Bug

Post by Shahriar Nirjon » Wed Jan 29, 2003 6:20 pm

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

User avatar
Moni
Experienced poster
Posts: 202
Joined: Fri Mar 22, 2002 2:00 am
Location: Chittagong. CSE - CUET
Contact:

Post by Moni » Tue Feb 04, 2003 9:41 pm

Suman have you read the thread in the C++ about "Bigint" of mine?
What's your opinion???
ImageWe are all in a circular way, no advances, only moving and moving!

suman
New poster
Posts: 45
Joined: Fri Oct 19, 2001 2:00 am
Contact:

About BUG : To Nirjon

Post by suman » Wed Feb 05, 2003 10:05 pm

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

suman
New poster
Posts: 45
Joined: Fri Oct 19, 2001 2:00 am
Contact:

To Moni

Post by suman » Wed Feb 05, 2003 10:13 pm

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

altaf hussain(sust_2002)
New poster
Posts: 10
Joined: Sat Aug 19, 2006 7:23 pm
Location: bangladesh
Contact:

THE BIGinteger class

Post by altaf hussain(sust_2002) » Sun Sep 24, 2006 9:32 pm

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

Post Reply

Return to “Algorithms”