Talk:Normalized loop

Latest comment: 1 year ago by 12.154.207.45

In my opinion the normalization of example 1 is not correct.

// Example 1

for ( i = 7; i < MAX; i+=3 )

 a[i] = b[i] + 5;

the normalization should look like this:

for ( i = 0; i < (MAX-7+3)/3; i++ )

 a[i*3+7] = b[i*3+7] + 5;

or

for ( i = 0; i < (MAX-7)/3+1; i++ )

 a[i*3+7] = b[i*3+7] + 5;

--Tuxold1964 (talk) 17:53, 9 May 2011 (UTC)Reply

The normalization as given is clearly incorrect. We can take MAX is 14, then the original loop will have 3 iterations: 7, 10, and 13.
The normalized loop will have 2 iterations. 0 and 1. `(14 - 7) / 3` is 2 and only 0 and 1 are less than 2.
With the `<` condition the iteration range is semi-open. `[7 .. MAX)`. One can convert this to the closed interval `[7 .. MAX-1]`. That is, if MAX-1 is to be executed it is on the possible interval.
```
// Example 1
for ( i = 7; i <= MAX-1; i+=3 )
a[i] = b[i] + 5;
```
Now that this is a closed interval, the total number of iterations can be computed as `(MAX-1 - 7 + 3) / 3`, or generally `(max - min + step) / step`. Again if MAX is 14 then this is `9/3 => 3`, which we know is the correct answer. (If the equation produces a non-positive result, the loop has no iterations.)
Now if MAX is 13, the original loop would execute 2 iterations: 7 and 10. `(MAX-7+3)/3 => 9/3 => 3`, not 2. And `(MAX-7)/3 + 1 => 6/3 + 1 => 3`, which is again not 2. However, `(MAX-1 - 7 + 3) / 3` is `8 / 3`, which is the correct answer, 2. 12.154.207.45 (talk) 21:07, 9 June 2023 (UTC)Reply