# How many multiplications to find n^k given n, for general k?

I was looking at the nice puzzle Find $n^{23}$ with the least multiplication. My first instinct for this would have been to find $n^{2^i}$ for each $i$ first and then multiply these together as necessary to get $n^{23}$. This basic algorithm will always work for any integer power of $n$, since we can write $k$ in base 2 (i.e. as a sum of powers of 2) to get $n^k$ as a product of $n^{2^i}$ terms.

However, it's clearly not optimal in all cases. For $n^{23}$, this method would involve seven multiplications (one each to get $n^2,n^4,n^8,n^{16}$, then three for $n^{16}\times n^4\times n^2\times n$), whereas Kalaivanan showed that it can be done in six multiplications. Presumably this six-part solution is a case of some more general algorithm which will work for any $n^k$, but I'm struggling to see what that algorithm would be, and can't really see the motivation/inspiration which led to Kalaivanan's solution.

What is the least number of multiplications, in terms of $k\in\mathbb{N}$, to find $n^k$ given a general $n$?

• Just a small comment. Wouldn't the problem sound a bit easier if stated. Find k through a set of additions starting from 1? Isn't this equivalent or am I missing something. – Marius Aug 28 '17 at 13:15
• @Marius Hmm, I suppose it is equivalent. But realising that is an interesting and non-obvious part of the solution in itself, so I'd rather not include it in the problem statement. – Rand al'Thor Aug 28 '17 at 13:21
• should I delete the comment above then? – Marius Aug 28 '17 at 13:22
• @wl As a sequence of numbers, yes, but not as a general algorithm/formula in terms of $k$, which is what I was hoping for. – Rand al'Thor Aug 28 '17 at 13:33

There is no simple algorithm for it, apart from essentially trying out all ways of splitting it up into smaller parts. The tricky bit lies in the fact that if you try to split the calculation of $x^n$ into two separate calculations $x^a$ and $x^b$ with $a+b=n$, then it is not the case that the two sub-problems $x^a$ and $x^b$ are independent. Intermediate results from one of them can be used in the other to shorten the number of multiplications you need.