# Divide and Conquer to find a power

I understand the concept behind Divide and Conquer, making one problem into sub problems and then merging the solutions together. However, from looking at a past paper a question has occured where it asks how 2^11 can be found using Divide and Conquer, I'm just confused how finding a power can be divided into sub problems =/

pow(2, 11) = 2 * pow(2, 5) * pow(2, 5)

pow(2, 5) = 2 * pow(2, 2) * pow(2,2)

pow(2, 2) = pow(2, 1) * pow(2, 1)

pow(2, 1) = 2

would this be correct?

• Other than $pow(2, 0)$ being $0$ that seems correct. – Tom van der Zanden Jan 2 '15 at 15:04

The algorithm relies on two facts:

• If $n$ is even, $n=2k$, we have $a^n = a^{2k}=a^ka^k = a^{n/2}a^{n/2} = (a^{n/2})^2$
• If $n$ is odd, $n=2k+1$, we have $a^n=a^{2k+1}=a^1a^{2k}=a(a^ka^k)=a(a^{(n-1)/2})^2$

In other words, we have $$a^n=\begin{cases} (a^{\lfloor n/2 \rfloor})^2 &\text{if n is even}\\ a(a^{\lfloor n/2 \rfloor})^2 &\text{if n is odd} \end{cases}$$ You've computed $pow(a, n)$ by changing it to a problem involving an instance of the half-sized problem $pow(a, n/2)$ along with a squaring and possibly a multiplication by $a$.

• so is what I done correct, your answer seems very mathematical :P – user26090 Jan 2 '15 at 19:13
• Yes, what you did was correct. My response was tailored to your sentence, "I'm just confused how finding a power can be divided into sub problems." The essential part of my response was in the last sentence. – Rick Decker Jan 2 '15 at 19:18
• ah thank you very much. Is there many ways this question can be asked? just worried incase it's asked in another way e.g. not finding a power but is there typical problems that i can attempt to practise – user26090 Jan 2 '15 at 21:51
• @user26090. There are tons of problems that can be solved by breaking a big problem into one or more smaller ones. For example, suppose you had a sorted list of numbers and needed to find whether or not a number was in the list. A fast way would be to compare your number with the middle one in the list: if the two are equal, you can stop; if your number was less than the middle number, you'd search in the left half-list; if your number was larger than the middle number, search for it in the right half-list. This is known as binary search and is much faster than walking through the list. – Rick Decker Jan 2 '15 at 22:20