Re: Comparisons and decorations
Arnold Neumaier wrote:
Nate Hayes wrote:
Arnold Neumaier wrote:
Nate Hayes wrote:
Arnole Neumaier wrote:
In [Re: Motion P1788/M0013.04 - Comparisons], Nate Hayes raised
an important issue about comparisons and decorations that has much
more general impact than apparent from his particular example:
How do decorations influence the outcome of comparison relations?
This must be decided unambiguously, and in a way consistent with
the uses of decorations for guaranteeing correctness of interval
programs.
Below is my proposal for handling this issue correctly.
Arnold Neumaier
=========================================================================
Nate Hayes wrote:
Arnold Neumaier wrote:
[etc.]
So this approach seems to retain all the important advantages of
unbounded intervals without actually introducing the
complications that arise from them.
Could you please point to a real complication of the implementation
that Inf in place of OVR produces?
This has already been done recently, in regards to discussions about
implementation of the arithmetic operations, e.g.,
[1,Overflow]*[0,0]=[1*0,Overflow*0]=[0,0]
etc.
But this does not execute in IEEE 754 as Overflow must be larger
than the largest machine number. So there is no saving compared to
using Inf in place of Overflow - one still needs a branching
operation.
Since one also needs to ensure that Overflow*finiteNumber = Overflow,
one also hasn't the option to use RealMax in place of Overflow.
In summary, Using Overflow dfoes not give an implementation advantage
over Inf when using 754 arithmetic. On the other hand, if 754
arithmetic is modified for directed rounding according to the
recommendations in
the final Section of the Vienna proposal then 0*inf = inf in roundup
mode, and one has exactly the behavior you want to have for Overflow.
Therefore there is no advantage at all in considering Overflow.
I think there is a SERIOUS misunderstanding going on here.
NO ONE is advocating that Overflow should be represented by RealMax!
Neither did I.
I considered two alternatives within 754: either you represnt it
that way, or you don't. In the first case, you get nonsens upon
multiplication with a finite number, in the second case, you must
represent it by Inf. But then Overflow is inf, and there is no need
to treat it as something new.
No. This is one of the points you miss. In the second case there is still
a distinction to be made between Overflow and Infinity, just as there is
still a distiction to be made between an interval [1,Infinity] that
either does or does not have the IsBounded decoration present.
Since we have Infinity anyway, what is the use to have in addition an
Overflow?
Overflow must behave just like Inf is handled in the suggestions of
the Vienna proposal for modifying the IEEE 754 directed rounding modes.
But then there is no need for distinguishing the two, beyond what the
usual Inf and the IsBounded decoration offer.
Whhat is the advantage of having another object Overflow?
It depends on many cases, none of which P1788 has made any decision about
yet (that I know of).
If P1788 decides to include an IsBounded decoration, then the decorated
intervals:
([1,Infinity],NotBounded) and ([1,Infinity],IsBounded)
are two different intervals. The upper bound of the former is truly
unbounded, but the upper bound of the latter is not. In this case, the
IsBounded decoration could be "stored" in the floating-point representation
of the Infinity, hence
[1,Infinity] and [1,Overflow]
makes the same difference as the two decorated intervals above. In this
sense, the "IsBounded" decoration of interval [1,Infinity] can be viewed as
an Overflow in disguise. The reson the opposite is not necissarily true,
however, is that certain representations are explicitly possible with
Overflow that would not other-wise be possible with just an IsBounded
interval deocration, e.g.
[-Infinity,Overflow] and [-Overflow,Infinity]
are two intervals that could not be represented if the IsBounded decoration
is an attribute of the interval, itself.
Now, regardless if P1788 includes an IsBounded decoration or not,
distinguishing between Overflow and Infinity in the IEEE 754 arithmetic (or
a replacement thereof) gives a fast and efficient way to compute
[1,Overflow]*[0,0]=[1*0,Overflow*0]=[0,0]
as opposed to the incorrect results obtained by using IEEE 754 arithmetic as
it exists today. Ian has already explained this in detail, so I'm not going
to repeat it all over again.
If P1788 does not include an IsBounded decoration, the overflow arithmetic
above gives the correct computational results for interval arithmetic,
anyway, even though in this case we would then want to intrepret the
computation as:
[1,Infinity]*[0,0]=[1*0,Infinity*0]=[0,0]
by Motion 5 semantics. However, the actual underlying computation of the
correct interval result could be due to use of Overflow in the enhanced IEEE
754 arithmetic.
I personally don't have strong feelings one way or the other whether or not
P1788 decides to include an IsBounded decoration. But it seems clear to me
Overflow as a concept is a relevant topic, either way.
The exact use and meaning of OVerflow for P1788, however, could depend on
decisions that have yet to be voted on (such as should P1788 include an
IsBounded decoration, etc.)
And I discussed a third alternative: Modifying 754.
But then one can simply modify the rules for directed rounding of
operations involving Inf, as done in the Vienna proposal, and one
again needs no special object called Overflow.
The idea is that Overflow would be something like a "decorated
floating-point infinity." New and special rules to the IEEE 754
arithmetic would then be required to compute with this value properly.
If such a change was (had been) made to the IEEE 754 arithmetic, there
would be benefits to implementations of IEEE 1788 arithmetic.
But no such change has been made.
With 754, you cannot take advantage of the formula claimed to be an
advantage, since
[1,Overflow]*[0,0]=[1*0,Overflow*0]=[0,0]
cannot be implemented in 754!
I KNOW!!
Please pay attention!
As has already been mentioned repeatedly, IEEE 754 arithmetic gives
[1,Infinity]*[0,0]=[1*0,Infinity*0]=[0,NaN]
which is _expensive_ to "fix" in order to obtain the correct interval
result.
WE BOTH KNOW!!
I paid attention!
Ok. I'm glad to hear you are listening. :-)
Sometimes you have to make a lot of noise to see if someone is paying
attention....
This is a problem with IEEE 754 as it exists today with regard to
efficient implementations of an IEEE 1788 standard.
As Ian mentions, it has been recognized as a _known_ (potential) problem
with IEEE 754 for decades, now.
But if you are going not to use IEEE 754 anyway, what is the advantage of
Overflow over the proposal in the final Section of the Vienna Proposal?
Because it has already been mentioned that Overflow is an incremental
improvement to existing hardware that would make IEEE 754 better, anyways.
THis gives possibility that interval software could then make good use of
this efficient new hardware operation: Overflow*0=0.
As mentioned above, keep in mind this is regardless if P1788 actually
includes an IsBounded decoration or not, e.g., even if we choose to
interpret the Overflow as Infinity:
[1,Infinity]*[0,0]=[1*0,Infinity*0]=[0,0]
the underlying operations in the hardware impelementation of the modified
IEEE 754 arithmetic would in this case be:
[1,Overflow]*[0,0]=[1*0,Overflow*0]=[0,0].
We should be careful to keep our Level 1 and Level 2 models separate from
the Level 3 and Level 4 implementations, which I think might not be
occurring in this present discussion (and hence leading to HUGE
misunderstandings and confusion).
I am just trying to learn the supposed advantage by restating what
we both know, so that you can figure out what I am missing.
But then please give the missing information - rather than just
asserting that a distinction still must be made tell me why?
From a conceptual point of view, this would be the same as leaving the
IEEE 754 arithmetic "as is," decorating the interval [1,Infinity] with
an IsBounded decoration, and then using special routines to "fix" the
endpoint results that are incorrectly produced by existing IEEE 754
arithmetic.
But if you need a special routine to fix the behavior depending on the
decoration, this is by no means better than fixing the behavior of Inf
as it is fixed traditionally, e.g., in Intlab.
On the other hand, you violate by this special procedure the general
conceptual rule that the result of the interval part should not depend
on the decorations.
The important differences (benefits) are in how the underlying interval
arithmetic operations are potentially implemented... not the definition
of interval arithmetic itself as we've already accepted in Motion 5
(that would NOT change).
I can't see how you'd implement your formula with Overflow more
efficiently than Rump implemented the treatment of Inf.
Will you please show me the source code of how Rump does this?
How he did it in version 5.0 is appended to the end of this mail.
But the code looks quite ugly since he does the real case and the
complex case and the vector-valued case simultaneously, and also has
overloading by real numbers and complex numbers/intervals as part of the
procedure. The essential part for real intervals is:
setround(-1)
c.inf = min( a.inf .* b.inf , a.inf .* b.sup );
c.inf = min( c.inf , a.sup .* b.inf );
c.inf = min( c.inf , a.sup .* b.sup );
setround(1)
c.sup = max( a.inf .* b.inf , a.inf .* b.sup );
c.sup = max( c.sup , a.sup .* b.inf );
c.sup = max( c.sup , a.sup .* b.sup );
It works correctly except for the case when a and b are [0,0] and Entire
(in some order), where the Intlab result is (wrongly) [NaN,NaN] rather
than [0,0]. The code can easily be fixed (for scalar intervals) by
appending
if isnan(c.sup), c.inf=0;c.sup=0; end;
Easy to write in code, I agree. But notice this puts a branch into the code
to detect what typically will be quite a rare case. The branch needs to be
tested and executed for every interval operation, though. This can lead to
big performance loss.
Nate Hayes
I think this is the best that can be done with standard IEEE 754
arithmetic. With 754 modified for directed rounding, the last section
of the Vienna Proposal gives the simplest implementation known to me.
(With sign masks, both the recipe of Rump and that of the Vienna Proposal
can be improved in certain cases, and in particular when
multiplying with zero.)
I'd be very surprised if any rules for an implementation of Overflow
different from those of Inf could improve upon this.>
I'm not sure where to obtain that.
Get the intlab distribution from
www.ti3.tu-harburg.de/~rump/intlab/
and look into
intlab5.0/intval/@intval/times.m
It seems to me this is the same as
[1,Overflow] \subseteq [1,Overflow]
yes, the same problems arise, nothing is gained by using Overflow
in place of Inf.
Arnold, with respect, you are still missing the previous point about
implementation of the underlying arithmetic operations.
Since you haven't told us how you implement Overflow efficiently
by means of decorations, I can't compare the merits of your proposal
with the treatment of unbounded intervals in, say, Intlab.
Arnold, IMHO if you would just relax and take some time to let the
discussion continue without trying so hard to stop it prematurely,
I never tried to stop the discussion. Like anybody else, I voice my
opinions, contribute information I know and ask for information I
don't know yet.
In the present discussion I try to find out what possibly could
be superior. Nothing on the table so far looks like a gain.
Arnold Neumaier
===========================
function c = times(a,b,dummy)
%TIMES Implements a .* b for intervals
%
% written 10/16/98 S.M. Rump
% modified 09/02/00 S.M. Rump rounding unchanged after use
% modified 04/04/04 S.M. Rump set round to nearest for safety
% remove check for 'double'
% extra argument for non-interval
output (internal use only)
% take care of Matlab sparse Inf/NaN
bug
%
setround(0) % set rounding to nearest
if ~isa(a,'intval') % a is double
if ~isreal(a) | b.complex % complex case
if ~b.complex
setround(1)
b.mid = b.inf + 0.5*(b.sup-b.inf);
b.rad = b.mid - b.inf;
end
c.complex = 1;
c.inf = [];
c.sup = [];
if isreal(a) | ~b.complex % R .* IC or C .* IC
setround(-1)
c1 = a .* b.mid;
setround(1)
c2 = a .* b.mid;
else % C .* IC
setround(-1)
c1 = real(a) .* real(b.mid) + (-imag(a)) .* imag(b.mid) + ...
( real(a) .* imag(b.mid) + imag(a) .* real(b.mid) ) * j;
setround(1)
c2 = real(a) .* real(b.mid) + (-imag(a)) .* imag(b.mid) + ...
( real(a) .* imag(b.mid) + imag(a) .* real(b.mid) ) * j;
end
c.mid = c1 + 0.5*(c2-c1); % R .* IC or C .* IC
c.rad = abs(c.mid-c1) + abs(a) .* b.rad;
if ~any(find(c.rad)) % take care of huge arrays
c.rad = 0;
end
else % real case R .* IR
c.complex = 0;
setround(-1)
c.inf = min( a .* b.inf , a .* b.sup );
setround(1)
c.sup = max( a .* b.inf , a .* b.sup );
c.mid = [];
c.rad = [];
end
elseif ~isa(b,'intval') % b is double
if a.complex | ~isreal(b) % complex case
if ~a.complex
setround(1)
a.mid = a.inf + 0.5*(a.sup-a.inf);
a.rad = a.mid - a.inf;
end
c.complex = 1;
c.inf = [];
c.sup = [];
if ~a.complex | isreal(b) % IC .* R or IC .* C
setround(-1)
c1 = a.mid .* b;
setround(1)
c2 = a.mid .* b;
else % IC .* C
setround(-1)
c1 = real(a.mid) .* real(b) + (-imag(a.mid)) .* imag(b) + ...
( real(a.mid) .* imag(b) + imag(a.mid) .* real(b) ) * j;
setround(1)
c2 = real(a.mid) .* real(b) + (-imag(a.mid)) .* imag(b) + ...
( real(a.mid) .* imag(b) + imag(a.mid) .* real(b) ) * j;
end
c.mid = c1 + 0.5*(c2-c1); % R .* IC or C .* IC
c.rad = abs(c.mid-c1) + a.rad .* abs(b) ;
if ~any(find(c.rad)) % take care of huge arrays
c.rad = 0;
end
else % real case IR .* R
c.complex = 0;
setround(-1)
c.inf = min( a.inf .* b , a.sup .* b );
setround(1)
c.sup = max( a.inf .* b , a.sup .* b );
c.mid = [];
c.rad = [];
end
else % both a and b interval
if a.complex | b.complex % complex case
if ~a.complex
setround(1)
a.mid = a.inf + 0.5*(a.sup-a.inf);
a.rad = a.mid - a.inf;
end
if ~b.complex
setround(1)
b.mid = b.inf + 0.5*(b.sup-b.inf);
b.rad = b.mid - b.inf;
end
c.complex = 1;
c.inf = [];
c.sup = [];
if ~a.complex | ~b.complex % one real factor
setround(-1)
c1 = a.mid .* b.mid;
setround(1)
c2 = a.mid .* b.mid;
else
setround(-1)
c1 = real(a.mid) .* real(b.mid) + (-imag(a.mid)) .* imag(b.mid) +
...
( real(a.mid) .* imag(b.mid) + imag(a.mid) .* real(b.mid) ) *
j;
setround(1)
c2 = real(a.mid) .* real(b.mid) + (-imag(a.mid)) .* imag(b.mid) +
...
( real(a.mid) .* imag(b.mid) + imag(a.mid) .* real(b.mid) ) *
j;
end
c.mid = c1 + 0.5*(c2-c1); % IR .* IC or IC .* IC
c.rad = abs(c.mid-c1) + ...
a.rad .* ( abs(b.mid) + b.rad ) + abs(a.mid) .* b.rad;
if ~any(find(c.rad)) % take care of huge arrays
c.rad = 0;
end
else % real case IR .* IR
c.complex = 0;
setround(-1)
c.inf = min( a.inf .* b.inf , a.inf .* b.sup );
c.inf = min( c.inf , a.sup .* b.inf );
c.inf = min( c.inf , a.sup .* b.sup );
setround(1)
c.sup = max( a.inf .* b.inf , a.inf .* b.sup );
c.sup = max( c.sup , a.sup .* b.inf );
c.sup = max( c.sup , a.sup .* b.sup );
c.mid = [];
c.rad = [];
end
end
% take care of Matlab sparse NaN bug
if issparse(a) & ( prod(size(a))~=1 )
index = ( isnan(b) | isinf(b) );
if any(any(index)) % b is two-dimensional
if prod(size(b))==1
if nnz(a)~=prod(size(a))
if intvalinit('SetSparseInfNanFlag')
error(intvalinit('SparseInfNanFlagErrorString'))
end
end
else
% take care of huge arrays
if prod(size(a))==1
if a==0
if intvalinit('SetSparseInfNanFlag')
error(intvalinit('SparseInfNanFlagErrorString'))
end
end
elseif prod(size(a))>=2^31-1
a = abss(a).*index;
if nnz(a)~=nnz(index)
if intvalinit('SetSparseInfNanFlag')
error(intvalinit('SparseInfNanFlagErrorString'))
end
end
else
%VVVV a_index = a(index);
s.type = '()'; s.subs = {index}; a_index = subsref(a,s);
%AAAA Matlab V5.2 bug fix
if any(any(a_index==0))
if intvalinit('SetSparseInfNanFlag')
error(intvalinit('SparseInfNanFlagErrorString'))
end
end
end
end
end
end
% take care of Matlab sparse NaN bug
if issparse(b) & ( prod(size(b))~=1 )
index = ( isnan(a) | isinf(a) );
if any(any(index)) % a is two-dimensional
if prod(size(a))==1
if nnz(b)~=prod(size(b))
if intvalinit('SetSparseInfNanFlag')
error(intvalinit('SparseInfNanFlagErrorString'))
end
end
else
% take care of huge arrays
if prod(size(b))==1
if b==0
if intvalinit('SetSparseInfNanFlag')
error(intvalinit('SparseInfNanFlagErrorString'))
end
end
elseif prod(size(b))>=2^31-1
b = abss(b).*index;
if nnz(b)~=nnz(index)
if intvalinit('SetSparseInfNanFlag')
error(intvalinit('SparseInfNanFlagErrorString'))
end
end
else
%VVVV b_index = b(index);
s.type = '()'; s.subs = {index}; b_index = subsref(b,s);
%AAAA Matlab V5.2 bug fix
if any(any(b_index==0))
if intvalinit('SetSparseInfNanFlag')
error(intvalinit('SparseInfNanFlagErrorString'))
end
end
end
end
end
end
% non-interval output for performance improvement for hessians
if nargin==2
c = class(c,'intval');
end
setround(0) % set rounding to nearest