2
$\begingroup$

In Writing Scientific Software: A Guide to Good Style, several disasters are mentioned including a missle defence system which led to deaths at a US base in Saudi Arabia in 1991.

The error was caused due to catastrophic cancellation in tracking the incoming Scud missile's velocity, in order to fire a missile before it hit the base:

$$\frac{x_{i+1}-x_i}{t_{i+1}-t_i}.$$

It is clear that for large times, and a small difference, this can lead to poor estimates because of catastrophic cancellation. When this was noticed in their C program, it was apparently fixed but how could this be done? Excluding solutions with third party libraries, e.g. GMP.

$\endgroup$
1
  • 1
    $\begingroup$ Well, with things like GMP (either by using GMP, or by rewriting similar algorithms within the software they used). But my recollection is that it wasn't that they had cancellation in a fraction like this, but that they just lost accuracy accumulating numbers over and over and over for too long a time. The problem was solved by just resetting the computer periodically and starting from a clean slate. $\endgroup$ Dec 9, 2017 at 17:31

2 Answers 2

4
$\begingroup$

The problem with the Patriot missile system was that time was stored in tenths of seconds as an integer. Before calculations (time difference between a radar pulse sent and detected back again), this integer was converted in a 24-bit floating point number. This proved too low in precision: after 100 hours of operation, the actual time was 360,000 seconds, the value in the floating point variable was 359,999.6567 seconds. This seems small, but with a velocity of such a SCUD missile (approx. 1676 m/s), this time off-set corresponded to a distance off-set of approximately 687 meters.

Using more bits in the floating point representation (classical double precision being 64 bits) would have solved the problem. No need to go to more advanced fixed precision libraries.

For completeness, this resulted in 28 casualties.

$\endgroup$
1
  • $\begingroup$ I have added an answer explaining why the error associated with the absolute time is irrelevant. $\endgroup$ Dec 10, 2017 at 11:29
4
$\begingroup$

The answer given by @GertVdE contains some of the information given in the official report from US General Accouting Office GAO IMTEC-92-26

However, that report is incomplete!

When tracking an incoming missile the absolute time is irrelevant, rather it is the elapsed time between two radar pulses which is essential.

The Patriot system's internal clock tick was 0.1 seconds. It counted time using integers. A function call converted the integer into a real time through multiplication with a binary approximation of 0.1 seconds.

The original function used a 24 bit approximation of 0.1 seconds. A upgrade, designed to cope with faster missiles, used a 48 bit approximation. Unfortunately, at least one call to the old function was not replaced with a call to the new function!

Therefore, time increments where computed by subtracting a highly accurate absolute time from a less accurate absolute time. Had the software patch not been applied, then the errors would have cancelled and the missile would have fired.

I have not been able to find an official report confirming this. The best I can do is cite SIAM News July 1992, Volume 25, Number 4, page 11

Since the author, Robert Skeel, later served on my thesis committee at Purdue, I am inclined to accept it :)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.