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

Question

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 07 '13 at 01:01

score 2 · Answer 1 · answered Jan 07 '13 at 01:02

2

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

answered Jan 07 '13 at 01:02

Robert Israel

448,999

score 0 · Answer 2 · answered Jan 07 '13 at 02:20

0

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.

answered Jan 07 '13 at 02:20

marty cohen

107,799

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

2 Answers2