# Exponentation

- 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 f
_{c}. - 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
- f
_{c}(0) = c_{1} - f
_{c}(1) = c_{2} - f
_{c}(n) = c_{3}+ f_{c}(n/2)

- f
- What function is this? Again, we will try some analysis by hand to figure it out.
- A few applications of the recursive rule
- f
_{c}(n) - = c
_{3}+ f_{c}(n/2) - = c
_{3}+ c_{3}+ f_{c}(n/4) - = c
_{3}+ c_{3}+ c_{3}+ f_{c}(n/8)

- f
- Can we generalize? Certainly.
- f
_{c}(n) = k*c_{3}+ f_{c}(n/2^{k})

- f
- When can we get rid of the recursive term? When n/2
^{k}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 log
_{2}(n).

- Hence,
- f
_{c}(n) = log_{2}(n)*c_{3}+ c_{2}

- f
- That is, this algorithm is an O(log
_{2}(n)) algorithm.