TAOCP 2.2.4 Exercise 6

Exercise 6. [18] Give diagrams of the list representation for the polynomials (a) $xz - 3$; (b) $0$.

Verified: no
Solve time: 35s

Solution

Each polynomial is represented by a circular list whose nodes are arranged in decreasing order of the field ABC. Every polynomial contains a special node with

$$ ABC=-1,\qquad COEF=0, $$

and this node links back to the largest ABC value. A term

$$ c,x^A y^B z^C $$

is represented by a node having coefficient COEF = c and exponent field ABC = +ABC.

(a) $xz-3$

The term $xz$ has exponents

$$ A=1,\quad B=0,\quad C=1, $$

hence

$$ ABC=+101. $$

The constant term $-3$ has exponents

$$ A=0,\quad B=0,\quad C=0, $$

hence

$$ ABC=+000. $$

Since $101>000$, the nodes occur in that order, followed by the special node. Therefore the circular list is

[+ 1 0 1 | +1] -> [+ 0 0 0 | -3] -> [- 0 0 1 | 0]
      ^__________________________________________|

where the first node represents $xz$, the second represents $-3$, and the special node links back to the first.

(b) $0$

The zero polynomial contains no nonzero terms. By the conventions of the section, the list still contains the special node

$$ ABC=-1,\qquad COEF=0. $$

Since there are no other nodes, the special node links to itself:

[- 0 0 1 | 0]
      ^    |
      |____|

Thus the representation of the zero polynomial is a one-node circular list consisting solely of the special node.

The final representations are

$$ \boxed{ xz-3: \ [ +101,|,1 ] \to [ +000,|,-3 ] \to [ -001,|,0 ] \to \text{back to } +101 } $$

and

$$ \boxed{ 0: \ [ -001,|,0 ] \to \text{itself} } $$