Consider the following pseudo-code fragment in which an invariant for the loop…
2019
Consider the following pseudo-code fragment in which an invariant for the loop is
“m * xk = pn” and k ≥ 0 (here p and n are integer variables that have been initialized).
Pre-conditions: p ≥ 1 and n ≥ 0. Assume the overflow condition never occurs.
int x = p;
int k = n;
int m = 1;
while (k <> 0) {
if (k is odd) then m = m * x;
x = x * x;
k = ⌊k / 2⌋;
}
Which of the following must be true at the end of the while loop?
- A.
x = pⁿ
- B.
m = pⁿ
- C.
p = xⁿ
- D.
p = mⁿ
Attempted by 291 students.
Show answer & explanation
Correct answer: B
Conclusion: m = p^n.
Key invariant: m * x^k = p^n.
Initialization: initially x = p, k = n, m = 1, so m * x^k = 1 * p^n = p^n. The invariant holds before the loop starts.
Maintenance: show each loop iteration preserves the invariant.
If k is odd: before the iteration m * x^k = p^n. The code sets m' = m * x, x' = x * x, k' = (k-1)/2. Then m' * x'^{k'} = (m * x) * (x^2)^{(k-1)/2} = m * x * x^{k-1} = m * x^k = p^n, so the invariant holds after the iteration.
If k is even: before the iteration m * x^k = p^n. The code leaves m unchanged, sets x' = x * x, k' = k/2. Then m * x'^{k'} = m * (x^2)^{k/2} = m * x^k = p^n, so the invariant is preserved.
Termination: the loop ends when k = 0. Plugging into the invariant gives m * x^0 = p^n, i.e. m * 1 = p^n, therefore m = p^n.
Hence the correct necessary fact at the end of the while loop is that m = p^n.
A video solution is available for this question — log in and enroll to watch it.