Boost logo

Boost :

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

Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk