**The Simplifier The Better**

*Previously:*

Simplification of algebraic expressions was never the intended destination of this series, but it's where we've landed. The rules of differentiation guarantee an answer for any input function, subject to certain reasonable conditions of continuity. They just don't promise aDifferentiating f(x)^g(x)

The Differentiator

Graphing Derivatives

*pretty*answer; that much is up to us! And generally, it requires more work.

Reduction of algebraic formulae is a big subject. Sometimes, to be fair, that's due to subjective constraints we place on answers. Take polynomials for example. It's natural to expect every power of

**to be expressed as**

*x***, rather than say**

*a*_{n}xⁿ**, albeit the algebra is indifferent to such distinctions. On the other hand, nobody ever ordered**

*(xⁿ)*a*_{n}**when they actually wanted**

*xⁿ+xⁿ***.**

*2xⁿ*Our

*Simplify()*method is a fairly arbitrary piece of ad-hoc coding, which applies a specific set of transformation rules to the expression tree. These rules are motivated by the particular output from certain popular examples of differentiation, and are all applied during a single traversal of the tree. Here we will consider an alternative, where rules are applied one by one to the entire tree, starting at the root and proceeding depth-first recursively. These steps successively transform the tree such that new invariants become true upon each pass, resulting in an overall directed process of reduction.

Let's continue using our informal rule notation, where

,*s*represent any subtrees of arbitrary size and complexity;*t*,*+*,*-*,***,*/*are binary operators;*^*,*u+*are the unary plus (identity) and minus (negate) operators respectively;*u-*,*c*are numeric constants;*d*,*0*,*1*are the particular numeric constants 0, ±1.*-1*

**to indicate the application of a transformation rule to its left operand, resulting in the new tree in its right operand, we have the following examples. First, the unary**

*'→'***operator represents the identity transformation, and can just be dropped from wherever it occurs:**

*u+*The unaryu+(s) → s(Rule 1)

**operator is equivalent to the binary**

*u-***with**

*'-'***on its left hand side. This is not strictly a reductive transformation, but it might be useful if we want to rid the tree of all unary operators, so that some other rule requiring this precondition can then be applied**

*(0)**(note: the converse rule, which*:

__is__reductive, was actually used in the original code)u-(s) → 0 - s(Rule 2)

**One And One Is One**

Any binary operator with constants on both sides (constant siblings) can be replaced by a single, computed constant value. Let

**be any one of the five binary operators. Then we have this rule template:**

*@*where the notationc @ d → c@d(Rule 3)

**written without intervening spaces indicates a single constant node, comprising an immediate numerical calculation. Obviously checks against division by zero, and other indeterminate forms such as**

*c@d**0⁰*, are assumed to raise the appropriate exceptions (

*DivideByZeroException*,

*InvalidOperationException*) when poked.

Similarly, certain constant niblings (nieces or nephews) can be combined, when their operators "match" - i.e., they are either both additive, or both multiplicative. For ease of legibility and comprehension in what follows, I'm going to let

**represent the commutative operator in such a pair (which will actually be either**

*'+'***or**

*'+'***), and let**

*'*'***represent its noncommutative inverse (actually**

*'-'***or**

*'-'***). Then we have these four templates:**

*'/'*Notice the pattern of operators in these templates. The first operator, following the(s + c) + d → s + c+d(Rule 4a)(s + c) - d → s + c-d(Rule 4b)(s - c) + d → s - c-d(Rule 4c)(s - c) - d → s - c+d(Rule 4d)

**, is unchanged; while the second is set to**

*s**either*the commutative

**if the original two operators were the same,**

*'+'**or*the noncommutative

**if they were different. This logic was handled by local variables**

*'-'**same*&

*opps*in the original

*SimplifyBinary()*method.

**Constant Craving**

Everything up to this point, with the singular exception of the unary

**noted above, was included in the earlier single traversal code. However these four latest example templates assume all the constants are on the RHS of their parent binaries. That suggests another twelve such patterns exist, where either one or both constants are actually on the LHS:**

*u-*Almost half of these can be handled by preprocessing the tree to ensure that whenever possible, i.e. when a binary operator is commutative, its constant term appears on the RHS, using this supplementary rule:(c + s) + d → s + c+d(Rule 5a)(c + s) - d → s + c-d(Rule 5b)(c - s) + d → c+d - s(Rule 5c)(c - s) - d → c-d - s(Rule 5d)c + (s + d) → s + c+d(Rule 6a)c + (s - d) → s + c-d(Rule 6b)c - (s + d) → c+d - s(Rule 6c)c - (s - d) → c-d - s(Rule 6d)c + (d + s) → s + c+d(Rule 7a)c + (d - s) → c+d - s(Rule 7b)c - (d + s) → c-d - s(Rule 7c)c - (d - s) → s + c-d(Rule 7d)

A single application of Rulec + s → s + c(Rule 8)

*8*carries Rules

*5a*and

*6a*into

*4a*,

*5b*into

*4b*, and

*6b*into

*4c*, while two successive applications carry

*7a*into

*4a*. That's five out of these new twelve cases dealt with. We are frustrated in claiming a full 50% by Rule

*7d*, which requires recognising that

**is governed by two**

*s***signs (or**

*'-'***signs in the multiplicative version).**

*'/'***Constant Cousins**

Another important transformation which could have been included in the original sample code, but was omitted for purposes of clarity, is the combination of

*cousin*constants. This is where a binary operation has two binary children, each of which has a constant operand. Since we are not handling distributivity here, the three binaries involved must be either all additive, or all multiplicative. This yields another 8 templates which can be expressed, reusing the previous operator definitions, like this:

Again there's a pattern to the operators, before and after. This time the first and second operators swap places, while the third is set(s + c) + (t + d) → (s + t) + c+d(Rule 9a)(s + c) + (t - d) → (s + t) + c-d(Rule 9b)(s + c) - (t + d) → (s - t) + c-d(Rule 9c)(s + c) - (t - d) → (s - t) + c+d(Rule 9d)(s - c) + (t + d) → (s + t) - c-d(Rule 9e)(s - c) + (t - d) → (s + t) - c+d(Rule 9f)(s - c) - (t + d) → (s - t) - c+d(Rule 9g)(s - c) - (t - d) → (s - t) - c-d(Rule 9h)

*either*to the commutative

**if the original set of three operators contained an**

*'+'**even*number (0 or 2) of

**s,**

*'-'**or*to the noncommutative

**if it contained an**

*'-'**odd*number (1 or 3). And just as before, the possibility of constants appearing in the LHS leads to another proliferation of additional cases (initially 24), around half of which are handled by our commutativity code, with the rest requiring further special handling.

**Finally, Semantix Rears Its Monstrous Head**

Merged constants aside, all of the foregoing transformations have been syntactical, in that they have not relied upon any particular constant values, function calls, powers of

**, etc. Now we've combined as many constants into single values as we feel inclined to do, we can take advantage of a few simple semantic rules, such as those pertaining to additive and multiplicative identities and inverses. Assuming we're on the final stretch, we presumably no longer need maintain the unary-free invariant property of our expression tree, and can also reintroduce negative versions of the multiplicative rules. So, we may have**

*x**0*or

*±1*on the RHS:

Ruless + 0 → s(Rule 10a)s - 0 → s(Rule 10b)s * 0 → 0(Rule 10c)s * 1 → s(Rule 10d)s * -1 → -s(Rule 10e)s / 1 → s(Rule 10f)s / -1 → -s(Rule 10g)s ^ 0 → 1(Rule 10h)s ^ 1 → s(Rule 10i)

*10e*&

*10g*are the negatives mentioned above. Finally, we may have

*0*or

*1*on the LHS, in these few cases which have not already been handled by commutativity:

Next time: work continues on the above optimisation system, and a new UI is simultaneously being developed to allow user entry of formulae as plain text. While all that rages on, I'll report on several interesting design snippets just to keep the post count ticking over. The first of these will be the addition of the0 / s → 0(Rule 11a)0 ^ s → 0(Rule 11b)1 ^ s → 1(Rule 11c)

*non-elementary error function Erf(x)*to the library.

## No comments:

## Post a Comment