For Loop UInt64 MaxValue Parallel Iteration Calculation Time

For Loop UInt64 MaxValue Parallel Iteration Calculation Time was an interesting Friday 30 Second question; if you were to iterate through a loop and you could parallelize your loop over 100 cores and each iteration took 1 nanosecond (i.e. 1 billion iterations per second) then how long would it take you to iterate over all the digits that could fit inside an UInt64?

e.g.

for (UInt64 i = 0; i < UInt64.MaxValue; i++)
{    
    ; // This operation takes 1 nanosecond and loop has no overhead
}

So this is really just a math situation. First we need to define what the value of Uint64.MaxValue is.  If we look up its value on MSDN, we know that it is a constant value of 18,446,744,073,709,551,615; that is, hexadecimal 0xFFFFFFFFFFFFFFFF.  Now at this point, it becomes common math.

This is the breakdown of how many operations will be happening per second in total across all cores.


Operations / Second / Thread = 1,000,000,000

Threads = 100

Operations / Second = 1,000,000,000 * 100 = 100,000,000,000

Now let’s apply it to the UInt64.MaxValue.

Seconds / Operation = 1 / 100,000,000,000

Total Seconds = Operations * (Seconds / Operation) = 18446744073709551615 * (1 / 100,000,000,000) = ~184467441

Minutes = 184467441/ 60 = 3074457

Hours = 3074457 / 60 = 51241

Days = 51241 / 24 = 2135

Weeks = 2135 / 7 = 305

Years = 305 / 52 = 5.86

The discussion and point that came out of this is a feature that was introduced in .Net 4.  It’s the concept of parallelizing your loops across all available processors with the Parallel.For<> loop. This will have its obvious benefits of being able to process at n times the amount of processors that are available.


For Loop Using UInt16 MaxValue

A demonstration of a For Loop Using UInt16 MaxValue. How would you iterate through all of the values in an unsigned 16-bit integer?

The following two loops will not work:


for (UInt16 i = 0; i < UInt16.MaxValue; i++)
{
    // Do something
}

for (UInt16 i = 0; i <= UInt16.MaxValue; i++)
{
    // Do something
}

The first loop skips the last value; the second loop goes into an infinite loop when it rolls over.

Let’s take a look at the first loop.


for (UInt16 i = 0; i < UInt16.MaxValue; i++)
{
    // Do something
}

First we need to know what UInt16.MaxValue equates to as a value.  UInt16.MaxValue is hexadecimal 0xFFFF which is a constant value of 65535.  So when we are looking into the loop with for (UInt16 i = 0; i < UInt16.MaxValue; i++) the last iteration will not happen because we would need an overflow value of 65536.  However, since UInt16.MaxValue is a constant value of 65535, the last value causes the loop to exit before the last Do Something is completed.

Let’s take a look at the second loop.

for (UInt16 i = 0; i <= UInt16.MaxValue; i++)
{
    // Do something
}

The problem we are seeing here is an infinite loop gets created.  This again takes us to needing to understand how UInt16.MaxValue works.  As we said, UInt16.MaxValue is the hexadecimal value of 0xFFFF.  So if you look at this loop if will actually go through and complete the last iteration at 65535.  However, in terms of this hexadecimal value, when you add 1 to it after the last iteration if wraps around to 0 again. Hence, our infinite loop problem.

Solution? Use a do/while loop.

ushort i = 0;
do
{
    // do something
}
 while(i++ < UInt16.MaxValue);

This is close to the first loop in our question, but it will cause the Do Something to iterate all the way through before it does a check on the UInt16 value.

Here it is as a test console app to confirm all the above from Guy Ellis.


static void Main(string[] args){
    UInt16 i = 0;
    do    {        if (i == UInt16.MinValue)
        {
            Console.WriteLine("MinValue");
        }
        if (i == UInt16.MaxValue)
        {
            Console.WriteLine("MaxValue");
        }
    } while (i++ < UInt16.MaxValue);
    Console.WriteLine("Enter to finish...");
    Console.ReadLine();}


StackOverflow Profile