Re: [boost] Patriot Calculation Failure (was Date/Time formal review)

From: Martin Weiser (weiser_at_[hidden])
Date: 2002-05-03 04:18:29

Note: This post is (slightly) off topic. If you're not interested in 
rounding errors or computing time differences, skip it.

On Freitag, 3. Mai 2002 02:13, Jeff Garland wrote:
> Gary Powell wrote:
> > So would the use of the boost Date/Time library have caught this
> > time/clock bug?
> >
> > > http://www.ima.umn.edu/~arnold/disasters/patriot.html
>
> Difficult to say.  Based on the information in the article, it makes me
> think the the inacurracy was created in what amounts to the 'clock
> subsystem'.  That is the low level drivers that measure time. Given a
> conversion error at this lowest level it is unclear to me if the
> problem would be resolved by use of a time library. It seems to me that
> the fundamental flaw is that the accuracy of the position projection is
> dependent on the uptime of the system.  Not good.

May be a time library might have helped - if the computation of *time 
differences* was implemented correctly in the library.

>From what I recall, the article misses the point. It concentrates on the 
representation error of 1/10 in 24-bit floating point arithmetics, 
leading to a 0.34s time offset after running 100 hours. This is true, but 
for intercepting a missile, the absolute time is not at all relevant, but 
(comparatively small) time differences are. However, the absolute offset 
of 0.34s cancels out in this difference, leading to a relative error of 
about 2e-24, which is pretty precise.

As far as I know the real problem was that time differences were computed 
in the following way (pseudocode):

float t0 = clockticks();
wait_for_event();
float t1 = clocktics();
float delta_t = t1-t0;

Looks sensible, but large integral numbers (e.g. clockticks() after 100h) 
cannot be represented exactly in floating point arithmetics. The lowest 
significant bits are simply chopped off. The error introduced is really 
small. But in the difference t1-t0, the leading digits cancel out (they 
are almost the same), and the lower bits are shifted forward. Of course, 
the error is shifted, too, such that the relative error increases 
dramatically. An example in 3-digit decimal mantissa floating point 
arithmetics:

t0 = 12426; // t0 = 1.24e4
// wait  80 clock ticks
t1 = 12506; // t1 = 1.25e4;
delta_t = 1.25e4 -1.24e4 = 1.00e2 // oops, correct value is 8.00e1
// 20% error from 0.1% rounding error in t0,t1 assignments.

The lesson to be learned for implementing time/date libraries: Be careful 
when computing small time differences in floating point arithmetics.

> Perhaps the most amazing thing here, is that apparently this somehow
> wasn't tested.  Although, as I recall the Patriots were initially built
> to shoot down planes, which fly slower than SCUDS, and they had to be
> 'rapidly adapted' for the SCUD mission.  So even though this article
> doesn't mention this, it makes you wonder if there weren't other
> factors involved as well.

Well, finding an error that occurs only when the device is running for at 
least 100h is difficult. Of course, dangerous devices should be tested 
well...

AFAIK the Patriots were not designed for shooting down planes. They work 
in the following way: Scanning for any flying objects. If one is found, 
the system immediately tries to find it again somewhere near by. If it is 
found again, a ballistic flight path is computed from the two 
measurements. On this flight path, two points later in time are computed, 
a verification point and an interception point. If the object appears at 
the verification point at the predicted time, it is almost sure that the 
object is a ballistic missile, and the interception device is immediately 
shot off towards the interception point.

Of course this concept is designed for fast missiles, and relies heavily 
on the ballistic flight path. For shooting planes, you'd have to design a 
completely different scheme. Whether such a scheme has ever been 
implemented for Patriots, I don't know.

For you to be able to judge my comments I must say I'm no military expert 
(nor do I ever intend to become), but a numerical analyst. My knowledge 
stems from reading several articles about the numerical problems leading 
to the Dharan desaster.

Martin

-- 
Dr. Martin Weiser            Zuse Institute Berlin
weiser_at_[hidden]                Scientific Computing
http://www.zib.de/weiser     Numerical Analysis and Modelling