OJ Board

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

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!!!

Hi,
Thanks for inspiring me that way, .

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

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

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

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?

Suman have you read the thread in the C++ about "Bigint" of mine?
What's your opinion???

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:

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

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