# Recursive algorithm for calculating powers

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.

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

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}

-
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