Previously:
Differentiating f(x)^g(x)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 a pretty answer; that much is up to us! And generally, it requires more work.
The Differentiator
Graphing Derivatives
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 x to be expressed as anxⁿ, rather than say (xⁿ)*an, albeit the algebra is indifferent to such distinctions. On the other hand, nobody ever ordered xⁿ+xⁿ when they actually wanted 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, t represent any subtrees of arbitrary size and complexity;
- +, -, *, /, ^ are binary operators;
- u+, u- are the unary plus (identity) and minus (negate) operators respectively;
- c, d are numeric constants;
- 0, 1, -1 are the particular numeric constants 0, ±1.
The unary u- operator is equivalent to the binary '-' with (0) 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 (note: the converse rule, which is reductive, was actually used in the original code):u+(s) → s (Rule 1)
One And One Is Oneu-(s) → 0 - s (Rule 2)
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 notation c@d 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 0⁰, are assumed to raise the appropriate exceptions (DivideByZeroException, InvalidOperationException) when poked.c @ d → c@d (Rule 3)
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, is unchanged; while the second is set to 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.(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)
Constant Craving
Everything up to this point, with the singular exception of the unary u- 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:
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 Rule 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 s is governed by two '-' signs (or '/' signs in the multiplicative version).c + s → s + c (Rule 8)
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 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.(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)
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 x, 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 0 or ±1 on the RHS:
Rules 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:s + 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)
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 the non-elementary error function Erf(x) to the library.0 / s → 0 (Rule 11a) 0 ^ s → 0 (Rule 11b) 1 ^ s → 1 (Rule 11c)
No comments:
Post a Comment