GATE CSE 1994 | Question: 6

Question

What function of $x$, $n$ is computed by this program?

Function what(x, n:integer): integer:
Var
    value : integer
begin
    value := 1
    if n > 0 then
    begin
        if n mod 2 =1 then
            value := value * x;
        value := value * what(x*x, n div 2);
    end;
    what := value;
end;

Comments

can anyone plz explain this ques and its relevant answer?

---

This program computes $x^n$ and T.C is $\Theta(logn)$ as n is divided by 2 each time.

---

Wow this is so beautiful

Answer 1

How you will compute $x^{n}$?

The first solution that we may think of is a brute force approach which is multiplying x, n times. Time complexity of this solution is $\Theta (n)$.

int fun(n) 
{ 
    int ans=1;  
    for(int i=1;i<=n;i++) 
        ans=ans*x; 
    return ans;
}

Can we do better? Can you reduce the time complexity of this problem?

The answer is yes and the solution is given in question 6.

This method is known as Exponentiation_by_squaring or Binary_exponentiation.

Algorithm: Exponentiation by squaring - Wikipedia | Binary Exponentiation - Competitive Programming Algorithms (cp-algorithms.com)

The time complexity of this solution is $O(\log n).$ That is the significance of this algorithm.

Answer 2

answer - $x^n$

Comments

why is it not working for   x=3 and n=6 or 5 ??

for what(3,6) I am getting 9 as the output.

Anyone pls help!!

@Arjunsir  @Abhrajyoti00

---

@Pranavpurkar It is working for $what(3,6)$ also.

$what(3,6) → value = 1*what(3^2,3)$

$what(3^2,3) → value = 1*3^2; value = 3^2*what(3^2 * 3^2, 1)$

$what(3^4,1) → value = 1*3^4*what(3^4*3^4,0)$

$what(3^4*3^4,0) → value = 1; $

---

Putting the values back in :-

$what(3,6) → value = 1*3^2*3^4 = 3^6$

 

P.s. I hope it will be clear now :)

---

Abhrajyoti00

I made a mistake here by considering the statement below if as the else .

Thanks brother! got it now.

Answer 3

take what(2,8) U will get 256 as ans.

what(2,7) U will get 128 as ans.

Hence ans is xⁿ.

But the beauty of this code is it is done in O(logn) time instead of O(n) time.