A ** heuristic** is a technique that works * sometimes*, without
guarantees. We all use heuristics, because they are often simple to
try (so they don't cost much if they fail), and also because they are
often all we have.

An ** algorithm** is a technique that comes with a guarantee. The
technique for rational function integration is an algorithm because it
always produces the answer, without exception. Differentiation is an
algorithm---given an elementary function, you can always find its derivative.
The Euclidean algorithm always gives you the GCD. Algorithms can be fast
or slow, but the important thing is the guarantee. In some sense, an
algorithm is a `predictable heuristic'---you can't tell if a heuristic
will work, before you try it, but you know in advance what the output of
an algorithm will be.

In the case of the Risch algorithm, the output will be either an elementary
antiderivative, or a proof that the antiderivative is not elementary.
Before we begin this, however, we look at a simpler technique that uses some
of the same ideas.

Thu Nov 23 10:59:42 PST 1995