X^Y
Algorithm
Input Two integer x and y
Output Print x^y
complexity O(logn)
power(x,y)
1 if (y==0) then
2 return 1;
3 else if(y%2==0)
4 return power(x,y/2)*power(x,y/2);
5 else
6 return x*power(x,y/2)*power(x,y/2);
Algorithm Description
The algorithm takes advantage of the fact that if n is an even number then xn=xn/2*xn/2 otherwise xn=x*xn/2*xn/2 By this divide and conquer approach only logn iterations will be required because in logn iterations number n will reach to 1
C Code
//Find the power of a number
//Input : Two positive integer say x,y
int power(int x,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);
}
int main()
{
int x,y,z;
printf("Enter x,y\n");
scanf("%d %d",&x,&y);
z=power(x,y);
printf("x raise to the power y is %d",z);
}
