Re: Branch & bound for not everywhere defiend constraints
> Date: Mon, 7 Sep 2009 14:50:05 -0400
> From: Nate Hayes <nh@xxxxxxxxxxxxxxxxx>
> Subject: Re: Branch & bound for not everywhere defiend constraints
> To: STDS-1788@xxxxxxxxxxxxxxxxx
>
> Dan Zuras Intervals wrote:
> >> . . .
> >
> > Isn't another name for "TotallyUndefined", "Empty"?
> > You define it to be true in exactly the same place
> > as empty is true & you use it as others use empty.
> >
> > Are we just a name away from agreement?
>
> Almost.
>
> The difference is "Empty" doesn't propagate the same way as
> "TotallyUndefined," since "Empty" may be absorbed by union operations
> whereas "TotallyUndefined" is guaranteed to propagate all the way
> to the end of a computation.
Oh, I think we may be able to accomodate both.
Read the propagation rules for decorations I proposed
in this forum more carefully.
You will find that a domain error results in both an
empty, which is a property of the of the interval
portion of the decorated interval & persists so long
as the interval is empty, AND emptyHappened (or you
could call it isOrWasEmpty) which is a decoration,
never goes away, & has all the properties of an NaI
that you require.
Further, you might object to a silent loss of information
in a PARTIAL domain error such as sqrt([-1,1]). I think
this a perfectly reasonable criticism. I also think it
perfectly reasonable to have a decoration called, say,
partialDomainError or partiallyEmpty that ALSO propagates
like an NaI.
Under these circumstances, your previously described
algorithm would require nothing more than these.
Would that get us closer?
>
>
>
> >
> > Finally, while I'm not happy with the concept of global
> > flags for any purpose, I agree that 'syntactic sugar' AKA
> > 'decorations' attached to intervals may be of value.
>
> Along this route, I think its important to distinguish: a "decorated
> interval" is [double,double] plus a byte for state information.
> So the size (in bits) of any decorated interval is by nature not
> going to be a power-of-two, which means generally speaking it will
> not fit in one piece into a hardware register or buss. For NaI,
> the information that would otherwise be in the byte of a decorated
> interval is encoded into the payload of the NaI. In this way, the
> size (in bits) of NaI can remain power-of-two.
Not so. Non-power-of-two busses happen all the time.
Intel is perfectly happy with 80-bit busses to accommodate
their double extended datatypes. As they generally run
their memory systems aligned to 32-bit boundaries, they
handle the alignment problem by packing their 80-bit
double extendeds into 96-bit windows when stored in memory.
There is every reason to expect that efficient hardware
support for decorated intervals could be implemented along
similar lines.
>
> So theoretically they may be similar concepts. In practice they have
> different implementation consequences.
While I don't agree with your argument above, this is
still true.
That is why one of the other principles I set forth in
the properties of decorated intervals is that the interval
portion of the result can only depend on the interval
portion of the operands. While the decoration portion of
the result may depend on BOTH the interval & decoration
portions of the operands.
It is quite possible that implementors may choose to go
the route of handling the floating-point task only & leave
the decoration task up to software or some slower form of
instruction support.
As a standard, we should permit this as a possibility.
>
> THis is why I believe both should be examined and considered.
Agreed. But, as it happens, for different reasons. :-)
>
> >
> > As for the naming of things, it could be that sufficiently
> > many 'flavors' of 'syntactic sugar' could take the place
> > of either or both of NaIs or empty for what we need them
> > to do.
> >
> > We are having that discussion now. Let's see how it turns
> > out.
>
> Yes.
>
> >
> > Thanks for your explanations,
>
> You're welcome!
>
> Nate Hayes
We may be closer than you think...
Dan