TAOCP 4.6.3 Exercise 30

Section 4.6.3: Evaluation of Powers

Exercise 30. [**] [20] An addition-subtraction chain has the rule $a_i = a_j \pm a_k$ in place of (a); the imaginary operation described in the text has a new operation code, SUB. (This corresponds in practice to evaluating $2^n$ using both multiplications and divisions.) Find an addition-subtraction chain, for some $n$, that has fewer than $l(n)$ steps.

Verified: yes
Solve time: 1m10s

Let $n = 31$. A minimal addition chain for $31$ has length $l(31) = 8$, for example:

$1 \leftarrow 1$

$2 \leftarrow 1 + 1$

$3 \leftarrow 2 + 1$

$5 \leftarrow 3 + 2$

$10 \leftarrow 5 + 5$

$20 \leftarrow 10 + 10$

$30 \leftarrow 20 + 10$

$31 \leftarrow 30 + 1$

This chain requires 8 steps. Using an addition-subtraction chain, we can reduce the number of steps. Consider:

$1 \leftarrow 1$

$2 \leftarrow 1 + 1$

$4 \leftarrow 2 + 2$

$8 \leftarrow 4 + 4$

$16 \leftarrow 8 + 8$

$32 \leftarrow 16 + 16$

$31 \leftarrow 32 - 1$

Here each line counts as one replacement, for a total of 7 replacements, which is fewer than $l(31) = 8$. This demonstrates that an addition-subtraction chain can require fewer steps than the minimal addition chain. $\boxed{7}$