Evaluation of Powers - janmr blog

How do you efficiently compute xⁿ for a positive integer n? Take x¹⁵ as an example. You could take x and repeatedly multiply by x 14 times. A better way to do it, however, is this:

• $t_0=x$
• $t_1=t_0 \cdot t_0 = x^2$
• $t_2=t_0 \cdot t_1 = x^3$
• $t_3=t_1 \cdot t_2 = x^5$
• $t_4=t_3 \cdot t_3 = x^{10}$
• $t_5=t_3 \cdot t_4 = x^{15}$

A shorter way to write this is $x^1,x^2,x^3,x^5,x^{10},x^{15}$, where each quantity is obtained by multiplying two of the previous quantities together. We can write it even shorter as 1,2,3,5,10,15, where only the exponents are written. Here each number is obtained by adding together two of the previous numbers. This is called an addition chain and is at the heart of studying the optimal way of evaluating powers. There is no simple expression that computes the minimal number of multiplications $a(n)$ needed to evaluate xⁿ. A list, however, is available from The On-Line Encyclopedia of Integer Sequences, where the first 40 entries are

0, 1, 2, 2, 3, 3, 4, 3, 4, 4, 5, 4, 5, 5, 5, 4, 5, 5, 6, 5, 6, 6, 6, 5, 6, 6, 6, 6, 7, 6, 7, 5, 6, 6, 7, 6, 7, 7, 7, 6, …

We see that $a(15)=5$, which shows that the addition chain 1,2,3,5,10,15 is indeed the shortest possible, and it follows that the procedure shown above to compute x¹⁵ required the minimal number of multiplications.

Since the numbers in an addition chain grows the fastest by doubling the previous item, it is fairly easy to see that

(1)

a(n)≥⌈log2(n)⌉.

Read full article from Evaluation of Powers - janmr blog