Re: value-preserving transformations
I'm quoting several related threads.
Thread 1:
Christian Keil <c.keil@xxxxxxxxxxxxx> wrote
on 20/11/2008 09:27:42 PM:
CK > I think we should be very cautious with such transformations. Currently
CK > writing an interval library or some rigorous algorithm is quite
CK > difficult because of compilers being too smart. Finding out what
really
CK > happens often involves going to assembler level and finally decorating
CK > the code with "volatile"s (telling a C/C++ compiler to
not assume
CK > anything about the variable, thereby precluding all optimizations
CK > involving it) and searching for expressions that the (current version
of
CK > the) compiler does not optimize away.
CK > In my opinion, one of the worst things that can happen to an IA
CK > implementation is that a "correct" program produces invalid
enclosures
CK > because of transformations done by the compiler.
CK > The question of independence is of course very important here.
[-2,3] *
CK > [-2,3] should not be optimized to [-2,3]**2 unless there is a clear
CK > dependence. Maybe this can be done at the level of variables.
CK >
CK > Cheers,
CK > Christian
CK >
CK > Michel Hack wrote:
CK > MH > Interval arithmetic presents some unique challenges compared
to
CK > CK > plain floating-point arithmetic in this regard.
CK > CK >
CK > CK > On (Thu, 20 Nov 2008 11:43:47 +0100) Arnold Neumaier wrote,
CK > CK > in thread
CK > CK > Subject: Version 2.11, Proposal for interval standardization
CK > CK >
CK > CK >CK > In addition, it will specify the following about
value-changing
CK > CK >CK > optimizations:
CK > CK >CK >
CK > CK >CK > Value-changing optimizations.
CK > CK >CK >
CK > CK >CK > These should be handled similar to
Section 10.4 of IEEE-754-2008.
CK > CK >CK > Transformations are allowed if and
only if they would be exact
CK > CK >CK > in exact real arithmetic and provably
lead to enclosures contained
CK > CK >CK > in the enclosures obtained by using
the original _expression_.
CK > CK >CK > A (nonexhaustive) list of such allowed
transformations should be
CK > CK >CK > provided in an appendix to the standard.
CK > CK >
CK > CK > Consider the fact that [-2,3] * [-2,3] = [-6,9]
CK > CK > whereas
[-2,3]**2 = [0,9]
CK > CK >
CK > CK > Is the language processor allowed to transform xx*xx
into xx**2
CK > CK > or sqr(xx)? This would tighten the enclosure,
hence would be
CK > CK > permitted by Arnold's description quoted above.
CK > CK >
CK > CK > Presumably the reverse transformation would not be allowed,
unless
CK > CK > the correlation (same xx) is observed and handled, as otherwise
CK > CK > the enclosure would widen.
CK > CK >
CK > CK > Should the language processor be allowed, or encouraged,
to go even
CK > CK > further and recognize
CK > CK > yy := xx; zz := xx*yy;
CK > CK > as being a product of correlated intervals?
CK > CK >
CK > CK > Note that similar concerns arise when interval arguments
to a function
CK > CK > are passed by value, compared to passed by reference. In
by-value the
CK > CK > function must assume independence; in by-reference it could
detect the
CK > CK > correlation. Should it act on it? Do we need
guidelines?
CK > CK >
CK > CK > The issue becomes critical when interval primitives are
implemented
CK > CK > as library subroutines, in languages that permit passing
structures
CK > CK > by value.
CK > CK >
CK > CK > Comments?
Thread 2:
Arnold Neumaier <Arnold.Neumaier@xxxxxxxxxxxx>
wrote on 20/11/2008 05:43:47 AM:
> . . .
> The next version of my proposal . . .
> . . .
> ... will specify the following about value-changing
> optimizations:
>
> Value-changing optimizations.
> These should be handled similar to Section 10.4 of IEEE-754-2008.
> Transformations are allowed if and only if they would
be exact
> in exact real arithmetic and provably lead to enclosures
contained
> in the enclosures obtained by using the original _expression_.
> A (nonexhaustive) list of such allowed transformations
should be
> provided in an appendix to the standard.
Thread 3:
Ian McIntosh/Toronto/IBM@IBMCA wrote on 19/11/2008
04:02:51 PM:
IM CK > The standard
IM CK > should require that a processor accomplish the required result
IM CK > . . .
IM CK > Alternatives and optimizations that do not change
IM CK > the result should of course be allowed. Those that slightly
change
IM CK > results (whether for the better or for the worse) can be allowed
IM CK > under user control and do not need to be part of the standard.
I think that the IEEE 754-2008 standard took the right
approach.
The semantics of each operation is defined. Only
a few deviations are
allowed (eg, whether certain things do/don't trigger
an exception?).
Every conforming implementation must have a mode that
produces EXACTLY
the specified result - no approximations, no improvements.
It may also have one or more modes (eg, GCC's fast,
IBM's nostrict)
in which some semantics are not exactly followed,
typically in order to
improve program execution speed but sometimes for
better accuracy, for
compatibility with other implementations, or for usability.
- One example would be replacing x/y with x*(1/y).
When y is a constant
or a loop invariant that's faster but
may give a one bit error.
- Another example is using higher precision
because using the requested
precision would require extra rounding
instructions so be slower.
- Another is replacing x+y*z with a single fused
multiply and add which
doesn't round between the multiply and
add. That's faster but will
usually give a more precise result than
the standard allows (or a less
precise final result when used in x*x-x*x).
- A fourth is replacing .1+.1+.1+.1+.1 with
.5 in binary floating point.
That's faster but gives the wrong answer
by losing the rounding error
in the binary representation of .1.
The control varies. C 99 has a pragma to control
where operations may
or may not be combined. Fortran forbids combining
operations across
parentheses (x+y*z may be combined but x+(y*z) may
not). Some compilers
have options for more control. There could be
one option to allow the
transformations that improve speed, and another option
to allow increasing
precision.
Some users want reproducability. Some want speed.
Some want the most
accurate results. The 754 rule allows a vendor
to provide answers for all.
I think 1788 should take the same approach. Another
benefit is that it lets
you focus now on what the operations and their semantics
should be, and
postpone (or totally avoid?) decisions on what deviations
might be allowed
because all of them are as long as the user has control
over them.
- Ian McIntosh
Toronto IBM Lab 8200 Warden D2-445 905-413-3411