very large loop counts in c

Question

How can I run a loop in c for a very large count in c for eg. 2^1000 times?

Also, using two loops that run a and b no. of times, we get a resultant block that runs a*b no. of times. Is there any smart method for running a loop a^b times?

Answer 1

You could loop recursively, e.g.

void loop( unsigned a, unsigned b ) {
    unsigned int i;
    if ( b == 0 ) {
        printf( "." );
    } else {
        for ( i = 0; i < a; ++i ) {
            loop( a, b - 1 );
        }
    }
}

...will print a^b . characters.

Answer 2

While I cannot answer your first question, (although look into libgmp, this might help you work with large numbers), a way to perform an action a^b times woul be using recursion.

function (a,b) {
   if (b == 0) return;
   while (i < a) {
     function(a,b-1);
   }
}

This will perform the loop a times for each step until b equals 0.

Answer 3

Regarding your answer to one of the comments: But if I have two lines of input and 2^n lines of trash between them, how do I skip past them? Can you tell me a real life scenario where you will see 2^1000 lines of trash that you have to monitor?

For a more reasonable (smaller) number of inputs, you may be able to solve what sounds to be your real need (i.e. handle only relevant lines of input), not by iterating an index, but rather by simply checking each line for the relevant component as it is processed in a while loop...

pseudo code:

BOOL criteriaMet = FALSE;
while(1)
{
    while(!criteriaMet)
    {
         //test next line of input
         //if criteria met, set criteriaMet = TRUE;
         //if criteria met, handle line of input
         //if EOF or similar, break out of loops
    }
    //criteria met, handle it here and continue
    criteriaMet = FALSE;//reset for more searching...

}

Answer 4

Use a b-sized array i[] where each cell hold values from 0 to a-1. For example - for 2^3 use a 3-sized array of booleans.

On each iteration. Increment i[0]. If a==i[0], set i[0] to 0 and increment i[1]. If 0==i[1], set i[1] to 0 and increment i[2], and so on until you increment a cell without reaching a. This can easily be done in a loop:

for(int j=0;j<b;++j){
    ++i[j];
    if(i[j]<a){
        break;
    }
}

After a iterations, i[0] will return to zero. After a^2 iterations, i[0],i[1] will both be zero. AFter a^b iterations, all cells will be 0 and you can exit the loop. You don't need to check the array each time - the moment you reset i[b-1] you know the all the array is back to zero.

Answer 5

Your question doesn't make sense. Even when your loop is empty you'd be hard pressed to do more than 2^32 iterations per second. Even in this best case scenario, processing 2^64 loop iterations which you can do with a simple uint64_t variable would take 136 years. This is when the loop does absolutely nothing.

Same thing goes for skipping lines as you later explained in the comments. Skipping or counting lines in text is a matter of counting newlines. In 2006 it was estimated that the world had around 10*2^64 bytes of storage. If we assume that all the data in the world is text (it isn't) and the average line is 10 characters including newline (it probably isn't), you'd still fit the count of numbers of lines in all the data in the world in one uint64_t. This processing would of course still take at least 136 years even if the cache of your cpu was fed straight from 4 10Gbps network interfaces (since it's inconceivable that your machine could have that much disk).

In other words, whatever problem you think you're solving is not a problem of looping more than a normal uint64_t in C can handle. The n in your 2^n can't reasonably be more than 50-55 on any hardware your code can be expected to run on.

So to answer your question: if looping a uint64_t is not enough for you, your best option is to wait at least 30 years until Moore's law has caught up with your problem and solve the problem then. It will go faster than trying to start running the program now. I'm sure we'll have a uint128_t at that time.