0
$\begingroup$

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.

  • 0
    @HenningMakholm Im sorry, I misspelled the question, it is indeed$x^p$instead of p^x2011-12-14

1 Answers 1

2

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

  • 0
    But that is unlikely to be the intended answer, because it doesn't use the explicitly given fact that $p$ is an integer.2011-12-14