algorithmloopsiterationformula

Explanation of formula to count # of iterations in a loop


https://stackoverflow.com/a/66458617/18069660

total iterations = (end - start + incr)/incr; // for <=
total iterations = (end - start  + incr - 1)/incr; // for <

I have tested both of these formulas and different versions of each for different kinds of for loops. I understand how they work, what I do not understand is how they were made.

Why does the total number of iterations = (the end value minus the start value + the increment)/(divided by the increment).

Why and how were these values chosen and used in such a manner to count the number of iterations. What is the connection between them? How was the formula derived?


Solution

  • Let's first look at the loop that uses <=:

    for (int i = start; i <= end; i += incr)
    

    Let's look at the value of i at each iteration:

    Iteration value of i
    1 start
    2 start + incr
    3 start + 2*incr
    4 start + 3*incr
    ... ...
    n start + (n-1)*incr

    Case A. i becomes equal to end

    If end happens to be one of the values in the second column, for instance, end == start + k*incr for some k, then we can see the number of iterations is k+1.

    So we have now the following rule:

    If end can be written as start + k*incr for some integer k, then the number of iterations is k+1 and so we can write:

    end == start + (numIterations - 1)*incr
    

    Which is equivalent to saying:

    numIterations = (end - start) / incr + 1
    

    Or also:

    numIterations = (end - start + incr) / incr
    

    Case B: i never becomes equal to end

    In this case there is no integer k such that end == start + k*incr. We can find the greatest k for which end < start + k*incr. In other words, there is a positive remainder < incr such that end == start + k*incr + remainder.

    We repeat the logic in the previous point, but with that non-zero remainder:

    end == start + (numIterations - 1)*incr + remainder
    

    Which is equivalent to saying:

    numIterations = (end - start - remainder) / incr + 1
    

    Or also:

    numIterations = (end - start - remainder + incr) / incr
    

    When / represents integer division, we don't have to subtract the remainder in that numerator. The integer division will exclude the fractional part that you would get with a real division. So we can simplify to:

    numIterations = (end - start + incr) / incr
    

    I hope this explains the case for a loop with <= end.

    Loop with < end

    When the loop variable cannot become equal to end, but at the most to end-1, then let's translate this case to a loop where the condition is <= end - 1. It is equivalent.

    Then apply the formula above by replacing end with end-1, and we get the second form of the formula you presented.