Page 1 of 1
BigInteger
Posted: Thu Jul 29, 2004 3:06 am
by Minilek
Hi. I wanted to ask, what do most people do to handle numbers that are more than 64 bits? java.math is disabled so we don't have access to BigInteger, and I can't seem to find anything in the gnu library for bigint. Do people just make their own? Or is there code out there that we can just use? (I've tried searching on google, but have only found very inefficient implementations that represented the bigints as strings).
Posted: Thu Jul 29, 2004 9:26 am
by Pavl0
in c++ sometimes j use long double
but most time you must wrore your implementation big num
for example table
0 1 2 3 4 5
4 5 6 7 5 3
can reprezent number 456753
Posted: Fri Jul 30, 2004 6:21 pm
by Minilek
That's what I've been doing so far actually (representing bignum's as just arrays of digits), but it seems so inefficient. For example, one could optimize it by making each element in the array as big as an int allows vs. just a single digit to get as much work done per instruction as possible (or at least maybe? I don't know..but it just seems like there are better ways out there anyway...). Is there no way other than just writing our own bignum classes? It seems pointless that everyone has to reinvent the wheel...
Posted: Fri Jul 30, 2004 9:41 pm
by Per
Minilek wrote:That's what I've been doing so far actually (representing bignum's as just arrays of digits), but it seems so inefficient. For example, one could optimize it by making each element in the array as big as an int allows vs. just a single digit to get as much work done per instruction as possible (or at least maybe? I don't know..but it just seems like there are better ways out there anyway...).
Well, how do you think the Java BigInteger or GMP works? They work exactly in this way. (Though of course people has spent
a lot of time optimising them.)
Minilek wrote:Is there no way other than just writing our own bignum classes? It seems pointless that everyone has to reinvent the wheel...
It builds character.
And it's definitely good practice to try to write short and neat, yet reasonably fast, biginteger routines.
Posted: Fri Dec 10, 2004 10:41 pm
by d91-lek
Everytime I'm doing bit manipulation in C I badly miss access to the carry and/or overflow flags. Last time I needed carry I wrote something like this
Code: Select all
unsigned long long a, b, sum;
sum = a + b;
carry = sum < a || sum < b;
The time before, I wrote something completely different but exactly as roundabout. Portable assembler code indeed. What good did C's lack of abstraction ever buy us? No, me, I'm always smiling at Smalltalk and Prolog.
And this, is this left rotation in a hardware close language of your choice?
Code: Select all
a = (a << 1) | (a >> 8*sizeof(a)-1)
Right shift through two variables?
Code: Select all
r = (r >> 1) | (l << 8*sizeof(l)-1);
l >>= 1;
How to write faster BigInteger routine ???
Posted: Sat Feb 19, 2005 5:02 pm
by nymo
I 've learnt that it is possible to do the computation in higher base, so, less computation is needed . But, if the base is somewhat higher like 1000 or 10000, how the remainders are represented for computation ? say, if base is 16 , we represent 10 -15 by A-F. What is the catch for base like 1000 or 10000 . In the forum , i 've found some post that they did it and did in a very efficient way so the timing is very good. Will you please share your knowledge ? pseudocode or a good discussion will be a great help .
Posted: Mon Feb 21, 2005 3:08 pm
by greco
Pavl0 wrote:in c++ sometimes j use long double
but most time you must wrore your implementation big num
for example table
0 1 2 3 4 5
4 5 6 7 5 3
can reprezent number 456753
You should represent the numbers in reversed order to keep the calculations simple. And v[0] should be the length of the number...
So for 456753,
v[0] = 6, v[1] = 3, v[2] = 5, v[3] = 7, v[4] = 6, v[5] = 5, v[6] = 4.
I'm writing my own adding, subtraction, multyplying, etc... procedures every time because that's what you have to do during a contest. I always start from scratch.
Posted: Mon Feb 21, 2005 4:52 pm
by misof
greco wrote:You should represent the numbers in reversed order to keep the calculations simple. And v[0] should be the length of the number...
Reverse order? Yes.
Length in v[0]?
NO, NEVER!
Something along the lines:
Code: Select all
class BigNum { int length; int digit[1000]; };
is by far less confusing when writing the code.
Why? Suppose we are using the classical decimal notation. In this case my BigNum corresponds to
Note that the index of the digit is exactly the corresponding power of ten. E.g. when multiplying/dividing the big numbers this makes the code more simple and readable.
Another possibility is (in C++) to use a vector<int> to store the digits in the same order as above, you get the size() for free
Posted: Mon Feb 21, 2005 8:47 pm
by greco
I read it in a book, I got used to it. And I am a C lover. In order to use nothing more than an array, I usually do something like
Code: Select all
typedef int huge[maxlength];
huge H;
And It works just fine I believe.
Posted: Wed Feb 23, 2005 1:46 am
by Larry
Sure, it might work fine.. and it might work fine if you wrote everything in asm.. but it's about maintainability!
Posted: Mon May 09, 2005 7:56 pm
by d91-lek
d91-lek wrote:Everytime I'm doing bit manipulation in C I badly miss access to the carry and/or overflow flags. Last time I needed carry I wrote something like this
Code: Select all
unsigned long long a, b, sum;
sum = a + b;
carry = sum < a || sum < b;
...
Hackers delight, Henry S. Warren Jr., ISBN: 0201914654, gives everyone who thought they knew something about bit manipulation a beating on the head. Yes, even me and you who thought we had read HAKMEM. Here is the homepage:
http://www.hackersdelight.org/