[std-interval] Revised document available
Dr John Pryce
j.d.pryce at ntlworld.com
Mon Sep 18 23:48:27 PDT 2006
Dear std-intervalers,
At 09:16 12/09/06, Sylvain Pion wrote:
>A revised version of the proposal is now available at:
>http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n2067.pdf
My first comments on the revised proposal were
about the use of "undefined". In this message, as
a second theme, I will comment on the status of
infinity (which I write oo) in the proposal.
A.
Sylvain and colleagues: your text (by this I mean
the draft standard text, excluding the preamble)
has at least one clause (p17 #16) that explicitly
prohibits a cset-based model. In particular your
present text prohibits Sun interval arithmetic,
and FILIB++ extended arithmetic.
I have no complaint about this in itself - the
ISL proposal explicitly allows ONLY a cset-based
model. We should have liked to be more
accommodating, but a draft that had both in one
document got so messy that we could not be sure it was logically consistent.
Therefore I am moving to favour two standards,
identically structured as far as possible,
defining a non cset-based and a cset-based model
respectively. What do people think?
B.
I do not feel the text makes it clear whether the
platform's arithmetic MUST support oo - which
more or less amounts to using IEEE arithmetic. On p4 we read
The value of whole() requires that T has an infinity
(in std::numeric_limits<T>).
and the definition of "whole()" has
Requires: std::numeric_limits<T>::has_infinity.
For the record the draft C++ standard says the
following (I believe "Required behavior:" and
"Requires:" paragraphs are the same thing).
>17.3#3
>Descriptions of function semantics contain ...
> Requires: the preconditions for calling the function.
>
>17.4.3.8 Required paragraph [lib.res.on.required]
>1 Violation of the preconditions specified in a
>functions "Required behavior:" paragraph
>results in undefined behavior unless the
>functions "Throws:" paragraph specifies
>throwing an exception when the precondition is violated.
Usually a "Requires:" gives preconditions on the
ARGUMENTS to a function (and the only other
"Requires:" in your text does just that). But
this one is a precondition on the PLATFORM. So it has the effect
This function MUST be provided on any platform, but on a platform that
does not support oo this function must never be called!
Actually one can easily (at the cost of some
performance penalty) encode "whole" and other
infinite intervals on an arithmetic without oo,
using reverse-ordered bounds, as recent postings to this group have hinted.
C.
More on ambiguous support for oo. The definition
of an interval<T> object 26.6#3 uses the phrase
"is specified by two values of type T ...". Implications of this wording are:
(a) If T does not support oo then infinite intervals are forbidden: one is
not permitted to encode them by some other method.
(b) A midpoint-radius (m-r) representation is forbidden: not explicitly, but
de facto. I don't think m-r is a good system on the real line (recall Rump's
INTLAB uses it in the complex plane) but I use it as a test. I don't think
a standard should rule out m-r, and believe one that does so is too
implementation-oriented.
The reason m-r is excluded is that it defines an interval by two type T numbers
m, r such that the exact mathematical interval is [m-r, m+r]. In general
these endpoints are not exact type T numbers,
but the text says they must be.
(c) Implementations that support non-closed intervals are explicitly forbidden.
This is indirectly related to handling oo, and
I will return to it in a later
message.
Actually George pointed out this is not
entirely true. By playing around with
the class hierarchy one can add other kinds of interval to those this
standard restricts one to. But it would be nice to permit them explicitly.
The ramifications of (a) are such that unless you
rewrite 26.6#3, you may as well say explicitly
that this standard only applies to IEEE systems. On systems without oo:
- You have no way to handle overflow, including conversion, say, of
interval<double>(x) to interval<float> where x is above float's
largest representable number.
- You cannot represent 1/[0,1].
etc.
D.
You could change 26.6#3 to say "... specified by
two values, denoted by [xlo,xhi], which are
either finite of type T, or infinite, and xlo is never greater than xhi."
This permits special encoding of infinite
intervals on systems without oo. However it still
forbids m-r form, so I feel it also is too implementation-oriented.
In the ISL proposal, I tried to get round this by
not saying anything to influence the
representation method, but merely saying that
every singleton interval<T>, x=[t,t] where t is
of type T, had to be stored exactly. That is, you
could recover t by doing inf(x), for example.
This gives interval<T> a "minimum QOI" by tying
it loosely to the precision of T, while allowing
both bounds and m-r representation. Maybe someone
will show this idea is seriously flawed but it
was the best I could think of ...
E.
Suppose 26.6#3 is reworded on the above lines.
Then we have a text that mandates (and makes
possible) support of whole and other infinite
intervals whether the arithmetic supports oo or
not. I have no basic theoretical quarrel with it. However:
1. It still does not state the Abstract Interval
Model (or preferably, the range of models)
supported by the standard. This makes it harder
to discuss alternatives and opportunities.
2. In particular - see 5.1 of the Pryce-Corliss
paper I circulated - in the cset context one gets
interesting opportunities from allowing (some, or
all possible) intervals with non-closed
endpoints. In particular allowing open ends at 0
and oo cures Sylvain's [REALMIN,REALMAX]^4 example of nasty cset behaviour.
It may be worth exploring this for a non-cset
system. For instance, allowing 1/[1,+oo) to be
represented as (0,1] rather than [0,1].
I think a small change to 26.6#3 would make such
intervals PERMISSIBLE without making them MANDATORY.
3. My main objection to the way this text treats
oo is that since 1985 - see interesting account
at http://www.cs.berkeley.edu/~wkahan/ieee754status/754story.html
- we have an arithmetic system, IEEE 754, in
which oo is treated systematically and
consistently as an actual number. (Except for the
behaviour of signed zeros, IEEE implements the
arithmetic of the extended reals R* that has been
used by mathematicians since around 1890.)
Moreover, IEEE 754 offers rounding modes
deliberately designed to help interval
arithmetic. And as far back as 1968, W.Kahan
gives a lecture course on a practical interval
arithmetic in which oo is an actual number.
Yet, 20 years later, we set out a standard for
interval arithmetic in which oo is not a number:
the existence of IEEE's -Inf and +Inf is just
used as a convenient way to encode infinite
intervals of the reals R, not of the extended
reals R*. Yes, choosing such a standard is much
better than no standard at all. But I cannot
believe that 10 years hence, anyone will praise
the wisdom of those who chose it rather than a
standard that supports infinity systematically.
BTW some people feel that the IEEE designers
"didn't really intend" Inf to be infinity, but
just to mean some finite number too large to
represent. But then, why is it that IEEE defines
Inf times 0 to be NaN rather than 0?
4. One other consequence of choosing this
standard is that, at the level of expressions
rather than individual elementary operations, one
loses the opportunities for optimization of
interval code offered by the Rational
Rearrangement Theorem of cset theory. It remains
to be seen how powerful a tool this is compared
with other methods for reducing "interval bloat",
such as constraint propagation, and methods being
studied by Lee Winter. But it should not be dismissed.
Regards
John Pryce
Dr John and Mrs Kate Pryce
142 Kingshill Rd
Swindon, Wiltshire SN1 4LW
UK
Tel (+44)1793-331062
More information about the Std-interval
mailing list