Home Misc Write a program to calculate pow(x,n)

Write a program to calculate pow(x,n)

by nikoo28
0 comment

We will discuss how to calculate the result when a number ‘x’ is raised to the power ‘y’.
Originally C provides a standard function that allows us to directly use the power function. It can be used in the following manner.


//We need to import this file

int main(void)
    int x =4;

    //calculates 4 ^ 3.
    int result = pow(x,3);

    printf("Result = %d",result);
    return 0;

Now suppose that we need to write a custom function by ourselves. Here are the sample methods by which we can do so.
Simple Iterative method

int power(int base, int num)
    int result = 1;

    // this function will return base ^ num
    int i= 1;
    for(i = 1; i<=num; i++)
        result = result * base;

    return result;

Recursive Method

int power_rec(int base, int num)
    if(num == 0)
        return 1;

        return base * power_rec(base, num);

But in both these methods, the time complexity is of O(n), and this can take a long time in operation.
We can modify our code and take advantage of this property of maths:-
We can write 2^6 as (2*2*2) * (2*2*2)
That means, we can call the power function as power(base,num/2)
Here is the implementation of the same.

//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);
        return x*power(x, y/2)*power(x, y/2);

The technique we are using here is Divide and Conquer. We can further reduce its complexity to O(log n) by calculating the result power(base,num/2) only once and then using it further.

/* 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;
        return x*temp*temp;

If we change the type of ‘temp’ to float and the return type of the function, we can use the above function for float values as well.

You may also like

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More