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

# Write a program to calculate pow(x,n)

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.

#include<stdio.h>

//We need to import this file
#include<math.h>

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;

if(num--)
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);
else
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;
else
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