Table 4 proposal version 0.1...
Folks,
John, Michel, & Vincent have all made comments that led
me to modify this proposal.
I still have no good answer for midpoint(Empty) so that
is still not part of this proposal. However, I disagree
with some that it should be NaN on several grounds.
I believe the user would be better served by an arbitrary
choice such as 0 than by introducing errors into a
potentially error free standard. That goal is worth the
occasional arbitrary choice, IMHO.
There are a number of arguments that wid/mag/rad should
all return -inf for Empty. Indeed, I use a similar line
of reasoning with inf(Empty) = +inf & sup(Empty) = -inf.
And while there is plenty of sound mathematical history
behind those arguments, once again, I believe the user
would be better served by an answer of 0 in these cases.
My argument is based on the belief that the user would
be astonished to find that functions that always return
non-negative answers might have a negative exception.
But I would not be greatly put out if we returned -inf.
I WOULD be greatly put out if we returned NaN.
Remember, this is a proposal to all of you for pinning
down the detailed properties of the table 4 functions.
It is not the proposed text of the draft. If accepted,
John will still write it up any way he sees fit.
Here is the updated proposal.
------------------
A Table 4 Proposal
Version 0.1
------------------
OK, I'd like to define the table 4 functions at level 1.
Then list some properties that live there. Then define
the level 1 to level 2 mapping in each case as is useful
for that case. Then show that the properties still hold
at level 2. All the properties are flavors of some weak
monotonicity property appropriate to each function.
That's pretty much all of it. But some things fall out
of this approach.
() All of them are defined for all X (including Empty)
except midpoint & midRad which remain undefined for Empty.
A 754 case could be made for midpoint(Empty) = NaN. But
it is my firm belief that NaN is a bad answer for (the
otherwise error free) 1788. Still, I have no good answer
for midpoint(Empty). I discuss the possibility of choosing
an arbitrary numeric answer for midpoint(Empty) such as 0.
But that arbitrary choice is not part of this proposal.
I just think it would be a good (as in, practical) idea.
I do, however, choose to have midpoint(Entire) = 0. It is
just as arbitrary as with Empty but less objectionable.
() Both the generic (result floating-point type the same
as that which underlies the operand) & formatOf functions
are explicitly defined. The properties still hold no
matter what the result format. But the midpoint will
not return an element of the interior unless there ARE
such elements in the result type. So it has to be taken
into consideration that "interiorness" is a derived
property rather than a fundamental one. Further, I assert
that this is a problem with the coercion not a problem
with the definition of midpoint.
() None of them reference any level 2 structure at all.
Michel pointed out that I could eliminate the reference
to Fmax_F that WAS in the coercion of midpoint by using
round2Zero in a couple of different ways. I chose one
that clamps midpoint to finite results only but does
not change its statistical behavior elsewhere.
() Unless I made a mistake somewhere (please check), all
the monotonicity properties still hold on coercion from
level 1 to level 2 (so long as our arithmetic does also &
we are careful how we coerce them there), all are defined
everywhere (except mid at Empty), & all do what we want them
to do. All very nice if we are going to support proofs.
() It is true that mid is defined pretty much as Michel
would have us do & has the effect of stripping off the
infinity every time you run into a semi-infinite interval.
But I'm beginning to be willing to live with that.
Let me go through the level 1 definitions; the level 1
properties; the coercions; & the level 2 properties for
each function in table 4.
----------
Level 1: inf(X) = { greatest i such that i <= x for all x in X }
Note that inf(Empty) = +inf. This is important.
Property: X \subset Y ==> inf(X) >= inf(Y)
Coercion: inf_F(X) = roundDown_F(inf(X))
That the level 1 property still holds follows from
weak monotonicity on the mapping of the Reals to
the elements of F. That we have inf(Empty) = +inf
is required as Empty is a subset of all sets. Any
semi-infinite on the -inf side & inf(Entire) = -inf.
Also, inf_F(X) may report -inf if F has insufficient
dynamic range to express an otherwise finite inf(X).
All other non-empty sets have finite inf's. So in
any given F it would be sufficient if
inf_F(Empty) >= Fmax_F. But +inf is the only
correct level 1 answer.
----------
Level 1: sup(X) = { least s such that s >= x for all x in X }
Thus, sup(Empty) = -inf.
Property: X \subset Y ==> sup(X) <= sup(Y)
Coercion: sup_F(X) = roundUp_F(sup(X))
Property still holds due to weak monotonicity.
And sup(Empty) = -inf is required at level 1
although sup_F(Empty) <= -Fmax_F is sufficient
for any given F. Semi-infinites on the +inf
side & sup(Entire) = +inf. Also, sup_F(X) may
report +inf if F has insufficient range to
express inf(X). All other non-emptys are finite.
----------
Level 1: mid(X) = for non-empty X only: if (X==Entire) then 0
else (inf(X) + sup(X))/2
Property: X \subset Y ==> if (inf(X)==inf(Y)) then mid(X) <= mid(Y) &
if (sup(X)==sup(Y)) then mid(X) >= mid(Y)
Coercion: mid_F(X) = if (abs_F(round2Nearest_F(mid(X))) = +inf)
then roundToZero_F(mid(X))
else round2Nearest_F(mid(X))
Note: Michel pointed out to me offline that I could
eliminate the reference to Fmax_F in the coercion
by rounding to zero. That would work & not violate
any containment or monotonicity property that I am
aware of. But I was afraid to do so on the grounds
that it might introduce some undesirable statistical
bias towards small numbers. Still, his point has
merit & so I did the coercion so as to effect only
the infinite cases. I can live with that.
Property still holds so long as weak monotonicity
holds for your arithmetic. That is true for 754
& all other arithmetics extant (that I am aware of).
But it was false for some sloppy arithmetics in the
past. One must take care that the arithmetic is
carried out in a fashion that does not overflow.
This includes making sure that (-inf + +inf)/2 does
not happen as an intermediate result. But both can
be accomplished in more than one way. Property is
trivially true for semi-infinite intervals in that
all have the same midpoint which is to the correct
"side" of all finite subsets. Further, the midpoint
is an interior point so long as X HAS points in its
interior that are representable in F. Otherwise,
the midpoint might be an endpoint or even exterior
to X altogether. Note that this is a problem with
F not a problem with the definition of midpoint.
Applying the Principle of Least Astonishment, it is
my firm belief that a finite element of F should
always be returned rather than a NaN on the grounds
that "interiorness" is a derived rather than
fundamental property of midpoint & is violated only
when the user insists on it. That is, either by
trying to split an unsplitable interval or by
insisting on representing the midpoint in a
floating-point type inadequate to the task.
(Aside: this is mostly equivalent to Michel's
midpoint.) Further, that mid returns a number
whether or not it is in the interior of X is
required for the definition of rad to work. The
midpoint of Entire is arbitrary. Any finite value
would do. But 0 is as good as any other & splits
Entire right down the middle (even though it has
no middle). Someday we may need to make a similar
argument concerning midpoint(Empty). Can we choose
0? I don't know yet. But I believe almost any
arbitrary choice will serve us better than a NaN.
(Still, that choice is for the future & not part
of this proposal.)
----------
Level 1: mag(X) = { least m>=0 such that m >= |x| for all x in X }
Property: X \subset Y ==> mag(X) <= mag(Y)
Coercion: mag_F(X) = roundUp_F(mag(X))
Property still holds although intervals of sufficient
finite magnitude may have +inf reported if F has
insufficient dynamic range to express that magnitude.
Other than Empty, [0,0] is the only interval with a
0 magnitude. All others are strictly positive. Both
John & Vincent have argued that the m>=0 should be
removed which would render mag(Empty) = -inf. A case
can be made for this but I, personally, prefer
mag(Empty) = 0 on Least Astonishment grounds. Still,
I would have no great objection to the change.
----------
Level 1: mig(X) = { greatest m such that m <= |x| for all x in X }
Property: X \subset Y ==> mig(X) >= mig(Y)
Coercion: mig_F(X) = roundDown_F(mig(X))
Property still holds although intervals of
sufficiently small mignitude may have 0 reported
if F has insufficient dynamic range to express
such a small number (all others are finite &
positive). The property still holds & this is
generally not a problem as it is a fault of F
rather than the definition of mignitude.
----------
Level 1: wid(X) = if (X==Empty) then 0
else if (X==Entire) then +inf
else sup(X) - inf(X)
Property: X \subset Y ==> wid(X) <= wid(Y)
Coercion: wid_F(X) = roundUp_F(wid(X))
Property still holds if weak monotonicity holds
in your arithmetic. Sufficiently wide finite
intervals may have an infinite width returned
if F has insufficient dynamic range to express
that width. And care should be taken that the
expressions +/-inf - +/-inf either never arise
or are dealt with properly (easy to do). The
"else if" clause is only needed for systems
that choke on +inf - -inf & return a NaN (there
are still such systems around). After that,
there is guaranteed to be one finite term in
the "else" clause. At least at level 1. Both
John & Vincent argue that wid(Empty) = -inf on
much the same grounds as mag(Empty) = -inf.
I prefer 0 on Least Astonishment grounds but
would have no great objection to the change.
----------
Level 1: rad(X) = if (X==Empty) then 0
else mag(X - mid(X))
Property: X \subset Y ==> rad(X) <= rad(Y)
Coercion: rad_F(X) = if (X==Empty) then 0
else mag_F(X - mid_F(X))
This one is a bit tricky. Note that the coercion
is subtly different from all the others & is needed
for both weak monotonicity & (22) to hold. Given
that, property still holds if (1) mid_F returns the
nearest representable finite number in F rather than
a NaN whether or not it is in the interior of X &
(2) weak monononicity holds in your arithmetic.
Some finite intervals will return an infinite result
if F is unable to represent the finite value. Care
should be taken that +/-inf - +/-inf either never
arises or is dealt with properly (easy to do).
Further, Nate's (22)
X \subset [mid_F(X) - rad_F(X), mid_F(X) + rad_F(X)]
holds so long as not both mid_F(X) & rad_F(X) are
infinite. It would also hold for Empty if mid(Empty)
is not a NaN. But chances are, that's too much to
ask for. Equation (22) is going to be needed if we
want to use X -> <mid_F(X),rad_F(X)> to preserve
containment on conversion to mid-rad. We already
have X -> [inf_F(X),sup_F(X)] for inf-sups. We will
need both. Note that we can have rad_F(X) > wid_F(X)/2
in some cases. Indeed, we can have rad_F(X) = wid_F(X).
I could make a good mathematical argument for why this
is so but only another mathematician would fall for it.
In the end, it is because wid() & rad() are defined
very differently. For the moment, we cannot have
rad(X) > wid(X) but if John's & Vincent's arguments
about Empty hold sway we will have rad(Empty)=0 >
wid(Empty)=-inf. Perhaps an argument against it.
Perhaps not. Because John & Vincent would also have
rad(Empty) = -inf. Note that cannot be so & still
preserve containment on conversion to mid-rad. That
is, IF we can settle on an answer for mid(Empty). :-)
Perhaps that works for you. It does not for me.
Vincent pointed out that mag(X - mid(X)) makes no
sense when mid(X) = inf. While true, Vincent also
notes that the width of an interval is unaffected by
translation. Thus, an infinite interval is still
infinite no matter how you shift it. The real
problem would come from the subtraction of infinities
at level 2. And this is avoided by clamping all
midpoints to finite values.
----------
Level 1: midRad(X) = for non-empty X only: <mid(X),rad(X)>
Property: mid property holds for mid part & rad for rad.
Coercion: midRad_F(X) = <mid_F(X),rad_F(X)>
This is a derived function, really. So its
behavior is derived from its components.
Kind of by definition of midRad, we have
that its version of (22) namely
X \subset midRad_F(X)
holds so long as not both mid_F(X) & rad_F(X)
are infinite & mid(X) not NaN. BTW, this
suggests to me that we might define an infSup(X)
which returns [inf(X),sup(X)]. And maybe both
this & midRad belong elsewhere than table 4.
----------
Well, I've shot my bolt. Again.
Is it any closer than the first?
Dan