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$
1
  • $\begingroup$ Other than $pow(2, 0)$ being $0$ that seems correct. $\endgroup$ Jan 2, 2015 at 15:04

1 Answer 1

3
$\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$
4
  • $\begingroup$ so is what I done correct, your answer seems very mathematical :P $\endgroup$
    – user26090
    Jan 2, 2015 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$ Jan 2, 2015 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, 2015 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$ Jan 2, 2015 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.