Re: Motion P1788/M0013.04 - Comparisons - Overflow / Infinity
Ian, P1788,
My apologies to Ian for perhaps not being clear in my first e-mails about
Overflow. In any case, thank you, Ian, for taking time to clarify.
BTW, _if_ there is enough interest by people to form a subgroup to study
this topic further, I'd be interested to help. I will even volunteer to head
it (which basically means I volunteer to do the paperwork :-) ... unless
someone else interested would rather do so.
Sincerely,
Nate
----- Original Message -----
From: "Ian McIntosh" <ianm@xxxxxxxxxx>
To: <stds-1788@xxxxxxxxxxxxxxxxx>
Sent: Monday, September 20, 2010 5:22 PM
Subject: Re: Motion P1788/M0013.04 - Comparisons - Overflow / Infinity
AN> We introduced in Motion 8 decorations to be able to distinguish the two
where necessary inninterval bounds by having the decoration IsBounded.
Yes, you can distinguish Overflow from Infinity by using decorations, and
that works well as long as no other operation supersedes that decoration.
Could one consider an Infinity decorated as having come from an overflowing
operation as being an Overflow?
JP> I have several objections to the idea e.g.:
JP>
JP> (1) What is, for instance, sqrt( [1,Overflow] ) or log( [1,Overflow] )?
For safety, you must consider sqrt ( [1, +Overflow] ) to be [1,
+Overflow], just as without Overflow you would consider sqrt ( [1,
+Infinity] ) to be [1, +Infinity], and you must consider log ( [1,
Overflow] ) to be [0, Overflow], just as without it you would consider
log ( [1, +Infinity] ) to be [0, +Infinity]. If you merge the concepts
of Overflow and Infinity, you have exactly the same problem.
JP> (2) [a,Overflow] doesn't really represent one interval, but an infinite
family of intervals: all [a,b] with b > MAXREAL. Hence how does one
evaluate [1,Overflow] JP> \subseteq [1,Overflow]? It seems to need a trit,
or a bool_set, result.
You're right, as I said Overflow is an infinite set just as Infinity is an
infinite set, so [a, Overflow] represents an infinite family of intervals
just as [a, Infinity] represents an infinite family of intervals. How does
one evaluate
[1, Infinity] \subseteq [1, Infinity] ? Which Infinity is larger? It's
the same problem, one which I did not claim to solve.
My only claims are that by distinguishing Overflow from Infinity you can
know whether multiplying whichever by zero gives zero or NaNQ in floating
point, and that if 754 already had that it would be helpful for interval
arithmetic.
JP> Siegfried Rump spent some time about 2 years ago trying to make a
provably consistent theory of this, and then went very quiet on it. If he
couldn't do it, I suspect no such theory exists.
I also suspect no such theory exists. I don't know if it could exist or
cannot, whether it's impossible or just difficult or just not done yet. No
IEEE Interval Arithmetic standard exists yet either. I think it's
impossible to develop one we all totally agree with, but just difficult to
develop one most of us can accept.
I wasn't trying to convince the committee to use Overflow (I'm not sure if
that's impossible or just very difficult), just to correct what appeared to
be misunderstandings in what I had said earlier, and now in its
implications. I'm still unenthused about 0 times Infinity producing 0
because it needs either special instructions I don't expect to see or
special checks after every operation. To anticipate what you may wonder,
no, I really don't expect IEEE 754 to ever include Overflow either. I just
think it would be better if it did.
- Ian McIntosh IBM Canada Lab Compiler Back End Support
and Development
|------------>
| From: |
|------------>
>--------------------------------------------------------------------------------------------------------------------------------------------------|
|John Pryce <j.d.pryce@xxxxxxxxxxxx>
|
>--------------------------------------------------------------------------------------------------------------------------------------------------|
|------------>
| To: |
|------------>
>--------------------------------------------------------------------------------------------------------------------------------------------------|
|Ian McIntosh/Toronto/IBM@IBMCA
|
>--------------------------------------------------------------------------------------------------------------------------------------------------|
|------------>
| Date: |
|------------>
>--------------------------------------------------------------------------------------------------------------------------------------------------|
|09/20/2010 03:05 PM
|
>--------------------------------------------------------------------------------------------------------------------------------------------------|
|------------>
| Subject: |
|------------>
>--------------------------------------------------------------------------------------------------------------------------------------------------|
|Re: Motion P1788/M0013.04 - Comparisons - Overflow / Infinity
|
>--------------------------------------------------------------------------------------------------------------------------------------------------|
On 20 Sep 2010, at 19:00, Arnold Neumaier wrote:
Ian McIntosh wrote:
NH> Keep in mind, Ian McKintosh has suggested replacing unbounded closed
NH> intervals with "overflown" compact intervals. In practice, there is
not
NH> really a difference between the two. For example, +INF and -INF are
NH> replaced by +OVR and -OVR in all compuations, where OVR is some
unknown
NH> finite real number larger than the magnitude of the largest
NH> floating-point number. In this way, intervals such as [1,+OVR]
remain
NH> compact intervals and are not unbounded like the interval [1,+INF].
NH> Arithmetic operations on the endpoints of compact overflown
intervals
is
NH> the same as in Motion 5, i.e., (-OVR) + (-OVR) = -OVR, 0 * OVR = 0,
etc.
AN> But then OVR has a different meaning in different places, which is
AN> unacceptable from a mathematical point of view. It is just INF in
AN> duisguise, and it hides mathematical propoerties of the limit under
AN> the carpet. One cannot use it in a mathematical argument....
AN>
AN> To argue for existence, one _needs_ in certain case the unbounded
case.
AN> Mathematical programming had once a tradition for using big M (which
is
AN> about the same as your OVR), and it is now deprecated (though still
used
AN> by a few who don't like unbounded variables) since it behaves poorly
not
AN> only mathematically but also algorithmically.
I did suggest Overflow (OVR) as a better floating point value than
Infinity
to represent an overflowed value, and that it would be very often more
useful as an interval endpoint.
In doing that I did not mean it to totally replace Infinity, and I did
not
mean they would have the same semantics. The whole point is to
distinguish
their semantics.
In IEEE floating point, you can get Infinity two ways. One is by
dividing
a nonzero by zero. The other is by overflow. The following mostly
ignores
signs for brevity:
IEEE nonzero / 0 = Infinity
IEEE overflow on any operation = Infinity
We introduced in Motion 8 decorations to be able to distinguish the two
where necessary inninterval bounds by having the decoration IsBounded.
I have several objections to the idea e.g.:
(1) What is, for instance, sqrt( [1,Overflow] ) or log( [1,Overflow] )?
(2) [a,Overflow] doesn't really represent one interval, but an infinite
family of intervals: all [a,b] with b > MAXREAL. Hence how does one
evaluate [1,Overflow] \subseteq [1,Overflow]? It seems to need a trit, or a
bool_set, result.
Siegfried Rump spent some time about 2 years ago trying to make a provably
consistent theory of this, and then went very quiet on it. If he couldn't
do it, I suspect no such theory exists.
John