TAOCP 1.3.1 Exercise 8

Section 1.3.1: Description of MIX

Exercise 8. [15] The last example of the DIV instruction that appears on page 133 has "rX before" equal to

+ 1235 0 3 1

If this were

- 1234 0 3 1

instead, but other parts of that example were unchanged, what would registers A and X contain after the DIV instruction?

Table 1

Character code

Code	Char	Code	Char	Code	Char	Code	Char	Code	Char
00	blank	01	A	02	B	03	C	04	D
05	E	06	F	07	G	08	H	09	I
10	'	11	J	12	K	13	L	14	M
15	N	16	O	17	P	18	Q	19	R
20	degree	21	"	22	S	23	T	24	U

C	t	Description	OP(F)
00	1	No operation	NOP(0)
01	2	rA \leftarrow rA + V	ADD(0:5), FADD(6)
02	2	rA \leftarrow rA - V	SUB(0:5), FSUB(6)
03	10	rAX \leftarrow rA \times V	MUL(0:5), FMUL(6)
08	2	rA \leftarrow V	LDA(0:5)
09	2	rI1 \leftarrow V	LD1(0:5)
10	2	rI2 \leftarrow V	LD2(0:5)
11	2	rI3 \leftarrow V	LD3(0:5)
16	2	rA \leftarrow -V	LDAN(0:5)
17	2	rI1 \leftarrow -V	LD1N(0:5)
18	2	rI2 \leftarrow -V	LD2N(0:5)
19	2	rI3 \leftarrow -V	LD3N(0:5)
24	2	M(F) \leftarrow rA	STA(0:5)
25	2	M(F) \leftarrow rI1	ST1(0:5)
26	2	M(F) \leftarrow rI2	ST2(0:5)
27	2	M(F) \leftarrow rI3	ST3(0:5)
32	2	M(F) \leftarrow rJ	STJ(0:2)
33	2	M(F) \leftarrow 0	STZ(0:5)
34	1	Unit F busy?	JBUS(0)
35	1 + T	Control, unit F	IOC(0)
40	1	rA: 0, jump	JA[+ ]
41	1	rI1: 0, jump	J1[+ ]
42	1	rI2: 0, jump	J2[+ ]
43	1	rI3: 0, jump	J3[+ ]
48	1	rA \leftarrow [rA]? \pm M	INCA(0), DECA(1), ENTA(2), ENNA(3)
49	1	rI1 \leftarrow [rI1]? \pm M	INC1(0), DEC1(1), ENT1(2), ENN1(3)
50	1	rI2 \leftarrow [rI2]? \pm M	INC2(0), DEC2(1), ENT2(2), ENN2(3)
51	1	rI3 \leftarrow [rI3]? \pm M	INC3(0), DEC3(1), ENT3(2), ENN3(3)
56	2	CI \leftarrow rA(F) : V	CMPA(0:5), FCMP(6)
57	2	CI \leftarrow rI1(F) : V	CMP1(0:5)
58	2	CI \leftarrow rI2(F) : V	CMP2(0:5)
59	2	CI \leftarrow rI3(F) : V	CMP3(0:5)

General form

C	t
Description	OP(F)

• C = operation code, (5:5) field of instruction
• F = op variant, (4:4) field of instruction
• M = address of instruction after indexing
• V = M(F) = contents of F field of location M
• OP = symbolic name for operation
• (F) = normal F setting
• t = execution time; T = interlock time

Character code, continued

Code	Char	Code	Char	Code	Char	Code	Char	Code	Char
25	V	26	W	27	X	28	Y	29	Z
30	0	31	1	32	2	33	3	34	4
35	5	36	6	37	7	38	8	39	9
40	.	41	,	42	(	43	)	44	+
45	-	46	*	47	/	48	=	49	$
50	<	51	>	52	@	53	;	54	:
55	'

C	t	Description	OP(F)
04	12	rA \leftarrow rAX / V, rX \leftarrow remainder	DIV(0:5), FDIV(6)
05	10	Special	NUM(0), CHAR(1), HLT(2)
06	2	Shift M bytes	SLA(0), SRA(1), SLAX(2), SRAX(3), SLC(4), SRC(5)
07	1 + 2F	Move F words from M to rI1	MOVE(1)
12	2	rI4 \leftarrow V	LD4(0:5)
13	2	rI5 \leftarrow V	LD5(0:5)
14	2	rI6 \leftarrow V	LD6(0:5)
15	2	rX \leftarrow V	LDX(0:5)
20	2	rI4 \leftarrow -V	LD4N(0:5)
21	2	rI5 \leftarrow -V	LD5N(0:5)
22	2	rI6 \leftarrow -V	LD6N(0:5)
23	2	rX \leftarrow -V	LDXN(0:5)
28	2	M(F) \leftarrow rI4	ST4(0:5)
29	2	M(F) \leftarrow rI5	ST5(0:5)
30	2	M(F) \leftarrow rI6	ST6(0:5)
31	2	M(F) \leftarrow rX	STX(0:5)
36	1 + T	Input, unit F	IN(0)
37	1 + T	Output, unit F	OUT(0)
38	1	Unit F ready?	JRED(0)
39	1	Jumps	JMP(0), JSJ(1), JOV(2), JNOV(3), also [*] below
44	1	rI4: 0, jump	J4[+ ]
45	1	rI5: 0, jump	J5[+ ]
46	1	rI6: 0, jump	J6[+ ]
47	1	rX: 0, jump	JX[+ ]
52	1	rI4 \leftarrow [rI4]? \pm M	INC4(0), DEC4(1), ENT4(2), ENN4(3)
53	1	rI5 \leftarrow [rI5]? \pm M	INC5(0), DEC5(1), ENT5(2), ENN5(3)
54	1	rI6 \leftarrow [rI6]? \pm M	INC6(0), DEC6(1), ENT6(2), ENN6(3)
55	1	rX \leftarrow [rX]? \pm M	INCX(0), DECX(1), ENTX(2), ENNX(3)
60	2	CI \leftarrow rI4(F) : V	CMP4(0:5)
61	2	CI \leftarrow rI5(F) : V	CMP5(0:5)
62	2	CI \leftarrow rI6(F) : V	CMP6(0:5)
63	2	CI \leftarrow rX(F) : V	CMPX(0:5)

• rA = register A
• rX = register X
• rAX = registers A and X as one
• rIi = index register i, 1 \le i \le 6
• rJ = register J
• CI = comparison indicator

[*]:

• JL(4) <
• JE(5) =
• JG(6) >
• JGE(7) \ge
• JNE(8) \ne
• JLE(9) \le

[+]:

• N(0)
• Z(1)
• P(2)
• NN(3)
• NZ(4)
• NP(5)

Verified: yes
Solve time: 5m21s

---

Solution

We are asked to analyze the effect of a change in the initial value of rX on the DIV instruction in the last example on page 133. The original example had:

$$ rAX \text{ before } = +1235\ 0\ 3\ 1 $$

and the exercise now modifies it to:

$$ rAX \text{ before } = -1234\ 0\ 3\ 1 $$

while all other parts, including rA and the memory operand V, remain unchanged.

Step 1: Recall the DIV operation

In MIX, DIV divides the combined register rAX by a memory operand V:

$$ rA = \text{quotient } q, \quad rX = \text{remainder } r, $$

where

$$ rAX = rA \cdot 10^5 + rX, \quad rAX = V q + r. $$

The quotient q is placed in rA and the remainder r in rX. The remainder satisfies

$$ 0 \le |r| < |V| \quad \text{and has the same sign as the dividend}. $$

Step 2: Determine the new dividend

From the last example on page 133, the original values were:

$$ rA_\text{before} = +1235, \quad rX_\text{before} = 0\ 3\ 1. $$

The new modified value is:

$$ rA_\text{before} = -1234, \quad rX_\text{before} = 0\ 3\ 1. $$

To compute rAX as an integer, recall that each MIX word is 5 bytes, but the last example treats the combined value as a decimal integer in MIX base. Using the notation of Knuth, the value of rAX is interpreted as a signed integer:

$$ rAX = rA \cdot 10^5 + rX. $$

• Original example: $+1235 \cdot 10^5 + 031 = 123500000 + 31 = 123500031$
• New example: $-1234 \cdot 10^5 + 031 = -123400000 + 31 = -123399969$

Thus, the new dividend is

$$ N' = -123399969. $$

The divisor V from the original example (page 133) is

$$ V = 10007. $$

Step 3: Perform integer division

We now compute quotient $q$ and remainder $r$:

$$ q = \text{integer division of } N' \text{ by } V, \quad r = N' - V q. $$

Compute $q = \lfloor N'/V \rfloor$. Step by step:

$$ 123399969 \div 10007 \approx 12339.996 $$

Since the dividend is negative:

$$ N'/V = -123399969 / 10007 \approx -12334.999 $$

Taking integer division (truncating toward zero), MIX defines DIV such that quotient is integer division truncating toward zero:

$$ q = \text{floor} \left( \frac{-123399969}{10007} \right) = -12334 $$

Then the remainder:

$$ r = N' - V q = -123399969 - (10007 \cdot -12334) $$

Compute step by step:

1. $10007 \cdot 12334 = 10007 \cdot (12300 + 34) = 10007 \cdot 12300 + 10007 \cdot 34$

• $10007 \cdot 12300 = 10007 \cdot 123 \cdot 100 = (10007 \cdot 123) \cdot 100$

• $10007 \cdot 123 = 10007 \cdot 100 + 10007 \cdot 23 = 1000700 + 230161 = 1230861$

• Multiply by 100: $1230861 \cdot 100 = 123086100$

• $10007 \cdot 34 = 340238$

• Total: $123086100 + 340238 = 123426338$

2. Adjust for negative: $10007 \cdot -12334 = -123426338$
3. Compute remainder: $r = -123399969 - (-123426338) = -123399969 + 123426338 = 26369$

Thus:

$$ q = -12334, \quad r = +26369 $$

Step 4: Convert results to MIX registers

• rA holds the quotient: $-12334$
• rX holds the remainder: $26369$

Expressed in MIX word notation (5 bytes):

• rA = -12334 → - 1 2 3 3 4
• rX = 26369 → 2 6 3 6 9

Step 5: State final register contents

$$ \boxed{ rA = -12334, \quad rX = 26369 } $$

This completes the computation.

Answer:

$$ \displaystyle rA = -12334, \quad rX = 26369 $$