OJ Board

Hi!

I'm facing up a bignum problems right now. I tried to write substraction, addition, multiplication and division on bignums. However, coding multiplication and division took me too long and I'm not still able to write it. Substraction and addition with carry operations can be easily written.

So far, I know that the best way to store bugnums are tables of longs (C++) where the number is read from right to left i.e. number = 1234567891011
t[0]=67891011 t[1]=12345
Is there anything better?

Could anybody tell me how to multiply and divide bignums (BIG1*BIG2 and BIG1/BIG2) as fast as it it possible?

I would be grateful for any useful pieces of advice. Thanks in advance for reply.

The easiest multiplication is O(n squared), but if you want to go for speed look up karatsuba multiplication on google or mathworld. But I think they are horribly difficult to code though worth the trouble for the speed improvement you get for really large numbers [O(n raised to 1.58 ) if I remember right. ]

And what about division?

maybe these links helps you


http://www.comp.nus.edu.sg/~stevenha/pr ... gInteger.h
http://www.comp.nus.edu.sg/~stevenha/pr ... esting.cpp

the BigInteger library in Steven Halim's website does not work properly for division of 2 big integers. But it does work quite ok if u divide a big integer by a constant

Unfortunately, those libraries do not satisfy me. I'd like to know how it's done and which algo has been used.

Think about the paper and pen method of division.

In fact, it's too slow. I need to know faster algo. Please help me!

Both multiplication and division can be done in O(n^2) without much trouble.
The so-called "karatsuba algorithm" (O(n^(log 3 / log2)) is just the divide-and-conquer method for integer multiplication found in every textbook. It isn't difficult to code, but as far as I know the gain in speed is only noticeable when multiplying numbers with several thousand digits.
As for division, you can use a variant of the paper-and-pencil method. The only difficulty is determining what the next "digit" (in a large base, such as 10^9) will be. You can use the result of dividing the first two digits of the dividend by the first digit of the divisor as an initial estimate for the next digit.
If the first "digit" of the dividend is no smaller than half the base, it can easily be shown that this estimate is at most four units away from the true result, so you only need to check at most four values. So the key to make this method work fast is to first multiply both dividend and divisor by a constant, so that the first digit of the divisor becomes >= base / 2.
I suppose none of these algorithms are the state of the art for integer arithmetics, but they work reasonably fast. I don't know what you intend to do, though.

I use string representation to deal with bigNums. A poblem that requires it it's the "How Many Fibs?" problem. I used character representation, i think it's more easy
But if you are using huge numbers, I don't know if it works hehe, cause a vector has a limit to be allocated..