• Advertisement

Archived

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

Help with HUGE numbers!?!

This topic is 6517 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
Yeah, we worked with the infamouse larger integer class...im not sure about floats tho.

Share this post


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

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
My highschool (and a lot of others) offer c++ AP courses, where you take a test at the end of the year for $76 and can earn college credits.

Well part of the test is based on a class (a C++ class, not a school classroom) that you are suppose to learn during the year. This year the class is called BigInt, and can hold any size (non decimal) numbers (well, limited to how much memory you have available).

maybe do a search on BigInt and see what it turns up...

Share this post


Link to post
Share on other sites
I took the AP exam last year. BigInt used a C++ class to store each digit in a string. Then worked on each term individually. (someone suggested this above). It isn''t exactly fast, but the method works. I personally disagree with the method it uses, it is slow and takes up way more memory than needed. Though, it is the easiest.

-Omalacon

Share this post


Link to post
Share on other sites
I give you an algorithm for division:

a/b

Stage 1:
Shift left b until the most significant 1 bit of b has the same position as the most significant 1 bit of a. Then x=2^(Number of bits shiftet).
Stage 2:
Then calculate a-x. With the amount of this difference you goto stage 1: /(a-x)//b. If a-x is positiv, you add /(a-x)//b to x, else you subtract it. You could implement this recursive and stop it if /(a-x)/
Visit our homepage: www.rarebyte.de.st

GA

Share this post


Link to post
Share on other sites
At work, our PC based applications do some talking to a Tandem computer. The biggest integer on the PC is 2^32 and the biggest integer on the is 2^64 (plus PC is intel format (byte reversed) and Tandem is correct format). We actually have some data that 2^32 would not handle so the Tandem uses their native format and we created longlong. This is a 2^64 integer in correct byte order (not intel format).

It should be very easy to extend to as many bytes as you like. For 2^1840 and no loss of precision you''ll need 230 bytes! We did functions for addition, subtraction, multiplication, divition, ascii to longlong,and longlong to ascii. Maybe kieren_j could compress your numbers for you with his Cold Fusion algorithm!

Since time for this bit of math magic is not a concern we just did it byte by byte, but I''m fairly certain the code can be optimized for a 32 byte word. Don''t know how fast or slow they are as is and thusly have no idea on what the effect of optimization should be, but it should speed them up. With your need for 230 bytes its not going to be super fast no matter what.

If you want like to have them e-mail me. I will have to clean them up a bit to remove some work related crap that you don''t need. As far as I know, all 6 functions are use in our code and have no problems, but there all no guarantees.

Michael L. Roberts
aka milo
mlbobs@telocity.com

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
quote:
Original post by Sage

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


Hi,

I''m fairly new to programming, but, in such cases, you should probably get or design your own custom integer.

I had to do something like that last term, in my C++ class, and also the term before, in my C class.

For C++, you need a BigInt class, where you have]

class BigInt{
public:
//all the overloaded operators and get and set methods
private:
int array[1000]
// all the variables and flags required.
};

What you do is take string of up to 1000 characters, and, if the string is valid (no letters or non-numerals), convert each character into an int (with atoi()), then slot that int into the appropriate place in the array.

This assignment can actually be fun, if you do it right. But this is such an obvious problem that you could probably get a free bigint from one of the professional software houses.

Is this for school?

Stanley

Share this post


Link to post
Share on other sites
Somewhat related to big numbers and datatypes

Most compilers have _int64 declarations
There''s also the
long long

Looking over the messages I see you are probably talking above that. But before developing a whole math system: Why the need for such big numbers?



ZoomBoy
A 2D RPG with skills, weapons, and adventure.
See my character editor, Tile editor and diary at
Check out my web-site

Share this post


Link to post
Share on other sites
Thanks for the responses, you guys are great!!!

No, i don't need this for school (unforunately my school only offers very, very basic programming courses in QBasic [on 386's])..

I. I do some pretty large numbered equations
II. For use with manipulating files as a whole number.
example: take a file, read it as bytes/bits, convert it into it's decimal representation.

foo.txt - 1010010101101010001010101111010100010101010
foo.txt - 35664623215984023540
(not a real base conversion here, typing in a hurry)

stuff like that....

-Sage

Edited by - Sage on 4/17/00 12:42:43 AM

Share this post


Link to post
Share on other sites

  • Advertisement