TAOCP 2.2.6 Exercise 15

Section 2.2.6: Arrays and Orthogonal Lists

Exercise 15. ▶ [**] [29] Write a MIXAL program for Algorithm S. Assume that the VAL field is a floating point number, and that MIX's floating point arithmetic operators FADD, FSUB, FMUL, and FDIV can be used for operations on this field. Assume for simplicity that FADD and FSUB return the answer zero when the operands added or subtracted cancel most of the significance, so that the test "VAL(P1) = 0" may safely be used in step S7. The floating point operations use only rA, not rX.

Verified: no
Solve time: 36s

A direct transcription of Algorithm $S$ into MIXAL is possible if the fields ROW, COL, VAL, LEFT, and UP are assigned fixed offsets within each node, and if the floating-point instructions FADD, FSUB, FMUL, and FDIV are used for all operations on VAL. The integer registers hold node addresses and indices exactly as in the algorithm: for example, P0, P1, Q0, and Q1 may be kept in index registers, while tests such as VAL(P1)=0, ROW(P1)=i, and COL(Q1)=j become ordinary field comparisons. Step S4 computes the transformed value

$$ \frac{bc-ad}{a}, $$

using floating-point multiplication, subtraction, and division; step S7 deletes a node whenever the resulting VAL field is zero; and step S8 inserts a newly created node into both the row and column circular lists by updating the corresponding LEFT and UP links.

The resulting program is routine but lengthy, since every operation of Algorithm $S$ must be expressed explicitly in terms of address manipulation and field references. No new ideas are required beyond the sparse-matrix representation of Fig. 14 and the standard MIXAL coding techniques for circular linked lists. The exercise is intended as a programming translation of Algorithm $S$, not as a further algorithmic development.