Re: On Arnold's challenge & Paul's Observation...
> Subject: RE: On Arnold's challenge & Paul's Observation...
> Date: Fri, 28 Nov 2008 09:34:24 -0700
> From: "Kreinovich, Vladik" <vladik@xxxxxxxx>
> To: "Dan Zuras Intervals" <intervals08@xxxxxxxxxxxxxx>,
> <stds-1788@xxxxxxxxxxxxxxxxx>
>
> Dear Dan, Many thanks for the clarification.=20
You're quite welcome.
>
> This raises a methodological question: where do we stop?=20
IMHO, at the point the transformation changes the value
of the expression. To do so would not only go against
the programmer's wishes it would mean the result varies
from compiler to compiler or from one optimization level
to the next.
This is just the sort of thing we want to avoid if the
world is to believe in the validity of intervals as a
method.
>
> For example, as everyone know from numerical math, computing a+b+c also
> depends on the order of the operations; some languages like C compute
> left to right, Fortran if I remember correctly computes right to left,
> and compilers change the order -- shall we prohibit this too?=20
There are many such examples. As you say, most people
know that addition is non-associative. Multiplication
is also non-associative but the problem is generally
much less severe.
But, let's use your example & see how it applies to
intervals.
As you say, in floating-point, an expression like
(-10^20 + 10^20) + 3.141592
is much more accurate (or, at least, different) than
-10^20 + (10^20 + 3.141592)
Thus in 754 we have had to ask of languages that they
maintain a consistent (and knowable) policy WRT left
or right association if they want to call their programs
reproducible. This can be found in clauses 10 & 11 of
the 2008 document.
But the world of intervals is a bit different.
Suppose we have:
x = [ -10^20,-2*10^20]
y = [ 10^20, 2*10^20]
z = [3.14159, 3.14160]
r = x + y + z
So, if I've done this correctly in my head, evaluated
left to right r = [-10^20,10^20+ULP] but right to left
r = [-10^20,10^20+ULP]. How about that?!?!
This doesn't mean that addition becomes magically
associative under intervals its just that the actual
answer (something near pi) is hidden in the very large
interval of the result. It is possible to construct
interval cases where the width of the interval will
depend strongly on the order of operations. (I leave
it as a problem for the reader to come up with some
good examples.)
But let's change the problem just a bit & see what
happens. Suppose, with x, y, & z, as above, we want
to evaluate r = -y + y + z. Under an evaluation rule
for interval expressions that has been proposed (namely,
to instantiate each interval exactly once) we would get
r = (-y + y) + z = [3.14159, 3.14160] but
r = -y + (y + z) = [0, ULP*10^20]
(Again, subject to the errors in my head.)
Both are correct. Both are better intervals than a
naive interpretation would return. And both depend
on the order of evaluation.
Therefore, I believe we are left with no choice but to
ask of the language committees to specify exactly how
expressions are evaluated in a manner that is obvious
to the programmer & disallow any transformation that
would change the result that has been written down.
>
> In my opinion, there is a big difference between transformations like
> (x+y)(x-y)=3Dx^2-y^2 which may change interval estimates and changes =
> like
> (x^2 - y^2)/x^2 with 1 - (y/x)^2
> Which of course depend on overflows etc. but only make interval
> estimations, in general, narrower.=20
The motivation for such a transformation (whether
stated or not) is the assumption that x is the
dominant term in the expression. Suppose it is y.
Now suppose it is the reciprocal expression we seek.
That is:
x^2/(x^2 - y^2) versus 1/(1 - (y/x)^2)
As y gets large both expressions nicely get small.
But as y is now dominant we must consider the
possibility that x is an interval containing zero.
In that case the former expression works out just
fine but the latter is in danger of having a divide
by zero.
Now, given that we are in the interval world here,
I'm not sure this makes much difference WRT the size
of the resulting interval but it makes a world of
difference WRT the errors the compiler must deal with.
Either way, the principle should be that we should
not second guess the programmer & 'help' in an
unnecessary or perhaps dangerous manner.
>
> Probably we should distinguish between the two situations:
>
> * first in an user-application situations in which a user (which is not
> a professional specialist in interval computations) describes an
> expression like (x^2 - y^2)/x^2 because this is exactly the formula that
> relates the desired quantity with the variables x and y; in this case,
> what the user wants is a valid interval enclosure for this particular
> expression; in this case, in my opinion, we should allow compilers to
> make transformations to 1 - (y/x)^2 because this helps the computer (in
> many cases except for overflow-underflow situations) to get narrower
> interval estimates
>
> * I agree with you there are other situations when the program is
> written by a professional in interval computations, in this case, the
> given expression has been designed by a programmer explicitly to take
> into account overflows or underflows etc.; in this case, we should
> indicate to the compiler that this particular operation should be
> performed exactly as written, and switch off any optimization features.
You say 'we should distinguish between' the naive
programmer & the experienced professional.
But I claim you cannot look at the programmer's source
code & make such a judgement.
Since we have no evidence on which to make such a
judgement, I believe the only thing we are permitted
to do is assume the programmer has reasons for casting
the problem in the way given & that we are obliged to
return what was asked for.
>
> Probably the same thing is needed for a+b+c: sometimes it is just the
> sum, and it does not matter whether we start with a+b or with b+c, and
> sometimes, the user on purpose described the order in exactly this way.
>
> Such an ability to switch compiler off and on for different expression
> may be useful.=20
>
Now this last is something I agree with: We should
always provide the programmer with the option of
allowing value changing optimizations to be performed
on the code SO LONG AS THE PROGRAMMER EXPLICITLY ASKS
FOR IT.
That way the programmer is again assumed to know what
is being asked for & we are providing just that.
Let me put this whole question in the form of a gedanken
experiment that came up from time to time when we were
discussing this issue in 754.
Suppose that the Ariane-6 rocket is designed with control
software using intervals to assure that it does not go
off course. Suppose further that the first launch DOES
go wildly off course & the range officer is forced to
destroy it. Now suppose that in the post-accident
investigation it is discovered that the control software
asked the rocket steering vanes to assume an impossible
position which was the cause of the accident. (If you
think it can't happen, it did on the Ariane-5.)
Now, we are in court. The company that made the $300M
communications satellite that was blown up along with
the rocket is trying to sue everyone in sight.
(1) They go after the Eurpoean Space Agency. The ESA
claims its not their fault. They asked for control
software that met certain specifications & the software
subcontractor failed to provide them.
(2) They go after the software subcontractor. They
claim its not their fault. They hired a contract
programmer to write the code & he failed to provide the
specified program.
(3) They go after the programmer. The programmer claims
its not his fault. Just such a case was in his test
suite & the program passed with an adequately small
interval. But the compiler was different in the actual
build for the rocket (or the optimization level was
different, it doesn't matter) and the final version
(that was out of the programmer's control) returned an
inteval wide enough to drive the rocket out of control.
(4) They go after the company that wrote the compiler
& the compiler writers within that company. They claim
its not their fault. They followed the guidelines set
out by IEEE-1788 which permitted such variation in the
evaluation of interval expressions.
(5) They go after the IEEE, the IEEE-SA, and the members
of IEEE-1788. US!! And we have no one to blame because
it was our decision that allowed the variation in the
first place.
Now, to a certain extent, this should not happen. The
IEEE is supposed to indemnify us against such lawsuits
on grounds that we are volunteer experts in our field.
But such indemnification never prevented anyone from
being named in a lawsuit & having to hire an expensive
lawyer to defend them in court.
Still when disasters happen, and they WILL happen, it
should be clear to everyone involved that the chain of
blame stops with the programmer.
Compilers that do EXACTLY what the programmer asks for
should not be blamed for being asked to do something
dangerous. (Expecially if they issue non-binding
warnings that something is or could be dangerous & why.)
And the standard we write should BE standard. That is,
if everyone returns EXACTLY the same answer there can
be no question beyond the skill of the programmer.
Finally, if we take great care & write an excellent
standard, the rocket will not blow up. And, as Prof
Kahan once enlightened me: Our reward will be that no
one will ever notice.
Dan
P.S. - As I finish this I realize that I've gone on a
rant. I apologise & will try to be more terse in the
future.