TAOCP 2.3.2 Exercise 21

Section 2.3.2: Binary Tree Representation of Trees

Exercise 21. [25] Algorithm D controls the differentiation activity for binary operators, unary operators, and nullary operators, thus for trees whose nodes have degree 2, 1, and 0; but it does not indicate explicitly how the control would be handled for ternary operators and nodes of higher degree. (For example, exercise 17 suggests making addition and multiplication into operators with any number of operands.) Is it possible to extend Algorithm D in a simple way so that it will handle operators of degree more than 2?

Verified: yes
Solve time: 1m20s

Solution

Yes.

Algorithm D is based on a postorder traversal of the formula tree. When a node is visited, the derivatives of all of its descendants have already been computed and are available. For a binary operator this permits the application of rules such as $(15)$ through $(19)$; for a unary operator it permits the application of $(13)$ or $(14)$.

The same principle applies to operators of arbitrary degree. Suppose an operator $\phi$ has degree $m$, and its operands are

$$ u_1,u_2,\ldots,u_m. $$

When the node corresponding to $\phi$ is reached in postorder, the quantities

$$ D(u_1),D(u_2),\ldots,D(u_m) $$

have already been computed. Therefore the differentiation action associated with $\phi$ need only examine the list of children of that node and construct the appropriate formula from the operands and their derivatives.

For example, if addition is treated as a single operator of arbitrary degree,

$$ \phi(u_1,\ldots,u_m)=u_1+\cdots+u_m, $$

then repeated use of rule $(15)$ yields

$$ D(\phi)=D(u_1)+D(u_2)+\cdots+D(u_m). $$

Similarly, if multiplication is treated as an operator of arbitrary degree,

$$ \phi(u_1,\ldots,u_m)=u_1u_2\cdots u_m, $$

repeated application of rule $(17)$ gives

$$ D(\phi) = \sum_{i=1}^{m} \left( D(u_i)\prod_{\substack{1\le j\le m\j\ne i}}u_j \right). $$

No change in the traversal mechanism is required. The only modification is that the action table for operators must contain, for each operator type, a routine capable of processing all children of the current node rather than assuming exactly one or two children.

In the tree representation of Section 2.3.2, the children of a node already form an ordered family. Under the natural correspondence, the first child is reached through the left link and the remaining children are obtained by following right-sibling links. Hence a differentiation routine for a node of degree $m$ can scan the complete child list, collecting the operands and their previously computed derivatives, and then construct the derivative formula prescribed for that operator.

Therefore Algorithm $D$ extends naturally to operators of degree greater than $2$. The control structure remains unchanged; only the operator-specific processing routines must be generalized from fixed arity to arbitrary arity. ∎