0
$\begingroup$

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?

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

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

$\endgroup$
  • $\begingroup$ so is what I done correct, your answer seems very mathematical :P $\endgroup$ – user26090 Jan 2 '15 at 19:13
  • $\begingroup$ 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. $\endgroup$ – Rick Decker Jan 2 '15 at 19:18
  • $\begingroup$ 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 $\endgroup$ – user26090 Jan 2 '15 at 21:51
  • 1
    $\begingroup$ @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. $\endgroup$ – Rick Decker Jan 2 '15 at 22:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.