Re: On Arnold's challenge & Paul's Observation... - reordering
"Kreinovich, Vladik" <vladik@xxxxxxxx>
wrote on 28/11/2008 11:34:24 AM:
> ...
> 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 ...
No, the C and Fortran standards both say the order
of a+b+c is unspecified.
It may be evaluated as (a+b)+c or (b+c)+a or (a+c)+b.
If you want a
specific order you must parenthesize. You can
also control order by
splitting the expession into separate statements,
and in C you can use
the "," operator to force a "sequence
point"; eg, instead of a+b+c
you could write aplusb=a+b, aplusb+c. Some compilers
have optimization
options to ignore the parentheses, but must have a
mode that obeys them.
(If you want quotes from or references to the standards,
let me know
which language and which version of the standard.)
> In my opinion, there is a big difference between transformations like
> (x+y)(x-y)=x^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.
> . . .
> * 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.
The IEEE 754 standard allows optimizations but requires
a mode in which the
results must be identical to doing all operations
one at a time, exactly
the way the program says. I think 1788 needs
a similar requirement. For
interval arithmetic it probably makes sense for compilers
to support three
modes: exact / allow narrower bounds / allow
both narrower and slightly
wider bounds.
In C, C++ and Fortran you can control it via parentheses.
C 99 also has a
pragma that specifies in which part of the program
a compiler is or is not
allowed to combine operations (eg, whether a*b+c must
be evaluated as a
rounded multiply then an add, or as a fused multiply
and add with no
rounding between them. The wording applies to
all kinds of operations
for all types.
One problem is that parentheses have multiple meanings,
including grouping
needed to describe what to calculate and grouping
to control what order it
must be done in. That's one reason for pragmas
and compiler options.
> 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.
Yes.
>
> -----Original Message-----
> From: ben@xxxxxxxxx [mailto:ben@xxxxxxxxx] On Behalf Of Dan Zuras
> Intervals
>
> >> Can you clarify this example? We are replacing an _expression_
with an
> > equal Single-Use _expression_ -- for which (modulo rounding errors)
> > straightforward interval computations produce the exact range,
what is
> > wrong with this transformation?
>
> >>> Then, those things in point (3), say replacing
an _expression_
> >>> like (x^2 - y^2)/x^2 with 1 - (y/x)^2, should
also be listed
> >>> but, as they are value changing, reserved to the
programmer
> >>> to use or not, as the problem warrents.
>
> Suppose the programmer knows that |y| < |x|. Then
if
> x^2 overflows, (x^2 - y^2)/x^2 would be oo/oo but
> 1 - (y/x)^2 would just get the right answer. If
x^2
> underflows, (x^2 - y^2)/x^2 would be 0/0 but 1 - (y/x)^2
> would still get the right answer. In other cases,
one
> _expression_ might be inexact while the other is exact.
>
> There are other algebraically equivalent expressions,
> (x + y)*(x - y)/x^2 or ((x + y)/x)*((x - y)/x) that
> have their own advantages & problems but this is
not
> the point.
When processing a program literally/exactly/strictly
(ie, exactly as it is
written) a compiler must not replace an _expression_
with an algebraically
equivalent one unless it will give exactly the same
answer in all cases OR
the language says the order is unspecified or the
_expression_ is ambiguous.
So when using IEEE 754 floating point, x*0 can't be
simplified to just 0
because infinity*0 is NaN not 0. (a+b)+c can't
be reordered, but a+b+c
can be (although in that mode most compilers wouldn't).
When given permission not just to optimize but also
to simplify and reorder
in fast/inexact/non-strict mode, then the compiler
can.
- Ian McIntosh
Toronto IBM Lab 8200 Warden D2-445 905-413-3411