COMPUTING SCIENCE

# A Lucid Interval

Give a digital computer a problem in arithmetic, and it will grind away methodically, tirelessly, at gigahertz speed, until ultimately it produces the wrong answer. The cause of this sorry situation is not that software is full of bugs—although that is very likely true as well—nor is it that hardware is unreliable. The problem is simply that computers are discrete and finite machines, and they cannot cope with some of the continuous and infinite aspects of mathematics. Even an innocent-looking number like 1/10 can cause no end of trouble: In most cases, the computer cannot even read it in or print it out exactly, much less perform exact calculations with it.

Errors caused by these limitations of digital machines are usually small and inconsequential, but sometimes every bit counts. On February 25, 1991, a Patriot missile battery assigned to protect a military installation at Dahrahn, Saudi Arabia, failed to intercept a Scud missile, and the malfunction was blamed on an error in computer arithmetic. The Patriot's control system kept track of time by counting tenths of a second; to convert the count into full seconds, the computer multiplied by 1/10. Mathematically, the procedure is unassailable, but computationally it was disastrous. Because the decimal fraction 1/10 has no exact finite representation in binary notation, the computer had to approximate. Apparently, the conversion constant stored in the program was the 24-bit binary fraction 0.00011001100110011001100, which is too small by a factor of about one ten-millionth. The discrepancy sounds tiny, but over four days it built up to about a third of a second. In combination with other peculiarities of the control software, the inaccuracy caused a miscalculation of almost 700 meters in the predicted position of the incoming missile. Twenty-eight soldiers died.

Of course it is not to be taken for granted that better arithmetic would have saved those 28 lives. (Many other Patriots failed for unrelated reasons; some analysts doubt whether *any* Scuds were stopped by Patriots.) And surely the underlying problem was not the slight drift in the clock but a design vulnerable to such minor timing glitches. Nevertheless, the error in computer multiplication is mildly disconcerting. We would like to believe that the mathematical machines that control so much of our lives could at least do elementary arithmetic correctly.

One approach to dealing with such numerical errors is a technique called interval arithmetic. It does nothing directly to improve the accuracy of calculations, but for every number it provides a certificate of accuracy—or the lack of it. The result of an ordinary (non-interval) computation is a single number, a point on the real number line, which lies at some unknown distance from the true answer. An interval computation yields a pair of numbers, an upper and a lower bound, which are guaranteed to enclose the exact answer. Maybe you still don't know the truth, but at least you know how much you don't know.

**IN THIS SECTION**

EMAIL TO A FRIEND :

**Of Possible Interest**

**Technologue**: The Quest for Randomness

**Feature Article**: Simulating Star Formation on a Galactic Scale

**Feature Article**: Digital Forensics