Sign in to follow this  
AnitraZ

Calculating big numbers

Recommended Posts

AnitraZ    122
Hello people. I'm writing an algorithm that produces an image based on a previous image. The whole set of images produced is made of a very large finite number of items. In other words, I have an algorithm that produces a sort of animation that will likely end in a dozen years from now. The total number of frames can be calculated using a rather complex formula, but for simplicity you can imagine I have something like 10^3000 frames. The problem here is simple: how can I manage such a big number in a C++ program, so that I can perform operations on it, like calculating the remaining time? A first guess might be making an array of long ints, but how many ints do I need for an arbitrary large number? Thanks :)

Share this post


Link to post
Share on other sites
grhodes_at_work    1385
You could use a pure-software extended precision math library. You'd need 3000 bits precision to be able to uniquely count up to 103000. You also certainly could construct this precision using a collection of long ints (or short ints for that matter), with each one incrementing when the block below it rolls over the maximum representable number. If all you need is to count the frames, that wouldn't be very hard to code up without actually using some existing custom library. But why do you need to count the frames?

That said...I'm not sure your program can complete in your lifetime. Consider this. IF you can produce a million frames a second, and there are 60 seconds per minute, 60 minutes per hour, 24 hours per day, 365 days per year, then you can produce 3.1 x 1013 frames per year. It'll take you 100 years to produce 3.1 x 101300 frames, and between 200 and 300 years to produce 103000 frames. That drops to 20 to 30 years if you can produce 10 million frames per second. but increases to 2000 to 3000 years if you can only do a hundred thousands frames per second. Using a custom software-only math library will run slower, not faster. Having many computers or processors running in parallel certainly can help, but this will still be a very slow process. You get the idea, I think. This assumes you have the storage you need, which also may be unlikely.

Share this post


Link to post
Share on other sites
alvaro    21246
Quote:
Original post by grhodes_at_work
[...]You'd need 3000 bits precision to be able to uniquely count up to 103000.

No, you'll need almost 10,000 bits for that.

Quote:
[...] then you can produce 3.1 x 1013 frames per year. It'll take you 100 years to produce 3.1 x 101300 frames, and between 200 and 300 years to produce 103000 frames.

No, it will take you 100 years to produce 3.1 x 1015 frames, and about 3 x 102984 years to produce 103000 frames.

If you need an integer-like data type that can hold very large values, try a library called GMP: http://swox.com/gmp/

Share this post


Link to post
Share on other sites
AnitraZ    122
Yes, I'm aware that in normal conditions such an algorithm can easily last much longer than me (and than my patience as well). Still, there are many variables that heavily affect speed and frame count, like image resolution, frame skipping, accuracy settings etc.
Also, the aim here is not to store every frame (at max a few screenshots), as the output is going to be something like Milkdrop or similar fractal generators (though the aim is different): frames are shown in realtime, then tossed progressively, producing a continous streaming animation.
Last thing, no one says I'm planning to watch the whole movie :)

I need the frame count because I need to give some outputs to the user (me!), like time left and task completion in percentage. With very low settings, I believe those values might have sense.

I guess your answer addressed me to a good direction, now I have to develop a little more the idea on my own. I'll let you know if I get hopelessly stuck or not :)

Share this post


Link to post
Share on other sites
AnitraZ    122
Quote:
Original post by grhodes_at_work
[...]You'd need 3000 bits precision to be able to uniquely count up to 103000.
No, you'll need almost 10,000 bits for that.

I noticed that, but I assume Graham was in a hurry. Counting bits didn't cross my mind at all, so I found this hint helpful, even if inaccurate.

Quote:
[...] then you can produce 3.1 x 1013 frames per year. It'll take you 100 years to produce 3.1 x 101300 frames, and between 200 and 300 years to produce 103000 frames.
No, it will take you 100 years to produce 3.1 x 1015 frames, and about 3 x 102984 years to produce 103000 frames.

Now this is not important, eventually my software will tell me how much time I have to wait. And surely, I will exit my program much sooner than 100 years, without counting that Windows will stop responding, sooner or later :p I think I can implement some "resume from last session" function, like those brute-force password recovery programs do, but this is outside the scope of the thread.

Quote:

If you need an integer-like data type that can hold very large values, try a library called GMP: http://swox.com/gmp/

Thank you, I'm sure a fully tested library will run better than any code I can write in a couple days.

Share this post


Link to post
Share on other sites
Agony    3452
Do you really need it to potentially run for 103000 frames? I suspect not. A signed 64-bit integer goes all the way up to +9,223,372,036,854,775,807, which, assuming 60 frames a second, would last for over 4,871,183,717 years. Since you refer to watching it, I assume that it won't run significantly faster than 60 Hz (even at 6000 Hz, that's still 48,711,837 years), so I see no reason for needing anything more special than a 64-bit integer, which uses the type name "__int64" (two underscores) on MSVC. (I don't know about other compilers/platforms. Perhaps they use "long long"?)

Share this post


Link to post
Share on other sites
AnitraZ    122
Guys, I know my application seems perfectly worthless, but that's my application, so please, bear with me.

Quote:

Look at the java.math package of Java standard programming library, and next time use proper tool for proper job. ~_^

For a number of reasons, including I don't know Java, I decided to stick to C++.

Agony:
The 103000 isn't but an example. As I said, this number will vary greatly. My bad, I should've said 10n from the beginning :/ For the sake of clearness, n ranges from 1 to some very large number. I made some maths with pen and paper, using dummy values to get a rough idea of what to expect, and in that specific case the result was near 103000. Now, of course I won't spend my after-life eternity watching my program's output, but this doesn't imply I don't want to know how many months/years/centuries my algorithm will run for. And, I want my computer to tell me.

Speaking of execution speed, I'm letting the main loop go as fast as it can, with no regard to vsync. I can decide to display only 1 frame every k, but most important, I can tell the algorithm to completely skip m frames. So, imagine I have 1010 frames, I can produce a frame every 1000 (with loss in accuracy, of course), and only display every other frame. Therefore, the CPU will make "only" 107 frames, and only half of that will be shown, which is more than enough to have a smooth and still super-long animation.

With this, I hope I satisfied the curiosity I might've cause in each of you, if I didn't, just tell me :)
For now, I'm trying the GMP library, and at a second time, I'll try to make a working "large number" class by myself, just for practicing.

Share this post


Link to post
Share on other sites
Rockoon1    104
Is an estimate good enough?

For instance the practical difference between 10^1000 frames and 10^1000 + 100,0000,000 frames is moot, right? The extra 100 million is a very minor component in such a case.

Doing estimation, just two 64 bit integers should be more than enough for you. One holds the 'mantissa' of a value and the other holds the 'exponent' (preferably base-2)

Working out the precise details involved should be quite easy. Multiplication involves multiplying mantissas and adding exponents, taking care to compensate for overflows by shifting the mantissa and biasing the exponent.

Share this post


Link to post
Share on other sites
grhodes_at_work    1385
Quote:
Original post by AnitraZ
Quote:
Original post by grhodes_at_work
[...]You'd need 3000 bits precision to be able to uniquely count up to 103000.
No, you'll need almost 10,000 bits for that.

I noticed that, but I assume Graham was in a hurry.


Yes! Both of my replies were hurried. Call it a double brain fart. I do not like when I post erroneous replies...and feel slight shame when I do, :(.

Share this post


Link to post
Share on other sites
AnitraZ    122
Quote:
Original post by Rockoon1
Is an estimate good enough?

For instance the practical difference between 10^1000 frames and 10^1000 + 100,0000,000 frames is moot, right? The extra 100 million is a very minor component in such a case.

Doing estimation, just two 64 bit integers should be more than enough for you. One holds the 'mantissa' of a value and the other holds the 'exponent' (preferably base-2)

Working out the precise details involved should be quite easy. Multiplication involves multiplying mantissas and adding exponents, taking care to compensate for overflows by shifting the mantissa and biasing the exponent.


Yeah, the main reason for which I need that number is for remaining time calculations. A result of 100 years with a +-1 year error margin won't trouble me much (as far as I can give a rough error esteem).

Note that I don't need to keep track of the current frame's number, unless I decide to show a progress bar and a dynamic time countdown, which sounds pretty useless. Maybe I might do the opposite, like telling the algorithm "start from 35%", alias "skip the first n frames", but I can work around this so that I can keep every big number outside the main loop.

Can you give me a better explanation of what you said? Are you telling me to "simulate" a larger IEEE float functioning?

Share this post


Link to post
Share on other sites
Rockoon1    104
Quote:
Original post by AnitraZ
Are you telling me to "simulate" a larger IEEE float functioning?


Yes thats basically it, 'cept you dont have to mess with the dirty details (such as an implied bit, a biased exponent, or obsessive normalization)

While it might seem intimidating at first, its really not. Its only slightly more complex than 'fixed point' math.

You can work it out on paper (or in notepad) by using scientific notation (base-10 rather than base-2) and a bit of reasoning ability.. for instance:

x = 4E+12
y = 6E+14

multiplication:

x * y = (4 * 6)E+(12+14) = 24E+26

having worked it out, if you define a structure with '.m' being the mantissa and '.e' being the exponent, then multiplication in general:

z.m = x.m * y.m;
z.e = x.e + y.e;

From here its just a matter of avoiding (or handling) overflows in the mantissa (its highly unlikely that you will overflow a 64-bit exponent in any reasonable calculation)

Share this post


Link to post
Share on other sites
SuperNerd    100
How about rather than having events based on the absolute position of the frame you could do amount of frames until the next event. That could result in smaller managable numbers.

Share this post


Link to post
Share on other sites
Swarmer    142
You could just make your own base system with an array. Each element holds an integer representing the next digit, up to the base number.

So a Base-100 system with the array being {99,34,0,3} stores the value 3*(100^3) + 0*(100^2) + 34*(100^1) + 99*(100^0).

So if you had a Base-10,000 system, you'd just need an array of 750 elements to hold a number of size 10^3000.


I just realized that's exactly what grhodes said in his first post, but maybe that example helps.

Share this post


Link to post
Share on other sites
AnitraZ    122
Rockoon1:
Thanks a lot, I'm sure that will be of help.

Swarmer:
I didn't solve the maths, but I guess using a 232 base with DWORD elements will yeld Graham's result. Though, it's an interesting point of view, this thread has revealed to be a good source for ideas :)

SuperNerd:
I still need the total count. At launch, I'm doing some dummy speed measurement, assuming my CPU can handle m frames per second and that I have a total of n frames, I need to compute n / m / 3600 / 24 etc, having sub-numbers is gonna turn into Swarmer's solution.

Thanks for answering, I'll let u guys know if things go well :)

Share this post


Link to post
Share on other sites
Bob Janova    769
I wrote a large number class in C# which can count up to 1e3000, though I wouldn't recommend starting from 1 ;). I really ought to write it up and post it on CodeProject or something, but if you're interested I'll post the code.

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