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;
}

7 comments :

  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);
    }

    ReplyDelete
  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;
    }

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

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

    ReplyDelete
  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

    ReplyDelete
  6. 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;
    }

    ReplyDelete