# Exponentation

Posted By on November 5, 2014

• 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.

#### Posted by Akash Kurup

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

Website: http://world4engineers.com