Re: Motion P1788/M0013.04 - Comparisons - Overflow / Infinity
> Subject: Re: Motion P1788/M0013.04 - Comparisons - Overflow / Infinity
> From: John Pryce <j.d.pryce@xxxxxxxxxxxx>
> Date: Tue, 21 Sep 2010 10:42:07 +0100
> To: stds-1788 <stds-1788@xxxxxxxxxxxxxxxxx>
>
> Ian
>
> On 20 Sep 2010, at 23:22, Ian McIntosh wrote:
> > 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.
>
> NO! You are falling into two traps at once.
>
> First, our interval model says intervals are subsets of the
> reals R; our notation says [1, Infinity] is just shorthand
> for {x in R | 1 <= x < oo}. Hence it is ONE set, not an
> infinite family of sets like [1, Overflow]. And standard set
> theory unambiguously says [1, Infinity] \subseteq [1, Infinity]
> is true.
>
> Second, even if we used an interval model on the extended
> reals R*, e.g. csets, then Infinity is a "single member" of
> R* just as much as 3.75 is. Not a placeholder for lots of
> fuzzy things. So [1, Infinity] \subseteq [1, Infinity] is
> true there also, because ([1, Infinity] in that model) is
> just ([1, Infinity] in our model) with one extra point added.
>
> That is what mathematicians have understood by R*, and the
> points -oo and +oo in it, since Lebesgue's "Sur une
> généralisation de l'intégrale définie", Comptes Rendus,
> 29 April 1901, and probably earlier; and it has stood the
> test of time.
Well, the French may have understood it in 1901.
I think it took the rest of us a bit longer. :-)
>
> It is also pretty clearly how the authors of 754, both the
> 1985 and the 2008 version, understand infinity.
>
> John
I like John's analysis here (no pun intended :-).
Let me offer one from the world of floating-point.
The function in question is ff(xx) = sqrt(xx^2). And
the question is what happens to intervals evaluated
through this function.
Let xx = [1-e,1+d] be the smallest representable
interval containing 1 entirely in its interior. For
explicit datatypes we will have d = b*e where b = 2
or 10 is our base. For implicit datatypes we will
have d = e = r or [1-r,1+r] for some small r. It
doesn't matter. The reasoning will be the same.
Evaluated to second order, the value of xx^2 is
[1 - 2e + e^2, 1 + 2d + d^2] or
[1 - 2r + r^2, 1 + 2r + r^2]
and, when mapped back down onto our representable
intervals, we will have to widen that result to
[1 - 2e, 1 + 3d] or [1 - 3r, 1 + 3r], depending on the
context. While the implicit case is relatively wider
it is actually substantially smaller absolutely as we
have r << e.
The widening is entirely due to the finiteness of our
representation & is therefore roundoff error.
Now, also to second order, the sqrt is
[1 - (2e)/2 - (2e)^2/8, 1 + (3d)/2 - (3d)^2/8] or
[1 - (3r)/2 - (3r)^2/8, 1 + (3r)/2 - (3r)^2/8]
which rounds to [1 - 2e, 1 + 2d] or [1 - 2r, 1 + 2r].
So the smallest interval surrounding 1 gets widened
by one roundoff error when passing through ff(xx).
No big deal. Other intervals could be worse. Still
others could be exact. It depends.
Now consider the interval xx = [1,large] where large
is sufficiently large that large^2 > maxPos, our
maximum positive representable finite number. (Let
me confine myself to explicits from here on for all
the obvious reasons.)
In this case xx^2 = [1,+infinity]. And this is ALSO
considered just one roundoff error. For indeed, given
a choice between the two representable numbers that
surround the exact result maxPos < large^2 < infinity,
we must choose infinity to preserve containment.
Then the sqrt([1,+infinity]) = [1,+infinity] is
considered to be exact.
So ff([1,large]) = [1,+infinity] must also be
thought of as having only one roundoff error.
Stated in another way, each time we take a step we
risk widening an interval by one roundoff error.
Its just that that last step between maxPos &
+infinity is a real doozy. :-)
Dan