MY AMERICAN SCIENTIST
LOG IN! REGISTER!
SEARCH
 
RSS
Logo IMG
HOME > PAST ISSUE > Article Detail

COMPUTING SCIENCE

A Lucid Interval

Brian Hayes

Measuring Ignorance

Suppose you are surveying a rectangular field. No matter how carefully you read the measuring tape, you can never be certain of the exact dimensions, but you can probably state with confidence that the correct figures lie within certain bounds. Perhaps you are sure the length is no less than 68 meters and no more than 72, while the width is between 49 and 51 meters. Then you can state with equal confidence that the area of the field lies somewhere between 3,332 square meters and 3,672 square meters. This is interval arithmetic in action: [68,72] x [49,51] = [3,332, 3,672]. (The bracketed pair [a,b] signifies the interval from a to b inclusive, with . Another useful notation is [], where the underscore indicates a lower limit and the overscore an upper limit.)

Doing basic arithmetic with intervals is not much more difficult than with ordinary ("pointlike") numbers. Indeed, a single formula extends the definition of the four standard arithmetic operations to intervals. If ° represents any of the operations +, –, x or ÷, then the corresponding interval operation is defined as:

Click to Enlarge Image

In other words, compute the four possible combinations of the upper and lower bounds, then choose whichever of these results is the smallest as the new lower bound, and likewise take the largest as the new upper bound. Every possible combination u°v must lie within these limits.

The min-max formula is a convenient definition of interval operations, but it is not always the best implementation. For example, in the case of addition it's obvious that + will always be the smallest sum, and + the largest, so that interval addition is simply [,] + [,] = [ + , + ]. By similar reasoning, subtraction is just [,]–[,] = [,]. Multiplication is not quite as well-behaved. Although shortcuts are sometimes possible (depending on the signs of the operands), in the worst case there is no choice but to compute all four of the combinations and select the extrema.

Division is much like multiplication, but with a further annoyance—the possibility of a zero divisor. With pointlike numbers, if you try to carry out an operation such as 2 ÷ 0, the error is obvious, and the system software will prevent you from doing the impossible. An interval division such as [2,4] ÷ [–1,1] has the same problem, but in disguise. You could very well perform the necessary calculations on the end points of the intervals without raising any alarms and without noticing that the divisor interval includes the value zero. But the answer you would arrive at in this way, [–4,4], is utterly wrong. It's not just wrong in the formal sense that it might be tainted by an illegal operation. It's also wrong because the interval [–4,4] does not enclose all possible quotients, even if the zero point itself is excluded from the divisor. A reliable system for interval arithmetic needs protection against this hazard. Usually, division by an interval that includes zero is simply forbidden, although there are also other ways of coping with the problem.

Figure 1. Computer numbering systemsClick to Enlarge Image

Apart from the rules for manipulating intervals arithmetically, there remains the question of what an interval really is and how we ought to think about it. In the context of dealing with errors and uncertainties of computation, we may see [,] as standing for some definite but unknown value x such that x . But [, ] could also be interpreted as the set of all real numbers between and —in other words, as a closed segment of the real number line. Or the interval [,] could be taken as denoting a new kind of number, in much the same way that two real numbers x and y combine to specify the complex number x+iy (where i represents the square root of –1). This last view is the most ambitious. It suggests the goal of a computing system where intervals are just another data type, interchangeable with other kinds of numbers. Wherever a pointlike number can appear in a program, an interval can be substituted. Conversely, exact pointlike numbers can be represented by "degenerate" intervals of zero width; the number 2 could be written [2,2].





» Post Comment

 

EMAIL TO A FRIEND :

Of Possible Interest

Feature Article: Simulating Star Formation on a Galactic Scale

Feature Article: Digital Forensics

Computing Science: First Links in the Markov Chain

Subscribe to American Scientist