(j3.2006) Interval arithmetic

[Van Snyder]

On Thu, 2009-03-12 at 15:30 -0700, Bill Long wrote:
> 
> Van Snyder wrote:
> > As a consequence of my involvement with P1788, I have concluded that it
> > is impossible in general to provide reliable interval arithmetic with
> > other than an intrinsic type.
> >
> > The killer is register spill.  When a compiler has a value in a register
> > that is wider than the memory representation of that variable, and needs
> > the register for other purposes, it generates spill code.  Storing from
> > registers to memory rounds (or, worse, truncates).  
> 
> Not on any modern processor / ABI that I know of.  This is a relic of 
> legacy Intel processors, and does not seem relevant to a future standard.

This has nothing to do with 80-bit registers.  Even without 80-bit
registers whose contents are rounded to 64 bits before being stored, we
still have 64-bit registers whose contents are rounded to 32 bits before
being stored.  Mixing decimal and binary leads to the same problem.

> > If intervals are not
> > intrinsic types, the compiler can't know how to round the high-precision
> > register to a lower-precision memory representation.  
> 
> 
> But if intervals are represented as structures, certainly the components 
> are of intrinsic type and the compiler knows how to deal with them.  
> Again, the lower precision memory representation is a relic, but any 
> argument about intrinsic versus defined types seems to be outside the 
> area of "impossible to provide reliable" operations.

The compiler ***absolutely does not*** know, and ***cannot*** be told
everything about how to deal with them just because the components are
of intrinsic type.  The program can specify how to round when a
calculation produces them, and how to round further ***explicit***
operations on those results, but that doesn't carry over to ***later
invisible*** operations that occur when higher-precision results in
registers are spilled into lower-precision representations in memory.

> > Ensuring that the
> > compiler respects the current rounding mode when it spills (I have heard
> > that some version of gcc did not) isn't enough, because it's impossible
> > for the program to know when the spill will take place, and set the
> > rounding mode appropriately.
> >
> > Attributes for variables that say "always round thus when storing this
> > into memory" would seem to solve the problem, but it doesn't tackle
> > anonymous temporaries.
> >
> > That's not to say that intrinsic interval arithmetic should therefore
> > necessarily be a part of a revision of Fortran in the immediate future.
> > Rather, it demonstrates that our hope in 2003 that we could cater for it
> > by providing adequate facilities to implement it using functions and
> > defined operations was a fool's errand.
> >   
> 
> I see no evidence of that. The only deficiency in the defined type 
> approach is that (some) compilers might not generate code that is as 
> efficient as for an intrinsic type.

The problem has nothing to do with efficiency...

> I strongly suspect any intrinsic 
> type spec would at least initially be implemented as a derived type 
> internally, and thus there would be no difference at all.

... nor with representation.  It has to do with specifying how to
manipulate the components of that representation at some arbitrarily
distant later time ***after*** explicit operations have produced their
values.  If one represents an interval as a derived type having two real
components, and the operations on them by procedures, the procedures
ultimately do arithmetic individually on the components.  The procedures
***cannot*** specify how long those results should be kept in registers,
and how to round those results to lower precision when, at some
arbitrarily distant later time, they are spilled from registers to
memory.  If the types are not intrinsic, the compiler will almost
certainly lose track of which registers contain upper bounds of
intervals and should therefore be rounded upward when stored, which ones
are lower bounds of intervals and should therefore be rounded downward
when stored, and which ones are points and should therefore be rounded
symmetrically when stored.  If one follows the process outlined in
14.11.21 separately to set the rounding modes for the lower and upper
bounds of an interval, and then returns from a procedure, at which time
14.4 ***requires*** to forget anything about the rounding modes in
effect within the procedure that calculated the bounds, the processor
***cannot possibly*** know how later to round results it hauls around in
registers for some duration that the program can neither inquire nor
control.

It is conceivable that an additional facility might be provided to
specify to round a result to a 32-bit representation even if it remains
in a 64-bit register (there isn't a standard one now, except maybe the
giant hammer of volatility if the "current IEEE rounding mode" applies),
but this would make intervals wider than otherwise necessary.  As Keith
has already pointed out, an answer in (-infinity .. +infinity) is
correct but uninteresting.

> Cheers,
> Bill
> 
> 
>