Hey! 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? Thanks for your time!!

A very long time ago (actually only a year or so) in my high school C++ class we created a class that represented very large numbers by using a string to store the number and then doing the math operations term by term. I cannot remember exactly how we did this, but this is an option if you need really really big numbers.

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

Do you need large ints or large floats??

Visit our homepage: www.rarebyte.de.st

GA

Edited by - ga on 4/14/00 5:48:39 PM

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

Mossmoss, that *is* cool!

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:

We have two unsigned long integers (value can go up to 4 billion + something) called num1 and num2. If these are any small numbers, say 10,000 and 15,000, and we add the two with the operator +, then the returned result will obviously be 25,000. Now just for the sake of it, we''ll say the overflow for an unsigned long integer is 4.1 billion. If we set num1 = 3.0 billion, and num2 = 2.0 billion, and call the operator + on them, then is the returning value going to be 5.0 billion, or (5.0 billion - 4.1 billion = ) 0.9 billion because of overflow?

If this is the case, then the last post''s method will not work, specifically because overflow will occur on every number that''s over 4.1 billion. What will happen?


ColdfireV

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

I suggest to use following data structure:

struct LongNumber
{
unsigned long nLongs; // Number of allocated unsigned longs
unsigned long *number;
};

With this structure you can extend the digits if the number becomes to large because of the calculations.
Has anyone thought about multiplying two of the big numbers?
You could use an algorithm we all learnt in ground school:

11000010110 * 101110

= 1100001011000000
(+ 000000000000000)
+ 11000010110000
+ 1100001011000
+ 110000101100
(+ 00000000000)
-------------------
10001011111110100

Visit our homepage: www.rarebyte.de.st

GA

Thanks alot guys! I didn''t expect to get so many replies.
I will definately be using a kind of Int (floats suck for this kind of thing).

And the base 32 # system doesn''t sound that bad, for space saving reasons.. It would be a like using Hexadecimal, just bigger..

Thanks for all the advice, i think i''ll go with a LargerInt/LongNumber sorta struct.. The only crappy part is having to write your own Operations (*/-+^) for these numbers... oh well!..
Thanks again!!