Skip to main content
PRL Project

next up previous
Next: Sparse Matrices Up: The Code Creation Previous: The Code Creation

Quadratic Formula


As a simple example of the transformational approach, consider writing a program to solve the quadratic equation, . Mathematically, it is most natural to write the solutions as:


From this mathematical specification, we can produce two different types of solvers: numerical solvers where the coefficients of the polynomial are expressed as floating point numbers and semi-numerical solvers for use when b and c are expressed exactly or in terms of symbolic expressions.

In the first case, we know that direct use of (1) is unacceptable for three reasons. First, the computation of can overflow even when the value of and can be expressed as floating point numbers. To deal with this (1) should be coded as:

Second, if is small then the subtraction case above will involve subtracting two nearly equal quantities. Thus, a better way to compute these two roots is

If the computer's arithmetic does not deal with underflow gracefully then an additional modification may be needed. Third, if is negative, then the square root will return a complex number which must be dealt with properly.

For each of the problems that arose, a suitable transformation could be defined to convert the original formula into one that does not have the indicated problem. Furthermore, these transforms could be reused to deal with numeric errors that arise in other calculations. These transformation, however, cannot be easily encoded in a subroutine library.

In the exact case, the formula (1) is satisfactory, however the square root must be dealt with carefully to avoid running afoul of branch cut problems.

From the perspective of creating a comprehensive problem solving environment, the transition from the numeric solvers to semi-numeric solvers needs to be seamless, since, for instance, the mathematician rarely feels that introducing into a computation a small (symbolic) increases the difficulty significantly. By encouraging the development of mathematical programs via program transformations and by providing a library of transforms, like those discussed above, we expect to ameliorate the problem.

next up previous
Next: Sparse Matrices Up: The Code Creation Previous: The Code Creation

nuprl project
Tue Nov 21 08:50:14 EST 1995