Usenet 1994 January/usenetsourcesnewsgroupsinfomagicjanuary1994.iso/sources/misc/volume24/gnucalc/part34

Text File | 1991-10-31 | 55.5 KB | 1,513 lines

Newsgroups: comp.sources.misc
From: [e-mail] (David Gillespie)
Subject:  v24i082:  gnucalc - GNU Emacs Calculator, v2.00, Part34/56
Message-ID: <[e-mail]>
X-Md4-Signature: 3fc5f7c3303aed7ac7de62e608e98d7b
Date: Thu, 31 Oct 1991 21:45:26 GMT
Approved: [e-mail]

Submitted-by: [e-mail] (David Gillespie)
Posting-number: Volume 24, Issue 82
Archive-name: gnucalc/part34
Environment: Emacs
Supersedes: gmcalc: Volume 13, Issue 27-45

---- Cut Here and unpack ----
#!/bin/sh
# do not concatenate these parts, unpack them in order with /bin/sh
# file calc.texinfo continued
#
if test ! -r _shar_seq_.tmp; then
    echo 'Please unpack part 1 first!'
    exit 1
fi
(read Scheck
 if test "$Scheck" != 34; then
    echo Please unpack part "$Scheck" next!
    exit 1
 else
    exit 0
 fi
) < _shar_seq_.tmp || exit 1
if test ! -f _shar_wnt_.tmp; then
    echo 'x - still skipping calc.texinfo'
else
echo 'x - continuing file calc.texinfo'
sed 's/^X//' << 'SHAR_EOF' >> 'calc.texinfo' &&
has a maximum value at @cite{x = 1.19023}.  (The function also has a
local @emph{minimum} at @cite{x = 0}.)
X
When we solved for @cite{x}, we got only one value even though
@cite{34 - 24 x^2 = 0} is a quadratic equation that ought to have
two solutions.  The reason is that @w{@kbd{a S}} normally returns a
single ``principal'' solution.  If it needs to come up with an
arbitrary sign (as occurs in the quadratic formula) it picks @cite{+}.
If it needs an arbitrary integer, it picks zero.  We can get a full
solution by pressing @kbd{H} (the Hyperbolic flag) before @kbd{a S}.
X
@group
@smallexample
1:  34 - 24 x^2 = 0    1:  x = 1.19023 s1      1:  x = -1.19023
X    .                      .                       .
X
X    r 3                    H a S x RET  s 5        1 n  s l s1 RET
@end smallexample
@end group
X
@noindent
Calc has invented the variable @samp{s1} to represent an unknown sign;
it is supposed to be either @i{+1} or @i{-1}.  Here we have used
the ``let'' command to evaluate the expression when the sign is negative.
If we plugged this into our second derivative we would get the same,
negative, answer, so @cite{x = -1.19023} is also a maximum.
X
To find the actual maximum value, we must plug our two values of @cite{x}
into the original formula.
X
@group
@smallexample
2:  17 x^2 - 6 x^4 + 3    1:  24.08333 s1^2 - 12.04166 s1^4 + 3
1:  x = 1.19023 s1            .
X    .
X
X    r 1 r 5                   s l RET
@end smallexample
@end group
X
@noindent
(Here we see another way to use @kbd{s l}; if its input is an equation
with a variable on the lefthand side, then @kbd{s l} treats the equation
like an assignment to that variable if you don't give a variable name.)
X
It's clear that this will have the same value for either sign of
@code{s1}, but let's work it out anyway, just for the exercise:
X
@group
@smallexample
2:  [-1, 1]              1:  [15.04166, 15.04166]
1:  24.08333 s1^2 ...        .
X    .
X
X  [ 1 n , 1 ] TAB            V M $ RET
@end smallexample
@end group
X
@noindent
Here we have used a vector mapping operation to evaluate the function
at several values of @samp{s1} at once.  @kbd{V M $} is like @kbd{V M '}
except that it takes the formula from the top of the stack.  The
formula is interpreted as a function to apply across the vector at the
next-to-top stack level.  Since a formula on the stack can't contain
@samp{$} signs, Calc assumes the variables in the formula stand for
different arguments.  It prompts you for an @dfn{argument list}, giving
the list of all variables in the formula in alphabetical order as the
default list.  In this case the default is @samp{(s1)}, which is just
what we want so we simply press @key{RET} at the prompt.
X
If there had been several different values, we could have used
@w{@kbd{V R X}} to find the global maximum.
X
Calc has a built-in @kbd{a P} command that solves an equation using
@w{@kbd{H a S}} and returns a vector of all the solutions.  It simply
automates the job we just did by hand.  Applied to our original
cubic polynomial, it would produce the vector of solutions
@cite{[1.19023, -1.19023, 0]}.  (There is also an @kbd{a X} command
which finds a local maximum of a function.  It uses a numerical search
method rather than examining the derivatives, and thus requires you
to provide some kind of initial guess to show it where to look.)
X
(@bullet{}) @strong{Exercise 2.}  Find the values for which the
original formula @cite{17 x^2 - 6 x^4 + 3} is zero.  (There are
four, two of which are complex numbers.)  Verify that these
solutions are in fact correct.  @xref{Algebra Answer 2, 2}. (@bullet{})
X
The @kbd{m s} command enables ``symbolic mode,'' in which formulas
like @samp{sqrt(5)} that can't be evaluated exactly are left in
symbolic form rather than giving a floating-point approximate answer.
Fraction mode (@kbd{m f}) is also useful when doing algebra.
X
@group
@smallexample
2:  34 x - 24 x^3        2:  34 x - 24 x^3
1:  34 x - 24 x^3        1:  [sqrt(51) / 6, sqrt(51) / -6, 0]
X    .                        .
X
X    r 2  RET     m s  m f    a P x RET
@end smallexample
@end group
X
One more mode that makes reading formulas easier is ``Big mode.''
X
@group
@smallexample
X               3
2:  34 x - 24 x
X
X      ____   ____
X     V 51   V 51
1:  [-----, -----, 0]
X       6     -6
X
X    .
X
X    d B
@end smallexample
@end group
X
Here things like powers, quotients and fractions, and square roots
are displayed in a two-dimensional pictorial form.  Calc has other
language modes as well, such as C mode, FORTRAN mode, and @TeX{} mode.
X
@group
@smallexample
2:  34*x - 24*pow(x, 3)               2:  34*x - 24*x ** 3
1:  @{sqrt(51) / 6, sqrt(51) / -6, 0@}  1:  /sqrt(51) / 6, sqrt(51) / -6, 0/
X    .                                     .
X
X    d C                                   d F
X
@end smallexample
@end group
@noindent
@group
@smallexample
3:  34 x - 24 x^3
2:  [@{\sqrt@{51@} \over 6@}, @{\sqrt@{51@} \over -6@}, 0]
1:  @{2 \over 3@} \sqrt@{5@}
X    .
X
X    d T   ' 2 \sqrt@{5@} \over 3 RET
@end smallexample
@end group
X
@noindent
As you can see, language modes affect both entry and display of
formulas.  They affect such things as the names used for built-in
functions, the set of arithmetic operators and their precedences,
and notations for vectors and matrices.
X
Notice that @samp{sqrt(51)} may cause problems with older
implementations of C and FORTRAN, which would require something more
like @samp{sqrt(51.0)}.  It is always wise to check over the formulas
produced by the various language modes to make sure they fully correct.
X
Type @kbd{m s}, @kbd{m f}, and @kbd{d N} to reset these modes.  (You
may prefer to remain in Big mode, but all the examples in the tutorial
are shown in normal mode.)
X
@cindex Area under a curve
What is the area under the portion of this curve from @cite{x = 1} to @cite{2}?
This is simply the integral of the function:
X
@group
@smallexample
1:  17 x^2 - 6 x^4 + 3     1:  5.6666 x^3 - 1.2 x^5 + 3 x
X    .                          .
X
X    r 1                        a i x
@end smallexample
@end group
X
@noindent
We want to evaluate this at our two values for @cite{x} and subtract.
One way to do it is again with vector mapping and reduction:
X
@group
@smallexample
2:  [2, 1]            1:  [12.93333, 7.46666]    1:  5.46666
1:  5.6666 x^3 ...        .                          .
X
X   [ 2 , 1 ] TAB          V M $ RET                  V R -
@end smallexample
@end group
X
(@bullet{}) @strong{Exercise 3.}  Find the integral from 1 to @cite{y}
of @c{$x \sin \pi x$}
@w{@cite{x sin(pi x)}} (where the sine is calculated in radians).
Find the values of the integral for integers @cite{y} from 1 to 5.
@xref{Algebra Answer 3, 3}. (@bullet{})
X
Calc's integrator can do many simple integrals symbolically, but many
others are beyond its capabilities.  Suppose we wish to find the area
under the curve @c{$\sin x \ln x$}
@cite{sin(x) ln(x)} over the same range of @cite{x}.  If
you entered this formula and typed @kbd{a i x RET} (don't bother to try
this), Calc would work for a long time but would be unable to find a
solution.  In fact, there is no closed-form solution to this integral.
Now what do we do?
X
@cindex Integration, numerical
@cindex Numerical integration
One approach would be to do the integral numerically.  It is not hard
to do this by hand using vector mapping and reduction.  It is rather
slow, though, since the sine and logarithm functions take a long time.
We can save some time by reducing the working precision.
X
@group
@smallexample
3:  10                  1:  [1, 1.1, 1.2,  ...  , 1.8, 1.9]
2:  1                       .
1:  0.1
X    .
X
X 10 RET 1 RET .1 RET        C-u v x
@end smallexample
@end group
X
@noindent
(Note that we have used the extended version of @kbd{v x}; we could
also have used plain @kbd{v x} as follows:  @kbd{v x 10 RET 9 + .1 *}.)
X
@group
@smallexample
2:  [1, 1.1, ... ]              1:  [0., 0.084941, 0.16993, ... ]
1:  sin(x) ln(x)                    .
X    .
X
X    ' sin(x) ln(x) RET  s 1    m r  p 5 RET   V M $ RET
X
@end smallexample
@end group
@noindent
@group
@smallexample
1:  3.4195     0.34195
X    .          .
X
X    V R +      0.1 *
@end smallexample
@end group
X
@noindent
(If you got wildly different results, did you remember to switch
to radians mode?)
X
Here we have divided the curve into ten segments of equal width;
approximating these segments as rectangular boxes (i.e., assuming
the curve is nearly flat at that resolution), we compute the areas
of the boxes (height times width), then sum the areas.  (It is
faster to sum first, then multiply by the width, since the width
is the same for every box.)
X
The true value of this integral turns out to be about 0.374, so
we're not doing too well.  Let's try another approach.
X
@group
@smallexample
1:  sin(x) ln(x)    1:  0.84147 x - 0.84147 + 0.11957 (x - 1)^2 - ...
X    .                   .
X
X    r 1                 a t x=1 RET 4 RET
@end smallexample
@end group
X
@noindent
Here we have computed the Taylor series expansion of the function
about the point @cite{x=1}.  We can now integrate this polynomial
approximation, since polynomials are easy to integrate.
X
@group
@smallexample
1:  0.42074 x^2 + ...    1:  [-0.0446, -0.42073]      1:  0.3761
X    .                        .                            .
X
X    a i x RET            [ 2 , 1 ] TAB  V M $ RET         V R -
@end smallexample
@end group
X
@noindent
Better!  By increasing the precision and/or asking for more terms
in the Taylor series, we can get a result as accurate as we like.
(Taylor series converge better away from singularities in the
function such as the one at @code{ln(0)}, so it would also help to
expand the series about the points @cite{x=2} or @cite{x=1.5} instead
of @cite{x=1}.)
X
@cindex Simpson's rule
@cindex Integration by Simpson's rule
(@bullet{}) @strong{Exercise 4.}  Our first method approximated the
curve by stairsteps of width 0.1; the total area was then the sum
of the areas of the rectangles under these stairsteps.  Our second
method approximated the function by a polynomial, which turned out
to be a better approximation than stairsteps.  A third method is
@dfn{Simpson's rule}, which is like the stairstep method except
that the steps are not required to be flat.  Simpson's rule boils
down to the formula,
X
@ifinfo
@example
(h/3) * (f(a) + 4 f(a+h) + 2 f(a+2h) + 4 f(a+3h) + ...
X              + 2 f(a+(n-2)*h) + 4 f(a+(n-1)*h) + f(a+n*h))
@end example
@end ifinfo
@tex
\turnoffactive
$$ \displaylines{{h \over 3} (f(a) + 4 f(a+h) + 2 f(a+2h) + 4 f(a+3h) + \cdots
X   \hfill \cr \hfill    {} + 2 f(a+(n-2)h) + 4 f(a+(n-1)h) + f(a+n h))} $$
@end tex
X
@noindent
where @cite{n} (which must be even) is the number of slices and @cite{h}
is the width of each slice.  These are 10 and 0.1 in our example.
For reference, here is the corresponding equation for the stairstep
method:
X
@ifinfo
@example
h * (f(a) + f(a+h) + f(a+2h) + f(a+3h) + ...
X          + f(a+(n-2)*h) + f(a+(n-1)*h))
@end example
@end ifinfo
@tex
\turnoffactive
$$ h (f(a) + f(a+h) + f(a+2h) + f(a+3h) + \cdots
X           + f(a+(n-2)h) + f(a+(n-1)h)) $$
@end tex
X
Compute the integral from 1 to 2 of @c{$\sin x \ln x$}
@cite{sin(x) ln(x)} using
Simpson's rule with 10 slices.  @xref{Algebra Answer 4, 4}. (@bullet{})
X
Calc has a built-in @kbd{a I} command for doing numerical integration.
It uses @dfn{Romberg's method}, which is a more sophisticated cousin
of Simpson's rule.  In particular, it knows how to keep refining the
result until the current precision is satisfied.
X
@c [fix-ref Selecting Sub-Formulas]
Aside from the commands we've seen so far, Calc also provides a
large set of commands for operating on parts of formulas.  You
indicate the desired sub-formula by placing the cursor on any part
of the formula before giving a @dfn{selection} command.  Selections won't
be covered in the tutorial; @pxref{Selecting Subformulas}, for
details and examples.
X
@c hard exercise: simplify (2^(n r) - 2^(r*(n - 1))) / (2^r - 1) 2^(n - 1)
@c                to 2^((n-1)*(r-1)).
X
@node Rewrites Tutorial, , Basic Algebra Tutorial, Algebra Tutorial
@subsection Rewrite Rules
X
@noindent
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 @dfn{rewrite rule} system
that you can use to define your own algebraic manipulations.
X
Suppose we want to simplify this trigonometric formula:
X
@group
@smallexample
1:  1 / cos(x) - sin(x) tan(x)
X    .
X
X    ' 1/cos(x) - sin(x) tan(x) RET   s 1
@end smallexample
@end group
X
@noindent
If we were simplifying this by hand, we'd probably replace the
@samp{tan} with a @samp{sin/cos} first, then combine over a common
denominator.  There is no Calc command to do the former; the @kbd{j M}
selection command will do the latter but we'll do both with rewrite
rules just for practice.
X
Rewrite rules are written with the @samp{:=} symbol.
X
@group
@smallexample
1:  1 / cos(x) - sin(x)^2 / cos(x)
X    .
X
X    a r tan(a) := sin(a)/cos(a) RET
@end smallexample
@end group
X
@noindent
(The ``assignment operator'' @samp{:=} has several uses in Calc.  All
by itself the formula @samp{tan(a) := sin(a)/cos(a)} doesn't do anything,
but when it is given to the @kbd{a r} command, that command interprets
it as a rewrite rule.)
X
The lefthand side, @samp{tan(a)}, is called the @dfn{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
@dfn{meta-variables}, and when matching the pattern each meta-variable
can match any sub-formula.  Here, the meta-variable @samp{a} matched
the actual variable @samp{x}.
X
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
@samp{sin(x) / cos(x)}.  Calc's normal algebraic simplifications then
mix this in with the rest of the original formula.
X
To merge over a common denominator, we can use another simple rule:
X
@group
@smallexample
1:  (1 - sin(x)^2) / cos(x)
X    .
X
X    a r a/x + b/x := (a+b)/x RET
@end smallexample
@end group
X
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 @samp{x} is used in both of the
denominators.
X
Second, meta-variable names are independent from variables in the
target formula.  Notice that the meta-variable @samp{x} here matches
the subformula @samp{cos(x)}; Calc never confuses the two meanings of
@samp{x}.
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
@samp{a = 1}, @samp{b = -sin(x)^2}, and @samp{x = cos(x)}.
X
@c [fix-ref Algebraic Properties of Rewrite Rules]
We could just as easily have written @samp{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 @samp{+} or only to @samp{-},
we could have used the @code{plain} symbol.  @xref{Algebraic Properties
of Rewrite Rules}, for some examples of this.)
X
One more rewrite will complete the job.  We want to use the identity
@samp{sin(x)^2 + cos(x)^2 = 1}, but of course we must first rearrange
the identity in a way that matches our formula.  The obvious rule
would be @samp{@w{1 - sin(x)^2} := cos(x)^2}, but a little thought shows
that the rule @samp{sin(x)^2 := 1 - cos(x)^2} will also work.  The
latter rule has a more general pattern so it will work in many other
situations, too.
X
@group
@smallexample
1:  (1 + cos(x)^2 - 1) / cos(x)           1:  cos(x)
X    .                                         .
X
X    a r sin(x)^2 := 1 - cos(x)^2 RET          a s
@end smallexample
@end group
X
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 @kbd{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.
X
@group
@smallexample
' tan(x) := sin(x)/cos(x) RET      s t tsc RET
' a/x + b/x := (a+b)/x RET         s t merge RET
' sin(x)^2 := 1 - cos(x)^2 RET     s t sinsqr RET
X
1:  1 / cos(x) - sin(x) tan(x)     1:  cos(x)
X    .                                  .
X
X    r 1                a r tsc RET  a r merge RET  a r sinsqr RET  a s
@end smallexample
@end group
X
To edit a variable, type @kbd{s e} and the variable name, use regular
Emacs editing commands as necessary, then type @kbd{M-# M-#} or
@kbd{C-c C-c} to store the edited value back into the variable.
You can also use @w{@kbd{s e}} to create a new variable if you wish.
X
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 @kbd{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.
X
(@bullet{}) @strong{Exercise 1.}  Type @kbd{m s} to get symbolic
mode, then enter the formula @samp{@w{(2 + sqrt(2))} / @w{(1 + sqrt(2))}}.
Using a rewrite rule, simplify this formula by multiplying both
sides by the conjugate @w{@samp{1 - sqrt(2)}}.  The result will have
to be expanded by the distributive law; do this with another
rewrite.  @xref{Rewrites Answer 1, 1}. (@bullet{})
X
The @kbd{a r} command can also accept a vector of rewrite rules, or
a variable containing a vector of rules.
X
@group
@smallexample
1:  [tsc, merge, sinsqr]          1:  [tan(x) := sin(x) / cos(x), ... ]
X    .                                 .
X
X    ' [tsc,merge,sinsqr] RET          =
X
@end smallexample
@end group
@noindent
@group
@smallexample
1:  1 / cos(x) - sin(x) tan(x)    1:  cos(x)
X    .                                 .
X
X    s t trig RET  r 1                 a r trig RET  a s
@end smallexample
@end group
X
@c [fix-ref Nested Formulas with Rewrite Rules]
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.
@xref{Nested Formulas with Rewrite Rules}.)
X
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 @kbd{a r} to specify any limit.  In particular, @kbd{M-1 a r} does
only one rewrite at a time.
X
@group
@smallexample
1:  1 / cos(x) - sin(x)^2 / cos(x)    1:  (1 - sin(x)^2) / cos(x)
X    .                                     .
X
X    r 1  M-1 a r trig RET                 M-1 a r trig RET
@end smallexample
@end group
X
You can type @kbd{M-0 a r} if you want no limit at all on the number
of rewrites that occur.
X
Rewrite rules can also be @dfn{conditional}.  Simply follow the rule
with a @samp{::} symbol and the desired condition.  For example,
X
@group
@smallexample
1:  exp(2 pi i) + exp(3 pi i) + exp(4 pi i)
X    .
X
X    ' exp(2 pi i) + exp(3 pi i) + exp(4 pi i) RET
X
@end smallexample
@end group
@noindent
@group
@smallexample
1:  1 + exp(3 pi i) + 1
X    .
X
X    a r exp(k pi i) := 1 :: k % 2 = 0 RET
@end smallexample
@end group
X
@noindent
(Recall, @samp{k % 2} is the remainder from dividing @samp{k} by 2,
which will be zero only when @samp{k} is an even integer.)
X
An interesting point is that the variables @samp{pi} and @samp{i}
were matched literally rather than acting as meta-variables.
This is because they are special-constant variables.  The special
constants @samp{e}, @samp{phi}, and so on also match literally.
A common error with rewrite
rules is to write, say, @samp{f(a,b,c,d,e) := g(a+b+c+d+e)}, expecting
to match any @samp{f} with five arguments but in fact matching
only when the fifth argument is literally @samp{e}!@refill
X
@cindex Fibonacci numbers
@tindex fib
Rewrite rules provide an interesting way to define your own functions.
Suppose we want to define @samp{fib(n)} to produce the @var{n}th
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:
X
@group
@smallexample
' [fib(1) := 1, fib(2) := 1, fib(n) := fib(n-1) + fib(n-2)] RET  s t fib
X
1:  fib(7)               1:  13
X    .                        .
X
X    ' fib(7) RET             a r fib RET
@end smallexample
@end group
X
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 @samp{fib(1)}, we know the first will
be used preferentially.
X
This rule set has one dangerous bug:  Suppose we apply it to the
formula @samp{fib(x)}?  (Don't actually try this.)  The third rule
will match @samp{fib(x)} and replace it with @w{@samp{fib(x-1) + fib(x-2)}}.
Each of these will then be replaced to get @samp{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 @samp{n} is an integer greater than two.  Type
@w{@kbd{s e fib RET}}, then edit the third rule to:
X
@smallexample
fib(n) := fib(n-1) + fib(n-2) :: integer(n) :: n > 2
@end smallexample
X
@noindent
Now:
X
@group
@smallexample
1:  fib(6) + fib(x) + fib(0)      1:  8 + fib(x) + fib(0)
X    .                                 .
X
X    ' fib(6)+fib(x)+fib(0) RET        a r fib RET
@end smallexample
@end group
X
@noindent
We've created a new function, @code{fib}, and a new command,
@w{@kbd{a r fib RET}}, which means ``evaluate all @code{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 @code{EvalRules}.
X
@group
@smallexample
1:  [fib(1) := ...]    .                1:  [8, 13]
X    .                                       .
X
X    s r fib RET        s t EvalRules RET    ' [fib(6), fib(7)] RET
@end smallexample
@end group
X
It turns out that this rule set has the problem that it does far
more work than it needs to when @samp{n} is large.  Consider the
first few steps of the computation of @samp{fib(6)}:
X
@group
@smallexample
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 = ...
@end smallexample
@end group
X
@noindent
Note that @samp{fib(3)} appears three times here.  Unless Calc's
algebraic simplifier notices the multiple @samp{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 @code{s e EvalRules}
to edit the rules (or just @kbd{s E}, a shorthand command for editing
@code{EvalRules}) and add another condition:
X
@smallexample
fib(n) := fib(n-1) + fib(n-2) :: integer(n) :: n > 2 :: remember
@end smallexample
X
@noindent
If a @samp{:: 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 @code{EvalRules}.)  For
example, if the rule rewrites @samp{fib(7)} to something that evaluates
to 13, then the rule @samp{fib(7) := 13} will be added to the rule set.
X
Type @kbd{' fib(8) RET} to compute the eighth Fibonacci number, then
type @kbd{s E} again to see what has happened to the rule set.
X
With the @code{remember} feature, our rule set can now compute
@samp{fib(@var{n})} in just @var{n} steps.  In the process it builds
up a table of all Fibonacci numbers up to @var{n}.  After we have
computed the result for a particular @var{n}, we can get it back
(and the results for all smaller @var{n}) later in just one step.
X
All Calc operations will run somewhat slower whenever @code{EvalRules}
contains any rules.  You should type @kbd{s u EvalRules RET} now to
un-store the variable.
X
(@bullet{}) @strong{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 @var{n} simple steps and without recourse
to the @code{remember} option, replaces @samp{fib(@var{n}, 1, 1)} with
@samp{fib(1, @var{x}, @var{y})} where @var{x} and @var{y} are the
@var{n}th and @var{n+1}st 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 @samp{fib(@var{n})},
get back a plain number.  @xref{Rewrites Answer 2, 2}. (@bullet{})
X
There are many more things that rewrites can do.  For example, there
are @samp{&&&} and @samp{|||} pattern operators that create ``and''
and ``or'' combinations of rules.  As one really simple example, we
could combine our first two Fibonacci rules thusly:
X
@example
[fib(1 ||| 2) := 1, fib(n) := ... ]
@end example
X
@noindent
That means ``@code{fib} of something matching either 1 or 2 rewrites
to 1.''
X
You can also make meta-variables optional by enclosing them in @code{opt}.
For example, the pattern @samp{a + b x} matches @samp{2 + 3 x} but not
@samp{2 + x} or @samp{3 x} or @samp{x}.  The pattern @samp{opt(a) + opt(b) x}
matches all of these forms, filling in a default of zero for @samp{a}
and one for @samp{b}.
X
(@bullet{}) @strong{Exercise 3.}  Your friend Joe had @samp{2 + 3 x}
on the stack and tried to use the rule
@samp{opt(a) + opt(b) x := f(a, b, x)}.  What happened?
@xref{Rewrites Answer 3, 3}. (@bullet{})
X
(@bullet{}) @strong{Exercise 4.}  Starting with an integer @cite{a},
divide @cite{a} by two if it is even, otherwise compute @cite{3 a + 1}.
Now repeat this step over and over.  A famous unproved conjecture
is that for any starting @cite{a}, the sequence always eventually
reaches 1.  Given the formula @samp{seq(@var{a}, 0)}, write a set of
rules that convert this into @samp{seq(1, @var{n})} where @var{n}
is the number of steps it took the sequence to reach the value 1.
Now enhance the rules to accept @samp{seq(@var{a})} as a starting
configuration, and to stop with just the number @var{n} by itself.
Now make the result be a vector of values in the sequence, from @var{a}
to 1.  (The formula @samp{@var{x}|@var{y}} appends the vectors @var{x}
and @var{y}.)  For example, rewriting @samp{seq(6)} should yield the
vector @cite{[6, 3, 10, 5, 16, 8, 4, 2, 1]}.
@xref{Rewrites Answer 4, 4}. (@bullet{})
X
(@bullet{}) @strong{Exercise 5.}  Define, using rewrite rules, a function
@samp{nterms(@var{x})} that returns the number of terms in the sum
@var{x}, or 1 if @var{x} is not a sum.  (A @dfn{sum} for our purposes
is one or more non-sum terms separated by @samp{+} or @samp{-} signs,
so that @cite{2 - 3 (x + y) + x y} is a sum of three terms.)
@xref{Rewrites Answer 5, 5}. (@bullet{})
X
(@bullet{}) @strong{Exercise 6.}  A Taylor series for a function is an
infinite series that exactly equals the value of that function at
values of @cite{x} near zero.
X
@ifinfo
@example
cos(x) = 1 - x^2 / 2! + x^4 / 4! - x^6 / 6! + ...
@end example
@end ifinfo
@tex
\turnoffactive \let\rm\goodrm
$$ \cos x = 1 - {x^2 \over 2!} + {x^4 \over 4!} - {x^6 \over 6!} + \cdots $$
@end tex
X
The @kbd{a t} command produces a @dfn{truncated Taylor series} which
is obtained by dropping all the terms higher than, say, @cite{x^6}.
Calc represents the truncated Taylor series as a polynomial in @cite{x}.
Mathematicians often write a truncated series using a ``big-O'' notation
that records what was the lowest term that was truncated.
X
@ifinfo
@example
cos(x) = 1 - x^2 / 2! + O(x^3)
@end example
@end ifinfo
@tex
\turnoffactive \let\rm\goodrm
$$ \cos x = 1 - {x^2 \over 2!} + O(x^3) $$
@end tex
X
@noindent
The meaning of @cite{O(x^3)} is ``a quantity which is negligibly small
if @cite{x^3} is considered negligibly small as @cite{x} goes to zero.''
X
The exercise is to create rewrite rules that simplify sums and products of
power series represented as @samp{@var{polynomial} + O(@var{var}^@var{n})}.
For example, given @samp{1 - x^2 / 2 + O(x^3)} and @samp{x - x^3 / 6 + O(x^4)}
on the stack, we want to be able to type @kbd{*} and get the result
@samp{x - 2:3 x^3 + O(x^4)}.  Don't worry if the terms of the sum are
rearranged or if @kbd{a s} needs to be typed after rewriting.  (This one
is rather tricky; the solution at the end of this chapter uses 6 rewrite
rules.  Hint:  The @samp{constant(x)} condition tests whether @samp{x} is
a number.)  @xref{Rewrites Answer 6, 6}. (@bullet{})
X
@c [fix-ref Rewrite Rules]
@xref{Rewrite Rules}, for the whole story on rewrite rules.
X
@node Programming Tutorial, Answers to Exercises, Algebra Tutorial, Tutorial
@section Programming Tutorial
X
@noindent
The Calculator is written entirely in Emacs Lisp, a highly extensible
language.  If you know Lisp, you can program the Calculator to do
anything you like.  Rewrite rules also work as a powerful programming
system.  But Lisp and rewrite rules take a while to master, and often
all you want to do is define a new function or repeat a command a few
times.  Calc has features that allow you to do these things easily.
X
One very limited form of programming is defining your own functions.
Calc's @kbd{Z F} command allows you to define a function name and
key sequence to correspond to any formula.  Programming commands use
the shift-@kbd{Z} prefix; the user commands they create use the lower
case @kbd{z} prefix.
X
@group
@smallexample
1:  1 + x + x^2 / 2 + x^3 / 6         1:  1 + x + x^2 / 2 + x^3 / 6
X    .                                     .
X
X    ' 1 + x + x^2/2! + x^3/3! RET         Z F e myexp RET RET RET y
@end smallexample
@end group
X
This polynomial is a Taylor series approximation to @samp{exp(x)}.
The @kbd{Z F} command asks a number of questions.  The above answers
say that the key sequence for our function should be @kbd{z e}; the
@kbd{M-x} equivalent should be @code{calc-myexp}; the name of the
function in algebraic formulas should be also be @code{myexp}; the
default argument list @samp{(x)} is acceptable; and finally @kbd{y}
answers the question ``leave it in symbolic form for non-constant
arguments?''
X
@group
@smallexample
1:  1.3495     2:  1.3495     3:  1.3495
X    .          1:  1.34986    2:  1.34986
X                   .          1:  myexp(a + 1)
X                                  .
X
X    .3 z e         .3 E           ' a+1 RET z e
@end smallexample
@end group
X
First we call our new @code{exp} approximation with 0.3 as an
argument, and compare it with the true @code{exp} function.  Then
we note that, as requested, if we try to give @kbd{z e} an
argument that isn't a plain number, it leaves the @code{myexp}
function call in symbolic form.  If we had answered @kbd{n} to the
final question, @samp{myexp(a + 1)} would have evaluated by plugging
@samp{a + 1} in for @samp{x} in the defining formula.
X
@cindex Fresnel C(x) and S(x)
(@bullet{}) @strong{Exercise 1.}  Fresnel's function @cite{C(x)} is
defined by the integral of @samp{cos(pi t^2 / 2)} for @cite{t = 0} to
@cite{x} in radians.  (It was invented because this integral has no
solution in terms of basic functions; if you give it to Calc's @kbd{a i}
command, it will ponder it for a long time and then give up.)  We can use
the numerical integration command, however, which in algebraic notation
is written like @samp{ninteg(f(t), t, 0, x)} with any integrand
@samp{f(t)}.  Define a @kbd{z c} command and @code{fresC} function
that implements this.  You will need to edit the default argument list
a bit.  As a test, @samp{fresC(1)} should return 0.77989.  (Hint:
@code{ninteg} will run a lot faster if you reduce the precision to, say,
six digits beforehand.)  @xref{Programming Answer 1, 1}. (@bullet{})
X
(Calc doesn't have Fresnel functions built-in, but it does have the
``error function'' @samp{erf(x)}.  It turns out Fresnel's @cite{C(x)}
and @cite{S(x)} (the same integral but with @code{sin} instead of
@code{cos}) can be written in terms of @code{erf} and complex numbers
as follows:  @samp{C(x) + i S(x) = (i+1) erf(sqrt(pi) (1-i) x / 2) / 2}.
If you are curious, you could implement an alternate @kbd{z c} command
that uses this method and compare the speeds of the two approaches.)
X
The simplest way to do real ``programming'' of Emacs is to define a
@dfn{keyboard macro}.  A keyboard macro is simply a sequence of
keystrokes which Emacs has stored away and can play back on demand.
For example, if you find yourself typing @kbd{H a S x @key{RET}} often,
you may wish to program a keyboard macro to type this for you.
X
@group
@smallexample
1:  y = sqrt(x)          1:  x = y^2
X    .                        .
X
X    ' y=sqrt(x) RET       C-x ( H a S x RET C-x )
X
1:  y = cos(x)           1:  x = s1 arccos(y) + 2 pi n1
X    .                        .
X
X    ' y=cos(x) RET           X
@end smallexample
@end group
X
@noindent
When you type @kbd{C-x (}, Emacs begins recording.  But it is also
still ready to execute your keystrokes, so you're really ``training''
Emacs by walking it through the procedure once.  When you type
@w{@kbd{C-x )}}, the macro is recorded.  You can now type @kbd{X} to
re-execute the same keystrokes.
X
You can give a name to your macro by typing @kbd{Z K}.
X
@group
@smallexample
1:  .              1:  y = x^4         1:  x = s2 sqrt(s1 sqrt(y))
X                       .                   .
X
X  Z K x RET            ' y=x^4 RET         z x
@end smallexample
@end group
X
@noindent
Notice that we use shift-@kbd{Z} to define the command, and lower-case
@kbd{z} to call it up.
X
Keyboard macros can call other macros.
X
@group
@smallexample
1:  abs(x)        1:  x = s1 y                1:  2 / x    1:  x = 2 / y
X    .                 .                           .            .
X
X ' abs(x) RET   C-x ( ' y RET a = z x C-x )    ' 2/x RET       X
@end smallexample
@end group
X
(@bullet{}) @strong{Exercise 2.}  Define a keyboard macro to negate
the item in level 3 of the stack, without disturbing the rest of
the stack.  @xref{Programming Answer 2, 2}. (@bullet{})
X
(@bullet{}) @strong{Exercise 3.}  Define keyboard macros to compute
the following functions:
X
@enumerate
@item
Compute @c{$\displaystyle{\sin x \over x}$}
@cite{sin(x) / x}, where @cite{x} is the number on the
top of the stack.
X
@item
Compute the base-@cite{b} logarithm, just like the @kbd{B} key except
the arguments are taken in the opposite order.
X
@item
Produce a vector of integers from 1 to the integer on the top of
the stack.
@end enumerate
@noindent
@xref{Programming Answer 3, 3}. (@bullet{})
X
(@bullet{}) @strong{Exercise 4.}  Define a keyboard macro to compute
the average (mean) value of a list of numbers.
@xref{Programming Answer 4, 4}. (@bullet{})
X
In many programs, some of the steps must execute several times.
Calc has @dfn{looping} commands that allow this.  Loops are useful
inside keyboard macros, but actually work at any time.
X
@group
@smallexample
1:  x^6          2:  x^6        1: 360 x^2
X    .            1:  4             .
X                     .
X
X  ' x^6 RET          4         Z < a d x RET Z >
@end smallexample
@end group
X
@noindent
Here we have computed the fourth derivative of @cite{x^6} by
enclosing a derivative command in a ``repeat loop'' structure.
This structure pops a repeat count from the stack, then
executes the body of the loop that many times.
X
If you make a mistake while entering the body of the loop,
type @w{@kbd{Z C-g}} to cancel the loop command.
X
@cindex Fibonacci numbers
Here's another example:
X
@group
@smallexample
3:  1               2:  10946
2:  1               1:  17711
1:  20                  .
X    .
X
1 RET RET 20       Z < TAB C-j + Z >
@end smallexample
@end group
X
@noindent
The numbers in levels 2 and 1 should be the 21st and 22nd Fibonacci
numbers, respectively.  (To see what's going on, try a few repetitions
of the loop body by hand; @kbd{C-j}, also on the Line-Feed or @key{LFD}
key if you have one, makes a copy of the number in level 2.)
X
@cindex Golden ratio
@cindex Phi, golden ratio
A fascinating property of the Fibonacci numbers is that the @cite{n}th
Fibonacci number can be found directly by computing @c{$\phi^n / \sqrt{5}$}
@cite{phi^n / sqrt(5)}
and then rounding to the nearest integer, where @c{$\phi$ (``phi'')}
@cite{phi}, the
``golden ratio,'' is @c{$(1 + \sqrt{5}) / 2$}
@cite{(1 + sqrt(5)) / 2}.  (For convenience, this constant is available
from the @code{phi} variable, or the @kbd{I H P} command.)
X
@group
@smallexample
1:  1.61803         1:  24476.0000409    1:  10945.9999817    1:  10946
X    .                   .                    .                    .
X
X    I H P               21 ^                 5 Q /                R
@end smallexample
@end group
X
@cindex Continued fractions
(@bullet{}) @strong{Exercise 5.}  The @dfn{continued fraction}
representation of @c{$\phi$}
@cite{phi} is @c{$1 + 1/(1 + 1/(1 + 1/( \ldots )))$}
@cite{1 + 1/(1 + 1/(1 + 1/( ...@: )))}.
We can compute an approximate value by carrying this however far
and then replacing the innermost @c{$1/( \ldots )$}
@cite{1/( ...@: )} by 1.  Approximate
@c{$\phi$}
@cite{phi} using a twenty-term continued fraction.
@xref{Programming Answer 5, 5}. (@bullet{})
X
(@bullet{}) @strong{Exercise 6.}  Linear recurrences like the one for
Fibonacci numbers can be expressed in terms of matrices.  Given a
vector @w{@cite{[a, b]}} determine a matrix which, when multiplied by this
vector, produces the vector @cite{[b, c]}, where @cite{a}, @cite{b} and
@cite{c} are three successive Fibonacci numbers.  Now write a program
that, given an integer @cite{n}, computes the @cite{n}th Fibonacci number
using matrix arithmetic.  @xref{Programming Answer 6, 6}. (@bullet{})
X
@cindex Harmonic numbers
A more sophisticated kind of loop is the @dfn{for} loop.  Suppose
we wish to compute the 20th ``harmonic'' number, which is equal to
the sum of the reciprocals of the integers from 1 to 20.
X
@group
@smallexample
3:  0               1:  3.597739
2:  1                   .
1:  20
X    .
X
0 RET 1 RET 20         Z ( & + 1 Z )
@end smallexample
@end group
X
@noindent
The ``for'' loop pops two numbers, the lower and upper limits, then
repeats the body of the loop as an internal counter increases from
the lower limit to the upper one.  Just before executing the loop
body, it pushes the current loop counter.  When the loop body
finishes, it pops the ``step,'' i.e., the amount by which to
increment the loop counter.  As you can see, our loop always
uses a step of one.
X
This harmonic number function uses the stack to hold the running
total as well as for the various loop housekeeping functions.  If
you find this disorienting, you can sum in a variable instead:
X
@group
@smallexample
1:  0         2:  1                  .            1:  3.597739
X    .         1:  20                                  .
X                  .
X
X    0 t 7       1 RET 20      Z ( & s + 7 1 Z )       r 7
@end smallexample
@end group
X
@noindent
The @kbd{s +} command adds the top-of-stack into the value in a
variable (and removes that value from the stack).
X
It's worth noting that many jobs that call for a ``for'' loop can
also be done more easily by Calc's high-level operations.  Two
other ways to compute harmonic numbers are to use vector mapping
and reduction (@kbd{v x 20}, then @w{@kbd{V M &}}, then @kbd{V R +}),
or to use the summation command @kbd{a +}.  Both of these are
probably easier than using loops.  However, there are some
situations where loops really are the way to go:
X
(@bullet{}) @strong{Exercise 7.}  Use a ``for'' loop to find the first
harmonic number which is greater than 4.0.
@xref{Programming Answer 7, 7}. (@bullet{})
X
Of course, if we're going to be using variables in our programs,
we have to worry about the programs clobbering values that the
caller was keeping in those same variables.  This is easy to
fix, though:
X
@group
@smallexample
X    .        1:  0.6667       1:  0.6667     3:  0.6667
X                 .                .          2:  3.597739
X                                             1:  0.6667
X                                                 .
X
X   Z `    p 4 RET 2 RET 3 /   s 7 s s a RET    Z '  r 7 s r a RET
@end smallexample
@end group
X
@noindent
When we type @kbd{Z `} (that's a back-quote character), Calc saves
its mode settings and the contents of the ten ``quick variables''
for later reference.  When we type @kbd{Z '} (that's an apostrophe
now), Calc restores those saved values.  Thus the @kbd{p 4} and
@kbd{s 7} commands have no effect outside this sequence.  Wrapping
this around the body of a keyboard macro ensures that it doesn't
interfere with what the user of the macro was doing.  Notice that
the contents of the stack, and the values of named variables,
survive past the @kbd{Z '} command.
X
@cindex Bernoulli numbers, approximate
The @dfn{Bernoulli numbers} are a sequence with the interesting
property that all of the odd Bernoulli numbers are zero, and the
even ones, while difficult to compute, can be roughly approximated
by the formula @c{$\displaystyle{2 n! \over (2 \pi)^n}$}
@cite{2 n!@: / (2 pi)^n}.  Let's write a keyboard
macro to compute (approximate) Bernoulli numbers.  (Calc has a
command, @kbd{k b}, to compute exact Bernoulli numbers, but
this command is very slow for large @cite{n} since the higher
Bernoulli numbers are very large fractions.)
X
@group
@smallexample
1:  10               1:  0.0756823
X    .                    .
X
X    10     C-x ( RET 2 % Z [ DEL 0 Z : ' 2 $! / (2 pi)^$ RET = Z ] C-x )
@end smallexample
@end group
X
@noindent
You can read @kbd{Z [} as ``then,'' @kbd{Z :} as ``else,'' and
@kbd{Z ]} as ``end-if.''  There is no need for an explicit ``if''
command.  For the purposes of @w{@kbd{Z [}}, the condition is ``true''
if the value it pops from the stack is a nonzero number, or ``false''
if it pops zero or something that is not a number (like a formula).
Here we take our integer argument modulo 2; this will be nonzero
if we're asking for an odd Bernoulli number.
X
The actual tenth Bernoulli number is @cite{5/66}.
X
@group
@smallexample
3:  0.0756823    1:  0          1:  0.25305    1:  0          1:  1.16659
2:  5:66             .              .              .              .
1:  0.0757575
X    .
X
10 k b RET c f   M-0 DEL 11 X   DEL 12 X       DEL 13 X       DEL 14 X
@end smallexample
@end group
X
Just to exercise loops a bit more, let's compute a table of even
Bernoulli numbers.
X
@group
@smallexample
3:  []             1:  [0.10132, 0.03079, 0.02340, 0.033197, ...]
2:  2                  .
1:  30
X    .
X
X [ ] 2 RET 30          Z ( X | 2 Z )
@end smallexample
@end group
X
@noindent
The vertical-bar @kbd{|} is the vector-concatenation command.  When
we execute it, the list we are building will be in stack level 2
(initially this is an empty list), and the next Bernoulli number
will be in level 1.  The effect is to append the Bernoulli number
onto the end of the list.  (To create a table of exact fractional
Bernoulli numbers, just replace @kbd{X} with @kbd{k b} in the above
sequence of keystrokes.)
X
With loops and conditionals, you can program essentially anything
in Calc.  One other command that makes looping easier is @kbd{Z /},
which takes a condition from the stack and breaks out of the enclosing
loop if the condition is true (non-zero).  You can use this to make
``while'' and ``until'' style loops.
X
If you make a mistake when entering a keyboard macro, you can edit
it using @kbd{Z E}.  First, you must attach it to a key with @kbd{Z K}.
One technique is to enter a throwaway dummy definition for the macro,
then enter the real one in the edit command.
X
@group
@smallexample
1:  3                   1:  3           Keyboard Macro Editor.
X    .                       .           Original keys: 1 RET 2 +
X
X                                        type "1\r"
X                                        type "2"
X                                        calc-plus
X
C-x ( 1 RET 2 + C-x )    Z K h RET      Z E h
@end smallexample
@end group
X
@noindent
This shows the screen display assuming you have the @file{macedit}
keyboard macro editing package installed, which is usually the case
since a copy of @file{macedit} comes bundled with Calc.
X
A keyboard macro is stored as a pure keystroke sequence.  The
@file{macedit} package (invoked by @kbd{Z E}) scans along the
macro and tries to decode it back into human-readable steps.
If a key or keys are simply shorthand for some command with a
@kbd{M-x} name, that name is shown.  Anything that doesn't correspond
to a @kbd{M-x} command is written as a @samp{type} command.
X
Let's edit in a new definition, for computing harmonic numbers.
First, erase the three lines of the old definition.  Then, type
in the new definition (or use Emacs @kbd{M-w} and @kbd{C-y} commands
to copy it from this page of the Info file; you can skip typing
the comments that begin with @samp{#}).
X
@smallexample
calc-kbd-push         # Save local values (Z `)
type "0"              # Push a zero
calc-store-into       # Store it in variable 1
type "1"
type "1"              # Initial value for loop
calc-roll-down        # This is the TAB key; swap initial & final
calc-kbd-for          # Begin "for" loop...
calc-inv              #   Take reciprocal
calc-store-plus       #   Add to accumulator
type "1"
type "1"              #   Loop step is 1
calc-kbd-end-for      # End "for" loop
calc-recall           # Now recall final accumulated value
type "1"
calc-kbd-pop          # Restore values (Z ')
@end smallexample
X
@noindent
Press @kbd{M-# M-#} to finish editing and return to the Calculator.
X
@group
@smallexample
1:  20         1:  3.597739
X    .              .
X
X    20             z h
@end smallexample
@end group
X
If you don't know how to write a particular command in @file{macedit}
format, you can always write it as keystrokes in a @code{type} command.
There is also a @code{keys} command which interprets the rest of the
line as standard Emacs keystroke names.  In fact, @file{macedit} defines
a handy @code{read-kbd-macro} command which reads the current region
of the current buffer as a sequence of keystroke names, and defines that
sequence on the @kbd{X} (and @kbd{C-x e}) key.  Because this is so
useful, Calc puts this command on the @kbd{M-# m} key.  Try reading in
this macro in the following form:  Press @kbd{C-@@} (or @kbd{C-SPC}) at
one end of the text below, then type @kbd{M-# m} at the other.
X
@group
@example
Z ` 0 t 1
X    1 TAB
X    Z (  & s + 1  1 Z )
X    r 1
Z '
@end example
@end group
X
(@bullet{}) @strong{Exercise 8.}  A general algorithm for solving
equations numerically is @dfn{Newton's Method}.  Given the equation
@cite{f(x) = 0} for any function @cite{f}, and an initial guess
@cite{x_0} which is reasonably close to the desired solution, apply
this formula over and over:
X
@ifinfo
@example
new_x = x - f(x)/f'(x)
@end example
@end ifinfo
@tex
$$ x_{\goodrm new} = x - {f(x) \over f'(x)} $$
@end tex
X
@noindent
where @cite{f'(x)} is the derivative of @cite{f}.  The @cite{x}
values will quickly converge to a solution, i.e., eventually
@c{$x_{\rm new}$}
@cite{new_x} and @cite{x} will be equal to within the limits
of the current precision.  Write a program which takes a formula
involving the variable @cite{x}, and an initial guess @cite{x_0},
on the stack, and produces a value of @cite{x} for which the formula
is zero.  Use it to find a solution of @c{$\sin(\cos x) = 0.5$}
@cite{sin(cos(x)) = 0.5}
near @cite{x = 4.5}.  (Use angles measured in radians.)  Note that
the built-in @w{@kbd{a R}} (@code{calc-find-root}) command uses Newton's
method when it is able.  @xref{Programming Answer 8, 8}. (@bullet{})
X
@cindex Digamma function
@cindex Gamma constant, Euler's
@cindex Euler's gamma constant
(@bullet{}) @strong{Exercise 9.}  The @dfn{digamma} function @c{$\psi(z)$ (``psi'')}
@cite{psi(z)}
is defined as the derivative of @c{$\ln \Gamma(z)$}
@cite{ln(gamma(z))}.  For large
values of @cite{z}, it can be approximated by the infinite sum
X
@ifinfo
@example
psi(z) ~= ln(z) - 1/2z - sum(bern(2 n) / 2 n z^(2 n), n, 1, inf)
@end example
@end ifinfo
@tex
\let\rm\goodrm
$$ \psi(z) \approx \ln z - {1\over2z} -
X   \sum_{n=1}^\infty {\code{bern}(2 n) \over 2 n z^{2n}}
$$
@end tex
X
@noindent
where @c{$\sum$}
@cite{sum} represents the sum over @cite{n} from 1 to infinity
(or to some limit high enough to give the desired accuracy), and
the @code{bern} function produces (exact) Bernoulli numbers.
While this sum is not guaranteed to converge, in practice it is safe.
An interesting mathematical constant is Euler's gamma, which is equal
to about 0.5772.  One way to compute it is by the formula,
@c{$\gamma = -\psi(1)$}
@cite{gamma = -psi(1)}.  Unfortunately, 1 isn't a large enough argument
for the above formula to work (5 is a much safer value for @cite{z}).
Fortunately, we can compute @c{$\psi(1)$}
@cite{psi(1)} from @c{$\psi(5)$}
@cite{psi(5)} using
the recurrence @c{$\psi(z+1) = \psi(z) + {1 \over z}$}
@cite{psi(z+1) = psi(z) + 1/z}.  Your task:  Develop
a program to compute @c{$\psi(z)$}
@cite{psi(z)}; it should ``pump up'' @cite{z}
if necessary to be greater than 5, then use the above summation
formula.  Use looping commands to compute the sum.  Use your function
to compute @c{$\gamma$}
@cite{gamma} to twelve decimal places.  (Calc has a built-in command
for Euler's constant, @kbd{I P}, which you can use to check your answer.)
@xref{Programming Answer 9, 9}. (@bullet{})
X
@cindex Polynomial, list of coefficients
(@bullet{}) @strong{Exercise 10.}  Given a polynomial in @cite{x} and
a number @cite{m} on the stack, where the polynomial is of degree
@cite{m} or less (i.e., does not have any terms higher than @cite{x^m}),
write a program to convert the polynomial into a list-of-coefficients
notation.  For example, @cite{5 x^4 + (x + 1)^2} with @cite{m = 6}
should produce the list @cite{[1, 2, 1, 0, 5, 0, 0]}.  Also develop
a way to convert from this form back to the standard algebraic form.
@xref{Programming Answer 10, 10}. (@bullet{})
X
@cindex Recursion
(@bullet{}) @strong{Exercise 11.}  The @dfn{Stirling numbers of the
first kind} are defined by the recurrences,
X
@ifinfo
@example
s(n,n) = 1   for n >= 0,
s(n,0) = 0   for n > 0,
s(n+1,m) = s(n,m-1) - n s(n,m)   for n >= m >= 1.
@end example
@end ifinfo
@tex
\turnoffactive
$$ \eqalign{ s(n,n)   &= 1 \qquad \hbox{for } n \ge 0,  \cr
X             s(n,0)   &= 0 \qquad \hbox{for } n > 0, \cr
X             s(n+1,m) &= s(n,m-1) - n s(n,m) \qquad
X                          \hbox{for } n \ge m \ge 1.}
$$
(These numbers are also sometimes written $\displaystyle{n \brack m}$.)
@end tex
X
This can be implemented using a @dfn{recursive} program in Calc; the
program must invoke itself in order to calculate the two righthand
terms in the general formula.  Since it always invokes itself with
``simpler'' arguments, it's easy to see that it will always
eventually finish the computation.  Recursion is a little
difficult with Emacs keyboard macros since the macro is executed
before its definition is complete.  So here's the recommended
strategy:  Create a ``dummy macro'' and assign it to a key with,
e.g., @kbd{Z K s}.  Now enter the true definition, using the
@kbd{z s} command to call itself recursively, then assign it to
the same key with @kbd{Z K s}.  Now the @kbd{z s} command will
run the complete recursive program.  (Another way is to use @w{@kbd{Z E}}
or @kbd{M-# m} (@code{read-kbd-macro}) to read the whole macro at once,
thus avoiding the ``training'' phase.)  The task:  Write a program
that computes Stirling numbers of the first kind, given @cite{n} and
@cite{m} on the stack.  Test it with @emph{small} inputs like
@cite{s(4,2)}.  (There is a built-in command for Stirling numbers,
@kbd{k s}, which you can use to check your answers.)
@xref{Programming Answer 11, 11}. (@bullet{})
X
The programming commands we've seen in this part of the tutorial
are low-level, general-purpose operations.  Often you will find
that a higher-level function, such as vector mapping or rewrite
rules, will do the job much more easily than a detailed, step-by-step
program can.
X
(@bullet{}) @strong{Exercise 12.}  Write another program for
computing Stirling numbers of the first kind, this time using
rewrite rules.  Once again, @cite{n} and @cite{m} should be taken
from the stack.  @xref{Programming Answer 12, 12}. (@bullet{})
X
@example
X
@end example
This ends the tutorial section of the Calc manual.  Now you know enough
about Calc to use it effectively for many kinds of calculations.  But
Calc has many features that were not even touched upon in this tutorial.
@c [not-split]
The rest of this manual tells the whole story.
@c [when-split]
@c Volume II of this manual, the @dfn{Calc Reference}, tells the whole story.
X
@page
@node Answers to Exercises, , Programming Tutorial, Tutorial
@section Answers to Exercises
X
@noindent
This section includes answers to all the exercises in the Calc tutorial.
X
@menu
* RPN Answer 1::           1 RET 2 RET 3 RET 4 + * -
* RPN Answer 2::           2*4 + 7*9.5 + 5/4
* RPN Answer 3::           Operating on levels 2 and 3
* RPN Answer 4::           Joe's complex problems
* Algebraic Answer 1::     Simulating Q command
* Algebraic Answer 2::     Joe's algebraic woes
* Algebraic Answer 3::     1 / 0
* Modes Answer 1::         3#0.1 = 3#0.0222222?
* Modes Answer 2::         16#f.e8fe15
* Modes Answer 3::         Joe's rounding bug
* Modes Answer 4::         Why floating point?
* Arithmetic Answer 1::    Why the \ command?
* Arithmetic Answer 2::    Tripping up the B command
* Vector Answer 1::        Normalizing a vector
* Vector Answer 2::        Average position
* Matrix Answer 1::        Row and column sums
* Matrix Answer 2::        Symbolic system of equations
* Matrix Answer 3::        Over-determined system
* List Answer 1::          Powers of two
* List Answer 2::          Least-squares fit with matrices
* List Answer 3::          Geometric mean
* List Answer 4::          Divisor function
* List Answer 5::          Duplicate factors
* List Answer 6::          Triangular list
* List Answer 7::          Another triangular list
* List Answer 8::          Maximum of Bessel function
* List Answer 9::          Integers the hard way
* List Answer 10::         All elements equal
* List Answer 11::         Estimating pi with darts
* List Answer 12::         Estimating pi with matchsticks
* List Answer 13::         Hash codes
SHAR_EOF
true || echo 'restore of calc.texinfo failed'
fi
echo 'End of  part 34'
echo 'File calc.texinfo is continued in part 35'
echo 35 > _shar_seq_.tmp
exit 0
exit 0 # Just in case...
--
Kent Landfield                   INTERNET: [e-mail]
Sterling Software, IMD           UUCP:     uunet!sparky!kent
Phone:    [phone]         FAX:      [phone]
Please send comp.sources.misc-related mail to [e-mail].