Consider the following pseudo-code fragment in which an invariant for the loop is “ $m ^*x^k=p^n$ and…

Question

Consider the following pseudo-code fragment in which an invariant for the loop is “ $m ^*x^k=p^n$ and $𝑘≥0$ ” (here, $𝑝$ and $𝑛$ are integer variable that have been initialized):

/* Pre-conditions : $p \geq 1 \wedge n \geq 0$ */

/* Assume that overflow never occurs */

int $𝑥=𝑝;$ int $𝑘=𝑛$; int $𝑚=1$;

while $(𝑘<>0$) {

if (k is odd) then $𝑚=𝑚∗𝑥$;

$𝑥=𝑥∗𝑥$;

$k=\lfloor k/2 \rfloor$; /* floor($𝑘/2$) */

}

Which of the following must be true ar the end of the while loop?

𝑥=𝑝𝑛
𝑚=𝑝𝑛
𝑝=𝑥𝑛
𝑝=𝑚𝑛

Accepted Answer

Correct answer: B — Answer: m = p^n Reasoning using the loop invariant: Invariant: m * x^k = p^n and k ≥ 0. Initially x = p, k = n, m = 1, so the invariant holds: 1 * p^n = p^n. Maintenance when k is odd: write k = 2q + 1. After the updates m' = m * x, x' = x^2, k' = q. Then m' * x'^{k'} = (m * x) * (x^2)^q = m * x^{2q+1} = m * x^k, so the invariant is preserved. Maintenance when k is even: write k = 2q. Then m remains the same, x' = x^2, k' = q, and m * x'^{k'} = m * (x^2)^q = m * x^{2q} = m * x^k, so the invariant is preserved. Termination: the loop stops when k = 0. Plugging into the invariant gives m * x^0 = p^n, so m = p^n. Thus m holds the value p^n at loop end. Notes on the other statements: x = p^n is not generally true at termination; x is repeatedly squared and may end up as a higher power of p. For example, p = 2, n = 3 yields final x = 16 while p^n = 8. p = x^n and p = m^n are not implied by the invariant or the updates and are false in general (see small numeric counterexamples above).

Answer

A. $x=p^n$

Answer

B. $m=p^n$

Answer

C. $p=x^n$

Answer

D. $p=m^n$

Consider the following pseudo-code fragment in which an invariant for the loop…