Previous: Basic Algebra, Up: Algebra and Calculus Tutorial [Contents][Index]
No matter how many built-in commands Calc provided for doing algebra, there would always be something you wanted to do that Calc didn’t have in its repertoire. So Calc also provides a rewrite rule system that you can use to define your own algebraic manipulations.
Suppose we want to simplify this trigonometric formula:
1: 2 sec(x)^2 / tan(x)^2 - 2 / tan(x)^2
.
' 2sec(x)^2/tan(x)^2 - 2/tan(x)^2 RET s 1
If we were simplifying this by hand, we’d probably combine over the common denominator. The a n algebra command will do this, but we’ll do it with a rewrite rule just for practice.
Rewrite rules are written with the ‘:=’ symbol.
1: (2 sec(x)^2 - 2) / tan(x)^2
.
a r a/x + b/x := (a+b)/x RET
(The “assignment operator” ‘:=’ has several uses in Calc. All by itself the formula ‘a/x + b/x := (a+b)/x’ doesn’t do anything, but when it is given to the a r command, that command interprets it as a rewrite rule.)
The lefthand side, ‘a/x + b/x’, is called the pattern of the rewrite rule. Calc searches the formula on the stack for parts that match the pattern. Variables in a rewrite pattern are called meta-variables, and when matching the pattern each meta-variable can match any sub-formula. Here, the meta-variable ‘a’ matched the expression ‘2 sec(x)^2’, the meta-variable ‘b’ matched the constant ‘-2’ and the meta-variable ‘x’ matched the expression ‘tan(x)^2’.
This rule points out several interesting features of rewrite patterns. First, if a meta-variable appears several times in a pattern, it must match the same thing everywhere. This rule detects common denominators because the same meta-variable ‘x’ is used in both of the denominators.
Second, meta-variable names are independent from variables in the target formula. Notice that the meta-variable ‘x’ here matches the subformula ‘tan(x)^2’; Calc never confuses the two meanings of ‘x’.
And third, rewrite patterns know a little bit about the algebraic properties of formulas. The pattern called for a sum of two quotients; Calc was able to match a difference of two quotients by matching ‘a = 2 sec(x)^2’, ‘b = -2’, and ‘x = tan(x)^2’.
When the pattern part of a rewrite rule matches a part of the formula, that part is replaced by the righthand side with all the meta-variables substituted with the things they matched. So the result is ‘(2 sec(x)^2 - 2) / tan(x)^2’.
We could just as easily have written ‘a/x - b/x := (a-b)/x’ for
the rule. It would have worked just the same in all cases. (If we
really wanted the rule to apply only to ‘+’ or only to ‘-’,
we could have used the plain symbol. See Algebraic Properties of Rewrite Rules, for some examples of this.)
One more rewrite will complete the job. We want to use the identity ‘tan(x)^2 + 1 = sec(x)^2’, but of course we must first rearrange the identity in a way that matches our formula. The obvious rule would be ‘2 sec(x)^2 - 2 := 2 tan(x)^2’, but a little thought shows that the rule ‘sec(x)^2 := 1 + tan(x)^2’ will also work. The latter rule has a more general pattern so it will work in many other situations, too.
1: 2
.
a r sec(x)^2 := 1 + tan(x)^2 RET
You may ask, what’s the point of using the most general rule if you have to type it in every time anyway? The answer is that Calc allows you to store a rewrite rule in a variable, then give the variable name in the a r command. In fact, this is the preferred way to use rewrites. For one, if you need a rule once you’ll most likely need it again later. Also, if the rule doesn’t work quite right you can simply Undo, edit the variable, and run the rule again without having to retype it.
' a/x + b/x := (a+b)/x RET s t merge RET ' sec(x)^2 := 1 + tan(x)^2 RET s t secsqr RET 1: 2 sec(x)^2 / tan(x)^2 - 2 / tan(x)^2 1: 2 . . r 1 a r merge RET a r secsqr RET
To edit a variable, type s e and the variable name, use regular Emacs editing commands as necessary, then type C-c C-c to store the edited value back into the variable. You can also use s e to create a new variable if you wish.
Notice that the first time you use each rule, Calc puts up a “compiling” message briefly. The pattern matcher converts rules into a special optimized pattern-matching language rather than using them directly. This allows a r to apply even rather complicated rules very efficiently. If the rule is stored in a variable, Calc compiles it only once and stores the compiled form along with the variable. That’s another good reason to store your rules in variables rather than entering them on the fly.
(•) Exercise 1. Type m s to get Symbolic mode, then enter the formula ‘(2 + sqrt(2)) / (1 + sqrt(2))’. Using a rewrite rule, simplify this formula by multiplying the top and bottom by the conjugate ‘1 - sqrt(2)’. The result will have to be expanded by the distributive law; do this with another rewrite. See 1. (•)
The a r command can also accept a vector of rewrite rules, or a variable containing a vector of rules.
1: [merge, secsqr] 1: [a/x + b/x := (a + b)/x, ... ]
. .
' [merge,secsqr] RET =
1: 2 sec(x)^2 / tan(x)^2 - 2 / tan(x)^2 1: 2
. .
s t trig RET r 1 a r trig RET
Calc tries all the rules you give against all parts of the formula, repeating until no further change is possible. (The exact order in which things are tried is rather complex, but for simple rules like the ones we’ve used here the order doesn’t really matter. See Nested Formulas with Rewrite Rules.)
Calc actually repeats only up to 100 times, just in case your rule set has gotten into an infinite loop. You can give a numeric prefix argument to a r to specify any limit. In particular, M-1 a r does only one rewrite at a time.
1: (2 sec(x)^2 - 2) / tan(x)^2 1: 2
. .
r 1 M-1 a r trig RET M-1 a r trig RET
You can type M-0 a r if you want no limit at all on the number of rewrites that occur.
Rewrite rules can also be conditional. Simply follow the rule with a ‘::’ symbol and the desired condition. For example,
1: sin(x + 2 pi) + sin(x + 3 pi) + sin(x + 4 pi)
.
' sin(x+2pi) + sin(x+3pi) + sin(x+4pi) RET
1: sin(x + 3 pi) + 2 sin(x)
.
a r sin(a + k pi) := sin(a) :: k % 2 = 0 RET
(Recall, ‘k % 2’ is the remainder from dividing ‘k’ by 2, which will be zero only when ‘k’ is an even integer.)
An interesting point is that the variable ‘pi’ was matched literally rather than acting as a meta-variable. This is because it is a special-constant variable. The special constants ‘e’, ‘i’, ‘phi’, and so on also match literally. A common error with rewrite rules is to write, say, ‘f(a,b,c,d,e) := g(a+b+c+d+e)’, expecting to match any ‘f’ with five arguments but in fact matching only when the fifth argument is literally ‘e’!
Rewrite rules provide an interesting way to define your own functions. Suppose we want to define ‘fib(n)’ to produce the nth Fibonacci number. The first two Fibonacci numbers are each 1; later numbers are formed by summing the two preceding numbers in the sequence. This is easy to express in a set of three rules:
' [fib(1) := 1, fib(2) := 1, fib(n) := fib(n-1) + fib(n-2)] RET s t fib 1: fib(7) 1: 13 . . ' fib(7) RET a r fib RET
One thing that is guaranteed about the order that rewrites are tried is that, for any given subformula, earlier rules in the rule set will be tried for that subformula before later ones. So even though the first and third rules both match ‘fib(1)’, we know the first will be used preferentially.
This rule set has one dangerous bug: Suppose we apply it to the formula ‘fib(x)’? (Don’t actually try this.) The third rule will match ‘fib(x)’ and replace it with ‘fib(x-1) + fib(x-2)’. Each of these will then be replaced to get ‘fib(x-2) + 2 fib(x-3) + fib(x-4)’, and so on, expanding forever. What we really want is to apply the third rule only when ‘n’ is an integer greater than two. Type s e fib RET, then edit the third rule to:
fib(n) := fib(n-1) + fib(n-2) :: integer(n) :: n > 2
Now:
1: fib(6) + fib(x) + fib(0) 1: fib(x) + fib(0) + 8
. .
' fib(6)+fib(x)+fib(0) RET a r fib RET
We’ve created a new function, fib, and a new command,
a r fib RET, which means “evaluate all fib calls in
this formula.” To make things easier still, we can tell Calc to
apply these rules automatically by storing them in the special
variable EvalRules.
1: [fib(1) := ...] . 1: [8, 13]
. .
s r fib RET s t EvalRules RET ' [fib(6), fib(7)] RET
It turns out that this rule set has the problem that it does far more work than it needs to when ‘n’ is large. Consider the first few steps of the computation of ‘fib(6)’:
fib(6) = fib(5) + fib(4) = fib(4) + fib(3) + fib(3) + fib(2) = fib(3) + fib(2) + fib(2) + fib(1) + fib(2) + fib(1) + 1 = ...
Note that ‘fib(3)’ appears three times here. Unless Calc’s
algebraic simplifier notices the multiple ‘fib(3)’s and combines
them (and, as it happens, it doesn’t), this rule set does lots of
needless recomputation. To cure the problem, type s e EvalRules
to edit the rules (or just s E, a shorthand command for editing
EvalRules) and add another condition:
fib(n) := fib(n-1) + fib(n-2) :: integer(n) :: n > 2 :: remember
If a ‘:: remember’ condition appears anywhere in a rule, then if
that rule succeeds Calc will add another rule that describes that match
to the front of the rule set. (Remembering works in any rule set, but
for technical reasons it is most effective in EvalRules.) For
example, if the rule rewrites ‘fib(7)’ to something that evaluates
to 13, then the rule ‘fib(7) := 13’ will be added to the rule set.
Type ' fib(8) RET to compute the eighth Fibonacci number, then type s E again to see what has happened to the rule set.
With the remember feature, our rule set can now compute
‘fib(n)’ in just n steps. In the process it builds
up a table of all Fibonacci numbers up to n. After we have
computed the result for a particular n, we can get it back
(and the results for all smaller n) later in just one step.
All Calc operations will run somewhat slower whenever EvalRules
contains any rules. You should type s u EvalRules RET now to
un-store the variable.
(•) Exercise 2. Sometimes it is possible to reformulate
a problem to reduce the amount of recursion necessary to solve it.
Create a rule that, in about n simple steps and without recourse
to the remember option, replaces ‘fib(n, 1, 1)’ with
‘fib(1, x, y)’ where x and y are the
nth and n+1st Fibonacci numbers, respectively. This rule is
rather clunky to use, so add a couple more rules to make the “user
interface” the same as for our first version: enter ‘fib(n)’,
get back a plain number. See 2. (•)
There are many more things that rewrites can do. For example, there are ‘&&&’ and ‘|||’ pattern operators that create “and” and “or” combinations of rules. As one really simple example, we could combine our first two Fibonacci rules thusly:
[fib(1 ||| 2) := 1, fib(n) := ... ]
That means “fib of something matching either 1 or 2 rewrites
to 1.”
You can also make meta-variables optional by enclosing them in opt.
For example, the pattern ‘a + b x’ matches ‘2 + 3 x’ but not
‘2 + x’ or ‘3 x’ or ‘x’. The pattern ‘opt(a) + opt(b) x’
matches all of these forms, filling in a default of zero for ‘a’
and one for ‘b’.
(•) Exercise 3. Your friend Joe had ‘2 + 3 x’ on the stack and tried to use the rule ‘opt(a) + opt(b) x := f(a, b, x)’. What happened? See 3. (•)
(•) Exercise 4. Starting with a positive integer ‘a’, divide ‘a’ by two if it is even, otherwise compute ‘3 a + 1’. Now repeat this step over and over. A famous unproved conjecture is that for any starting ‘a’, the sequence always eventually reaches 1. Given the formula ‘seq(a, 0)’, write a set of rules that convert this into ‘seq(1, n)’ where n is the number of steps it took the sequence to reach the value 1. Now enhance the rules to accept ‘seq(a)’ as a starting configuration, and to stop with just the number n by itself. Now make the result be a vector of values in the sequence, from a to 1. (The formula ‘x|y’ appends the vectors x and y.) For example, rewriting ‘seq(6)’ should yield the vector ‘[6, 3, 10, 5, 16, 8, 4, 2, 1]’. See 4. (•)
(•) Exercise 5. Define, using rewrite rules, a function ‘nterms(x)’ that returns the number of terms in the sum x, or 1 if x is not a sum. (A sum for our purposes is one or more non-sum terms separated by ‘+’ or ‘-’ signs, so that ‘2 - 3 (x + y) + x y’ is a sum of three terms.) See 5. (•)
(•) Exercise 6. A Taylor series for a function is an infinite series that exactly equals the value of that function at values of ‘x’ near zero.
cos(x) = 1 - x^2 / 2! + x^4 / 4! - x^6 / 6! + ...
The a t command produces a truncated Taylor series which is obtained by dropping all the terms higher than, say, ‘x^2’. Calc represents the truncated Taylor series as a polynomial in ‘x’. Mathematicians often write a truncated series using a “big-O” notation that records what was the lowest term that was truncated.
cos(x) = 1 - x^2 / 2! + O(x^3)
The meaning of ‘O(x^3)’ is “a quantity which is negligibly small if ‘x^3’ is considered negligibly small as ‘x’ goes to zero.”
The exercise is to create rewrite rules that simplify sums and products of power series represented as ‘polynomial + O(var^n)’. For example, given ‘1 - x^2 / 2 + O(x^3)’ and ‘x - x^3 / 6 + O(x^4)’ on the stack, we want to be able to type * and get the result ‘x - 2:3 x^3 + O(x^4)’. Don’t worry if the terms of the sum are rearranged. (This one is rather tricky; the solution at the end of this chapter uses 6 rewrite rules. Hint: The ‘constant(x)’ condition tests whether ‘x’ is a number.) See 6. (•)
Just for kicks, try adding the rule 2+3 := 6 to EvalRules.
What happens? (Be sure to remove this rule afterward, or you might get
a nasty surprise when you use Calc to balance your checkbook!)
See Rewrite Rules, for the whole story on rewrite rules.
Previous: Basic Algebra, Up: Algebra and Calculus Tutorial [Contents][Index]