Consider the C program fragment below which is meant to divide \(x\) by \(y\)…
2017
Consider the C program fragment below which is meant to divide \(x\) by \(y\) using repeated subtractions. The variables \(x,y,q\) and \(r\) are all unsigned int.
while (r >= y) { r=r-y; q=q+1; }
Which of the following conditions on the variables \(x,y,q\) and \(r\) before the execution of the fragment will ensure that the loop terminated in a state satisfying the condition \(x==(y*q + r)\) ?
- A.
\((q==r) \ \&\& \ (r==0)\) - B.
\((x>0) \ \&\& \ (r==x) \ \&\& \ (y>0)\) - C.
\((q==0) \ \&\& \ (r==x) \ \&\& \ (y >0)\) - D.
\((q==0) \ \&\& \ (y>0)\)
Attempted by 234 students.
Show answer & explanation
Correct answer: C
Correct precondition: q == 0, r == x, and y > 0.
Invariant: Before the loop and after every iteration we have x == y*q + r.
Initialization: With q == 0 and r == x, x == y*q + r holds because x == y*0 + x.
Preservation: If x == y*q + r holds and the loop body executes (r >= y), after r := r - y and q := q + 1 we have y*(q+1) + (r-y) = y*q + r, so the invariant is preserved.
Termination: The loop exits when r < y. At that point the invariant still holds, so x == y*q + r is true at termination.
Note: y > 0 is required so that each executed iteration decreases r (ensuring progress). If y were zero the loop would not make progress and could not guarantee termination.
A video solution is available for this question — log in and enroll to watch it.