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.