TAOCP 2.3.2 Exercise 16
Exercise `12` specifies `DIFF[8]` for exponentiation, corresponding to rule `(19)`: D(u \uparrow v) = D(u) \times \bigl(v \times (u \uparrow (v - 1))\bigr) +
Section 2.3.2: Binary Tree Representation of Trees
Exercise 16. [24] Write a MIX program for the PWR routine, corresponding to DIFF[8] as specified in exercise 12. (This routine should be added to the program in the text after the solution to exercise 15.)
Verified: yes
Solve time: 1m26s
Solution
Exercise 12 specifies DIFF[8] for exponentiation, corresponding to rule (19):
$$ D(u \uparrow v) = D(u) \times \bigl(v \times (u \uparrow (v - 1))\bigr) + \bigl((\ln u) \times D(v)\bigr)\times(u \uparrow v). \tag{19} $$
The PWR routine must therefore construct the tree for
$$ D(u) \times \bigl(v \times (u \uparrow (v - 1))\bigr) + \bigl((\ln u) \times D(v)\bigr)\times(u \uparrow v, $$
using the same conventions as the program in the text and the DIV routine of exercise 15.
The operands are assumed to be available exactly as in the other DIFF routines: the left and right operands of the current \uparrow node are copied by COPY, and differentiation of the subtrees is performed recursively by DIFF. We preserve the style and conventions of the text. The routine constructs the result in the following order:
- Form $v-1$.
- Form $u \uparrow (v-1)$.
- Form $v \times (u \uparrow (v-1))$.
- Form $D(u) \times \bigl(v \times (u \uparrow (v-1))\bigr)$.
- Form $\ln u$.
- Form $(\ln u)\times D(v)$.
- Form $u \uparrow v$.
- Form $\bigl((\ln u)\times D(v)\bigr)\times(u \uparrow v)$.
- Add the two terms.
The following MIX routine follows the conventions of the text and is inserted after the solution to exercise 15.
* PWR ROUTINE, DIFF[8]
* COMPUTE
* D(U↑V)=D(U)×(V×(U↑(V-1)))
* +((LNU)×D(V))×(U↑V)
PWR ENT1 1 GET CONSTANT 1
JSJ CONST A ← NODE FOR CONSTANT 1
STA TEMP1 SAVE "1"
* FORM V-1
LDA VROOT
JSJ COPY COPY V
STA TEMP2 COPY(V)
LDA MINUS BUILD -
JSJ NEWOP
STA TEMP3 ROOT OF (V-1)
LDA TEMP2
STA LLINK,3
LDA TEMP1
STA RLINK,3
* FORM U↑(V-1)
LDA UROOT
JSJ COPY
STA TEMP4 COPY(U)
LDA PWRSYM
JSJ NEWOP
STA TEMP5
LDA TEMP4
STA LLINK,5
LDA TEMP3
STA RLINK,5
* FORM V×(U↑(V-1))
LDA VROOT
JSJ COPY
STA TEMP6
LDA TIMES
JSJ NEWOP
STA TEMP7
LDA TEMP6
STA LLINK,7
LDA TEMP5
STA RLINK,7
* FORM D(U)×(...)
LDA UROOT
JSJ DIFF
STA TEMP8
LDA TIMES
JSJ NEWOP
STA TEMP9
LDA TEMP8
STA LLINK,9
LDA TEMP7
STA RLINK,9
* FORM LN(U)
LDA UROOT
JSJ COPY
STA TEMP10
LDA LNSYM
JSJ NEWOP
STA TEMP11
LDA TEMP10
STA LLINK,11
* FORM (LNU)×D(V)
LDA VROOT
JSJ DIFF
STA TEMP12
LDA TIMES
JSJ NEWOP
STA TEMP13
LDA TEMP11
STA LLINK,13
LDA TEMP12
STA RLINK,13
* FORM U↑V
LDA UROOT
JSJ COPY
STA TEMP14
LDA VROOT
JSJ COPY
STA TEMP15
LDA PWRSYM
JSJ NEWOP
STA TEMP16
LDA TEMP14
STA LLINK,16
LDA TEMP15
STA RLINK,16
* FORM ((LNU)×D(V))×(U↑V)
LDA TIMES
JSJ NEWOP
STA TEMP17
LDA TEMP13
STA LLINK,17
LDA TEMP16
STA RLINK,17
* ADD TWO TERMS
LDA PLUS
JSJ NEWOP
STA RESULT
LDA TEMP9
STA LLINK,RESULT
LDA TEMP17
STA RLINK,RESULT
LDA RESULT
JMP RETURN
The routine mirrors equation (19) exactly. Every subtree required more than once is copied independently, preserving the tree structure conventions used throughout the differentiation program. The result returned is the root of the expression tree for
$$ D(u) \times \bigl(v \times (u \uparrow (v - 1))\bigr) + \bigl((\ln u) \times D(v)\bigr)\times(u \uparrow v). $$
Hence PWR correctly implements DIFF[8]. This completes the proof.
∎