next up previous
Next: The Method of Up: Today's Notes Previous: Remarks on Last

Heuristics Versus Algorithms

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.

Rob Corless
Thu Nov 23 10:59:42 PST 1995