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 :)

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.

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 :)

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.

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"?)

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.

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, :(.