GATE CS 2016 Set 2 Q.45 (CS Q.35): Functions, Recursion, Scope and Storage Classes

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?

$X^Y = a^b$

$(res * a)^Y = (res * X)^b$

$X^Y = res * a^b$

$X^Y = (res * a)^b$

Official answer and solution

Official answer: C
From: Official GATE 2016 answer key

Solution

Identify the loop invariant of the binary exponentiation algorithm.

The function implements the classic binary exponentiation algorithm (exponentiation by squaring) to compute $X^Y$ .

Trace the loop variables:

Initial state: res = 1, a = X, b = Y.
Testing Option (C): $\text{res} \times a^b = 1 \times X^Y = X^Y$ . The relation holds initially.

Inductive step: Assume $X^Y = \text{res} \times a^b$ holds before an iteration with $b > 0$ :

Case 1: $b$ is even ( $b \% 2 == 0$ ).
The code updates $a_{\text{new}} = a^2$ and $b_{\text{new}} = b / 2$ , leaving res unchanged. $\text{res}_{\text{new}} \times (a_{\text{new}})^{b_{\text{new}}} = \text{res} \times (a^2)^{b/2} = \text{res} \times a^b = X^Y$
Case 2: $b$ is odd ( $b \% 2 \ne 0$ ).
The code updates $\text{res}_{\text{new}} = \text{res} \times a$ and $b_{\text{new}} = b - 1$ , leaving a unchanged. $\text{res}_{\text{new}} \times (a_{\text{new}})^{b_{\text{new}}} = (\text{res} \times a) \times a^{b-1} = \text{res} \times a^b = X^Y$

In both branches, the quantity $\text{res} \times a^b$ is invariant and remains equal to $X^Y$ .

When the loop terminates ( $b = 0$ ):

\text{res} \times a^0 = \text{res} = X^Y

Therefore, the condition $X^Y = \text{res} * a^b$ is TRUE before every iteration of the loop (Option C).

Final answer

Common trap

Selecting $X^Y = a^b$ , which only holds at initialization and is violated as soon as res is multiplied.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2016 Computer Science and Information Technology (CS) Session 2
Question: 45 of 65, printed as CS Q.35
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source