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←