TAOCP 2.2.4 Exercise 14

Section 2.2.4: Circular Lists

Exercise 14. [22] Write a MIX subroutine with the following specifications:

Calling sequence: JMP ZERO
Entry conditions: None
Exit conditions:  rI2 points to a newly created polynomial equal to 0; other register
                  contents are undefined.

Verified: yes
Solve time: 3m01s

---

Solution

In the representation used in §2.2.4, a polynomial is a circular linked list. The zero polynomial is represented by a circular list consisting only of the special node. For such a node,

$$ \mathrm{COEF}=0,\qquad \mathrm{ABC}=-1, $$

and the link field points back to the node itself.

Using the node layout defined earlier in the section,

• word $0$: COEF,
• word $1$: ABC,
• word $2$: LINK.

Therefore the subroutine must:

1. take one node from the AVAIL list;
2. set its coefficient field to $0$;
3. set its exponent field to $-1$;
4. set its link field to its own address;
5. leave that address in rI2;
6. return to the caller.

A correct MIX subroutine is:

ZERO    ENT2    AVAIL

        LDA     0,2(0:2)
        STA     AVAIL

        ENTX    0
        STX     0,2(0:2)

        ENTA    -1
        STA     1,2(0:2)

        ST2     2,2(0:2)

        JMP     0,1

Verification

After

ENT2    AVAIL

register rI2 contains the address of the first node on the available-space list.

The instructions

LDA     0,2(0:2)
STA     AVAIL

read the link field of that node and store it into AVAIL. Hence the node addressed by rI2 is removed from the available-space list.

Next,

ENTX    0
STX     0,2(0:2)

store $0$ into the COEF field of the allocated node.

Then

ENTA    -1
STA     1,2(0:2)

store $-1$ into the ABC field.

The instruction

ST2     2,2(0:2)

stores the contents of rI2, namely the node's own address, into the LINK field. Thus the node links to itself and forms a one-node circular list.

At this point the allocated node satisfies

$$ \mathrm{COEF}=0,\qquad \mathrm{ABC}=-1,\qquad \mathrm{LINK}=\text{its own address}. $$

Therefore it is exactly the distinguished special node representing the zero polynomial.

Finally,

JMP     0,1

returns control to the caller through the return address established by the calling sequence JMP ZERO. Thus the routine is a proper MIX subroutine.

On exit, rI2 points to the newly created one-node circular list representing the polynomial $0$, which is exactly the required result. ∎