GATE 2016 CS (CS2) – Question 45
This function computes $X^Y$ for positive integers. Which invariant holds before every loop iteration?
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;
}Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (C) $X^Y=res\,a^b$
Explanation
Initially res·aᵇ=1·Xʸ. The even step preserves aᵇ because $(a^2)^{b/2}=a^b$. The odd step multiplies res by a and reduces b by one, preserving their product. Thus C is invariant; at termination b=0 it yields res=Xʸ.