Morphed to bare intervals & fast hardware...
> Date: Tue, 28 Sep 2010 18:50:54 +0200
> From: Arnold Neumaier <Arnold.Neumaier@xxxxxxxxxxxx>
> To: Dan Zuras Intervals <intervals08@xxxxxxxxxxxxxx>
> CC: stds-1788@xxxxxxxxxxxxxxxxx
> Subject: Re: Comparisons and decorations, part 2
>
> Dan Zuras Intervals wrote:
> >> From: Arnold Neumaier <Arnold.Neumaier@xxxxxxxxxxxx>
> >> (i) Constructors always create decorated intervals, never bare ones.
> >> Bare intervals are created by stripping decorated ones using the
> >> operator Bare.
> >
> > I suggest, for the sake of assured computing, that we
> > ALWAYS deal with decorated intervals at a formal level.
> > Then we can leave it to compiler optimizers to know
> > when it is safe to strip them bare & run without the
> > decorations.
>
> A compiler must be very intelligaent to know that without directives
> from the user, since it must understand some mathematical theory.
Not at all.
It must merely know that there is no call to
something that extracts the value of a decoration.
Simple.
(I said as much in the next sentence.)
> We cannot expect the compiler to do theorem proving....
Compilers do it all the time in other contexts.
But I am not a compiler expert.
Seek out one to know their possibilities & limitations.
>
> Probably the casual user should always work (invisibly) with
> decorated intervals and have compiler support for more trivial
> cases where decorations can be dropped because they are never queried.
>
> But expert users must be able to strip the decorations explicitly,
> without having to prove to the compiler that it is allowed.
>
>
> > As this should be most of the time (when
> > it is known that no one is looking at the decorations,
> > for example), it should be a relatively easy task.
> >
> >> (ii) The empty interval Empty is represented by [NaN,NaN] when bare,
> >> and by ([NaN,NaN],IsEmpty) when created by a constructor.
> >> However, _every_ decorated interval of the form ([any,any'],IsEmpty)
> >> is interpreted as Empty.
> >
> > There are two possibilities here.
> >
> > Either we decide how the empty interval is to be
> > represented or we leave it up to the implementers
> > to decide what is best for them.
> >
> > In the latter case, we could put in an informative
> > note suggesting the use of [NaN,NaN] & explaining
> > why.
>
> Yes.
>
> >> (iii) The stripping of a decorated interval may modify its bare part
> >> iff the semantics necessitates it. In particular,
> >> Bare(([any,any'],IsEmpty)) = [NaN,NaN].
> >
> > That would work.
> >
> >> (iv) Arithmetic operations on decorated intervals always preserve
> >> an IsEmpty decoration.
> >
> > Of course.
> >
> >> This indeed captures the necessary behavior of Empty, and improves
> >> the efficiency of propagating decorated intervals in general, while
> >> not harming fast expression evaluation for bare intervals.
> >>
> >> However, it still means that
> >> bare[a,b] interior bare[c,d]
> >> needs a branch to handle bareEmpty.
> >
> > Well, as a bare evaluation of sqrt(bare[-5,4]) would
> > lead to bare[NaN,2] rather than bare[0,2],
>
> Why? According to Motion 8, it must return a valid interval that is
> an enclosure of bare[0,2], Only a naive, wrong evaluation produces
> the non-interval bare[NaN,2].
>
> Similarly, bare[1,1]/bare[0,0] must return a valid interval,
> and the only natural choice is Empty.
In your previous note you said, & I quote:
Since bare[1,1]/bare[0,0] or sqrt(bare[-2,-1])
must be empty, this conflicts with the need of
a fast mode for arithmetic operations for bare
intervals.
As an argument for 'a fast mode for arithmetic operations'
which is almost the definition of bare mode, one can only
really expect that the arithmetic engine will handle these
cases without intervention & produce the right results.
Well if you use [NaN,NaN] for empty then, on existing 754
hardware, the latter produces a correct result while the
former does not. Nor does sqrt(bare[-5,4]) fall out
naturally.
The real answer is that you have to change the arithmetic
engine to have these things happen both fast & correct.
And in the case of something like sqrt(bare[-5,4]) = [0,2]
that engine must look at both endpoints to know what the
sqrt of the first one is.
That sounds like a specialized interval engine to me.
And there is no reason why an engine designed for our
purposes cannot also handle the decorations just as fast
(or faster) than the arithmetic.
If the only justification for bare mode is speed, we are
rapidly losing that argument.
>
>
> > I'm sure
> > there are many examples that would need careful
> > analysis rather than blind bare evaluation.
>
> The problem I posed is on the conceptual Level 2 rather than
> on the level of a particular algorithm. The operations are
> _defined_ conceptually, and must be _implementend_ in a way
> conforming to the conceptual specifications.
Very well, let's stay at level 2.
At that level, I believe you will end up defining an
arithmetic that is both different from existing hardware
implementations in its case analysis & requires the
input of both endpoints to know the output of either.
It is a reasonable thing to define.
At that level we will also be defining how decorations
work without reference to how their actual bits are
assigned or laid out.
Again, unlike existing hardware.
But both can form the description of a specialized
interval engine that handles both the interval part &
the decoration part of an interval with a speed that
rivals or exceeds existing floating-point engines.
Something we all hope will actually find its way into
hardware some day.
>
>
> > This is a good reason to leave the decision to run
> > bare up to the compiler optimizer. It might only
> > choose to optimize to bare when such things cannot
> > happen. Or, more to the point, can be PROVED not
> > to happen.
>
> Nevertheles, we must consider the options in order to know
> what can reasonably be required.
>
As, I believe, you & I are doing right now. :-) - Dan