TAOCP 1.3.1 Exercise 22

Section 1.3.1: Description of MIX

Exercise 22. [28] Location 2000 contains an integer number, X. Write two programs that compute X^{13} and halt with the result in register A. One program should use the minimum number of MIX memory locations; the other should require the minimum execution time possible. Assume that X^{13} fits into a single word.

Verified: no
Solve time: 2m49s

Program 1: minimum memory usage

The goal is to use the smallest possible number of MIX memory locations. Only location $2000$ (holding $X$) is used as data memory; all intermediates remain in registers.

After loading $X$ into $rA$, we multiply by $X$ twelve additional times. After the initial load, $rA = X$. Each instruction

$$ \texttt{MUL 2000} $$

updates $rA \leftarrow rA \cdot X$. Hence after $k$ multiplications, $rA = X^{k+1}$.

Program:

After the twelfth MUL, $rA = X^{13}$. No auxiliary memory locations are used, so this is minimal in memory under the standard interpretation (instruction storage is not counted).

Program 2: minimum execution time

Execution time is minimized by minimizing the number of MIX multiplications, since all other instructions are constant overhead. We therefore seek a shortest addition chain for exponent $13$.

Step 1: lower bound

Each MUL corresponds to one multiplication in the exponentiation chain. We show that at least 5 multiplications are necessary.

With 4 multiplications, the longest possible chain starting from $X$ has 5 terms:

$$ X = X^{1} \to X^{a_2} \to X^{a_3} \to X^{a_4} \to X^{a_5}. $$

The maximal growth occurs by repeated doubling:

$$ 1 \to 2 \to 4 \to 8 \to 16. $$

Any deviation from doubling replaces some step $a_{k+1} = a_i + a_j$ with $i \neq j$, which strictly reduces the maximum attainable final exponent below $16$. Therefore, 4 multiplications cannot produce all exponents up to 16 except by the pure doubling chain, and that chain yields exactly powers of two only. Since $13$ is not a power of two, it cannot be obtained in 4 multiplications.

Thus at least 5 multiplications are required.

Step 2: optimal addition chain for 13

We use the optimal chain:

$$ 1 \to 2 \to 3 \to 6 \to 12 \to 13, $$

which corresponds to:

$$ 2 = 1+1,\quad 3 = 2+1,\quad 6 = 3+3,\quad 12 = 6+6,\quad 13 = 12+1. $$

This uses exactly 5 multiplications.

Step 3: MIX program (5 multiplications)

We store intermediate results to avoid recomputation.

        LDA 2000
        MUL 2000        ; X^2
        STA 2001

        LDA 2001
        MUL 2000        ; X^3
        STA 2002

        LDA 2002
        MUL 2002        ; X^6
        STA 2003

        LDA 2003
        MUL 2003        ; X^12
        STA 2004

        LDA 2004
        MUL 2000        ; X^13
        HLT

Step 4: verification of optimality

The program performs exactly 5 multiplications, matching the lower bound proved above. Therefore it is optimal in execution time.

Final conclusion

Program 1 uses the minimum possible memory (only location $2000$ as data storage).
Program 2 achieves the minimal possible execution time by using the shortest addition chain for exponent $13$, requiring exactly 5 multiplications, and this is provably optimal under MIX multiplication semantics.