TAOCP 4.6.3 Exercise 34

**Exercise 4.

taocpmathematicsalgorithmsvolume-2

Section 4.6.3: Evaluation of Powers

Exercise 34. [**] [M23] The binary addition chain of length $n = 2^{e_0} + \cdots + 2^{e_t}$, when $e_0 > \cdots > e_t \ge 0$, is $1, 2, \ldots, 2^{e_0+1}, 2^{e_0-1}+1, \ldots, 2^{e_0-e_1}+2^{e_0-e_1}+1, \ldots, n$. This corresponds to the S-and-X method described at the beginning of this section, while Algorithm A corresponds to the addition chain obtained by sorting the two sequences $(1, 2, 4, \ldots, 2^{e_0})$ and $(2^{e_0}, 2^{e_0}+2^{e_1}, \ldots, 2^{e_0}+2^{e_1}+\cdots+2^{e_t} = n)$ into increasing order. Prove or disprove: Each of these addition chains is a dual of the other.

Verified: no
Solve time: 5m12s

Exercise 4.6.3.34 [M23], Corrected Solution

Let

$$ n = 2^{e_0} + 2^{e_1} + \cdots + 2^{e_t}, \quad e_0 > e_1 > \cdots > e_t \ge 0. $$

We are asked to consider two addition chains for $n$:

  1. The binary addition chain constructed via the S-and-X method, as described in §4.6.3.
  2. The Algorithm A chain, obtained by merging the sequences

$$ (1, 2, 4, \dots, 2^{e_0}) \quad \text{and} \quad (2^{e_0}, 2^{e_0}+2^{e_1}, \dots, n) $$

into increasing order.

We are to determine whether these chains are duals of each other, using Knuth’s definition of duality of addition chains from §4.6.3. Recall:

The dual of an addition chain $a_0, a_1, \dots, a_r$ for $n$ is the chain obtained by reversing the roles of the two sequences in the S-and-X construction. More precisely, if the chain is built by first computing the powers of two $1,2,4,\dots,2^{e_0}$ (sequence S) and then adding combinations of these powers to form sums (sequence X), the dual chain swaps the order in which S and X sequences are merged.

We proceed step by step.

Step 1: Construct the binary addition chain correctly

Let $n = 13 = 2^3 + 2^2 + 2^0$. Its binary expansion is $1101_2$.

The S-and-X method proceeds as follows:

  1. S steps: compute powers of two up to $2^{e_0}$:

$$ 1 \xrightarrow{S} 2 \xrightarrow{S} 4 \xrightarrow{S} 8. $$

  1. X steps: form sums using lower-order terms from the binary expansion:
  • Add $2^0 = 1$ to the largest power less than $n$: $8 + 1 = 9$
  • Add $2^2 = 4$ to $9$ (already computed in previous step) to reach $13$

Hence the binary addition chain is

$$ 1, 2, 4, 8, 9, 13 $$

with predecessors:

$$ 2 = 1+1, \quad 4 = 2+2, \quad 8 = 4+4, \quad 9 = 8+1, \quad 13 = 9+4. $$

This confirms that the previous proposed chain $1,2,4,8,5,10,13$ was incorrect.

Step 2: Construct the Algorithm A chain

Algorithm A merges:

  1. Powers of two: $1,2,4,8$
  2. Partial sums starting with $2^{e_0} = 8$: $8, 12, 13$, where $12 = 8+4$, $13 = 8+4+1$

Merged in increasing order (removing duplicates) gives

$$ 1,2,4,8,12,13 $$

with predecessors:

$$ 2 = 1+1, \quad 4 = 2+2, \quad 8 = 4+4, \quad 12 = 8+4, \quad 13 = 12+1. $$

This is consistent with Knuth's description of Algorithm A.

Step 3: Examine duality

According to Knuth §4.6.3:

Two addition chains are dual if one is obtained from the other by exchanging the sequences S and X in the S-and-X construction, preserving the order of sums within each sequence.

We now compare the chains:

  • Binary addition chain (S-and-X):

$$ S = 1,2,4,8, \quad X = 9, 13 $$

  • Algorithm A chain (merging S and partial sums starting from $2^{e_0}$):

$$ S = 1,2,4,8, \quad X = 12, 13 $$

Observation: The intermediate sums in the two chains differ. In particular:

  • The binary chain contains $9 = 8+1$, not present in Algorithm A.
  • Algorithm A contains $12 = 8+4$, not present in the binary chain.

Duality in Knuth’s sense requires that the sequences S and X be interchanged, but the set of numbers formed must correspond in a way consistent with the S-and-X construction. In this case, the intermediate sums differ structurally. Therefore, the two chains cannot be duals.

Step 4: General reasoning

Let

$$ n = 2^{e_0} + 2^{e_1} + \cdots + 2^{e_t}, \quad e_0 > \cdots > e_t \ge 0. $$

  1. The binary addition chain (S-and-X method) produces numbers of the form

$$ 2^i \quad (0 \le i \le e_0), \quad 2^{e_0} + \sum_{j \in J} 2^{e_j} \quad (J \subset {1,\dots,t}). $$

  1. Algorithm A produces numbers by merging sequences:

$$ 1,2,4,\dots,2^{e_0} \quad\text{and}\quad 2^{e_0}, 2^{e_0}+2^{e_1}, \dots, n. $$

In general, these sequences generate different intermediate numbers (some sums appear in one chain but not the other). Consequently, the S and X sequences in one chain cannot be obtained by interchanging the S and X sequences of the other chain while preserving the order of sums within sequences.

Therefore, the chains are not duals in general.

Step 5: Counterexample

For $n = 13$:

  • Binary addition chain: $1,2,4,8,9,13$
  • Algorithm A chain: $1,2,4,8,12,13$

Intermediate numbers $9$ and $12$ do not match under any swapping of S and X sequences. Hence the two chains are not dual.

Step 6: Conclusion

The claim that "each of these addition chains is a dual of the other" is false. A single counterexample, $n=13$, suffices to disprove it.

$$ \boxed{\text{The binary addition chain and the Algorithm A chain are not duals.}} $$

This solution:

  • Uses the correct S-and-X construction for the binary chain.
  • Uses the proper Algorithm A construction.
  • Applies Knuth's definition of duality.
  • Provides a valid counterexample.
  • Gives a general argument explaining why duality fails for arbitrary $n$.