Alyssa P. Hacker is designing a system to help people solve engineering problems. One feature she wants to provide in her system is the ability to manipulate inexact quantities (such as measured parameters of physical devices) with known precision, so that when computations are done with such approximate quantities the results will be numbers of known precision.

Electrical engineers will be using Alyssa's system to compute
electrical quantities. It is sometimes necessary for them to compute
the value of a parallel equivalent resistance *R*_{p} of two
resistors *R*_{1} and *R*_{2} using the formula

Resistance values are usually known only up to some tolerance guaranteed by the manufacturer of the resistor. For example, if you buy a resistor labeled ``6.8 ohms with 10% tolerance'' you can only be sure that the resistor has a resistance between 6.8-0.68=6.12 and 6.8+0.68=7.48 ohms. Thus, if you have a 6.8-ohm 10% resistor in parallel with a 4.7-ohm 5% resistor, the resistance of the combination can range from about 2.58 ohms (if the two resistors are at the lower bounds) to about 2.97 ohms (if the two resistors are at the upper bounds).

Alyssa's idea is to implement ``interval arithmetic'' as a set of arithmetic operations for combining ``intervals'' (objects that represent the range of possible values of an inexact quantity). The result of adding, subtracting, multiplying, or dividing two intervals is itself an interval, representing the range of the result.

Alyssa postulates the existence of an abstract object called an
``interval'' that has two endpoints: a lower bound and an upper bound.
She also presumes that, given the endpoints of an interval, she can
construct the interval using the data constructor
`make-interval`.
Alyssa first writes a procedure for adding two intervals. She
reasons that the minimum value the sum could be is the sum of the two
lower bounds and the maximum value it could be is the sum of the two
upper bounds:

(define (add-interval x y) (make-interval (+ (lower-bound x) (lower-bound y)) (+ (upper-bound x) (upper-bound y))))Alyssa also works out the product of two intervals by finding the minimum and the maximum of the products of the bounds and using them as the bounds of the resulting interval. (

(define (mul-interval x y) (let ((p1 (* (lower-bound x) (lower-bound y))) (p2 (* (lower-bound x) (upper-bound y))) (p3 (* (upper-bound x) (lower-bound y))) (p4 (* (upper-bound x) (upper-bound y)))) (make-interval (min p1 p2 p3 p4) (max p1 p2 p3 p4))))To divide two intervals, Alyssa multiplies the first by the reciprocal of the second. Note that the bounds of the reciprocal interval are the reciprocal of the upper bound and the reciprocal of the lower bound, in that order.

(define (div-interval x y) (mul-interval x (make-interval (/ 1.0 (upper-bound y)) (/ 1.0 (lower-bound y)))))

**Exercise.**
Alyssa's program is incomplete because she has not specified the
implementation of the interval abstraction. Here is a definition of
the interval constructor:

(define (make-interval a b) (cons a b))Define selectors

**Exercise.**
Using reasoning analogous to Alyssa's, describe how the difference
of two intervals may be computed. Define a corresponding subtraction
procedure, called
`sub-interval`.

**Exercise.**
The *width* of an interval is half of the difference between its
upper and lower bounds. The width is a measure of the uncertainty of
the number specified by the interval. For some arithmetic operations
the width of the result of combining two intervals is a function only
of the widths of the argument intervals, whereas for others the width
of the combination is not a function of the widths of the argument
intervals. Show that the width of the sum (or difference) of two
intervals is a function only of the widths of the intervals being
added (or subtracted). Give examples to show that this is not true
for multiplication or division.

**Exercise.**
Ben Bitdiddle, an expert systems programmer, looks over Alyssa's
shoulder and comments that it is not clear what it means to
divide by an interval that spans zero. Modify Alyssa's code to
check for this condition and to signal an error if it occurs.

**Exercise.**
In passing, Ben also cryptically comments: ``By testing the signs of
the endpoints of the intervals, it is possible to break `
mul-interval` into nine cases, only one of which requires more than
two multiplications.'' Rewrite this procedure using Ben's
suggestion.

After debugging her program, Alyssa shows it to a potential user, who complains that her program solves the wrong problem. He wants a program that can deal with numbers represented as a center value and an additive tolerance; for example, he wants to work with intervals such as rather than [3.35, 3.65]. Alyssa returns to her desk and fixes this problem by supplying an alternate constructor and alternate selectors:

(define (make-center-width c w) (make-interval (- c w) (+ c w))) (define (center i) (/ (+ (lower-bound i) (upper-bound i)) 2)) (define (width i) (/ (- (upper-bound i) (lower-bound i)) 2))

Unfortunately, most of Alyssa's users are engineers. Real engineering situations usually involve measurements with only a small uncertainty, measured as the ratio of the width of the interval to the midpoint of the interval. Engineers usually specify percentage tolerances on the parameters of devices, as in the resistor specifications given earlier.

**Exercise.**
Define a constructor
`make-center-percent` that takes a center and
a percentage tolerance and produces the desired interval. You must
also define a selector `percent` that produces the
percentage tolerance for a given interval. The `center` selector
is the same as the one shown above.

**Exercise.**
Show that under the assumption of small percentage tolerances there is
a simple formula for the approximate percentage tolerance of the
product of two intervals in terms of the tolerances of the factors.
You may simplify the problem by assuming that all numbers are
positive.

After considerable work, Alyssa P. Hacker delivers her finished
system. Several years later, after she has forgotten all about it, she
gets a frenzied call from an irate user, Lem E. Tweakit.
It seems that Lem has
noticed that the formula for parallel resistors can be written in two
algebraically equivalent ways:

and

He has written the following two programs, each of which computes the parallel-resistors formula differently:

(define (par1 r1 r2) (div-interval (mul-interval r1 r2) (add-interval r1 r2))) (define (par2 r1 r2) (let ((one (make-interval 1 1))) (div-interval one (add-interval (div-interval one r1) (div-interval one r2)))))Lem complains that Alyssa's program gives different answers for the two ways of computing. This is a serious complaint.

**Exercise.**
Demonstrate that Lem is right. Investigate the behavior of the
system on a variety of arithmetic expressions. Make some intervals *A* and *B*,
and use them in computing the expressions *A*/*A* and *A*/*B*. You will
get the most insight by using intervals whose width is a small
percentage of the center value. Examine the results of the computation
in center-percent form (see exercise ).

**Exercise.**
Eva Lu Ator, another user, has also noticed the different intervals
computed by different but algebraically equivalent expressions. She
says that a formula to compute with intervals using Alyssa's system
will produce tighter error bounds if it can be written in such a form
that no variable that represents an uncertain number is repeated.
Thus, she says, `par2` is a ``better'' program for parallel
resistances than `par1`. Is she right? Why?

**Exercise.**
Explain, in general, why equivalent algebraic expressions may lead to
different answers. Can you devise an interval-arithmetic package that
does not have this shortcoming, or is this task impossible? (Warning:
This problem is very difficult.)