Compilers
In the loop above, which transformation applies strength reduction to the index computation i * 4?
for (i = 0; i < n; i++)
sum += a[i * 4];- AReplacing i * 4 with a constant computed at compile time
- BCutting the iterations to a quarter and replicating the body four times
- CKeeping another variable and adding 4 to it each iteration
Show answer and explanation
Answer: C. Keeping another variable and adding 4 to it each iteration
Strength reduction replaces expensive operations with cheaper ones. Instead of multiplying i * 4 on every iteration, starting j at 0 and doing j += 4 each time turns the multiplication into an addition. The value changes with i, so it cannot be replaced by a constant. Multiplying by 4 can also become a shift (i << 2), another form of strength reduction. Replicating the body four times is loop unrolling.
- A. Its value changes with i, so it cannot become a constant.
- B. Replicating the body is loop unrolling.
- C. Correct. The multiplication becomes an addition per iteration.