Yeah, I think the string method would work best. Although if you want to be a little more efficient, you may want to work in base 65536 (or 2^16) instead of base 10. Just store each 'digit' as an unsigned short, and operate on those. That way you can still fit multiplications into 32 bits, but it will still take a whole lot less digits to hold your number. You'd have to convert to decimal for displaying it or whatever, but I don't think that would be too hard.
For adding, you'd just do like
carry = 0;
loop number of digits
dest[curDigit] = (src1[curDigit] + src2[curDigit]) & 0xffff;
carry = (src1[curDigit] + src2[curDigit]) >> 16;
You either need to have both numbers with the same digits and just zero the upper ones, or do some checking on which has more digits and setting all the dest digits accordingly
And multiplying,
for(j=0 to src2 digits)
{
for(i=0 to src1 digits)
{
unsigned long product = src1 * src2[j];<br> BigNum bigProduct;<br> bigProduct[0] = product & 0xffff;<br> bigProduct[1] = product >> 16;<br> bigProduct *= 1 << ((i + j) * 16); //basically 16^(i+j)<br> AddBigNum(dest, bigProduct); //this is that add function above<br> }<br>}<br>So it's like regular multiplying off paper, where say you're doing column 0 * column 1, you shift over offe space, multiplying by 10. Then in column 1 by column 1, you multiply by 10^2. I think that 16^(i+j) will need to be a BigNum too, which means you'll have to do shifts too (set a BigNum to 1, then shift it by (i+j)*16), but that shouldn't be too hard either. Division's the kicker though. I'm not too familiar with division algorithms yet, so I can't give an example. I think the easiest offe is just like checking if the number is >= to the denominator times each power of 2, and if so, subtract that denom*power of 2 from it, and add the power of 2 to the quotient. Start at the highest power and successively check smaller ones, so by the end you're checking with 2^0, or 1*denom, and what's left after that is the remainder. <br><br><SPAN CLASS=editedby>[edited by - dekutree64 on February 26, 2004 10:53:38 PM]</SPAN>
BIG numbers in C++
The most efficient way that I can think of is to use an array of unsigned longs (or __int64, on a 64 bit system), and then just treat it like base-(2^32), as opposed to base-10. The math will still work out the same, but it will be much more efficient in terms of memory, and some calculations can probably be optimized as well. The only difficulty is printing it out, which isn''t really overly hard, but it''s probably pretty complicated, in terms of processor usage, but you shouldn''t be converting to strings all the time anyway.
Ill agree on the base-2 thing and reusing standard integer types/arithmetic to build on.
If you need rational numbers or more complex arithmetic than multiplication/addition you are a masochist to not use an existing library though.
GMP downloads fine for me.
If you need rational numbers or more complex arithmetic than multiplication/addition you are a masochist to not use an existing library though.
GMP downloads fine for me.
Author
Weird, ok, I''ll go for the string method. More programming fun for me tonight :-p thanks guys.
Hi,
Maybe you could use raw bytes to represent the big number and
then define arithmetic operations for it -
byte1 = 0-256
byte2 = 257 - 512
byte3 = 513 - 1024
etc for n bytes
alternatively, if you wanted to use base 10 aritmethic, you
only need 4 bits for each 10:-
int x = ConvertToBase10(1010); /* x = 10 */
this would leave 5 numbers missing for each 4 bit chunk, but
the arithmetic would be easier since you could just separate
the 10''s and shove the bit''s on the end without muliplying
massive numbers.
for instance:-
51235737327 =
50000000000 +
1000000000 +
200000000 +
30000000 +
5000000 +
700000 +
30000 +
7000 +
300 +
20 + 7
then, you just take the position of the byte and print out
the correct number of zeros. Hope this is some help.
Maybe you could use raw bytes to represent the big number and
then define arithmetic operations for it -
byte1 = 0-256
byte2 = 257 - 512
byte3 = 513 - 1024
etc for n bytes
alternatively, if you wanted to use base 10 aritmethic, you
only need 4 bits for each 10:-
int x = ConvertToBase10(1010); /* x = 10 */
this would leave 5 numbers missing for each 4 bit chunk, but
the arithmetic would be easier since you could just separate
the 10''s and shove the bit''s on the end without muliplying
massive numbers.
for instance:-
51235737327 =
50000000000 +
1000000000 +
200000000 +
30000000 +
5000000 +
700000 +
30000 +
7000 +
300 +
20 + 7
then, you just take the position of the byte and print out
the correct number of zeros. Hope this is some help.
Actually we just finished a project in my CS class that dealt with infinitely large numbers.
Basically what it was, was a class that contained a linked list, each node containing a digit, with a special value signifying a negative sign if applicable.
Then we had to write functions such as add(otherNum), subtract(..), multiply(..), divide(..), power(exponent), absoluteValue(), and a few others like isEqual(otherNum), etc.
It was pretty tough to do (maybe with more experience it would be easier though). However, it could be quite useful in a variety of applications.
Basically what it was, was a class that contained a linked list, each node containing a digit, with a special value signifying a negative sign if applicable.
Then we had to write functions such as add(otherNum), subtract(..), multiply(..), divide(..), power(exponent), absoluteValue(), and a few others like isEqual(otherNum), etc.
It was pretty tough to do (maybe with more experience it would be easier though). However, it could be quite useful in a variety of applications.
If you decide to go the string route, you might take a hint from BER-encoded integers, and do something like this for each character:
MSB = continuation bit; 0 indicates this is the last digit-pair in the string
other bits = 2 decimal digits using values 0-99; 100-127 are illegal. (In BER encoding you use the whole range, which is nice for the speed of arithmetic internally but probably a horrible pain when you need to input/output a value from an ASCII representation.)
I read about this encoding in the Perl man pages. Simple enough idea really
MSB = continuation bit; 0 indicates this is the last digit-pair in the string
other bits = 2 decimal digits using values 0-99; 100-127 are illegal. (In BER encoding you use the whole range, which is nice for the speed of arithmetic internally but probably a horrible pain when you need to input/output a value from an ASCII representation.)
I read about this encoding in the Perl man pages. Simple enough idea really
There''s a lot of code already written that cna do this ...
www.google.com
ENJOY!
"Arguing on the Internet is like winning in the Special Olympics, in the end, you''''re still retarded"
www.google.com
ENJOY!
"Arguing on the Internet is like winning in the Special Olympics, in the end, you''''re still retarded"
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
