# How to solve this recurrence relation? (number of multiplications to calculate $x^n$)

I'm trying to find the number of multiplications to calculate $x^n$. I have arrived at this:

$$M(n) = \begin{cases} - 1 + M\left(\frac{n}{2}\right) & \text{if n even}\\ - 2 + M\left(\frac{n-1}{2}\right) & \text{if n odd} \end{cases}$$

with initial conditions $M(1) = 0$ and $M(2) = 1$.

so how do I solve this? Thanks for any help!

-
There is an easy answer in terms of the binary representation of $n$. I am sure you can work it out given this hint. –  André Nicolas Jan 7 '13 at 1:01

## 2 Answers

Sequence A014701 in the OEIS: https://oeis.org/A014701.

-

But that is not always the best. Knuth has a very detailed (as always) discussion of this problem. iirc, 15 is the first value at which your method is not the best.

-