Yeah, we worked with the infamouse larger integer class...im not sure about floats tho.

quote: Original post by Sage
I'm doing some math with pretty big #s (like 2^1840), but i can't get it to work without an overflow, or using crappy float's (and it's important that i keep track of every digit)...

Could anybody help me with this, or refer me to a tutorial/website or something?

There's a very cool way to think about this. Normally, we count in base 10, with 10 digits (0 to 9). Each digit fits in a "space", and we can build numbers like this:

3951 = (3 * 10^3) + (9 * 10^2) + (5 * 10^1) + (1 * 10^0)

The binary number system (base 2) works similarly, but we only have two digits (0 and 1). And again, we build a number like so:

1011 = (1 * 2^3) + (0 * 2^2) + (1 * 2^1) + (1 * 2^0)

Now take this one step further. With most current compilers, the largest builtin integral type tends to be the 'long', which is 32 bits. Well, why not count numbers in base 2^32?

It sounds weird, but it is logical. Now imagine how you add two base 10 numbers. You sum up the "ones" column, which are the 0th digits (ie, those digits in the 10^0 position). This gives you a new 0th digit and possible carry into the 1st digit position. Add the carry with both 1st digits (the "tens"), and you have the new 1st digit and possible carry to 2nd digit. And so on.

This will work just fine in base 2^32. If you keep arrays of unsigned long, each array element counts as a digit. You can loop through the arrays, adding a[0] + b[0], then a[1] + b[1]. You have to be a little careful, making sure you watch for overflow in a particular digit (which indicates there is a carry).

I don't have time right now to detail this all out here. But I hope the above should get the brain juices flowing. If you need additional assistance, feel free to email me at moss@null.net and I'll see what I can do.


---- --- -- -
Blue programmer needs food badly. Blue programmer is about to die!

Edited by - mossmoss on 4/14/00 7:38:07 PM

quote: Original post by ColdfireV
I agree with the last post, but one thing has always got me thinking... If you were to add two numbers that are larger than the largest data types, then is the returning result going to overflow as well? Okay, you probably didn't get that, so here's an example:

Yes, you have to be careful in how you go about adding digits. Doing something like this:

if (a[0] + b[0] > MAXINT) {    //adjust and carry}   

won't work because a[0] + b[0] might overflow before comparing against MAXINT. A little thought will prove that this test will ALWAYS fail, whether there is overflow or not!!!

The way around this is to use a little algebra. Subtract b[0] from both sides of the comparison and write your check like this:

if (a[0] > MAXINT - b[0]) {    //adjust and carry}   

Now, neither side will overflow, and since b[0] can't be larger than MAXINT, neither side will underflow. Isn't that cool???

Again, be careful. I'm pulling that off the top of my head (and assuming all unsigned long here), and I'm not mentally checking all cases right now. But it should give you the basic idea.

---- --- -- -
Blue programmer needs food badly. Blue programmer is about to die!


Edited by - mossmoss on 4/14/00 7:27:41 PM