WAP to Calculate The Power x^n Efficiently in O(logn)

Method 1 Using Iterative Method

#include
main()
{
int num, p , result;
printf("Enter the number : ");
scanf("%d",&num);
printf("\nAnd its power also. : ");
scanf("%d",&p);

result = power(num,p);
printf("\nThe result is %d\n", result);
}
power(int x, int y)
{
int i,temp =1;
if(y==0)
return(1);
if(y==1)
return(x);
else
{
for(i=1;i<=y;i++)
temp = temp*x;
return(temp);
}
}

Method 2 Using Recursion

Below solution divides the problem into subproblems of size y/2 and call the subproblems recursively.


#include

/* 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.

Method 3 Reducing Instruction to Nearly Half

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)

Method 4 case handled for -Ive Number

Let me 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

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;
}

Method 5 Power calculation Using + and - Operator Only

#include



/* assumption: y is greater than or equal to 0*/
int multiply(int x, int y)
{
if(y)
return (x + multiply(x, y-1));
return 0;
}
/* assumption: b is greater than or equal to 0*/
int pow(int a, int b)
{
if(b)
return multiply(a, pow(a, b-1));
return 1;
}
int main()
{
printf("\n %d", pow(3, 2));
getchar();
return 0;
}


Time Complexity O(n)
Space Complexity O(n) if Stack Space else O(1)

Run Here https://ideone.com/BBdU1