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.
Bignum arithmetic
Moderator: Board moderators
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. ]
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
http://www.comp.nus.edu.sg/~stevenha/pr ... gInteger.h
http://www.comp.nus.edu.sg/~stevenha/pr ... esting.cpp
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.
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.
