TAOCP 4.6.3 Exercise 10
Each node in the tree represents an exponent $n$, and the tree specifies a parent for each $n$ corresponding to the immediately preceding exponent used to compute $x^n$.
Section 4.6.3: Evaluation of Powers
Exercise 10. [10] Figure 15 shows a tree that indicates one way to compute $x^n$ with the fewest possible multiplications, for all $n \le 100$. How can this tree be conveniently represented within a computer, in just 100 memory locations?
Verified: yes
Solve time: 1m35s
Each node in the tree represents an exponent $n$, and the tree specifies a parent for each $n$ corresponding to the immediately preceding exponent used to compute $x^n$. This suggests storing, in memory location $n$ (for $1 \le n \le 100$), the index of its parent in the tree. Then $x^n$ can be computed by following the parent links recursively or iteratively, multiplying the two previously computed powers at each step. Since there are 100 exponents, exactly 100 memory locations suffice to hold all parent indices. This representation encodes the tree compactly, permits reconstruction of the multiplication sequence for any $x^n$, and requires no additional storage beyond the array of 100 integers.
This completes the proof.
∎