The following function computes XY for positive integers X and Y. int exp (int…
2016
The following function computes XY for positive integers X and Y.
int exp (int X, int Y) {
int res = 1, a = X, b = Y;
while (b != 0) {
if (b % 2 == 0) {a = a * a; b = b/2; }
else {res = res * a; b = b - 1; }
}
return res;
}
Which one of the following conditions is TRUE before every iteration of the loop?
- A.
XY = ab
- B.
(res ∗ a)Y = (res ∗ X)b
- C.
XY = res ∗ ab
- D.
XY = (res ∗ a)b
Attempted by 152 students.
Show answer & explanation
Correct answer: C
Claim: The invariant X^Y = res * a^b holds before every iteration of the loop.
Initialization: Before the first iteration res = 1, a = X, b = Y, so res * a^b = 1 * X^Y = X^Y. The invariant holds initially.
Maintenance: Assume the invariant X^Y = res * a^b holds at the start of an iteration. Consider the two branches of the loop:
If b is even: the code sets a ← a * a and b ← b / 2, while res is unchanged. The new right-hand side is res * (a*a)^{b/2} = res * a^b, so the invariant is preserved.
If b is odd: the code sets res ← res * a and b ← b - 1, while a is unchanged. The new right-hand side is (res*a) * a^{b-1} = res * a^b, so the invariant is preserved.
Termination: The loop stops when b = 0. The invariant then gives X^Y = res * a^0 = res, so res holds X^Y and the function returns the correct result.
A video solution is available for this question — log in and enroll to watch it.