Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

Sage

Help with HUGE numbers!?!

This topic is 6612 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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!!

Share this post


Link to post
Share on other sites
Advertisement
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.

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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!!

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!