Sign in to follow this  
Muzzy A

Extremely Large numbers in C++

Recommended Posts

Muzzy A    737
Hey I want to make a datatype for myself that can hold very large numbers like a 'Googol' or maybe even a little bigger.

a Googol is 10,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000


I want a datatype that can hold this number, and be able to perform mathematical operations on it. and possibly if it's not to hard, have decimal values as well that go 100 digits below 0


basically I want to make a datatype that has at least 512 bits(64 bytes), or larger if need be.


the only way i've thought of doing this is to make an array of char's and then calculate where in the array each number would go(the number 35 would be arry[1] = 3 arry[0] = 5). But i realize that would very bad on the cpu plus very complex.

I don't want any libraries that are out there, I'm looking for a way to do this myself.

Does anyone know of a way to do this? Edited by Muzzy A

Share this post


Link to post
Share on other sites
Zoomulator    273
It'd be easier to just say 10^100.. save you the counting of zeros ;)

A standard 64bit datatype that covers this number already exists. It's called a double! It'll give you numbers up to something around 2.2*10^308 and down to 2.2*10^-308 with precision of 15-17 digits.

But, if you want to cover 10^100 + 1 with exact precision, then you'll need a heck of a big data type.. and its beyond me how you'd do it.

I suggest a bit of reading on wikipedia:
[url="http://en.wikipedia.org/wiki/Double-precision_floating-point_format"]http://en.wikipedia....ng-point_format[/url]
[url="http://en.wikipedia.org/wiki/Integer_(computer_science)"]http://en.wikipedia....mputer_science)[/url]

And the recent altdevblog series on float:
[url="http://www.altdevblogaday.com/2012/05/20/thats-not-normalthe-performance-of-odd-floats/"]http://www.altdevblo...-of-odd-floats/[/url] (this article has links to all the previous ones, start with the first one ) Edited by Zoomulator

Share this post


Link to post
Share on other sites
Muzzy A    737
thanks, i'll look into those, but if I can't figure anything out within the next couple of days i'll probably be back here [img]http://public.gamedev.net//public/style_emoticons/default/tongue.png[/img]

and yeah I'm look for exact precision. Edited by Muzzy A

Share this post


Link to post
Share on other sites
apatriarca    2365
You can take a look at the [url="http://gmplib.org/"]GMP library[/url]. It is written in C, but there are wrappers for several languages, including C++ (you can clearly also use directly the C API). It is used in many computer algebra systems like Mathematica and Maple, in computational geometry libraries like CGAL, in some programming languages supporting big numbers like haskell and so on..

Share this post


Link to post
Share on other sites
Waterlimon    4398
I believe you would make it by having an array of ints of some size, and do the operations 1 int pair at a time like a1[0]+a2[0], and that should give you the result and an overflow, and somehow you put the overflow somewhere so that it gets to the calculation between the next pair of ints or something like that.

You can also google for big number libraries.

Share this post


Link to post
Share on other sites
Muzzy A    737
hey bacterious, i'm going to go ahead and say. "I love you man!". You just knocked out several several hours of troubleshooting for me in that one post. I can't thank you enough for that. Now teach me some quantum physics =). just playin llol. Thanks alot for your help, and you should be a teacher at some college, cause you're good. ;)

Share this post


Link to post
Share on other sites
Bacterius    13165
[quote name='Narf the Mouse' timestamp='1339240291' post='4947630']
It might be trivial, but Google is not useful for finding out about carry flags - At least not for me.
[/quote]
Sorry about my use of the word trivial. I was mostly using it in saying that the algorithm isn't complicated (it's just a bit lookup in a CPU register, instead of an elaborate procedure to detect overflow in a sum). Of course knowing about it isn't trivial, I wasn't being condescending [img]http://public.gamedev.net//public/style_emoticons/default/smile.png[/img] And yes I agree, I noticed "carry flag" was not a good term to use in google, I don't know why! It might be too short or something.


[quote name='Muzzy A' timestamp='1339241062' post='4947633']
hey bacterious, i'm going to go ahead and say. "I love you man!". You just knocked out several several hours of troubleshooting for me in that one post. I can't thank you enough for that. Now teach me some quantum physics =). just playin llol. Thanks alot for your help, and you should be a teacher at some college, cause you're good. ;)
[/quote]
Thanks! But I'm still a student so becoming a teacher would be quite impossible at the moment [img]http://public.gamedev.net//public/style_emoticons/default/tongue.png[/img] Edited by Bacterius

Share this post


Link to post
Share on other sites
apatriarca    2365
At least when working with x86 assembly, there are the ADC and SBB instructions implementing respectively addition with carry and subtraction with borrow. These instructions greatly simplify the implementation of addition and subtraction between large numbers. You clearly have to write some assembly to use them though. This is probably one of the few cases where it is easier to write the code in assembly than C/C++. Multiplication is more complicated and there exists several different algorithms to do it as you can see [url=http://gmplib.org/manual/Multiplication-Algorithms.html]here[/url].

Share this post


Link to post
Share on other sites
Narf the Mouse    322
[quote name='Bacterius' timestamp='1339243840' post='4947638']
[quote name='Narf the Mouse' timestamp='1339240291' post='4947630']
It might be trivial, but Google is not useful for finding out about carry flags - At least not for me.
[/quote]
Sorry about my use of the word trivial. I was mostly using it in saying that the algorithm isn't complicated (it's just a bit lookup in a CPU register, instead of an elaborate procedure to detect overflow in a sum). Of course knowing about it isn't trivial, I wasn't being condescending [img]http://public.gamedev.net//public/style_emoticons/default/smile.png[/img] And yes I agree, I noticed "carry flag" was not a good term to use in google, I don't know why! It might be too short or something.
[/quote]
Apologies on my part; I could have done that much better. I didn't think you were being condescending; I thought Google was being annoying again. :) In what little defence I have, it was very late at night and I'm pretty sure I didn't mean it the way it came across, which isn't really a defence at all. :)

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this