N Doors Puzzle
June 13, 2012k'th Node from End
June 13, 2012Divide & Conquer Approach to find a^n
If you want to compute a^n ( a raised to the power n), then the algorithm is simple:
long power(int a, int n)
{
long prod = 1, i=0;
for(; i<n; i++)
prod = prod * a;
return prod;
}
But the above function will take O(n) time.
Write a divide & conquer algorithm which takes O(lg(n)) time to compute an.
Solution:
Linear Approach (given in question):
The function given in question will take O(n), because the product will happen n times.
The result is derived in a linear fashion multiplying a, n times. So Product is computed as
Prod = a * a * a * … … n-times
By the way, for those who are fascinated with recursion, the corresponding recursive function (for linear approach is)
long power(int a, int n)
{
if(n==0)
return 1;
else
return a * power(a, n-1)
}
Divide & Conquer Approach:
If we use the divide & conquer approach the time complexity can be reduced to O(lg(n)). This way we can get the same difference which is there in the linear search and binary search.
The Divide & Conquer approach square a each time, rather than multiplying it with a itself. i.e If we want to compute 2^8 we actually compute it like
Prod = ( (a ^ 2) ^ 2) ^ 2
Hence the operation (of square) will be performed only 3 (lg(8)) times and not 8 times.
I am sure you can write the program on your own, to help you I am writing the recursive program of divide-n-conquer below, If you are not able to write the iterative version, just leave a comment or mail me at kamal@ritambhara.com
/** divide & Conquer function to compute a^n.
* n is a positive integer */
long power(int a, int n)
{
if(n==0)
return 0;
// putting a check to avoid unnecessary recursive calls
if(a == 0)
return 0;
if(n%2 == 0) // b is even
return power(a*a, b/2);
else
return a * power(a*a, b/2);
}
Note: Recursion is not really a good optimized practice. Because each recursive call will have an overhead of function call and will take extra memory (to store the activation record of a function) on the stack.
5 Comments
Thanks.This post was really helpful. Especially the divide and conquer approach.
I would like to point out one error in the divide and conquer code.
I believe it should be-
if (n==0)
return 1;
yes, It’s one(1)
1 more error. You need to put an exit condition. I put n=n/2 in my code and used the condition while (n>1), so that once value of n becomes less than 1. The recursion stops.
Thanks a lot.
you had written wrong code of divide and conquer approach of exponentiation
Correct Code:-
#include
long int power(int x,int n){
if(n==0){
return 1;
}
else if(n%2==0){
return power(x,n/2)*power(x,n/2);
}
else{
return x*power(x,(n-1)/2)*power(x,(n-1)/2);
}
}
int main(){
int x,y;
printf(“Enter Number:- “);
scanf(“%d”,&x);
printf(“Enter Power:- “);
scanf(“%d”,&y);
printf(“%d^%d=%d”,x,y,power(x,y));
return 0;
}