TAOCP 1.3.1 Exercise 24

Exercise 24. [21] Assuming that registers A and X contain

+ 0 a b c d

and

+ e f g h i

respectively, write two programs that change the contents of these registers to

+ a b c d e

and

+ 0 f g h i

respectively, using (a) minimum memory space and (b) minimum execution time.

Verified: yes
Solve time: 1m22s

Solution

Let

rA = + 0 a b c d,
rX = + e f g h i.

The desired final state is

rA = + a b c d e,
rX = + 0 f g h i.

The five bytes $a,b,c,d,e$ must appear in $rA$ in the same order in which they occur initially, namely as bytes $2,3,4,5$ of $rA$ followed by byte $1$ of $rX$. Therefore the transformation is exactly a one-byte left shift of the ten-byte register pair $(rA,rX)$:

0 a b c d e f g h i
      ↓
a b c d e 0 f g h i.

Section 1.3.1 introduces the extension register $rX$ precisely for shifts between $rA$ and $rX$; a single shift instruction accomplishes this transformation.

(a) Minimum memory space

A program consisting of one instruction suffices:

SLAX 1
HLT

After SLAX 1, the ten-byte quantity formed by $rA$ followed by $rX$ is shifted left one byte. Hence

0 a b c d e f g h i

becomes

a b c d e 0 f g h i,

rA = + a b c d e,
rX = + 0 f g h i.

The program occupies two memory locations.

To prove minimality, at least one executable instruction is necessary, since the initial and final register contents differ. A MIX program that halts must also contain a HLT instruction. Therefore at least two instruction words are required. The program above uses exactly two words, hence the memory usage is minimal.

(b) Minimum execution time

The same program is optimal:

SLAX 1
HLT

The transformation cannot be completed in zero executed instructions because the registers must change. Thus at least one non-halting instruction is necessary before termination. Any terminating program therefore executes at least two instructions: one instruction that performs the transformation and one HLT.

The program above executes exactly those two instructions. Since SLAX 1 performs the entire required transformation in a single operation, no program can execute fewer instructions.

Therefore the minimum-time program is again

SLAX 1
HLT

The final answer is

$$ \boxed{\text{SLAX 1;\ HLT}} $$

for both parts (a) and (b). ∎