Exponentation

Posted By on November 5, 2014


Download PDF
Problems Solved by divide and conquer strategy
Problem solved using Greedy strategy
  • Can we use divide-and conquer to solve the exponentiation problem (or to improve our solution)?
  • What can we divide in half? (What gives the “size” of the problem?)
  • Here’s another version of exponentiation, based on a divide-and-conquer strategy.
      /**
       * Compute x^n by a recursive divide-and-conquer algorithm.
       */
      public static double expC(double x, int n) {
        // Handle negative exponents.  x^(-n) = 1/(x^n)
        if (n < 0) {
          return 1/expB(x,-n);
        } // if (n < 0)
    
        // Base case: x^0 is 1.
        if (n == 0) {
          return 1;
        } // Base case: n == 0
    
        // Recursive case (when n is odd)
        //   x*x*...*x = x*(x*...*x)
        //   That is: x^n = x*(x^(n-1))
        else if (n % 2 == 1) {
         return x * expC(x,n-1);
        } // Recursive case (when n is odd)
    
        // Recursive case (when n is even)
        //   Let n be 2k
        //   x^n = x^(2k) = x^k * x^k
        else {
          int k = n/2;
          double tmp = expC(x,k);
          return tmp*tmp;
        } // Recursive case (when n is even)
      } // expC
    
  • We’ll use the same technique of “define a function whose value is the number of steps the algorithm takes”. This time, we’ll call the function fc.
  • This time, life is a little harder because we have two different recursive cases. (Odd and Even).
    • Fortunately, the odd case transforms into the even case. That is, if n is odd, then on the next recursive call it will be even.
    • In effect, by choosing a bigger value for the “constant” work, we can pretend that n is divided by two in each recursive call.
    • If it makes it easier, think about replacing the lines that read
          else if (n % 2 == 1) {
           return x * expC(x,n-1);
          } // Recursive case (when n is odd)
      

      with

          else if (n % 2 == 1) {
            double tmp = expC(x, (n-1)/2);
            return x * tmp * tmp;
          } // Recursive case (when n is odd)
      
  • So
    • fc(0) = c1
    • fc(1) = c2
    • fc(n) = c3 + fc(n/2)
  • What function is this? Again, we will try some analysis by hand to figure it out.
  • A few applications of the recursive rule
    • fc(n)
    • = c3 + fc(n/2)
    • = c3 + c3 + fc(n/4)
    • = c3 + c3 + c3 + fc(n/8)
  • Can we generalize? Certainly.
    • fc(n) = k*c3 + fc(n/2k)
  • When can we get rid of the recursive term? When n/2k is 1.
    • That is, k is “the power to which you must raise 2 in order to get n”.
    • Fortunately, there’s a name for that value. We call it log2(n).
  • Hence,
    • fc(n) = log2(n)*c3 + c2
  • That is, this algorithm is an O(log2(n)) algorithm.
Problems Solved by divide and conquer strategy
Problem solved using Greedy strategy

Download PDF

Posted by Akash Kurup

Founder and C.E.O, World4Engineers Educationist and Entrepreneur by passion. Orator and blogger by hobby

Website: http://world4engineers.com