TAOCP 2.3.2 Exercise 15

The routine `DIV` computes the derivative of a formula of the form $u / v$ with respect to the variable $x$, according to rule `(18)`: D(u/v) = D(u)/v - (u \times D(v))/(v \uparrow 2).

taocpmathematicsalgorithmsvolume-1medium

Section 2.3.2: Binary Tree Representation of Trees

Exercise 15. [23] Write a MIX program for the DIV routine, corresponding to DIFF[7] as specified in the text. (This routine should be added to the program in the text after line 217.)

Verified: yes
Solve time: 1m21s

Solution

The routine DIV computes the derivative of a formula of the form $u / v$ with respect to the variable $x$, according to rule (18):

$$ D(u/v) = D(u)/v - (u \times D(v))/(v \uparrow 2). $$

We assume that the trees representing $u$ and $v$ are right-threaded binary trees in the format described in Section 2.3.2. The program must produce a new tree representing the derivative, preserving the right-threaded structure and storing nodes in memory according to the TYPE, INFO, LLINK, RLINK, and RTAG fields.

The DIV subroutine follows the same strategy as DIFF[7] for binary operators: it recursively computes D(u) and D(v) using the existing differentiation routines for subtrees, then combines them according to (18).

Let U and V be the roots of the left and right subtrees of the current node (the numerator and denominator). Let DU and DV denote the roots of the copied trees resulting from the recursive differentiation of U and V. Let T1 and T2 be temporary storage nodes used to construct the intermediate multiplications and divisions.

The steps of DIV are as follows, in TAOCP step-style notation consistent with Section 2.3.2:

E1. Recursively compute D(U). Call COPY to store the result in a new subtree with root DU.

E2. Recursively compute D(V). Call COPY to store the result in a new subtree with root DV.

E3. Construct the term (DU / V):

  • Allocate a new node T1 with TYPE = "/" and INFO = "/".
  • Set LLINK(T1) = DU.
  • Set RLINK(T1) = COPY(V), where COPY(V) produces a new tree representing V.
  • Set RTAG(T1) = 0.

E4. Construct the term (U * DV):

  • Allocate a new node T2 with TYPE = "*".
  • Set LLINK(T2) = COPY(U).
  • Set RLINK(T2) = DV.
  • Set RTAG(T2) = 0.

E5. Construct the term ((U * DV) / (V \uparrow 2)):

  • Allocate a new node RL with TYPE = "/".

  • Set LLINK(RL) = T2.

  • Construct V \uparrow 2 as a new node VP:

  • TYPE = "^"

  • INFO = "^"

  • LLINK(VP) = COPY(V)

  • RLINK(VP) = leaf node containing 2

  • Set RLINK(RL) = VP.

  • Set RTAG(RL) = 0.

E6. Construct the final node representing the difference of the two terms:

  • Allocate node ROOT with TYPE = "-".
  • Set LLINK(ROOT) = T1.
  • Set RLINK(ROOT) = RL.
  • Set RTAG(ROOT) = 0.

E7. Return ROOT as the root of the derivative tree for u / v.

This program recursively constructs all necessary subtrees, allocating new nodes for each arithmetic operation, and ensures that no original nodes are overwritten. Each recursion terminates at terminal nodes, applying rules (11) and (12) for constants and variables.

Memory management is consistent with the convention in Section 2.3.2: COPY produces right-threaded binary trees with RTAG = 0 for normal links and negative for threads.

The final tree represents $D(u/v)$ exactly according to (18) and is ready for subsequent traversal or further algebraic manipulation.

This completes the solution.

∎