Version v3.0 of Vienna proposal
Attached is the
Vienna proposal for interval standardization
Arnold Neumaier, Vienna
Version v3.0 of November 21, 2008
with improvements suggested by remarks of
Bo Einarsson, Maarten van Emden,
Michel Hack, Nate Hayes, Ulrich Kulisch,
Sylvain Pion, John Pryce,
and Hermann Schichl
In spirit, I took into account all contributions to the
discussion on the stds-1788 mailing list that I received before
November 21, 2008, 18:00 local time, though this proposal takes
a definite stand on all controversial issues.
Please consider this proposal as a piece of scientific advice
of the Computational Mathematics Group in Vienna, intended to give
the future interval standard a maximal impact without imposing
unreasonable demands on implementors and users.
None of our group in Vienna will take part in the voting process
that determines the final standard. As in the past, we shall live
with whatever is made available by implementors, and modify it
to suit the needs of our applications to global optimization,
constraint programming, and computer-assisted proofs.
However we believe that
1. the proposal is fair to everyone in the interval community,
2. apart from minor amendmends it has a good chance of finding an
overwhelming majority, and
3. any significant deviation from the basic decisions taken in this
proposal and spelled out in Part 1 will degrade the quality of
the standard.
Present:
With exactly 25 pages of 64 lines each, it is nearly tripled in size
compared with the previous public version 2.11 of November 10, 2008,
since many things have been spelled out in detail that were only
summarized before.
Moreover, an extended Part 1 was added that contains a concise summary
of the basic assumptions (some of which may be controversial) upon
which the remaining document is based. The items in Part 1 are grouped
such that separate voting on each issue is meaningful.
In addition, there are numerous changes inspired by the general
discussion and by remarks on version 2.11 by the people mentioned
above.
In particular, comprehensive discussions with Michel Hack, who read
and commented in detail several intermediate versions, had a strong
influence on the present version.
Some time next week, I'll send out a separate email commenting on the
position the proposal takes with respect to linear interpolation
operations (cf. Section 5.8) and modal intervals (cf. Sections 1,2,
1.4 and 5.9), based on prior off-line discussions with a few people
not on the mailing list, and with Alexandre Goldsztejn, Nate Hayes,
and Svetoslav Markov, who already contributed to the discussion on
stds-1788. Most likely, they will present themselves their own,
deviating view on the matter.
Past:
Version v1.0 (not named so) was the text operations.txt submitted to
the mailing list on September 24, and just contained something accorded
with my collegue Hermann Schichl.
Version v2.0 of November 4 was created by me based on v1.0 and
the discussion until that date.
Version v2.11 of November 10 was the slightly corrected version based on
corrections that were discussed on the list.
Afterwards, I received mostly privat emails discussing smaller or larger
changes to v2.11, and I found it easier to discuss intermediate versions
offline with the people involved. In particular, comprehensive
discussions with Michel Hack, who read and commented in detail several
intermediate versions, had a strong influence on the present version.
Essentially, each working day a version was exchanged with him,
and email comments (not attachments) were received and addressed.
In addition, I took into account the discussion on the list and
comments from others (who didn't see all intermediate versions).
Now some sort of fixed point has been reached, resulting in
Version v3.0 presented here.
Future:
I'd like to keep this way of working, since I believe that details
about misprints, formulations, etc. are not of general interest for
the genaral subscriber to the list.
Thus please discuss things that are likely to be controversial
(or where you don't reach agreement with me) on the list (always based
on v3.0), and discuss details that are only of technical interest
off-line, sending them directly to me at <Arnold.Neumaier@xxxxxxxxxxxx>
based on whatever is the most current version v3.x you received.
When some sort of fixed point has been reached again (or, if sensible,
earlier), I'll post version v4.0 to the list.
Arnold Neumaier
Vienna proposal for interval standardization
Arnold Neumaier, Vienna
Version v3.0 of November 21, 2008
with improvements suggested by remarks of
Bo Einarsson, Maarten van Emden,
Michel Hack, Nate Hayes, Ulrich Kulisch,
Sylvain Pion, John Pryce,
and Hermann Schichl
This is a semiformal document written in a form that should be not
too difficult to transform into a formal, complete and fully precise
document specifying the standard to be.
With exactly 25 pages of 64 lines each, it is nearly tripled in size
compared with the previous public version 2.11 of November 10, 2008,
since many things have been spelled out in detail that were only
summarized before.
Moreover, an extended Part 1 was added that contains a concise summary
of the basic assumptions (some of which may be controversial) upon
which the remaining document is based. The items in Part 1 are grouped
such that separate voting on each issue is meaningful.
In addition, there are numerous changes inspired by the general
discussion and by remarks on version 2.11 by the people mentioned
above.
In particular, comprehensive discussions with Michel Hack, who read
and commented in detail several intermediate versions, had a strong
influence on the present version.
Please send technical corrections and comments directly to me
at <Arnold.Neumaier@xxxxxxxxxxxx>, while addressing contributions
likely to be controversial to the whole mailing list.
Arnold Neumaier
Table of contents
-----------------
This version has the parts rearranged, and part and section numbers
adapted to reflect the new ordering. For compatibility, the old
section numbers (mostly from v2.11, but some only from intermediate
versions) are given below.
Part 1. Basic assumptions
new: 1.0, 1.1, 1.2, 1.3, 1.4, 1.5, 1.6, 1.7, 1.8, 1.9
old: 0.0, 0.1, 0.2, 0.3, 0.4, 0.5, 0.5a, 0.6, 0.6a, 0.7
Part 2. Representation and semantics
new: 2.0, 2.1, 2.2, 2.3, 2.4, 2.5, 2.6, 2.7
old: 1.0, 1.1, 1.2, 1.3, 1.4, 1.5, 1.6, 1.7
Part 3. Arithmetic operations
new: 3.0, 3.1, 3.2, 3.3, 3.4, 3.5, 3.6, 3.7, 3.8, 3.9, 3.10, 3.11, 3.12, 3.13
old: 3.0, ---, 3.1/3.4, 3.2, 3.5, 3.3, 3.6, 3.7, 3.8, 3.9, 3.10, 3.11, 3.12, 3.13
Part 4: Mixed operations and type conversion
new: 4.0, 4.1, 4.2, 4.3, 4.4
old: 5.0, 5.1, 5.2, 5.3, 5.5 (old 5.4 is new 5.10)
Part 5: Non-arithmetic operations
new: 5.0, 5.1, 5.2, 5.3, 5.4, 5.5, 5.6, 5.7, 5.8, 5.9, 5.10
old: 4.0, 4.9/4.6, 4.1, 4.8, 4.2, 4.3, 4.4, 4.5, 4.10, 4.7, 5.4
Part 6. Text to interval conversion
new: 6.0, 6.1, 6.2, 6.3, 6.4, 6.5, 6.6, 6.7, 6.8
old: 2.0, 2.1, 2.2, 2.3, 2.4, 2.5, ---, 2.6, 2.7
Part 7: Useful directed rounding properties
new: 7.0, 7.1, 7.2, 7.3, 7.4, 7.5, 7.6, 7.7, 7.8, 7.9, 7.10, 7.11
old: 6.0, 6.1, 6.2, 6.2a, 6.3, 6.4, 6.4a, 6.5, 6.6, 6.7, 6.8, 6.9
Part 1. Basic assumptions
-------------------------
1.0. Theme of Part 1
This part summarizes basic assumptions upon which the
remaining document is based, grouped such that separate voting on
each issue is meaningful.
1.1. The number system
This document restricts attention to interval arithmetic as the
collection of operations underlying the practice of rigorously working
on a computer with certain (exactly known) and uncertain (i.e.,
possibly not exactly known) real numbers, represented as intervals.
All operation symbols in this document denote (unless explicitly said
otherwise) exact operations on real numbers.
Complex numbers or complex intervals are nowhere discussed in
this document.
Finite numerals (integers, finite floating-point numbers, fixed-point
numbers, etc.) denote real numbers, which define their value.
Other numerals are classified as +Inf,-Inf, and NaN, depending on
whether their value is +Inf, -Inf, or undefined; they do not denote real
numbers, no matter how they were generated.
(See Section 2.1 about the values of numerals.)
1.2. The set of intervals
Textbook intervals are closed and connected sets of real
numbers, the closed intervals familiar from mathematical textbooks.
Nonempty textbook intervals are represented by two bounds, their
infimum and their supremum. (See also Section 1.6.)
Standard intervals denote textbook intervals whose infimum and supremum
are representable by two B-numerals (B for bounds, see Section 1.6).
Nonstandard intervals do not denote textbook intervals.
Except in Part 1, Part 2, and Section 5.9, where nonstandard intervals
are discussed, the unqualified word 'interval' always refers to
standard intervals with the above textbook interpretation.
This excludes infinite numbers as element of an interval,
which would give unduly pessimistic results in cases such as division
by an interval with a zero endpoint.
It also excludes the consideration of arithmetic based on a
midpoint-radius representation (which is considered only in conversion
between text and interval).
It also excludes the consideration of arithmetic based on
nonstandard intervals (Kahan intervals, Kaucher intervals,
modal intervals).
However, the availability of nonstandard intervals allows
(but does not force) implementors to extend the functionality of
interval arithmetic to handle Kahan intervals or Kaucher intervals
consistent with their traditional interpretation.
Moreover the availability of division with gaps (Section 5.7) and
of dual operations (Section 5.9) allows a reasonably efficient
implementation of Kahan interval arithmetic, Kaucher interval
arithmetic, and modal interval arithmetic, the latter for pairs (xx,p)
consisting of a standard interval xx and a Boolean variable p which
encodes the interpretation mode (proper or improper) of xx.
1.3. Arithmetic operations on intervals
Nullary, unary, and binary interval operations are defined
(in Part 3) in a forward mode in such a way that
- they can be used inside arbitrary arithmetic expressions and yield
an enclosure of the range of the function defined by this
expression on the set of all arguments inside the corresponding
intervals for which the expression makes sense in real arithmetic;
- the result is always a standard interval if the inputs are standard
intervals;
- the most basic single operations give the tightest possible enclosure.
In addition, to support correct constraint propagation, there are
reverse operations (Sections 3.9 and 3.11) that enclose the set of
solutions of equations involving a single operation only, restricted
by enclosures of the arguments and results within given intervals.
This excludes division with a noninterval set result,
which instead is provided as division with gap (Section 5.7).
It also excludes cset arithmetic (without infinity-as-number)
which is unduly pessimistic in cases such as division by an interval
with a zero endpoint.
The advantages that csets had in the past for applications to
constraint propagation and in the interval Newton method are
fully conserved by the availability of the forward and the reverse
mode, needed for optimal results in constraint programming and
global optimization.
1.4. Non-arithmetic operations related to intervals
A number of non-arithmetic operations are needed to support
the use of intervals. The list given in Part 5 is fairly liberal,
and in particular contains
- division with gap (Section 5.7) to support Kahan arithmetic or
arithmetic based on lists of intervals;
- the tightest enclosure of a scalar product of two vectors of
B-numerals (Section 5.7) to support applications to least
significant bit algorithms;
- linear interpolation and extrapolation operations, required for
applications in computational geometry (Section 5.8),
- optional dual operations (Section 5.9) to support Kaucher arithmetic
and modal arithmetic;
Only the minimal support needed to enable these uses is provided.
1.5. Conversion of text and numerals
The conversion of text (in Part 6) and numerals (in Part 4) is
guided by the principle that it should allow rigor to be easily
specified by the user, and that conversion results in intervals which
preserve rigor throughout semantically correct programs.
In particular, it is considered to be semantically incorrect
- to use the constructor interval(x) with a numeral
x not known to be finite and exact;
instead one should use intervalabs or intervalrel; see Section 4.5;
- to use in a compiled arithmetic expression that results in an
interval any inexact unary or binary arithmetic operation between
two nonintervals;
- to use a binary operation involving an interval and a noninterval
number if the latter is not known to be finite and exact;
- to introduce intervals except through operations conforming to the
standard. (Additional care must be taken with intervals constructed
from computed endpoints, and with operations producing nonstandard
intervals; this may lead to semantic errors unless backed up by
appropriate theory.)
For example, if zz is an interval variable, writing
interval('1.1'), interval('1e309'), '1.1'*zz, or '1e309'*zz
or - in languages where user-defined literals are available -
interval(1.1x), interval(1e309x), 1.1x*zz, or 1e309x*zz
is semantically correct. On the other hand, writing any of
interval(1.1), interval(1e309), 1.1*zz, or 1e309*zz
is semantically incorrect, unless it is known
- either that 1.1 or 1e309 are represented exactly by the underlying
system,
- or that these constants are translated at compile time to one of
the correct forms mentioned above.
On the other hand, relying on the behavior of the compiler or the
underlying system is not recommended since it makes the program not
portable.
1.6. Numerals representing bounds
B-numerals (representing the bounds of intervals) are numerals
of a particular, distinguished format, most likely binary 64-bit
floating point data.
As stated, this excludes the consideration of multiple formats for
interval arithmetic implementations. (However, changes to incorporate
multiple interval formats are minor, and could be accommodated at a
later stage.)
High precision rigorous calculations and calculations with intervals
with extremely large bounds are probably best done by representing
uncertain numbers as triples (x,ex,ee) consisting of a variable
precision numeral x with the same basis (or a power of it) as used for
B-numerals, an integer exponent ex, and a standard interval ee,
representing an arbitrary number xtilde with
(xtilde-x)/basis^ex in ee
thus making optimal use of standard multiprecision packages and
standard interval arithmetic implementations.
1.7. Relation to IEEE 754-2008
Care has been taken to make the bulk of the proposed standard
(Parts 1-6) independent of the arithmetical properties of numerals,
and hence of the IEEE 754-2008 floating-point standard.
However, Part 7 indicates desirable properties of directed rounding
deviating from the IEEE 754-2008 floating-point standard
that would facilitate implementation.
1.8. Suggestions for hardware implementation
A proposed minimal useful set of hardware operations which would
significantly speed up existing applications in constraint programming,
global optimization, and computational geometry are the following
operations defining core interval arithmetic.
- forward and reverse interval operations for
plus, minus, times, divide, sqr (Sections 3.8-3.11 and 7.9)
- mixed operations with one interval argument for
plus, minus, times, divide (Section 4.2)
- forward sqrt, exp, log (Sections 3.8-3.9)
- linearInt, linearExt, linearInv (Sections 5.8 and 7.11)
- mid, rad (Sections 5.2 and 7.11)
- division with gaps (Section 5.7)
- optimal enclosure of inner product (Section 5.7)
These operations might be singled out to represent (together with the
operations from Section 2.5) level 1 of the standard; the remaining
operations would represent level 2.
An appendix may suggest explicit model algorithms for all level 1
operations.
1.9. Optional features
In a number of cases of minor importance (often indicated by the word
''may''), suggestions were made what might or might not be included
into the standard.
1.10. Value-changing optimizations
These should be handled similar to Section 10.4 of IEEE-754-2008.
Transformations are allowed if and only if they would be exact
in exact real arithmetic and provably lead to enclosures contained
in the enclosures obtained by using the original expression.
A (nonexhaustive) list of allowed and forbidden transformations should
be provided in an appendix to the standard.
For example, zz = xx^2 or zz = xx*xx or the sequence of assignments
yy = xx; zz = xx*yy;
may be optimized to zz = sqr(xx), but [-2,3]*[-2,3] may not be
optimized to sqr([-2,3]).
When interval arguments to a function are passed by value, the arguments
must be treated as if they were independent. When interval arguments
to a function are passed by reference, the arguments may be treated
by an optimizing compiler as the expression they denote.
The programmer must be able to enable or disable expression
transformations of the above kind for particular blocks of a program.
(Unlike everything said before, the contents of this section is nowhere
detailed in the remainder of this proposal.)
1.11. Other issues
Things not yet treated which also need to be addressed:
- conversion between different interval formats (should there be any)
- perhaps more usage suggestions/examples
- perhaps more implementation suggestions
- expand on Section 1.10
Part 2. Representation and semantics
------------------------------------
2.0. Theme of Part 2
This part defines the representation and semantics of intervals,
regarded as machine representations of uncertain real numbers.
The possible values are required to form a subset of the closed and
connected set of real numbers represented by the interval.
2.1. Assumptions about numerals
The numerals (integers, finite floating-point numbers, +Inf, -Inf, NaN,
fixed-point numbers, etc., independent of their format) representable
in a particular implementation form a finite set F.
There is a partial mapping from F to R^* = R union {-Inf,+Inf},
the order completion of the set R of real numbers, which assigns to
certain elements x of F their value value(x).
NaN, -Inf, +Inf, and 0 denote any numeral x such that value(x) is
undefined, -Inf, +Inf, and 0, respectively; Inf and +Inf are used
synonymously.
One particular format of numerals (most likely binary 64-bit floating
point data) is distinguished to represent bounds of intervals.
Numerals in this format are called B-numerals.
It is required that the B-numerals NaN, -Inf, +Inf, and 0 exist.
(See Section 1.6 for possible multiple formats of B-numerals.)
2.2. Representation of intervals, bounds, endpoints
An interval is represented by two B-numerals called the lower
bound and the upper bound. Both the lower the and upper bound are
referred to as a bound or endpoint of the interval.
In this documents, intervals are written either with explicit bounds
as [l,u], with l and u replaced by the intended lower and upper bound,
respectively, or as single object by a repeated letter, such as xx,
yy, zz, aa, bb, cc, gg. In the latter case, a generic element of the
interval (i.e., the uncertain number represented by the interval)
is denoted by the corresponding single letter; e.g., x in xx.
Empty denotes the empty interval, and Entire the interval consisting
of all real numbers.
Two intervals are regarded as equal if the values of the lower bounds
agree and the values of the upper bounds agree, otherwise as distinct.
Which of the equivalent representations of an interval is used may
depend on the implementation.
Thus if there are B-numerals +0 and -0 both with value 0
then [-0,Inf] and [+0,Inf] are equal. However, an implementation
may choose to represent the interval [-0,Inf] as [+0,Inf].
(This is relevant for the considerations in Part 7.)
2.3. Standard intervals
A standard interval has the form [l,u], where one of the following
holds:
(i) Both bounds are finite, and l <= u.
(ii) One bound is finite, and l = -Inf or u = +Inf.
(iii) l = -Inf and u = +Inf (entire interval Entire).
(iv) l = NaN and u = NaN (empty interval Empty).
A standard interval [l,u] represents in case (i)-(iii) the set
(equivalently an arbitrary number from the set) of all real numbers x
with value(l) <= x <= value(u), and in case (iv) the empty set
(equivalently, no number).
In particular,
- standard intervals describe closed and connected sets of real
numbers, including the empty set Empty = [NaN,NaN] and the set
Entire = [-Inf,Inf] of all reals;
- numeral bounds with value 0, +Inf, -Inf, or NaN have the
same meaning in standard intervals independent of their
representation;
- bounds with subnormal numbers (formerly known as denormalized)
are valid bounds for standard intervals;
- Since they are not real numbers, +Inf, -Inf, and NaN are not members
of any standard interval (though they may be bounds);
- standard intervals do not represent closed disconnected sets such
as [-Inf,-1] union [1,Inf].
Remark.
In IEEE 754-2008, there are multiple NaNs having a payload that
propagates; see Section 7.2 of the IEEE 754-2008 standard.
This may be used to implement labelled empty sets
which carry debugging information about the operation which created
the empty set in the first place, and thus to distinguish between
empty sets produced by exceptions (''Not-an-Interval, NaI'') and
genuine empty sets.
The standard may perhaps describe how this feature should be used,
and if so, how the labels should propagate in operations. This may
also need a recommendation (to be added to Part 7) about how two
NaNs with payload propagate under directed rounding in a binary
operation (which is left open in IEEE 754-2008).
2.4. Nonstandard intervals
An interval [l,u] is nonstandard if it is not a standard interval.
No specification is made for the meaning of nonstandard intervals.
In particular, [-Inf,-Inf] and [+Inf,+Inf] are nonstandard intervals;
intervals with exactly one bound NaN, and intervals [l,u] with l>u
are also nonstandard.
2.5. Operations checking the semantics
Here for brevity 1 = true, 0 = false.
1. There is an operation Empty() with value Empty.
(In programming languages, it is recommended to have a
corresponding constant Empty.)
There is an operation isEmpty(xx) that outputs 1 or 0
depending on whether or not the interval xx is Empty.
2. There is an operation Entire() with value Entire.
(In programming languages, it is recommended to have a
corresponding constant Entire.)
There is an operation isEntire(xx) that outputs 1 or 0 depending
on whether or not the interval xx is Entire.
3. There is an operation isStandard(xx) that outputs 1 or 0
depending on whether or not the input interval xx is standard.
4. There is an operation standard(xx) that outputs xx if xx
is standard, and Empty otherwise.
5. There is an operation standardInterval(l,u) that returns the
interval [l,u] from two numerals l and u if it is
standard, and Empty otherwise.
6. There is an operation anyInterval(l,u) that creates the
interval [l,u] from two numerals l and u without
checking whether or not it is standard.
7. There is an operation areIdentical(xx,yy) that outputs for two
intervals xx=[l,u] and yy=[l',u'] the value 1 if both l and l'
represent the same value and u and u' represent the same value,
or if all four bounds are NaN, and otherwise the value 0.
There is an operation areDistinct(xx,yy) that outputs
not(areIdentical(xx,yy)).
Note the difference between areIdentical, areDistinct and the
comparison operations equalToAA, unequalToAA from Section 5.4.
8. There is an operation isCompact(xx) that outputs 1 or 0 depending
on whether or not the interval xx represents a compact textbook
interval.
In particular, the output is zero for nonstandard intervals.
9. There is an operation inf(xx) that returns for any interval
xx=[l,u] the lower bound l.
10. There is an operation sup(xx) that returns for any interval
xx=[l,u] the upper bound u.
11. There is an operation isIn(x,xx) or an operation contains(xx,x)
(Which one of the two, or both?)
that outputs 1 or 0 depending on whether or not the numeral x is in
the standard interval xx.
The behavior for a nonstandard interval xx is not specified.
In particular, isIn(x,xx) returns 0 when x is +-Inf and the
interval is standard.
Perhaps one may add further operations isPositivelyBounded,
isNegativelyBounded, isSingleton, although these can been easily
constructed from the operations provided in Section 5.2.
2.6. Scope of operations
All operations with interval input shall be defined by the
implementation both for standard and for nonstandard intervals,
although the behavior for nonstandard input is not defined by this
standard.
All operations with interval output permit both standard
and nonstandard intervals as output. However, all arithmetic
operations (see Part 3) have standard intervals as output if all
interval inputs are standard intervals.
With the exception of the operations listed in Section 2.5,
the standard makes no specification for the result of operations
involving some nonstandard interval since there are several mutually
conflicting extensions of the interval calculus interpreting
[l,u] for l>u, including those which interpret them either as
Kahan-style intervals (complements of open intervals)
or as Kaucher-style intervals (involving ideal objects that allow
to define the inverse operation for addition).
2.7. Convention on using the word ''interval''
In the remainder of this document, all unqualified intervals will
be assumed to be standard intervals (rather than nonstandard intervals
or intervals in the mathematical sense).
Part 3. Arithmetic operations
-----------------------------
3.0. Theme of Part 3
This part specifies the behavior for interval arguments of arithmetic
operations either required by the standard, or of further
implementation-dependent arithmetic operations. An implementation is
standard-conforming only if all its required and all its
implementation-dependent arithmetic operations conform to the
requirements below.
3.1. Arithmetic operations on intervals
Arithmetic operations on intervals are based on corresponding real
operations, whose names are used in overloading arithmetic expressions.
All interval operations are specified in such a way that the evaluation
of an arithmetic expression involving intervals only contain all
possible results of the arithmetic expression obtained by specializing
each interval to an arbitrary real number contained in the interval.
In certain cases, the containment is pessimistic, in which case more
elaborate range enclosure methods discussed in the literature must be
used in place of simple interval evaluation.
An arithmetic expression involving an empty interval always evaluates
to Empty. (This need not be the case for expressions involving
non-arithmetic operations.)
3.2. Accuracy modes
Interval arithmetic operations are implemented in one of three
accuracy modes, 'tightest', 'accurate', or 'valid'. An operation
may be implemented in any accuracy mode if only 'valid' is required,
in the accuracy modes 'tightest' or 'accurate' if 'accurate' is
required, and must be implemented in the accuracy mode 'tightest'
if 'tightest' is required.
There is a function accuracy(f) that outputs, for each arithmetic
constant, unary operation, or binary operation with name passed as
string f, the actually implemented accuracy mode (which may be tighter
than required), or 'missing' if the string does not represent
an implemented operation. This information should also be available
at compile-time.
If ENUM (enumerated) types are available, the output would naturally
be ENUM; e.g., in C:
enum accuracy_enum { tightest, accurate, valid, missing };
typedef enum accuracy_enum accuracy_t;
3.3. Propagation of Empty
Independent of the accuracy mode, all arithmetic operations with
one or more arguments Empty must have the result Empty, propagating
labels in case of labelled empty sets. (The case of conflicting labels
must be discussed.)
(Non-arithmetic operations need not propagate Empty.)
3.4. Test for continuity and undefined
For every unary or binary operation which is not everywhere continuous,
- the possiblyUndefined flag must be raised when the operands contain
values for which the operation is not defined (not a finite real
number), and
- the definedButPossiblyDiscontinuous flag must be raised when the
operation is defined (a finite real number) for all values contained
in the operands but is discontinuous for at least one of these values.
This is necessary in order to correctly infer validity and continuity
of function evaluation, which is indispensable for the application of
existence theorems.
Examples:
1/xx with 0 in xx raises possiblyUndefined.
sqrt(xx) with xx=[-1,1] raises possiblyUndefined.
sign(xx) with xx=[-1,1] raises definedButPossiblyDiscontinuous.
3.5. Usage of the word ''hull''
The hull of a set of real numbers refers to an interval (in the
sense of this standard) containing the set, with the additional
property that:
1. in accuracy mode 'tightest', the interval is the tightest interval
containing the set.
2. in accuracy mode 'accurate', the interval is contained in
the tightest interval containing all sets obtained from arguments
whose Hausdorff distance from the inputs is at most one ulp
of the corresponding inputs (in the sense that the symmetric
difference consists at most of endpoints of the wider interval).
3. in accuracy mode 'valid', no further requirement is imposed.
3.6. Table: Arithmetic constants
pi 4*atan(1)
twopi 8*atan(1)
pihalf 2*atan(1)
e exp(1)
goldenratio (1+sqrt(5))/2,
and implementation-dependent arithmetic constants.
3.7. Arithmetic constants as intervals
For each arithmetic constant from Table 3.6,
there is a nullary operation resulting in the tightest interval
containing this constant.
In exact expressions (Section 6.7), nullary operations may be called
either by writing the name or by adding after the name the
characters (); e.g., both pi and pi() are acceptable.
3.8. Table: Unary arithmetic operations
The first column gives the name of a real unary operation, the second
its use in arithmetic expressions (Section 6.6), the third the minimal
accuracy requirement (Section 3.3) for the interval version as
specified in Section 3.9, the fourth whether a reverse mode
(Section 3.9) is required.
negation - x tightest
square sqr(x), x^2 tightest reverse
inverse inv(x), 1/x tightest reverse
abs abs(x) tightest reverse
sign3 sign(x) tightest
ceiling ceil(x) tightest
floor floor(x) tightest
sqrt sqrt(x) tightest
exp exp(x) tightest
log log(x), ln(x) tightest
log10 log10(x) tightest
log2 log2(x) tightest
intpow x^k (see 3.12) accurate reverse
root x^(1/q) (see 3.13) accurate reverse
ratpow x^(p/q) (see 3.13) accurate reverse
sin sin(x) accurate reverse
cos cos(x) accurate reverse
tan tan(x) accurate reverse
sinh sinh(x) accurate
cosh cosh(x) accurate reverse
tanh tanh(x) accurate
asin asin(x), arcsin(x) accurate
acos acos(x), arccos(x) accurate
atan atan(x), arctan(x) accurate
asinh asinh(x), arsinh(x) accurate
acosh acosh(x), arcosh(x) accurate
atanh atanh(x), artanh(x) accurate
and implementation-dependent unary arithmetic operations with
implementation-specified calling syntax in arithmetic expressions
and arbitrary accuracy mode.
Here sign3 is the 3-valued sign, with sign(0)=0.
The precise list of operations to require or to recommend may also
be discussed; cf. Section 3.13 for root and ratpow.
Suggested further unary operations (forward mode only; relevant for
constructing optimal linear and quadratic underestimators):
exp2(x) := (e^x-1-x)/x^2
sin2(x) := (sin(x)-x)/x^2
cos2(x) := (cos(x)-1)/x^2
sinh2(x) := (sinh(x)-x)/x^2
cosh2(x) := (cosh(x)-1)/x^2
extended by continuity to x=0.
3.9. Unary arithmetic operations on intervals
For each (partial) unary operation <phi> from Table 3.8,
there is a unary forward interval operation <phi>Hull defined by
<phi>Hull(xx) = convex hull of the set of <phi>(x) with x in xx
such that <phi>(x) is defined and finite,
and, if required,
a binary reverse interval operation <phi>Inv defined by
<phi>Inv(zz,xx) = convex hull of the set of x in xx for which
<phi>(x) is defined, finite, and in zz.
Here the second argument is optional, with default xx=Entire if absent.
Within arithmetic expressions, the unary operator <phi>
applied to an interval is always overloaded by <phi>Hull.
Note that inverse functions available as standard functions are
unary operations in their own right, with the usual definition.
Thus there will be a sqrthull in addition to sqrinv, and
sqrthull(9)=3, while sqrinv(9)=[-3,3].
3.10. Table: Binary arithmetic operations
Notation is as in Section 3.8.
plus x + y tightest
minus x - y tightest
times x * y tightest reverse
divide x / y tightest reverse
min min(x,y) tightest
max max(x,y) tightest
pow x^y (see 3.12) accurate reverse
atan2 atan2(x,y) accurate reverse
and implementation-dependent binary arithmetic operations with
implementation-specified calling syntax in arithmetic expressions
and arbitrary accuracy mode.
Note that max and min are treated here as arithmetic operations, hence
return Empty when an argument is Empty, in apparent contrast to maxNum
and minNum in IEEE 754-2008, where NaNs are ignored. But this contrast
is spurious, as the semantics of NaN and Empty are different.
3.11. Binary arithmetic operations on intervals
For each (partial) binary operation <circ> from Table 3.10, there
should be a binary forward interval operation <circ>Hull defined by
<circ>Hull(xx,yy) = xx <circ>Hull yy
= convex hull of the set of x <circ> y
with x in xx, y in yy, such that
x <circ> y is defined and finite.
and, if required,
two ternary reverse interval operations <circ>Inv1 and <circ>Inv2
defined by
<circ>Inv1(bb,cc,xx) = convex hull of the set of x in xx
for which b in bb exists such that
x <circ> b is defined, finite, and in cc,
<circ>Inv2(aa,cc,xx) = convex hull of the set of x in xx
for which a in aa exists such that
a <circ> x is defined, finite, and in cc.
Here the third argument is optional, with default xx=Entire if absent.
Within arithmetic expressions, the binary operator <circ>
applied to an interval is always overloaded by <circ>Hull.
If <circ> is commutative then <circ>Inv1 and <circ>Inv2 agree and may be
implemented simply as <circ>Inv.
[There is no need to spell out in the standard the mathematical
proposition which translates the above specification into tables with
formulas for the end points. These formulas, if desired, can be put
into an appendix, for all functions where someone is willing to
provide explicit formulas. It would be more useful to provide sample
implementations of a subset of the standard.]
3.12. The power operation
The binary operation pow,
where a pow b is defined for nonnegative a and real b,
provided that b is positive when a is zero
must be complemented by a binary operation intpow,
where a intpow p is defined for real a and integer p,
provided that p is nonnegative when a is zero.
In particular, 0 pow 0 is undefined, while 0 intpow 0 = 1.
This allows the polynomial f(x) = sum_{p=0:n} a_p x^p
to have the value p(0)=a_0 at x=0.
The operation intpow should, however, be viewed as a family of unary
operations parameterized by the exponent; thus the exponent is not
allowed to be an interval, intpowinv2 does not exist, and
intpowinv = intpowinv1 although the operation is not commutative.
For example,
[0,1] intpowhull -2 = [0,Inf] and [0,1] powhull -2 = [0,Inf];
but
[-1,1] intpowhull 3 = [-1,1] while [-1,1] powhull 3 = [0,1];
0 intpowhull 0 = 1 while 0 powhull 0 = Empty.
3.13. Remarks
1. The above guarantees that the result of arithmetic operations
with standard intervals is again a standard interval.
2. Overloading arithmetic expressions for interval arguments is always
done by using the forward hull; in particular this applies to
the evaluation referred to in Section 6.7.
3. Should all above operations be required, or should there be levels
of conformance to the standard, with level 1 only catering for the
most basic functionality?
4. We may also consider a ternary operation ratpow implementing
x^(p/q) for x>=0, integer p, and positive integer q, with x>0
if p<0, viewed as a family of unary operations parameterized
by p and q.
Or a binary operation root implementing x^(1/q) for x>0 and a
positive integer q, viewed as a family of unary operations
parameterized by q.
5. We may also require ratmul(xx,p,q) for intervals xx and
integers p, q with q>0, enclosing x*p/q for all x in xx,
again viewed as a family of unary operations parameterized by
p and q?
This might be useful for interfaces with computer algebra packages.
Part 4: Mixed operations and type conversion
--------------------------------------------
4.0. Theme of Part 4
This part specifies the conversion of numbers to intervals and the
behavior of mixed arithmetic operations with an interval and a
noninterval argument. These are important since they are often much
faster than full interval operations.
Warning:
-------
If the user means by a numeral anything different from what its value
actually is, the user is required to pass the exact definition of the
intended uncertain number as text (see Part 6) or via the constructors
from Section 4.5.
Otherwise results obtained could be invalid (i.e. not honor guaranteed
enclosure rules).
4.1. Conversion of numerals
There is an operation number2interval(x) that converts a
numeral x to the tightest interval containing x if x is finite, but to
Empty if x is infinite or NaN. In the latter case the nonstandardNumber
flag is raised.
This ensures that
xx = number2interval(x) implies isIn(x,xx)=not(isEmpty(xx)).
Remarks:
1. A similar but not identical effect as with xx = number2interval(x)
is obtained with xx = realHull(x,x); the difference is that +-Inf
are converted by the second statement to a nonempty set.
2. Care must be taken when converting intended infinities.
For example, if fun(x) denotes a user-defined expression in the
variable x which is monotone as a function of x then, for a compact
interval xx,
ff1=fun(number2interval(inf(xx)))
ff2=fun(number2interval(sup(xx)))
ff=convexHull(ff1,ff2) (see Section 5.6)
yields an enclosure for fun(x) for all x in xx, which is usually
excellent since in exact arithmetic the exact range is obtained.
However, for xx with one or two infinite bounds, the present
definition gives an invalid result but an exception is generated
by setting the nonstandardNumber flag.
The alternative of defining number2interval(Inf) as either
[HUGEPOS,Inf] or Entire would provide a valid but often useless
enclosure:
For fun(x)=(x-1)/(x+1), xx=[0,Inf], where one would like to see
[-1,1] as result, we get with this alternative Entire.
Similarly, for fun(x)=x^2-x, xx=[1,Inf], we get Entire instead
of [0,Inf].
Thus the potential loss of functionality of the adopted exception
handling seems to be slight.
3. I expect that the nonstandardNumber flag will never be inspected,
except for debugging purposes. Since Empty will usually propagate
very fast through complex calculations, this is the cheapest way
to handle the exceptions.
(See also the remark in Section 2.3 on labelled versions of Empty,
which would make setting the flag superfluous.)
4.2. Implicit conversion
Binary arithmetic operations from Table 3.10 with an interval
argument and a numeral or text argument should give the same result
as if a prior conversion of the noninterval according to Section 6.1
or 4.1 had been performed. This implicit conversion may be carried out
outside or inside interval arithmetic proper.
Example:
For addition xx+y, where, for simplicity, xx=[l,u] and y are finite:
(i) external conversion: implementation as xx+interval(y);
(ii) internal conversion: implementation as [l+y,u+y].
The result is exactly the same, but (ii) can be cheaper
(not for + used here for simplicity, but for * and /)
and to be preferred.
4.3. Mixed binary operations
For each binary arithmetic operation from Table 3.10,
there are binary operations which take as input numerals and return as
output the tightest enclosure of the exact result of the operation
if it is a real number, and Empty otherwise.
4.4. Conversion of numerals with known uncertainty
There is an operation intervalabs(x,d) that returns for two
finite numerals x and d the tightest interval containing
all real numbers z with |z-x|<=d, and Empty if x or d are not finite.
There is an operation intervalrel(x,d) that returns for two
finite numerals x and d the tightest interval containing
all real numbers z with |z-x|<=d|x|, and Empty if x or d are not finite.
Note that intervalrel(x,TINY), where TINY denotes the smallest
positive numeral, has a similar effect as
inflate(number2interval(x)); cf. Section 5.3.
Part 5: Non-arithmetic operations
---------------------------------
5.0. Theme of Part 5
This part defines non-arithmetic operations whose input or output
involve intervals.
5.1. Interval-valued operations on noninterval arguments
1. There is an operation realHull(l,u) that returns for two B-numerals
l and u the interval [l',u'] with
l' = NaN, u' = NaN if l or u is NaN,
l' = min(l,u,HUGEPOS), u' = max(l,u,HUGENEG) otherwise
where HUGEPOS and HUGENEG are the finite numerals
closest to +Inf and -Inf. (In the first case, the bounds may be
required to preserve the payload of the NaN.)
2. There is a function sumAll(\x) returning the tightest interval
enclosing the sum of entries of a vector \x of finite B-numerals,
or Empty if one of the components is not finite.
3. There is a function innerProduct(\x,\y) returning the tightest
interval enclosing a scalar product of two vectors \x and \y of
finite B-numerals, or Empty if one of the components is not finite.
5.2. Numeral-valued unary operations on an interval
1. Midpoint and radius.
There are an operation mid(xx) that returns for any interval xx
a B-numeral m called the midpoint of xx, an operation rad(xx)
that returns for any interval xx a B-numeral r called the radius
of xx, and an operation midRad(xx) that returns both m and r.
If xx=[l,u] is compact, m and r shall have the values defined by
set round up
r = 0.5*(u-l);m=l+r.
If xx is Empty, m = NaN, r = NaN. (This happens automatically with
the above algorithm.)
If xx has an infinite bound, r = Inf, and m is the absolutely
smallest number in xx,
m = l, r = Inf if xx = [l,Inf] with l>=0,
m = u, r = Inf if xx = [-Inf,u] with u<=0,
m = 0, r = Inf otherwise.
This guarantees the two essential properties
mid(x) in xx if xx is nonempty,
|x-mid(x)|<=rad(x) for all x in xx.
2. Diameter, width.
There is an operation diam(xx) or width(xx) that returns for any
interval xx=[l.u] its diameter or width, the smallest B-numeral
greater or equal to u-l, but NaN if xx is Empty.
3. Magnitude and mignitude.
There is an operation mag(xx) that returns for any nonempty
interval xx=[l,u] its magnitude, the smallest B-numeral greater
or equal to max{abs(x) | x in xx}.
There is an operation mig(xx) that returns for any nonempty
interval xx=[l,u] its mignitude, the largest B-numeral less or
equal to min{abs(x) | x in xx}.
If xx is Empty, NaN is returned in both cases.
4. Smallest.
There is an operation smallest(xx) that returns for any nonempty
interval xx the absolutely smallest number in the interval, i.e.,
0 if xx contains 0, and the absolutely smaller bound otherwise.
If xx is Empty, NaN is returned.
5. Sign.
There is an operation sign2(xx) that returns for any interval
xx=[l,u] the 2-valued sign, namely
-1 if 0>l<=u<=0, +1 if 0<=l<=u>0, NaN otherwise.
5.3. Interval-valued unary operations on an interval
1. There is an operation inflate(xx) that returns an interval [l,u]
containing xx such that
- the only numerals whose values are possibly contained in the set
complement [l,u]\xx are l and u,
- l<inf(xx) unless inf(xx)=-Inf,
- u>sup(xx) unless sup(xx)=+Inf,
The IEEE 754-2008 functions nextUp and nextDown are likely to be
used for the implementation.
Should one provide eps-inflation for eps>0?
5.4. Boolean-valued binary operations on intervals
In this section, 1 or 0 stand for the Boolean values true and false.
1. Comparisons and disjointness.
For each relation <omega> from the list
equalTo ==
unequalTo !=
lessThan <
greaterThan >
lessEqual <=
greaterEqual >=
there is an operation <omega>AA(xx,yy) that assigns to
any two intervals xx and yy the value 1 or 0 depending on whether
or not x <omega> y holds for all x in xx and all y in yy.
Note that not(<omega>AA(xx,yy)) is generally not the same as
<notomega>AA(xx,yy). Also, equalToAA and unequalToAA have
a different meaning from isIdentical and isDistinct from
Section 2.5.
Note also that unequalToAA(xx,yy) has the value 1 or 0 depending
on whether or not xx and yy are disjoint, i.e., have no common
element. This operation may also be provided in the additional form
areDisjoint(xx,yy).
equalToAA(xx,yy) is 1 only if xx and yy are identical singleton
intervals.
2. Variants of comparisons.
There may be optional operations <omega>SS(xx,yy) that assign to
any two intervals xx and yy the value 1 or 0 depending on whether
or not x <omega> y holds for some x in xx and some y in yy.
There may be optional operations <omega>AS(xx,yy) that assign to
any two intervals xx and yy the value 1 or 0 depending on whether
or not x <omega> y holds for all x in xx and some y in yy.
There may be optional operations <omega>SA(xx,yy) that assign to
any two intervals xx and yy the value 1 or 0 depending on whether
or not x <omega> y holds for some x in xx and all y in yy.
In my opinion, the variants are rarely needed in applications,
hence are taken as optional only.
The AA mode and SS mode corresponds to ''certainly'' and
''possibly'' versions of comparison operations in some
implementations of interval arithmetic.
3. Containment.
There is an operation containedIn(xx,yy) that assigns to
any two intervals xx and yy the value 1 or 0 depending on whether
or not x in yy for all x in xx.
There is an operation containedInInterior(xx,yy) that assigns to
any two intervals xx and yy the value 1 or 0 depending on whether
or not x in yy for all x in xx, and x is not the value of a bound
of yy.
Note that, according to standard topology, the empty set is
(as here) contained in the interior of any set.
There may be an optional operation containedInProperly(xx,yy) that
assigns to any two intervals xx and yy the value 1 or 0 depending
on whether or not x in yy for all x in xx, and xx and yy are
distinct.
5.5. Numeral-valued binary operations on intervals
1. Hausdorff distance.
There is an operation distance(xx,yy) that returns for any two
intervals xx and yy the smallest B-numeral greater
or equal to their Hausdorff distance if xx and yy are nonempty,
and otherwise NaN.
(See Section 7.10 for an explicit formula.)
(So far no other item item here.)
5.6. Interval-valued binary operations on intervals
1. Intersection.
There is an operation intersection(xx,yy) that returns for any two
intervals xx and yy the interval representing the intersection of
xx and yy.
Note that semantically invalid conversions (see Section 1.5)
may result in spurious empty intersections, such as in case of
xx=number2interval(0.1)*10
yy=[0,1]
zz=intersection(xx,yy)
when binary 64-bit floating point data are used as B-numerals.
2. Convex hull.
There is an operation convexHull(xx,yy) that returns for any two
intervals xx=[l,u] and yy=[l',u'] the tightest interval containing
the union of xx and yy.
Note that unlike in arithmetic operations, an argument Empty does
not propagate unless the other argument is Empty, too.
3. Inner operations.
There is an operation innerAddition(xx,yy) that returns for any
two intervals xx=[l,u] and yy=[l',u'] the tightest interval
containing l+u' and u+l' if l+u'<=u+l', and Empty otherwise.
There is an operation innerSubtraction(xx,yy) that returns for any
two intervals xx=[l,u] and yy=[l',u'] the tightest interval
containing l-l' and u-u' if l+u'>=u+l', and Empty otherwise.
5.7. Division with gap
There is an operation divisionWithGap(xx,yy) that returns for any two
intervals xx=[l,u] and yy=[l',u'] the interval zz=divideHull(xx,yy)
(see Section 3.11) and the gap gg, which is
- Empty if xx contains 0 or yy does not contain 0,
- Entire if xx or yy is Empty, and
- otherwise the subinterval whose interior cannot be
realized as quotient x/y with x in xx, y in yy.
Similarly one may provide perhaps implementations of inverse with gap
and inverse trigonometric or hyperbolic functions with gaps.
5.8. Linear interpolation
1. There is an operation linearInt(xx,yy,tt) that provides, for any
two compact intervals xx=[xl,xu], yy=[yl,yu], and any interval
tt=[tl,tu] contained in [0,1] an enclosure of the set of all
(1-t)*x+t*y such that x in xx, y in yy, t in tt, which is
equivalent to or tighter than the result [l,u] of the following
algorithm.
set round down
dl = yl-xl;tl1=(tl if dl>=0 else tu);l=xl+tl1*dl;
set round up
du = yu-xu;tu1=(tu if du>=0 else tl);u=xu+tu1*du;
The behavior for noncompact xx or yy and for tt not in [0,1] is
not specified.
2. There is an operation linearExt(xx,yy,tt) that provides, for any
two compact intervals xx=[xl,xu], yy=[yl,yu], and any interval
tt=[tl,tu] contained in [1,Inf] an enclosure of the set of all
(1-t)*x+t*y such that x in xx, y in yy, t in tt, which is
equivalent to or tighter than the result [l,u] of the following
algorithm.
set round down
dl = yl-xu;tl1=(tl if dl>=0 else tu);l=xu+tl1*dl;
set round up
du = yu-xl;tu1=(tu if du>=0 else tl);u=xl+tu1*du;
The behavior for noncompact xx or yy and for tt not in [1,Inf] is
not specified.
3. There is an operation linearInv(xx,yy,zz,tt) that provides,
for any four compact intervals xx, yy, zz, and tt=[tl,tu] with
tl>=0 an enclosure of the set of all t in tt such that
z=(1-t)*x+t*y for some x in xx, y in yy, z in zz,
which is equal to or tighter than
convexHull(timesInv(zz-xl,yy-xl,tt),timesInv(zz-xl,yy-xl,tt))
with convexHull and timesInv defined in Sections 5.6 and 3.11,
respectively.
The behavior for noncompact xx, yy, or zz is not specified.
The extrapolation behavior for t in [-Inf,0] can be obtained by
replacing t with 1-t. Cases where tt is an interval containing
0 or 1 in the interior are not needed in computational
geometry; not requiring them saves case distinctions.
Note that the four equations
z=(1-t)*x+t*y, y=(1-s)*x+s*z,
x=(1-p)*y+p*z=(1-q)*z+q*y, t=(z-x)/(y-x)
are equivalent if s=1/t, p=1/(1-t), q=1/(1-s), as are the conditions
0<t<1, s>1, p>1, q<0
and
t>1, 0<s<1, p<0, q>0
This explains the sign restrictions used.
5.9. Dual operations
1. For certain binary operations <circ> (we may perhaps require
that these include <circ> = times and <circ> = divide), there are
an operation <circ>Dual1(xx,yy) which returns for two nonempty
intervals xx and yy a (standard or nonstandard) interval [l,u],
where
l = min_{y in yy}max_{x in xx} x <circ> y, rounded down,
u = max_{y in yy}min_{x in xx} x <circ> y, rounded up,
an operation <circ>Dual2(xx,yy) which returns [l,u], where
l = min_{x in xx}max_{y in yy} x <circ> y, rounded down,
u = max_{x in xx}min_{y in yy} x <circ> y, rounded up,
and an operation <circ>Dual12(xx,yy) which returns [l,u], where
l = min_{x in xx}min_{y in yy} x <circ> y, rounded up,
u = max_{x in xx}max_{y in yy} x <circ> y, rounded down,
Apart from the different (inward) rounding, <circ>Dual12 is the
same as <circ>Hull.
2. For certain unary operations <phi>, there is an operation
<phi>Dual(xx) which returns for any nonempty interval xx a
(standard or nonstandard) interval [l,u], where
l = min_{x in xx} <phi>(x), rounded up,
u = max_{x in xx} <phi>(x), rounded down,
Apart from the different (inward) rounding, <phi>Dual is the same
as <phi>Hull.
3. There is an operation dual(xx) which returns for any (standard or
nonstandard) interval xx=[l,u] the (standard or nonstandard)
interval [u,l].
These dual operations allow a reasonably efficient software
implementation of modal interval arithmetic and Kaucher interval
arithmetic.
Note that the results of dual operations will in many cases be
nonstandard intervals.
The behavior of dual operations when an argument is Empty
still needs to be specified.
5.10. Type conversion in non-arithmetic operations
All non-arithmetic operations shall allow for implicit type
conversion when a numeral appears in place of an interval
argument.
This may need exceptions for certain cases where all interval
arguments are replaced by numerals.
Part 6. Text to interval conversion
-----------------------------------
6.0. Theme of Part 6
This part defines which texts denoting a mathematical definition
of an exact or uncertain real number shall be convertible into a
standard interval guaranteed to contain any valid interpretation of
this number.
This section is a discussion version only, without a full syntax
specification; instead, it proceeds by examples.
6.1. General conversion rule
There is an operation text2interval(t) which returns for a given
text t an interval containing a valid enclosure of all real numbers
matching the definition given in the text according to the rules given
in Sections 6.2-6.7 and raises a flag nonstandardNumber if the text
cannot be interpreted by these rules. It may also raise additional
implementation-dependent flags.
6.2. Textbook intervals
A text t taking one of the forms
'[<literal_float>,<literal_float>]'
where <literal_float> stands for a string acceptable as input to
the IEEE 754-2008 string->float conversions (clause 5.12 in 754-2008;
this includes representations of Inf, -Inf, and NaN)
followed and/or preceded by optional blanks, is converted by
text2interval(t) into a (standard or nonstandard) interval whose lower
bound is the largest B-numeral less or equal to the exact value of the
literal lower bound, and whose upper bound is the smallest B-numeral
greater or equal to the exact value of the literal upper bound.
6.3. Centered intervals
A text t taking the form
'<<literal_float>+-<nonneg>>',
where <literal_float> is as in Section 6.2, <nonneg> is a nonnegative
<literal_float>, and the outer pointed brackets denote these as
characters, is considered to be an interval, and is required to be
converted by text2interval(t) into the tightest interval containing the
numbers <literal_float>-<nonneg> and <literal_float>+<nonneg>.
I prefer the notation <2.3+-0.005> to the Intlab style centered interval
<2.3,0.005> since it is suggestive of its meaning and more easily
readable. Note that 2.3+-0.005 without pointed brackets would be
ambiguous since it is equivalent to the exact expression 2.3-0.005
(Section 2.6) if negation has higher precedence than plus.
6.4. Uncertain numbers
A text t taking one of the forms
'<fixpart>?<expart>', '<fixpart>_<expart>',
'<fixpart>?<unctype><fixpart><expart>',
where <fixpart> is a decimal <literal_float> without exponent part,
<expart> is the possibly empty exponent part of a decimal
<literal_float>, and <unctype> is one of the characters in 'udar',
is considered to be an uncertain number, and is required to be
converted by text2interval(t) into the tightest interval containing
all real numbers represented by this uncertain number.
(The precise semantics needs to be described here.)
Examples:
(ulp is one unit in the last place of the decimal number displayed)
12.3_ # represents 12.3 +- 1 ulp, i.e., [12.2,12.4]
1.23?e3 # represents 1.23e3 +- 1/2 ulp, i.e., [12250,12350]
Note: An earlier version had here erroneously 1 ulp
1.23?5d-1 # represents 1.23d-1 +- 5 ulp, i.e., [0.118,0.128]
.23?u2 # represents .23 + <=2 ulp, i.e., [.23,.25]
.23?d2 # represents .23 - <=2 ulp, i.e., [.21,.23]
.234?a0.01 # represents .234 +- 0.01, i.e., [.224,.244]
.23?r0.1e2 # represents .23e2 * (1+-0.1), i.e., [20.7,25.3]
6.5. Exact numbers
A text t taking one of the forms
'<sign><natural>/<natural>' or '<literal_float>',
where <sign> is empty or one of the characters + or -, <natural>
is a natural number in decimal notation without exponent,
and <literal_float> is as in Section 6.2, is considered to be an exact
number, and is required to be converted into the tightest interval
containing this number.
Note that very long rationals frequently arise in problems generated
from computer algebra packages using rational arithmetic.
For example, I have seen rationals with 800 digits in a particular
constraint satisfaction problem posed to me, generated for a
computer-assisted proof in the geometry of numbers.
6.6. Use at compile-time
Conversion according to Section 6.1-6.5 should yield the same result
regardless of whether it is done at compile time or at run time.
In the future C++0x standard, conversion according to Section 6.1-6.5
could be done via user defined literals
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2765.pdf
Thus exact numbers 2, 0.1, and 1e400 can be encoded as
2x, 0.1x, 1e400x, etc.
and intervals as
"[1.1,1.2]"i, ".23?r0.1e-5"i, etc.
6.7. Exact constant expressions
A text t taking the form of an arithmetic expression in the
operations from Section 3.6, 3.7, 3.8, and 3.10 below (including
standard-conforming operations which a particular implementation
provides), containing no variables but only constants of the form
'<literal_float>' or '<literal_float>x', is considered to be an exact
constant expression.
It is recommended that there be a library routine exactExpression(t)
that converts an exact expression into an interval containing this
number, at least as tight as if the corresponding computation would
have been done by converting each of the constants to intervals and
then performing the corresponding interval operations.
Precedence must be specified!
This facilitates the accurate enclosure of exact values of compound
expressions such as
goldenratio = (1+sqrt(5))/2,
continuedfraction = 1/(1-1/(1-1/(1-1/(1-1/(1-1/(1-1/123456789)))))),
pisixth = atan(1)*2/3,
pisixth = arctan(1)*2/3,
pisixth = pi()/6,
pisixth = pi/6, etc.
In particular (whether or not atan is in the mandatory list
of unary operations), text2interval(t) should recognize both strings
'4*atan(1)' and '4*arctan(1)' and get a valid enclosure for pi
returned if the arc tangent is implemented.
The formulation above is such that conversion may be done either by
calling the corresponding converters of '<literal_float>' or
'<literal_float>x', followed by the interval operations, or in a
more involved way that gives extra accuracy. A high quality
implementation would probably do this using multiprecision
arithmetic or a staggered correction format.
6.8. Interval to text conversion
There is an operation text(xx,m) which returns for a given interval xx
and a given conversion mode m a text t describing (depending on the
mode)
- decimal textbook intervals as in Section 6.2,
- hexadecimal textbook intervals as in Section 6.2,
- uncertain numbers as in Section 6.4,
or intervals in another form, such that
- the textbook interval equivalent to the text t contains xx,
- the only numerals whose values are possibly contained in the set
complement text2interval(t)\xx are the endpoints of text2interval(t).
There is at least one exact conversion mode m for which a text t
is returned such that text2interval(t) recovers xx exactly.
Inexact conversion modes (e.g., binary to decimal) are the rule;
in those cases one cannot always avoid losing some accuracy.
If the B-numerals are binary, the exact conversion mode would
most likely be hexadecimal conversion.
Part 7: Useful directed rounding properties
-------------------------------------------
7.0. Theme of Part 7
This part describes desirable properties of floating-point
operations under directed rounding, which facilitate the implementation
of the proposed standard when all zero bounds are represented as +0
for lower bounds and -0 for upper bounds (rather than as an arbitrary
zero).
In this part we assume that each B-numeral is represented as a
floating-point datum according to the IEEE 754-2008 standard.
Listed are desirable deviations from the standard behavior of
operation; these deviations are restricted to the behavior in the two
rounding modes
- up = roundTowardPositive and
- down = roundTowardNegative.
7.1. Behavior for zero values
All arithmetic operations (in the sense of IEEE 754-2008)
with a result having the value 0 (whether exact or inexact)
should represent the result as -0 in rounding mode up,
and as +0 in rounding mode down.
This need not be the case for quiet operations such as minNum and
maxNum. (Do not confuse these with the interval operations min and max,
overloaded as minHull and maxHull, defined in Section 3.10-3.11.)
7.2. Product zero times infinity
The product of a number with value 0 and a number with value
+-Inf should have the value 0, with sign as specified in Section 7.1.
7.3. Adding and subtracting infinities
The result of x-x for x=Inf or x=-Inf, and the result of
x+y for x=Inf, y=-Inf or x=-Inf, y=Inf should be 0, with sign as
specified in Section 7.1.
Note that +-Inf are used as bounds only, not as numbers.
7.4. Division by +0
The result of the division of a number x by +0 should be
NaN if x is NaN, +Inf if x>0, -Inf if x<0, and if x=0 then 0, with
sign as specified in Section 7.1.
7.5. Division by -0
The result of the division of a number x by -0 should be
NaN if x is NaN, -Inf if x>0, +Inf if x<0, and if x=0 then 0, with
sign as specified in Section 7.1.
7.6. Quotient of infinities
The result of x/y when x and y are infinite should be the
value 1 if x and y have the same sign, and -1 otherwise.
7.7. Disabling denormalized numbers
Disabling denormalized numbers is harmless for most applications
of interval arithmetic as long as in rounding mode up (down), the
computed result is greater (smaller) than or equal to the result
obtained in exact arithmetic.
7.8. Benefits of the deviant behavior
If these deviations from the IEEE 754-2008 standard are realized,
and bounds l=0 are represented by +0, bounds u=0 are represented by -0,
then the statements 7.9-7.11 hold:
(Someone please check this! I hope I didn't forget any case.)
7.9. Binary operations +,-,*,/
For <circ> in {+,-,*,/},
[l,u] <circ> [l',u'] = [l'',u'']
with
l'' = min(l <circ> l', l <circ> u', u <circ> l', u <circ> u')
in rounding mode down,
u'' = max(l <circ> l', l <circ> u', u <circ> l', u <circ> u')
in rounding mode up
will give the correct results in all cases with two exceptions:
(i) For <circ> = / and l' < 0 < u', [l,u] not [0,0]
we must have l''=-Inf, u''=Inf,
(ii) For <circ> = / and [l',u'] = [0,0],
we must have l''=NaN, u''=NaN.
Note that by Section 7.1, all zero arguments of the min (or max) will
be +0 (or -0) when l'' (or u'') has the value zero, so that the
IEEE 754-2008 behavior of minNum and maxNum will produce results
conforming to Section 7.1.
7.10. Hausdorff distance
The formula
set round up
distance([l,u],[l',u']) = max(abs(l-l'),abs(u-u'))
for the Hausdorff distance (Section 5.5) works correctly for all
intervals.
7.11. Linear interpolation
The algorithms from Section 5.8 also work correctly
when xx or yy or both are noncompact.
7.12. Midpoint and radius
The proposed formulas for midpoint and radius in Section 5.2. need
the exceptions mentioned, no matter how one specifies the exceptional
behavior of the arithmetic operations under directed rounding.