BigInteger

[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).

[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

[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...

[Per]

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.)

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.

[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;

[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 .

[greco]

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.

[misof]

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

Code: Select all

SUM (x < length) 10^x * digit[x]

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

[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.

[Larry]

Sure, it might work fine.. and it might work fine if you wrote everything in asm.. but it's about maintainability!

[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;

...

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/