Jun 132012
 

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.

  2 Responses to “Divide & Conquer Approach to find a^n”

Comments (2)
  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.

  2. 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;

 Leave a Reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

(required)

(required)