Thread Links Date Links
Thread Prev Thread Next Thread Index Date Prev Date Next Date Index

Re: Include language bindings? Re: Draft Standard Text, V02.1

Dan Zuras Intervals wrote:

From: "Nate Hayes" <nh@xxxxxxxxxxxxxxxxx>
To: "P1788" <stds-1788@xxxxxxxxxxxxxxxxx>
Subject: Re: Include language bindings? Re: Draft Standard Text,
V02.1 Date: Tue, 16 Mar 2010 10:04:24 -0500

I think to study the algebraic properties of intervals and make sure
these semantics are clearly delineated in the standard will be
helpful along this direction. For example, if an implementation
violates the algebraic properties, then it would be clear the
implementation is non-conforming.

Also, if some sorts of expression rearrangement are allowed, this
will particularly ensure various compiler optimizations by different
vendors will be more consistent accross implementations.

Nate



When Nate speaks of the algebraic properties of intervals
he is including issues peculiar to interval expressions
which have no analogy among real or floating-point
expressions.

Let me illustrate with 3 different ways of evaluating some
polynomial pp(xx):


pp = ((((c0*xx + c1)*xx + c2)*xx + c3)*xx + c4)*xx + c5;

tt0 = c0;
tt1 = tt0*xx + c1;
tt2 = tt1*xx + c2;
tt3 = tt2*xx + c3;
tt4 = tt3*xx + c4;
pp = tt4*xx + c5;

tt[0] = c0;
for (i = 1; i < n; i++) tt[i] = tt[i-1]*xx + c[i];
pp = tt[n-1];


All are exactly the same.  If implemented in floating-point,
all would be implemented with exactly the same sequence of
floating-point operations.  (Let's pass on the FMA issue for
now.)  In a very real sense, all have the same 'meaning'.

However, as we discussed at length in the stds-1788-er
subgroup, the resulting interval would be unnecessarily wide
unless one recognises that each instance of the interval
variable 'xx' are the SAME variable.  That is, all of the
instances co-vary rather than vary independently of one
another.


THis is the problem of unrecognized "interval dependence."




Nate calls this an 'algebraic' property of the expression.


Just to be clear:
When I talk about "algebraic" property of intervals, I mean properties such as commutativity, associativity, identity element, inverse elements, etc. These describe characteristics of the individual arithmetic operations... for example, the operations that are likely to be performed by a simple interval processor.
Attempting to defeat the pessimism caused by unrecognized interval dependence is a much larger problem that I believe is beyond the scope of P1788. The reason is because defeating interval dependence usually requires a-priori knowledge of the entire syntax tree of an expression. This is too much to expect from a simple interval processor.
HOWEVER, to consider the role algebraic properties play in defeating interval dependence is important, since authors of Computer Algebra Systems and optimizing compilers can apply these basic principles in a rigorous and consistent manner to help achieve the Holy Grail of computing narrow bounds on complicated interval expressions. 

Nate