Question Why did this for loop run forever?

glasswizzard

Well-known member
Joined
Nov 22, 2019
Messages
126
Programming Experience
Beginner
Here is a problem I have just solved, but I'd like to know why it happened in the first place. Here is a console program from the web that populates a list of prime numbers:

C#:
using System;
using System.Collections.Generic;

namespace PrimeFactorCalculator
{
    /// <summary>
    /// This program will calculate and populate a list of prime factors.
    /// </summary>
    class Program
    {
        private static List<long> _primes = new List<long>();

        static void Main(string[] args)
        {
            // Manually add the first prime number.
            _primes.Add(2);
            Console.WriteLine(2);

            for (long checkValue = 3; checkValue <= long.MaxValue; checkValue += 2)
            {
                if (IsPrime(checkValue))
                {
                    _primes.Add(checkValue);
                    Console.WriteLine(checkValue);
                }
            }
        }

        private static bool IsPrime(long checkValue)
        {
            bool isPrime = true;

            foreach (long prime in _primes)
            {
                if ((checkValue % prime) == 0 && prime <= Math.Sqrt(checkValue))
                {
                    isPrime = false;
                    break;
                }
            }
            return isPrime;        
        }
    }
}

It works fine. I have a program where I manually populate a list of primes and I used the above code to replace my huge list of PrimeList.Add method calls. Here is how the relevent parts of my code look, this is the list itself:

C#:
public static List<short> PrimeList { get; }

It is instantiated in the constructor:

C#:
static NumberPropertiesModel()
{
    PrimeList = new List<short>();
    PopulatePrimeList();
    // more code
}

I put the main code I got from the web into the PopulatePrimeList() method:

C#:
public static void PopulatePrimeList()
{
    // Manually add the first prime number.
    PrimeList.Add(2);

    for (short checkValue = 3; checkValue <= short.MaxValue && checkValue > 0; checkValue += 2)
    {
        if (IsPrime(checkValue))
        {
            PrimeList.Add(checkValue);
        }
    }
}

private static bool IsPrime(short checkValue)
{
    bool isPrime = true;

    foreach (short prime in PrimeList)
    {
        if ((checkValue % prime) == 0 && prime <= Math.Sqrt(checkValue))
        {
            isPrime = false;
            break;
        }
    }

    return isPrime;
}

You may notice apart from using shorts instead of longs I have also added a condition for the for loop, that being "&& checkValue > 0". I had to add this because the loop would run forever, I used Debug.WriteLine to see what was happening and the checkValue variable would end up going from one end of it's maxvalue to the other and just kept cycling through.

When I saw this it made me think that somehow checkValue ended up at it's maxvalue - 1, thereby going over it's limit when it's incremented by 2, and then wrapping back around from the other end. This gave me the idea to make sure it's always above zero. But when I saw that the max value for a short is an odd number I realized my thinking was wrong, a shorts maxvalue - 1 will always be an even number and since checkedValue starts at 3 and is incremented by 2 it can never be an even number. So my idea on what was going wrong was itself wrong, but my solution did work.

I'm very curious to know if anyone can tell why this happened?
 
Do you know how to set conditional breakpoints? If not, you should read up on how to do so and use one here. That way, you can do things like run your loop until you are nearly at what you think should be the last iteration and then break, so you can step line by line from there and see for yourself exactly what's happening.
 
If you think about it logically though, the issue is obvious. You tell the loop to continue as long as a short variable is either less than or equal to the maximum value a short variable can have. That means that, for your loop to terminate, your short variable would have to be greater then the greatest value it can possibly be, which is nonsense.

Your loop continues until your variable is either equal to or one less than its maximum possible value and then you add 2 to it. What do you think should happen when you perform that addition? It obviously can't create a value greater then the greatest possible value so there are only two possibilities: either it overflows and causes an exception or it doesn't overflow and the highest-order bit is somehow treated differently. Obviously it is not the former so it must be the latter. That highest-order bit ends up in the position used to represent the sign and that is why it wraps back to a negative number.

If you don't already know about two's complement representation of numbers, now would be a good time to look into it.
 
If you think about it logically though, the issue is obvious. You tell the loop to continue as long as a short variable is either less than or equal to the maximum value a short variable can have. That means that, for your loop to terminate, your short variable would have to be greater then the greatest value it can possibly be, which is nonsense.

But why doesn't that happen for the original code that uses a long variable instead of a short?
 
I don't know what did or did not happen when you ran any of your code but you can see what's happening if you run this code:
C#:
static void Main(string[] args)
{
    short s = short.MaxValue;
    long l = long.MaxValue;

    Console.WriteLine(s);
    Console.WriteLine(l);

    Console.WriteLine(Convert.ToString(s, 2).PadLeft(16, '0'));
    Console.WriteLine(Convert.ToString(l, 2).PadLeft(64, '0'));

    s += 1;
    l += 1;

    Console.WriteLine(s);
    Console.WriteLine(l);

    Console.WriteLine(Convert.ToString(s, 2).PadLeft(16, '0'));
    Console.WriteLine(Convert.ToString(l, 2).PadLeft(64, '0'));

    Console.ReadLine();
}
 
Back
Top Bottom