Fixing catastrophic cancellation in velocity formula

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.

• 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. – Wolfgang Bangerth Dec 9 '17 at 17:31

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.

• I have added an answer explaining why the error associated with the absolute time is irrelevant. – Carl Christian Dec 10 '17 at 11:29

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 :)