Expand description
§Chapter 11.9 — Intervals by computed directed rounding
§Purpose
Interval: closed intervals with f64 endpoints whose operations
contain the exact result (invariant I1) and are as tight as the
endpoints allow (I3) — in ordinary round-to-nearest arithmetic, without
touching the rounding mode of the processor (question E3 of Chapter 11,
D-0109). They are the last step of a certificate: Chapter 11.10 turns a
double-double residual and its error bound into an interval, and the
caller tests it with the certainly_* predicates.
§Notation
F is the set of finite f64 values, RN rounding to nearest, u = 2⁻⁵³, η = 2⁻¹⁰⁷⁴, Ω the largest element of F. For a real t,
▽t = max{f ∈ F ∪ {−∞} : f ≤ t} and △t = min{f ∈ F ∪ {+∞} : f ≥ t}
are the two directed roundings; so ▽t = Ω for every t ≥ Ω
(overflow never produces +∞ as a lower endpoint) and ▽t = −∞ for t < −Ω. pred and succ are the neighbours in F ∪ {±∞}
(f64::next_down, f64::next_up). An interval X = [x̲, x̄] has x̲ ∈ F ∪ {−∞}, x̄ ∈ F ∪ {+∞}, x̲ ≤ x̄, and stands for the set of real
numbers {x ∈ R : x̲ ≤ x ≤ x̄}: an infinite endpoint says “unbounded”,
it is not an element. ∅ is the empty set.
§Algorithms
Every operation reduces to one or two calls of a directed primitive:
a ∘ b rounded ▽ or △, for endpoints a, b.
Algorithm N (directed rounding of an operation). Input: endpoints
a, b, an operation ∘ ∈ {+, ·, /} or √, a direction.
N1. [Infinite and zero operands.] a + b with an infinite operand is
that operand (the other is never the opposite infinity: N-pre
below). a · b is 0 when either is zero — also when the other
is infinite: an infinite endpoint bounds a set of reals, and
every real times zero is zero — and otherwise, with an infinite
operand, the infinity of the product’s sign. a / b is 0 for a = 0 or b = ±∞, and the infinity of the quotient’s sign for a = ±∞. √0 = 0, √(+∞) = +∞. Return.
N2. [Nearest.] v ← RN(a ∘ b), one f64 operation.
N3. [Overflow.] If v = +∞: return Ω for ▽, +∞ for △. If v = −∞: return −∞ for ▽, −Ω for △.
N4. [Residual sign.] Compute σ, a number with the sign of the exact
a ∘ b − v (zero iff v is exact):
* +: the error term of Fast2Sum on the operands ordered by
magnitude, exact whenever v is finite (invariant T1 of Chapter
11.1);
* ·, with |v| ≥ 2⁻⁹⁶⁸: σ = RN(a b − v), one FMA, exact
(invariant T2: |a b| ≥ 2⁻⁹⁶⁹);
* /, with |a| ≥ 2⁻⁹⁶⁸: ρ = RN(a − v b), one FMA, and σ = ρ
for b > 0, −ρ for b < 0;
* √, with a ≥ 2⁻⁹⁰⁰: σ = RN(a − v²), one FMA;
* below those thresholds: step N6.
N5. [Step.] Return pred(v) if the direction is ▽ and σ < 0,
succ(v) if it is △ and σ > 0, and v otherwise.
N6. [Underflow range.] The FMA residual of N4 may itself be rounded
there (to zero, in the worst case: the sign is lost), so the
operation is redone 2²⁰⁰ times larger, where it is exact, and
brought back by Algorithm U:
* ·: if v = 0 (so 0 < |a b| ≤ η/2) the result is known from
the signs: (0, η) as (▽, △) for a positive product, (−η, 0)
for a negative one. Otherwise (w, δ) ← 2Prod(2²⁰⁰ s, ℓ) for
s, ℓ the operand of smaller and of larger magnitude, and
return U(w, δ).
* /: a′ ← 2²⁰⁰ a, w ← RN(a′ / b), δ ← ± RN(a′ − w b) with
the sign rule of N4; return U(w, δ).
* √: return 2⁻¹⁰⁰ times the result of N2–N5 for 2²⁰⁰ a (both
scalings exact: a square root is never subnormal).
Algorithm U (directed rounding of (w + δ) 2⁻²⁰⁰). Input w ∈ F,
δ with |δ| < ulp(w) of which only the sign is used, a direction.
U1. v ← RN(2⁻²⁰⁰ w) (rounded only when v is subnormal).
U2. τ ← w − 2²⁰⁰ v, exact. σ ← τ if τ ≠ 0, else σ ← δ.
U3. Step N5 on (v, σ).
Algorithm I (the interval operations). With X = [a, b], Y = [c, d] non-empty (an empty operand gives ∅):
I1. [+, −.] X + Y = [▽(a + c), △(b + d)], X − Y = [▽(a − d), △(b − c)].
I2. [·.] By the signs of the operands, two products (four when both
intervals contain zero in their interior): the table below, the
first entry of each cell rounded ▽, the second △.
I3. [/, 0 ∉ Y.] Likewise: for c > 0, [a/d, b/c], [a/c, b/c]
or [a/c, b/d] as X is ≥ 0, mixed or ≤ 0; for d < 0,
[b/d, a/c], [b/d, a/d] or [b/c, a/d].
I4. [/, 0 ∈ Y.] The hull of {x / y : x ∈ X, y ∈ Y, y ≠ 0}: [0, 0] if X = [0, 0] and Y ≠ [0, 0]; a half-line when zero is an
endpoint of Y and X has one sign (Y = [0, d]: [▽(a/d), +∞]
for a ≥ 0, [−∞, △(b/d)] for b ≤ 0; Y = [c, 0]: [−∞, △(a/c)] for a ≥ 0, [▽(b/c), +∞] for b ≤ 0); [−∞, +∞]
otherwise — in particular for Y = [0, 0], where no quotient is
defined and the set is empty: “nothing is known” is returned rather
than ∅, so that a division by an exact zero can never prove
anything downstream (invariant C3 of Chapter 11).
I5. [√, x², |x|.] √X = [▽√max(a, 0), △√b], or ∅ if b < 0.
X² = [▽a², △b²] for a ≥ 0, [▽b², △a²] for b ≤ 0, [0, △max(a², b²)] otherwise. |X| and −X are exact.
I6. [A point operand.] X ∘ y for an f64 y is X ∘ [y, y] with
the case of I2–I3 chosen by the sign of y (two directed
operations). A NaN or infinite y is not a real number: the result
is [−∞, +∞] (C3), never a panic.
The table of step I2 (rows: the sign of X = [a, b]; columns: that of
Y = [c, d]):
c ≥ 0 | c < 0 < d | d ≤ 0 | |
|---|---|---|---|
a ≥ 0 | [ac, bd] | [bc, bd] | [bc, ad] |
a < 0 < b | [ad, bd] | [min(ad, bc), max(ac, bd)] | [bc, ac] |
b ≤ 0 | [ad, bc] | [ad, ac] | [bd, ac] |
§Proofs
(N-pre) The primitives never see ∞ − ∞, 0/0, ∞/∞ or a NaN. A
lower endpoint is never +∞ and an upper one never −∞ (I2), and
Algorithm I adds lower to lower and upper to upper (for −, after
negating the subtrahend); the table of I2 and step N1 remove 0 · ∞;
in I3 the divisor is never zero, and whenever the divisor can be
infinite the dividend is an endpoint that the sign case makes finite
(a in a/d with a ≥ 0; b in b/c with b ≤ 0; …).
(N) Steps N2–N5 return the directed rounding. v = RN(t) for the
exact t = a ∘ b, so pred(v) ≤ t ≤ succ(v): ▽t is v when v ≤ t
and pred(v) otherwise, and that is the sign of t − v. It remains
that σ has that sign.
+: Fast2Sum with|hi| ≥ |lo|returns the exact error for any finite sum, subnormal or not (T1).·:|v| ≥ 2⁻⁹⁶⁸gives|a b| ≥ 2⁻⁹⁶⁸(1 − u) > 2⁻⁹⁶⁹, the exact range of 2ProdFMA (T2)./: letq = vandt = a − q b. Withulpof a subnormal equal toη,tis an integer multiple ofg = ulp(q) ulp(b)and|t| ≤ ½ ulp(q) |b| < 2⁵² g, sot ∈ Fas soon asg ≥ η. For normalqandbthat ise_q + e_b ≥ −970, implied by|a| ≥ 2⁻⁹⁶⁸(e_q + e_b ≥ e_a − 1); a subnormalqforces|b| > 2⁵⁴and a subnormalbforces|q| > 2⁵⁴, andg ≥ ηagain. So the FMA returnstexactly, anda/b − q = t/b.√: withs = v,t = a − s²is a multiple ofulp(s)²and|t| ≤ ulp(s) s + ¼ ulp(s)², at most2⁵³such units; sot ∈ Fwhenulp(s)² ≥ η, i.e.a ≥ 2⁻⁹⁷⁰. (The thresholds2⁻⁹⁶⁸and2⁻⁹⁰⁰are sufficient, not sharp.)
(U) Algorithm U. 2²⁰⁰ v is exact (|v| ≤ 2⁻⁷⁶⁷). If v is normal,
U1 was exact and τ = 0. Otherwise 2²⁰⁰ v is w rounded to the grid
2⁻⁸⁷⁴ Z, both are multiples of ulp(w) and |τ| ≤ |w|, so τ ∈ F
and the subtraction is exact. The exact value is 2⁻²⁰⁰(w + δ), and
(w + δ) − 2²⁰⁰ v = τ + δ: a nonzero τ is a multiple of ulp(w) > |δ| and decides the sign; if τ = 0, δ does. In step N6 the
hypotheses hold: for the product, v ≠ 0 gives |a b| > η/2, so
2²⁰⁰ |a b| > 2⁻⁸⁷⁵ is in the exact range of 2Prod, and |s| < 2⁻⁴⁸³
makes 2²⁰⁰ s exact; for the quotient, |a′| ≥ 2⁻⁸⁷⁴ puts a′ − w b
under the argument of (N) — when w underflows the residual may be
rounded, but it is a nonzero multiple of η ulp(b) with |b| > 2¹⁴⁸,
far above η: its sign survives, which is all U2 reads.
(I) Inclusion and tightness. +, −, · and / (for 0 ∉ Y) are
monotone in each argument on the boxes that the sign cases delimit, so
the exact range over X × Y is the interval between the two endpoint
expressions of I1–I3; ▽ of the lower one and △ of the upper one are
by definition the tightest endpoints in F ∪ {±∞} (I3, with no
exception for underflow or overflow: steps N3 and N6). When an operand
endpoint is infinite, the corresponding expression is the limit, and N1
returns it. I4 and I5 follow the same way; I6 is I2–I3 for c = d.
§Exceptional cases, in one place
- Overflow.
▽saturates atΩ,△goes to+∞(N3); a result may be a half-line, never invalid and never empty. - Subnormals and underflow. Sums are exact there. Products and
quotients whose FMA residual could be rounded take step N6 and are
still the exact directed roundings (a result of magnitude below
ηbecomes[0, η]or[−η, 0], keeping its sign). - Zero in the divisor. I4: a half-line or
[−∞, +∞]; no panic. - NaN. No interval holds a NaN (I2), and no operation on valid
intervals produces one (N-pre). A NaN enters only through a
constructor or a point operand:
Interval::newreturns an error,Interval::pointandInterval::mid_radpanic, an operator andFrom<f64>return[−∞, +∞],Interval::enclosereturns[−∞, +∞],Interval::containsand thecertainly_*predicates returnfalse. - The empty set. Stored as
[+∞, −∞]; every arithmetic operation with an empty operand returns∅;hullignores it;mid,width,magandmigare NaN. Thecertainly_*predicates arefalseon∅, although “every element of∅is≤ b” is vacuously true: they are the last step of a certificate, and an empty enclosure means that a hypothesis failed upstream, not that a claim was proved (C3).is_subset_of, a set relation, istruefor∅ ⊆ Y.
§Printing
Algorithm D (decimal output, {} and {:e}). Input: a non-empty
X = [a, b], the precision p of the format, if any.
D1. [No precision.] Print each endpoint as f64 prints it: the
shortest decimal that reads back as the same f64. The text
identifies the interval (it is not an enclosure by decimals: the
shortest decimal of a may lie on either side of a).
D2. [Exact expansion.] With a precision: write |a| exactly — an
f64 has at most 1074 fractional and 767 significant decimal
digits, and the formatting of f64 is exact at that length.
D3. [Directed truncation.] Keep p fractional digits ({}) or 1 + p significant digits ({:e}); if a discarded digit is nonzero and
the direction points away from zero (▽ for a negative a, △
for a positive b), add one unit in the last kept place, carrying
(in {:e} a carry out of the leading digit is 1.00… with the
exponent one higher).
(D) The printed pair, read as exact decimals, contains X, and each
printed endpoint is within one unit of its last digit of the true one:
truncation moves toward zero, the added unit moves past the value by
less than one unit. An infinite endpoint prints as -inf or inf, ∅
as ∅. With a precision, the only other flag honoured is +; the
width and the fill are not.
§Invariants
(I1) Inclusion. x ∈ X, y ∈ Y and x ∘ y defined imply x ∘ y ∈ X ∘ Y.
(I2) Well-formed. A non-empty interval has lo ≤ hi, no NaN, lo < +∞, hi > −∞; ∅ is the pair [+∞, −∞] and nothing else.
Interval::check_invariants; a debug_assert! after every
operation.
(I3) Tightness. +, −, ·, / (divisor without zero), √ and
x² return the hull of the exact range rounded outward to F:
each endpoint is the directed rounding of the exact one. In
particular an operation on points returns an interval of at most
one ulp (two adjacent f64), and a point when the result is
an f64. The tests check both against exact rationals.
(I4) Operator forms. X ∘= Y, X ∘= y, y ∘ X return, bit for bit,
X ∘ Y, X ∘ y and [y, y] ∘ X (with [−∞, +∞] for a y that
is not a real number, as in step I6).
§Cost
Per directed endpoint: one operation, one EFT or FMA and a branch — 4 flops for a sum, 2 for a product, quotient or root, against 1 with a hardware rounding mode. No allocation.
§References
Rump, Zimmermann, Boldo & Melquiond, “Computing predecessor and
successor in rounding to nearest”, BIT 49 (2009) — directed results
from round-to-nearest ones; Boldo & Daumas, “Representable correcting
terms for possibly underflowing floating point operations”, ARITH-16
(2003) — when the residuals of / and √ are representable; Muller et
al., Handbook of Floating-Point Arithmetic, 2nd ed. (2018), §4.3–4.4
and §5.2; IEEE Std 1788-2015 (the set-based model: an infinite
endpoint is not an element; division by an interval containing zero;
mid of an unbounded interval); Hickey, Ju & van Emden, “Interval
arithmetic: from principles to implementation”, J. ACM 48 (2001) — the
sign table of I2 and the convention 0 · ∞ = 0 for endpoints. None
of these was reread for this chapter: the statements used are proved
above (Proofs N, U, I) from invariants T1–T2 of Chapter 11.1, and the
tests check every operation against exact rational arithmetic.
Macros§
- assign_
ops 🔒 - The assigning forms:
X ∘= YisX = X ∘ Y,X ∘= yisX = X ∘ y(invariant I4 of Chapter 11.9).
Structs§
- Interval
- A closed interval
[lo, hi]withf64endpoints, or the empty set (invariants I1–I3). Operations round outward by computed directed rounding (Chapter 11.9). - Invalid
Interval lo > hi, or an endpoint is NaN, orlo = +∞, orhi = −∞.
Enums§
- Dir 🔒
- A rounding direction:
▽or△.
Constants§
- DOWNSCALE 🔒
- DOWNSCALE_
SQRT 🔒 - ETA 🔒
η, the smallest positive subnormal.- EXACT_
FRACTION_ 🔒DIGITS - Fractional digits that write any
f64exactly (it is a multiple of2⁻¹⁰⁷⁴). - EXACT_
MANTISSA_ 🔒DIGITS - Digits after the leading one that write any
f64exactly in scientific notation (767 significant digits at most; a round number above it). - EXACT_
RESIDUAL 🔒 2⁻⁹⁶⁸: at or above it (for|RN(a b)|, resp. for the dividend|a|) the FMA residual of step N4 is exact.- EXACT_
SQRT_ 🔒RESIDUAL 2⁻⁹⁰⁰: the same for the radicand (a round number above2⁻⁹⁷⁰whose scaling by2²⁰⁰is exact).- UPSCALE 🔒
2²⁰⁰,2⁻²⁰⁰and2⁻¹⁰⁰: the scalings of steps N6 and U.
Functions§
- add_dir 🔒
- Algorithm N for
a + b. - away 🔒
- Whether step D3 adds a unit: the discarded digits are not all zero and the direction points away from zero.
- descale 🔒
- Algorithm U: the directed rounding of
(w + δ) 2⁻²⁰⁰. - div_dir 🔒
- Algorithm N for
a / b,b ≠ 0. - increment 🔒
- Adds one unit in the last place of a string of ASCII decimal digits;
trueif the carry leaves the leading digit (the digits are then all zero). - left_
point 🔒 - The point
[y, y]of a left scalar operand, or what the operation returns without computing:∅for an emptyx,Interval::ENTIREfor aythat is not a real number (step I6). - mul_dir 🔒
- Algorithm N for
a · b. - overflow 🔒
- Step N3: the directed rounding of a finite exact value whose nearest
rounding
voverflowed. - sqrt_
dir 🔒 - Algorithm N for
√a,a ≥ 0ora = +∞. - step 🔒
- Step N5:
vmoved one step in the directiondirwhen the exact value lies strictly on that side (sigmahas the sign ofexact − v). - write_
exp 🔒 - Steps D2 and D3 for
{:.pe}:xwith1 + psignificant digits, rounded in the directiondir. - write_
fixed 🔒 - Steps D2 and D3 for
{:.p}:xwithpfractional digits, rounded in the directiondir.