Differentiation
---------------
Differentiation is achieved using just another expression transformation with a
set of reduction rules, located towards the end of →#.math←. "∆x" can be read as
"dx". For example, the product rule D(u*v) = uD(v) + vD(u) is expressed:
(p*q)∆a = p∆a * q + p * q∆a
Pattern matching variables a, b, c match expression variables x and t, as in the
expression: (3*x∧2 + 2*x + 1)∆x, or (t∧2)∆t.
The name '∆' has no special significance to the code that implements reduction;
it is just another function defined as having high precedence and binding left.
← ∆() ⍝ derivative wrt ⍵
Left binding means that we can write a second differential without parentheses:
load math
until''
(1/t)∆t∆t
2*t∧-3
Symbol 'd' could equally well have been used for the operator, although there
would be a danger of confusion caused by errors such as:
a+b+c+d, a=1, b=2, c=3, d=4
\ missing operand
Donald Knuth says: "Programs for algebraic differentiation were among the first
symbol-manipulation routines ever written for computers; they were used as early
as 1952".
The reduction process is vital to the rules that define differentiation; other-
wise, unmanageably large expressions result. Even so, there is much scope for
improvement as the following third derivative shows:
load math
eval'(x∧x∧x)∆x∆x∆x' ⍝ 3rd derivative in linear form
((ln(x)+1)*x∧x+1)*x∧(x+x∧x-2)+(x+x∧x-1)*((x+x∧x-2)*x∧(x+x∧x-3)+((ln(x)+1)*x∧x+1)
*ln(x)*x∧(x+x∧x-2))+((x∧(x-1)+x∧x*(ln(x)+1)∧2)*ln(x)+((ln(x)+1)*x∧x+1)/x)*
x∧(x+x∧x-1)+((ln(x)+1)*x∧x+1)*ln(x)*((x+x∧x-1)*x∧(x+x∧x-2)+((ln(x)+1)*x∧x+
1)*ln(x)*x∧(x+x∧x-1))+(((x-1)*x∧(x-2)+ln(x)*x∧(x-1)+(ln(x)+1)*x∧x*(ln(x)+1
)∧2+2*(x∧x*((ln(x)+1)/x)))*ln(x)+(x∧(x-1)+x∧x*(ln(x)+1)∧2)/x+((x∧(x-1)+x∧x
*(ln(x)+1)∧2)/x-(ln(x)+1)*x∧x/x∧2))*x∧x∧x+2*(((x∧(x-1)+x∧x*(ln(x)+1)∧2)*ln
(x)+(ln(x)+1)*x∧x/x)*(x∧(x+x∧x-1)+(ln(x)+1)*x∧x*ln(x)*x∧x∧x))+(ln(x)+1)*x∧
x*ln(x)*((x+x∧x-1)*x∧(x+x∧x-2)+((ln(x)+1)*x∧x+1)*ln(x)*x∧(x+x∧x-1)+((x∧(x-
1)+x∧x*(ln(x)+1)∧2)*ln(x)+(ln(x)+1)*x∧x/x)*x∧x∧x+(ln(x)+1)*x∧x*ln(x)*(x∧(x
+x∧x-1)+(ln(x)+1)*x∧x*ln(x)*x∧x∧x))
't' eval '(x∧x∧x)∆x∆x∆x' ⍝ 3rd derivative in tree form
+
┌────────────────────────────────────────────────────────────┴───────────┐
+ *
┌───────────────────────────────────────────────────────────────────────────────────────────────────────────┴─┐ ┌──┴──────────────────────────────────────────────────────────────────────────────┐
+ * * +
┌───────────────────────────────────────────────────────┴─────────────────────────────────────────────────────────────────────────────────────────────────────┐ ┌┴──────────────────────────────┐ ┌───┴─┐ ┌────────────────────────────────────┴───────────┐
+ * 2 * * ln + *
┌──────────────────────────────────────────┴─────────────┐ ┌───────────────────────────────┴─┐ ┌──────────┴─────────┐ ┌─┴─┐ └┐ ┌───────────────────────┴──────────────────────────────┐ ┌──┴─────────┐
+ * + ∧ + + + ∧ x + * * +
┌─────────────────────────────────────────────────┴────────────────────────────────┐ ┌──┴─────────────────┐ ┌──────────────────┴──────────────────┐ ┌┴─┐ ┌──┴────────┐ ┌───────┴───────────┐ ┌─┴┐ ┌┴┐ ┌─────────┴─────────────┐ ┌──────────┴─┐ ┌───┴─┐ ┌───────┴───────────┐
+ * * + + - x ∧ * / ∧ * ln 1 x x * * + ∧ * ln ∧ *
┌─────────┴───────┐ ┌────────────┴─┐ ┌─┴─┐ ┌─────────┴─────────────┐ ┌──┴────────────────┐ ┌─┴────────┐ ┌┴┐ ┌──────────┴─┐ ┌───┴┐ ┌┴─────┐ ┌──┴─┐ └┐ ┌─┴─┐ ┌──┴─┐ ┌──┴────────┐ ┌┴─┐ ┌─┴─┐ └┐ ┌┴─────┐ ┌──┴─┐
* * + ∧ + ln * * * / / / x x + ln * x x - * ∧ x - ∧ * ∧ * / x ∧ + ∧ x x - * ∧
┌─┴─┐ ┌─┴─────────────────┐ ┌──┴──────────┐ ┌┴─────┐ ┌───┴┐ └┐ ┌─┴─┐ ┌──┴─┐ ┌────────────┴─┐ ┌──────────┴┐ ┌──────────┴┐ ┌───┴─┐ ┌───┴───┐ └┐ ┌─┴─┐ ┌───┴┐ ┌───┴─┐ ┌┴─┐ ┌───┴┐ ┌┴─────┐ ┌─┴─┐ ┌┴─────┐ ┌──────────┴─┐ ┌───┴┐ ┌┴┐ ┌─┴┐ ┌┴┐ ┌───┴┐ ┌───┴─┐ ┌┴─┐
+ ∧ - + * / x - * 1 x - ∧ * ∧ + ln + x + x * ∧ ∧ * x + ∧ + 1 * ln x ∧ + 1 x - + ln x - + ln * x x x ln 1 x x + 1 * ln x ∧
┌───┴┐ ┌┴─────┐ ┌───┴┐ ┌─────────┴─────────────┐ ┌──────────┴─┐ ┌─┴┐ ┌───┴┐ ┌─┴─┐ ┌───┴┐ ┌┴─────┐ ┌─┴─┐ ┌┴─────┐ ┌───────────────┴─┐ └┐ ┌───┴───┐ ┌───┴───┐ ┌─┴─┐ ┌┴┐ ┌┴─┐ ┌─┴────┐ ┌─┴┐ ┌┴┐ ┌┴─┐ ┌─┴─┐ └┐ ┌┴┐ ┌┴─┐ ┌───┴┐ ┌───┴┐ └┐ ┌───┴┐ ┌───┴───┐ └┐ ┌─┴─┐ └┐ ┌┴─┐ ┌─┴─┐ └┐ ┌┴┐
* 1 x - + 1 * * + ln + x + 1 + ∧ + 1 x - + ln x - + * x ∧ * ∧ * + ∧ x 2 x - ∧ ∧ ln 1 x x x ∧ + ∧ x x x x ∧ + 2 * 1 x + 1 ∧ * x + ∧ x x ∧ + ∧ x x x
┌─┴─┐ ┌───┴┐ ┌┴─┐ ┌─┴─┐ ┌──┴─┐ ┌───┴───┐ └┐ ┌───┴┐ ┌┴─┐ ┌─┴┐ ┌┴┐ ┌┴─┐ ┌───┴┐ ┌───┴┐ └┐ ┌───┴┐ ┌────────┴────────┐ ┌┴───┐ ┌┴─┐ ┌─┴────┐ ┌┴─┐ ┌─┴────┐ ┌─┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌─┴┐ └┐ ┌┴┐ ┌─┴┐ ┌┴┐ ┌┴┐ ┌┴─┐ ┌─┴─┐ ┌┴─┐ ┌┴─┐ ┌─┴────┐ ┌─┴┐ ┌┴┐ ┌┴┐ ┌─┴┐ ┌┴┐
+ ∧ + 2 x ∧ - ∧ * ∧ ∧ * x * 1 x ∧ ln 1 x x x ∧ + 2 * 1 x + 1 + * 2 * x - ∧ ∧ x - ∧ ∧ ln 1 x x x 1 x x + 2 x x x ln 1 x x x x x ∧ + ∧ x ∧ x - ∧ ∧ ln 1 x x x x ln 1 x x
┌─┴┐ ┌┴┐ ┌┴─┐ ┌┴┐ ┌───┴┐ ┌┴─────┐ ┌─┴─┐ ┌┴─────┐ ┌┴─┐ ┌─┴────┐ ┌─┴─┐ ┌┴┐ └┐ ┌┴┐ ┌┴─┐ ┌─┴─┐ ┌┴─┐ ┌─────┴──┐ ┌───┴────┐ ┌─┴────┐ ┌┴┐ ┌┴┐ ┌─┴┐ ┌┴┐ ┌┴┐ ┌─┴┐ └┐ ┌─┴┐ └┐ ┌┴┐ ┌─┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌─┴┐ └┐ └┐
ln 1 x x x ∧ x x + 2 x - + ln x - x - ∧ ∧ + ∧ x x x x x x ∧ + ∧ x ∧ * * * ∧ ∧ / x 1 x x + 2 x 1 x x + 2 x ln 1 x x x ln 1 x x x x x 1 x x + 2 x x
└┐ ┌┴┐ ┌┴─┐ ┌───┴┐ ┌───┴┐ └┐ ┌───┴┐ ┌┴┐ ┌┴┐ ┌─┴┐ ┌─┴┐ ┌┴┐ ┌┴┐ ┌─┴┐ ┌┴┐ ┌┴┐ ┌─┴─┐ ┌─┴─┐ ┌─┴─┐ ┌─┴┐ ┌┴┐ ┌─┴┐ ┌─┴┐ ┌─┴┐ └┐ └┐ ┌─┴┐
x x x x ∧ + 3 * 1 x + 2 x 1 x x + 2 ln 1 x x x x ln 1 x x x x - ∧ ln ∧ + ∧ + 2 x x + x ln 1 ln 1 x x ln 1
┌┴┐ ┌┴─┐ ┌─┴─┐ ┌┴─┐ ┌─┴┐ └┐ └┐ ┌┴┐ ┌┴─┐ └┐ ┌┴─┐ ┌─┴┐ ┌┴┐ ┌─┴┐ ┌─┴┐ └┐ └┐ └┐
x x x ∧ + ∧ x ∧ ln 1 x x x 1 x - x x - ln 1 x x ln 1 ln 1 x x x
┌┴┐ ┌─┴┐ ┌┴┐ ┌┴┐ └┐ ┌┴┐ ┌┴┐ └┐ └┐ └┐
x x ln 1 x x x x x x 2 x 1 x x x
└┐
x
References:
Knuth, D.E., "The Art of Computer Programming" Vol 1: "Fundamental Algorithms",
Ch 2.3.2.
Kahrimanian, H.G., "Analytical differentiation by a digital computer", master's
thesis, Temple University, May 1953.
"Symposium on Automatic Programming" (Washington, D.C: Office of Naval Research,
May 1954), 6-14.
See also: →#.math←
Back to: →Contents←