Calculate pow function

Lets look at some solutions.

Solution 1 - Using recursion

int pow(int x, int y)
{
  if(y == 1) return x ;
  return x * pow(x, y-1) ;
}





Divide and Conquer C program

/* Function to calculate x raised to the power y */
int power(int x, unsigned int y)
{
    if( y == 0)
        return 1;
    else if (y%2 == 0)
        return power(x, y/2)*power(x, y/2);
    else
        return x*power(x, y/2)*power(x, y/2);
 
}
 
/* Program to test function power */
int main()
{
    int x = 2;
    unsigned int y = 3;
 
    printf("%d", power(x, y));
    getchar();
    return 0;
}

Time Complexity: O(n)
Space Complexity: O(1)
Algorithmic Paradigm: Divide and conquer.
Above function can be optimized to O(logn) by calculating power(x, y/2) only once and storing it.

/* Function to calculate x raised to the power y in O(logn)*/
int power(int x, unsigned int y)
{
    int temp;
    if( y == 0)
        return 1;
    temp = power(x, y/2);
    if (y%2 == 0)
        return temp*temp;
    else
        return x*temp*temp;
}

Time Complexity of optimized solution: O(logn)
Let us extend the pow function to work for negative y and float x.

* Extended version of power function that can work
 for float x and negative y*/
#include<stdio.h>
 
float power(float x, int y)
{
    float temp;
    if( y == 0)
       return 1;
    temp = power(x, y/2);      
    if (y%2 == 0)
        return temp*temp;
    else
    {
        if(y > 0)
            return x*temp*temp;
        else
            return (temp*temp)/x;
    }
} 
 
/* Program to test function power */
int main()
{
    float x = 2;
    int y = -3;
    printf("%f", power(x, y));
    getchar();
    return 0;
}

Source -http://www.geeksforgeeks.org/write-a-c-program-to-calculate-powxn/

Thanks.