Sunday, December 26, 2010

Compute the Power(x,n) in log(n) steps

Implement the power(x,n) which finds the value of x^n efficiently.

Approach:

Power of x^n can be naively computed by multiplying 'x' n times.
```void power(int x, int n) {
int r = 1;
for (int i=0;i<n;i++)
r *= x;
return r;
}
```

We can divide the problem in smaller similar problems.
x^n = x^(n/2) * x^(n/2)   //If n is even
x^n = x^(n/2) * x^(n/2) * x // If x is odd

Using the above result, we can recursively reduce the problem to log(n) steps only.
```int power(int x, int y) {
int r;
if(!y)
return 1;
r = power(x, y/2);
if (y%2 == 0)
return r*r;
else
return r*r*x;
}
```

1. int pow(int x, int n)
{
if (n==1)
return x;
else if(n==2)
return x*x;
else if(n%2)
return x*pow(pow(x,n/2),2);

else
return pow(pow(x,n/2),2);
}

2. int pow(int x, int n)
{
int res = x;
while(n > 1){
res = res*res;
if(n % 2 == 1){
res = res * x;
}
n = n / 2;
}
return res;
}

3. @banka, imavalon.. correct!!! but taking an iterative approach is a better idea.....

4. @Imavalon: pow(2,5),pow(2,9) gives incorrect result.

5. This should do the trick (Python):
def pow(x, n):
res = 1
while n:
if n % 2 == 0:
x *= x
n /= 2
else:
res *= x
n -= 1
return res

Regards,
Matteo

6. @landimatte .. good job!!!

7. correcting, i think.

int pow(int x, int n)
{
int res = 1;
while(n > 0){
if(n % 2 == 1){
res = res*x;
}
x = x*x;
n = n/2;
}
return res;
}