Re: Re-submission of motion 5: multiple-format arithmetic.
John Pryce wrote:
[motion 5]
This is already much better than the first version.
Here a few comments, and suggestions for improvement:
M2. An implementation shall specify which interval formats it supports
(it is permitted to support only one). Support consists of the following
two items.
- For each supported interval format, operations (as P1788 will in due
course specify) shall be provided, to at least SRSF level - see R6.6.
- Conversions shall be provided between any two supported interval
formats - see R6.5.
M3. An implementation shall be called 754-conforming if: (i) its
underlying system is 754-conforming (Definition D1) and the
implementation supports an interval format for each supported
floating-point format;
This is ambiguous. Floating-point formats are supported by 754, interval
formats are supported by 1788. M2 defined only which interval formats
are supported.
So what happens if the system supports many floating-point formats?
Does the implementation have to support all corresponding interval
formats? Literally reading, it seems, yes. But this should definitely
not be the case.
R5. Level 1 description.
------------------------
This section recapitulates matters at the mathematical level that have,
I believe, already been decided. The notation is similar to the Vienna
proposal's, which is suitable for a plain-text document such as this.
I believe nothing in this motion and rationale hinders the
implementation of various forms of non-standard intervals -- Kahan,
modal, etc. -- as discussed at the end of Vienna/1.2. It is incompatible
with certain _representations_, e.g., with a finite precision midrad
(midpoint-radius) representation of intervals, though there is nothing
to stop an algorithm using midrad form internally.
R5.1. R is the set of reals. R* is the set of extended reals
R* = R union {-oo, +oo},
where we use -oo and +oo to denote negative and positive infinity.
Using the terminology of 754 (see /2.1.25 and elsewhere), any member
of R* is called a number: it is a "finite number" if it is in R, else
an "infinite number".
R5.2. Following Motion 3, the set of "textbook" intervals (Vienna/1.2)
in R,
denoted (IR), comprises the empty set together with all nonempty
intervals
xx = { x in R | xlo <= x <= xhi }, denoted [xlo, xhi],
where -oo <= xlo <= xhi <= +oo.
I find the notation (IR) strange and completely against mathematical
practices.
Motion 3 did not define a notation for the set of all closed intervals.
The paper "Standardized notation in interval analysis" (adopted in
Motion 1) had a notation that cannot be represented in ASCII.
Thus in principle we are free to decide on how to represent the set
of intervals in ASCII.
My proposal would be to use \R (read: fat R) for the reals,
\R^* for the extended reals, and \IR (fat IR) for the set of all
real closed intervals. This distinguishes \R from the letter R
(needed, e.g. for the factor in a QR factorization) and resolves
previous incompatibilities inan elegant way.
Square bracket notation xx = [xlo, xhi] is used in all cases,
except for the empty interval Empty.
for
simplicity. However the above definition implies -oo and +oo are never
members of an interval. The traditional round bracket notation may be
used
for specific intervals with an infinite end point, e.g. [2, +oo) instead
of [2, +oo].
Thus, [2, +oo) = [2, +oo], etc., which is consistent with the definition
[a,b) = { x in \R | a<=x<b},
(a,b] = { x in \R | a<x<=b},
(a,b) = { x in \R | a<x<b}.
The requirement that xx be nonempty implies xlo cannot be +oo, and xhi
cannot be -oo, so I regard [-oo, -oo] and [+oo, +oo] as having no meaning
(rather than being empty).
The empty set is denoted by Empty. The whole of R is denoted by Entire.
R5.3. The (interval) hull of an arbitrary subset ss of R, written hull(ss),
is the tightest member of (IR) that contains ss.
(The "tightest" set with a given property is the unique one that is
contained in all other sets having that property. In many areas of
mathematics, "smallest" is used with the same meaning.)
''smallest'' is generic when a single partial order is defined.
But it is ambiguous and should therefore be avoided when, as for
intervals, several natural partial orders coexist.
R5.4. A "point function" is a (possibly partial) multivariate real
function:
that is, a mapping f from a subset D of R^n to R^m for some integers n
>= 0,
m > 0. (When n=0 and m=1, we have a "named real constant".)
When not otherwise specified, a scalar function is assumed, i.e. m=1.
If m>1,
the function is called a vector function.
D = D_f is the domain of f.
To specify n, call f an "n-variable point function", or denote f as
f(x_1, ..., x_n).
The "range" (often called "exact range" in the literature) of f over
an arbitrary subset ss of R^n is the set
range(f, ss) = {f(x) | x in ss and x in D_f}.
Notes.
- Here, f is a mapping, not an expression.
- For instance range(sqrt, [-1,1]) = [0,1]. We follow the convention,
usual in mathematics, that when evaluating over sets, points outside
D_f are simply ignored. The Kulisch-Einarsson position paper on the
basic operations (May 09) makes the same definition.
So does the Vienna proposal.
- For the 754 policy on evaluating point functions outside the domain,
see 754/9.1.1.
R5.5. Unless otherwise specified, an "interval mapping" is a mapping ff
from
(IR)^n to (IR)^m for some n,m >= 0. To specify n, call ff an "n-variable
interval mapping", or denote ff as
ff(xx_1, ..., xx_n).
As with point functions, m=1 is assumed unless specified otherwise.
An interval mapping is called an "interval function" if it is an interval
extension of some point function, as defined next. Examples of interval
mappings that are not interval functions are the interval hull and
intersection operations.
Given an n-variable point function f, an "interval extension" of f, also
called an "interval version" of f, is any interval function ff such that
ff(ss) contains range(f,ss) for any subset ss of R^n.
The "sharp interval extension" of f is defined by
ff(ss) = hull(range(f,ss)) for any subset ss of R^n.
Equivalently, for the case where ff has separate arguments ss_1, ...,
ss_n,
each being a subset of R, an interval extension satisfies
ff(ss) contains range(f,ss_1, ..., ss_n),
range(f,ss_1, ..., ss_n) has not yet been defined.
and the sharp interval extension satisfies
ff(ss_1, ..., ss_n) = hull(range(f,ss_1, ..., ss_n)),
for any ss_1, ..., ss_n.
This is an alternative notation for the case where ss is the cartesian
product of the ss_i.
When f is a binary operator "op" written in infix notation, this gives
the usual definition of its (sharp) interval extension as
xx op yy = hull({x op y | x in xx, y in yy, and x op y is defined}).
Notes.
- Example. With these definitions
xx * {0} = {0} and xx / {0} = Empty, for any nonempty interval xx.
- All interval functions used here are automatically defined for all
arguments -- e.g. for the sharp extension of "point sqrt",
sqrt([-1,4]) = [0,2], sqrt([-2,-1]) = Empty.
R6. Level 2 description.
--------------------
R6.1. A floating point "abstract format" ("aformat") F is a finite
subset of R*
such that at least -oo and +oo are elements of F.
A neater formulation with the same content is:
''A floating point "abstract format" ("aformat") is a finite
subset of R* containing -oo and +oo.''
Also, it seeems to me that it is better English to write
''An abstract floating point format ("af-format") is a finite
subset of R* containing -oo and +oo.''
A format in the 754 sense (a "concrete format") shall be identified with
the aformat comprising those extended-real numbers that are exactly
representable in that format, where -0 and +0 both represent 0. This is
the aformat "associated to" the concrete format.
Notes.
- In view of this definition, 754's -0 and +0 are considered identical.
Also, in 754 decimal formats, numbers in the same cohort are considered
identical.
- For examples, we use the abbreviations b64 to mean 754's 64-bit binary
format, b32 for 32-bit binary, and d64 for 64-bit decimal.
R6.2. An "interval format" is the set (IR)_F of "F-intervals" for some
aformat
Shouldn't that be called an "abstract interval format" ("ai-format")-
since there should be later also concrete interval formats?
F, comprising the empty set together with all textbook intervals whose
endpoints are in F. When it is necessary to distinguish, it is called an
"infsup interval format" by contrast to, say, a "midrad interval format".
Notes.
- Clearly an aformat uniquely determines an interval format (also vice
versa), and a 754 concrete format uniquely determines an aformat.
- An example of a possibly useful aformat that is not associated to a
concrete format (but is derived from one), is a "flush underflows to
zero" interval system. Say the concrete format is binary64. Then the
nonempty intervals are those whose endpoints belong to F, which is
defined to consist of all binary64 numbers that are not subnormal.
Such a system may give speed advantages on some architectures.
- This definition implies some form of infsup, that is (lower bound,
upper bound) representation at level 3. Variants of this exist, see
for instance Vienna/1.6.
- It also implies that it is not just wrong, but actually meaningless at
this level, to speak of an interval that has NaN as an endpoint or has
its lower bound greater than its upper bound.
R6.3. An "F-interval datum", by analogy with the definition of
floating-point
datum in 754/3.2, is either
- an F-interval; or
- the abstract object NaI, "Not an Interval".
An "interval datum" is an F-interval datum of any relevant aformat F.
Note.
At this level we consider there is just one NaI for all aformats; at the
More precisely, given the preamble:
''At this level we consider there is at most one NaI for all aformats''
representation level this will probably not be the case.
My view of the purpose of NaI is that it is like NaN in floating point
computation: if any operand to an operation is NaI, the result is
NaI. Not everyone agrees with this definition, but this controversy is
peripheral to multiple-format issues, so from now on it is assumed that
no operand to an operation is NaI.
... without deciding this issue (according to the preamble).
R6.4. The (interval) F-hull of an arbitrary subset ss of R, written
hull_F(ss),
is the tightest F-interval that contains ss.
Notes.
- The set hull_F(ss) always exists, because F is finite and contains -oo
and +oo.
- Always, hull_F(ss) contains hull(ss). If aformat G contains aformat F
in the sense of subsets of R* -- equivalently in the 754 case, if
format
G is wider than F in the sense of 754/2.1.36 -- then hull_F(ss)
contains
hull_G(ss).
R6.5. Interval format conversion.
If F is an aformat, the "conversion" to format F shall mean the operation
that maps an interval xx of any other supported format to its F-hull,
yy = hull_F(xx).
<754>This interval operation can in all cases (whether xx has the same
radix
as F or not) be implemented in terms of one of the floating point
operations
formatOf-convertFormat
defined in 754/5.4.2, with the appropriate outward rounding.
</754>
R6.6. Interval elementary functions: some options.
The Basic Theorem of Interval Arithmetic (BTIA) relies on each point
elementary function e in a real expression being replaced by an
"interval version", ee. Mathematically, ee can be an arbitrary interval
version of e, and its arguments and result are not limited by any
concrete interval format.
Practically, a level 2 "interval version" must be implemented at level
3 in terms of concrete formats such as binary64. Typically, ee is coded
to deliver a result of a _specified_ format, from operands of a _limited
number_ of formats. What should multiple-format support mean? Let F be a
supported interval format, and e be an elementary function. Three levels
of support are suggested by the design of the 754 standard. In all of
them, conversions as in R6.5 are provided between all supported interval
formats.
- Single-radix, single-format (SRSF).
In SRSF support, e has an interval version ee that takes F-interval
operand(s) and gives an F-interval result. Thus explicit format
conversion is needed for any operand of a different interval format from F.
- Single-radix, mixed-format (SRMF).
In SRMF support, e has an interval version ee that takes operand(s) of
any supported interval format of the same radix as F, and gives an
F-interval result. Thus explicit format conversion is needed for any
operand of a whose interval format has a different radix from F.
What is ''a'' in the last sentence?
Arnold Neumaier