Skip to main content

Module interval

Module interval 

Source
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 ≥ 0c < 0 < dd ≤ 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).
  • /: let q = v and t = a − q b. With ulp of a subnormal equal to η, t is an integer multiple of g = ulp(q) ulp(b) and |t| ≤ ½ ulp(q) |b| < 2⁵² g, so t ∈ F as soon as g ≥ η. For normal q and b that is e_q + e_b ≥ −970, implied by |a| ≥ 2⁻⁹⁶⁸ (e_q + e_b ≥ e_a − 1); a subnormal q forces |b| > 2⁵⁴ and a subnormal b forces |q| > 2⁵⁴, and g ≥ η again. So the FMA returns t exactly, and a/b − q = t/b.
  • √: with s = v, t = a − s² is a multiple of ulp(s)² and |t| ≤ ulp(s) s + ¼ ulp(s)² , at most 2⁵³ such units; so t ∈ F when ulp(s)² ≥ η, i.e. a ≥ 2⁻⁹⁷⁰. (The thresholds 2⁻⁹⁶⁸ and 2⁻⁹⁰⁰ 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::new returns an error, Interval::point and Interval::mid_rad panic, an operator and From<f64> return [−∞, +∞], Interval::enclose returns [−∞, +∞], Interval::contains and the certainly_* predicates return false.
  • The empty set. Stored as [+∞, −∞]; every arithmetic operation with an empty operand returns ∅; hull ignores it; mid, width, mag and mig are NaN. The certainly_* predicates are false on ∅, 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, is true for ∅ ⊆ 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 ∘= Y is X = X ∘ Y, X ∘= y is X = X ∘ y (invariant I4 of Chapter 11.9).

Structs§

Interval
A closed interval [lo, hi] with f64 endpoints, or the empty set (invariants I1–I3). Operations round outward by computed directed rounding (Chapter 11.9).
InvalidInterval
lo > hi, or an endpoint is NaN, or lo = +∞, or hi = −∞.

Enums§

Dir 🔒
A rounding direction: ▽ or △.

Constants§

DOWNSCALE 🔒
DOWNSCALE_SQRT 🔒
ETA 🔒
η, the smallest positive subnormal.
EXACT_FRACTION_DIGITS 🔒
Fractional digits that write any f64 exactly (it is a multiple of 2⁻¹⁰⁷⁴).
EXACT_MANTISSA_DIGITS 🔒
Digits after the leading one that write any f64 exactly 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 above 2⁻⁹⁷⁰ whose scaling by 2²⁰⁰ is exact).
UPSCALE 🔒
2²⁰⁰, 2⁻²⁰⁰ and 2⁻¹⁰⁰: 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; true if 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 empty x, Interval::ENTIRE for a y that 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 v overflowed.
sqrt_dir 🔒
Algorithm N for √a, a ≥ 0 or a = +∞.
step 🔒
Step N5: v moved one step in the direction dir when the exact value lies strictly on that side (sigma has the sign of exact − v).
write_exp 🔒
Steps D2 and D3 for {:.pe}: x with 1 + p significant digits, rounded in the direction dir.
write_fixed 🔒
Steps D2 and D3 for {:.p}: x with p fractional digits, rounded in the direction dir.