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