Efficient Exponentiation

The most naive way of computing $n^{15}$ requires fourteen multiplications:
$$n \times n \times \cdots \times n = n^{15}.$$
But using a “binary” method you can compute it in six multiplications:
\begin{align}
n \times n &= n^2\\
n^2 \times n^2 &= n^4\\
n^4 \times n^4 &= n^8\\
n^8 \times n^4 &= n^{12}\\
n^{12} \times n^2 &= n^{14}\\
n^{14} \times n &= n^{15}
\end{align}
However it is yet possible to compute it in only five multiplications:
\begin{align}
n \times n &= n^2\\
n^2 \times n &= n^3\\
n^3 \times n^3 &= n^6\\
n^6 \times n^6 &= n^{12}\\
n^{12} \times n^3 &= n^{15}
\end{align}
We shall define $m(k)$ to be the minimum number of multiplications to compute $n^k$; for example $m(15) = 5$.
For $1 \le k \le 200$, find $\sum m(k)$.

The problem involves a concept called addition chains, which are sequences that start with one and every number from the second element on is the sum of two earlier elements (maybe the same one). Now we can see that every full binary tree (a tree where all nodes have 0 or 2 children) represents a calculation that we can do in order to calculate $n^k$, where $k$ is the number of leaf nodes.

The height of the tree (the maximum length from root to a leaf) determines the number of multiplications it takes to compute $n^k$. What we need in order to minimize the number of multiplications is to find the shortest such tree. This is called the minimal addition chain for $k$.

A few rules can be determined. First, if $k$ is even, the shortest chain ends with a doubling, so $m(k) = m(k/2) + 1$. If $k$ is odd, we cannot do any better than adding the largest power of 2 less than $k$ and the rest, thus $m(k) = m(k – 2^{\lfloor \log_2{k} \rfloor}) + 1$ if $k$ is odd.

However, those two rules alone lead to suboptimal results for some $k$ (like 15). You can notice that for every $n$, $m(n) = m(n – 1) + 1$ or $m(n) < m(n - 1) + 1$. This is because we can always add 1 to the last element of the addition chain for $m(n - 1)$ to find a valid addition chain for $m(n)$, or we can find a better solution. This gives rise to a dynamic programming solution to solve for each $m(k)$ from 1 to 200. The result turns out to be 1582. Here is a Python program which implements this idea: ```python m = [0, 1] for i in range(2, 201): if i % 2 == 0: m.append(m[i // 2] + 1) else: m.append(min((m[i-1] + 1, min((m[i // 2] + 1 + m[i // 2 + j +1] for j in range(i // 2)))))) print(sum(m)) ``` When you run this Python program, it will calculate and print out the sum of minimum multiplications for exponents from 1 up to 200 which is 1582.

More Answers: