Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am working on a maths exercise and got this question:

Make a recursive algorithm on the calculation of $x^p$, where $x$ is a real number and $p$ is a natural number of $n$ bits.

I really don't know where to start. Whats the way of solving this?

Ps. english isn't my first language.

share|improve this question
    
What is it that you're learning about -- i.e., what is the context of the exercise? –  Henning Makholm Dec 14 '11 at 15:37
1  
Note that if it were $x^p$ instead of $p^x$, you would be looking for some variant of exponentiation by squaring. –  Henning Makholm Dec 14 '11 at 15:43
    
The context of the exercise is ICT related. I translated the question from dutch. –  Jef Dec 14 '11 at 15:52
    
@HenningMakholm Im sorry, I misspelled the question, it is indeed x^p instead of p^x –  Jef Dec 14 '11 at 15:56
add comment

1 Answer

up vote 2 down vote accepted

Solution for the original formulation $p^x=?$

Note that $$p^x = \exp(x \log p) = \sum_{i=0}^\infty \frac{\log^ip}{i !}x^i.$$

You can now truncate the series at some $i$ and recursively compute the partial sum up to that point.

If you cannot use the logarithm or exponential functions, you could also express $x$ in binary and adapt the exponentiation by squaring algorithm.

Solution for the correct formulation For the corrected version of the problem, where you are asked to compute $x^p$, you can use exponentiation by squaring directly using

$$\begin{align} x^0&=1\\ x^n&=(x^{n/2})^2 \ \text{for even }n\\ x^n&=x \cdot (x^{(n-1)/2})^2 \ \text{for odd }n \end{align} $$

share|improve this answer
    
But that is unlikely to be the intended answer, because it doesn't use the explicitly given fact that $p$ is an integer. –  Henning Makholm Dec 14 '11 at 15:45
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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