Discussion
The following function computes \(X^{Y}\) 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?
Answer: C
The loop invariant is \(X^{Y} = \mathrm{res} * a^{b}\).
Check that it holds at the start and is preserved by each branch:
- Initially \(\mathrm{res} = 1\), \(a = X\), \(b = Y\), so \(\mathrm{res} \cdot a^{b} = X^{Y}\).
- If \(b\) is even, \(a\) becomes \(a^{2}\) and \(b\) becomes \(b/2\): \((a^{2})^{b/2} = a^{b}\), unchanged.
- If \(b\) is odd, \(\mathrm{res}\) becomes \(\mathrm{res} \cdot a\) and \(b\) becomes \(b - 1\): \(\mathrm{res} \cdot a \cdot a^{b-1} = \mathrm{res} \cdot a^{b}\), unchanged.
When the loop ends, \(b = 0\), so \(X^{Y} = \mathrm{res}\), which is what the function returns.
\(X^{Y} = a^{b}\) fails after the first odd step, when part of the power has moved into \(\mathrm{res}\). \(X^{Y} = (\mathrm{res} * a)^{b}\) raises \(\mathrm{res}\) to the power \(b\) as well, and \((\mathrm{res} * a)^{Y} = (\mathrm{res} * X)^{b}\) holds at the start but fails after the first even step, when \(a\) becomes \(X^{2}\) while \(b\) halves.
Post your comment
Please log in or register to post a comment.
Examination Categories
- SSC Exams
- Banking Exams
- Teaching Exams
- Civil Services Exams
- Railways Exams
- Engineering Recruitment Exams
- Defence Exams
- State Government Exams
- Police Exams
- Insurance Exams
- Nursing Exams
- Other Government Exams
- NRA CET
- PG Entrance Exams
- Campus Placement
- MBA Entrance Exams
- CUET and UG Entrance
- Judiciary Exams
- Regulatory Body Exams
- Software Development