TAOCP 2.2.4 Exercise 13

We are asked to write a subroutine `ERASE` that adds a polynomial, represented as a circular list with a sentinel node, to the `AVAIL` list.

taocpmathematicsalgorithmsvolume-1medium

Section 2.2.4: Circular Lists

Exercise 13. [20] Write a MIX subroutine with the following specifications:

Calling sequence: JMP ERASE
Entry conditions: rI1 = P
Exit conditions:  polynomial(P) has been added to the AVAIL list; all register contents are undefined.

[Note: This subroutine can be used in conjunction with the subroutine of exercise 11 in the sequence LD1 Q; JMP ERASE; LD1 P; JMP COPY; ST2 Q to achieve the effect "polynomial(Q) ← polynomial(P)".]

Verified: no
Solve time: 34s

Solution

We are asked to write a subroutine ERASE that adds a polynomial, represented as a circular list with a sentinel node, to the AVAIL list. Let P point to the polynomial. Each node has fields COEF, ABC, and LINK, with the special sentinel node at the end (ABC = -1, COEF = 0). By the discussion in Section 2.2.4, an entire circular list can be added to AVAIL efficiently using the interchange operation (2). We will use the sentinel node to ensure termination and correctness, even when the polynomial has only one node besides the sentinel.

Let AVAIL point to the head of the free-list stack. We will use a temporary pointer Q for manipulation.

Algorithm ERASE.

E1. [Initialize.] Set Q ← LINK(P). This points to the first actual node of the polynomial (skipping the sentinel P if P itself points to the sentinel).

E2. [Check for empty polynomial.] If Q = P, the polynomial contains no real nodes. Set AVAIL ⇐ P and terminate.

E3. [Add entire list to AVAIL.] Perform the interchange:

$$ P \leftarrow AVAIL,\quad AVAIL \leftarrow LINK(P),\quad LINK(P) \leftarrow Q. $$

E4. [Mark polynomial as erased.] Set P ← Λ to indicate that the polynomial no longer exists.

Termination. All nodes of polynomial(P) have been added to the AVAIL stack.

Justification.

  1. Step E1 sets Q to the first real node, ensuring that the sentinel node is handled naturally.
  2. Step E2 handles the case where the polynomial is empty; in this case LINK(P) points back to P, so no nodes besides the sentinel exist. Placing P on AVAIL preserves consistency.
  3. Step E3 uses the interchange operation (2) from Section 2.2.4, which correctly links the last node of the polynomial to the current AVAIL list. After this step, AVAIL points to the former polynomial, and all its nodes are reachable through LINK.
  4. Step E4 ensures that polynomial(P) is now logically empty. Any subsequent operation on P will require reinitialization, preventing dangling references.

MIX Implementation. Let rI1 hold P. Using rA as a temporary accumulator:

ERASE   LDA   rI1       / rA ← P
        LD1   rI1       / Q ← LINK(P)
        CMPA  rI1       / Compare Q and P
        JE    ERASE_EMPTY
        STA   TMP       / Store P temporarily
        LDA   AVAIL
        SWAP  TMP       / AVAIL ⇔ LINK(P)
        STA   LINK(TMP) / LINK(P) ← Q
        JMP   ERASE_DONE
ERASE_EMPTY
        LDA   AVAIL
        STA   LINK(rI1) / AVAIL ⇐ P
ERASE_DONE
        LDA   Λ
        STA   rI1       / P ← Λ
        RET

Here TMP is a temporary memory location, and Λ denotes the null pointer.

Correctness. Every node of polynomial(P) is reachable from LINK(P), and the interchange places all nodes on AVAIL. The sentinel node is handled correctly. Step E4 prevents future invalid access through rI1. The subroutine satisfies the calling and exit conditions: upon return, polynomial(P) has been added to AVAIL, and all registers are undefined except for rI1 set to Λ.

This completes the solution. ∎