The Exponent Zero Case
This fast-exponentiation routine is supposed to return for :
int f(int x, int y) {
int r = 1;
int b = x; /* base */
int e = y; /* exponent */
while (e > 1) {
if (e % 2 == 1) { r = b * r; }
b = b * b;
e = e / 2;
}
return r * b;
}
Tracing f(2, 7) shows the quantity never moves:
| iteration | b |
e |
r |
||
|---|---|---|---|---|---|
| 0 | 2 | 7 | 1 | 128 | 128 |
| 1 | 4 | 3 | 2 | 64 | 128 |
| 2 | 16 | 1 | 8 | 16 | 128 |
The loop exits with e == 1, and return r * b reads off . Which call still returns the wrong answer?
Sign in to answer questions and track your progress
Sign In