Skip to main content

xingo_extprec/
interval.rs

1//! # Chapter 11.9 — Intervals by computed directed rounding
2//!
3//! ## Purpose
4//! [`Interval`]: closed intervals with `f64` endpoints whose operations
5//! *contain* the exact result (invariant I1) and are as tight as the
6//! endpoints allow (I3) — in ordinary round-to-nearest arithmetic, without
7//! touching the rounding mode of the processor (question E3 of Chapter 11,
8//! D-0109). They are the last step of a certificate: Chapter 11.10 turns a
9//! double-double residual and its error bound into an interval, and the
10//! caller tests it with the `certainly_*` predicates.
11//!
12//! ## Notation
13//! `F` is the set of finite `f64` values, `RN` rounding to nearest, `u =
14//! 2⁻⁵³`, `η = 2⁻¹⁰⁷⁴`, `Ω` the largest element of `F`. For a real `t`,
15//! `▽t = max{f ∈ F ∪ {−∞} : f ≤ t}` and `△t = min{f ∈ F ∪ {+∞} : f ≥ t}`
16//! are the two *directed roundings*; so `▽t = Ω` for every `t ≥ Ω`
17//! (overflow never produces `+∞` as a lower endpoint) and `▽t = −∞` for `t
18//! < −Ω`. `pred` and `succ` are the neighbours in `F ∪ {±∞}`
19//! (`f64::next_down`, `f64::next_up`). An interval `X = [x̲, x̄]` has `x̲ ∈
20//! F ∪ {−∞}`, `x̄ ∈ F ∪ {+∞}`, `x̲ ≤ x̄`, and stands for the set of **real**
21//! numbers `{x ∈ R : x̲ ≤ x ≤ x̄}`: an infinite endpoint says "unbounded",
22//! it is not an element. `∅` is the empty set.
23//!
24//! ## Algorithms
25//! Every operation reduces to one or two calls of a *directed primitive*:
26//! `a ∘ b` rounded `▽` or `△`, for endpoints `a`, `b`.
27//!
28//! **Algorithm N (directed rounding of an operation).** Input: endpoints
29//! `a`, `b`, an operation `∘ ∈ {+, ·, /}` or `√`, a direction.
30//!
31//! N1. \[Infinite and zero operands.\] `a + b` with an infinite operand is
32//!     that operand (the other is never the opposite infinity: N-pre
33//!     below). `a · b` is `0` when either is zero — **also when the other
34//!     is infinite**: an infinite endpoint bounds a set of reals, and
35//!     every real times zero is zero — and otherwise, with an infinite
36//!     operand, the infinity of the product's sign. `a / b` is `0` for `a
37//!     = 0` or `b = ±∞`, and the infinity of the quotient's sign for `a =
38//!     ±∞`. `√0 = 0`, `√(+∞) = +∞`. Return.
39//! N2. \[Nearest.\] `v ← RN(a ∘ b)`, one `f64` operation.
40//! N3. \[Overflow.\] If `v = +∞`: return `Ω` for `▽`, `+∞` for `△`. If `v =
41//!     −∞`: return `−∞` for `▽`, `−Ω` for `△`.
42//! N4. \[Residual sign.\] Compute `σ`, a number with the sign of the exact
43//!     `a ∘ b − v` (zero iff `v` is exact):
44//!     * `+`: the error term of Fast2Sum on the operands ordered by
45//!       magnitude, exact whenever `v` is finite (invariant T1 of Chapter
46//!       11.1);
47//!     * `·`, with `|v| ≥ 2⁻⁹⁶⁸`: `σ = RN(a b − v)`, one FMA, exact
48//!       (invariant T2: `|a b| ≥ 2⁻⁹⁶⁹`);
49//!     * `/`, with `|a| ≥ 2⁻⁹⁶⁸`: `ρ = RN(a − v b)`, one FMA, and `σ = ρ`
50//!       for `b > 0`, `−ρ` for `b < 0`;
51//!     * `√`, with `a ≥ 2⁻⁹⁰⁰`: `σ = RN(a − v²)`, one FMA;
52//!     * below those thresholds: step N6.
53//! N5. \[Step.\] Return `pred(v)` if the direction is `▽` and `σ < 0`,
54//!     `succ(v)` if it is `△` and `σ > 0`, and `v` otherwise.
55//! N6. \[Underflow range.\] The FMA residual of N4 may itself be rounded
56//!     there (to zero, in the worst case: the sign is lost), so the
57//!     operation is redone `2²⁰⁰` times larger, where it is exact, and
58//!     brought back by Algorithm U:
59//!     * `·`: if `v = 0` (so `0 < |a b| ≤ η/2`) the result is known from
60//!       the signs: `(0, η)` as `(▽, △)` for a positive product, `(−η, 0)`
61//!       for a negative one. Otherwise `(w, δ) ← 2Prod(2²⁰⁰ s, ℓ)` for
62//!       `s`, `ℓ` the operand of smaller and of larger magnitude, and
63//!       return `U(w, δ)`.
64//!     * `/`: `a′ ← 2²⁰⁰ a`, `w ← RN(a′ / b)`, `δ ← ± RN(a′ − w b)` with
65//!       the sign rule of N4; return `U(w, δ)`.
66//!     * `√`: return `2⁻¹⁰⁰` times the result of N2–N5 for `2²⁰⁰ a` (both
67//!       scalings exact: a square root is never subnormal).
68//!
69//! **Algorithm U (directed rounding of `(w + δ) 2⁻²⁰⁰`).** Input `w ∈ F`,
70//! `δ` with `|δ| < ulp(w)` of which only the sign is used, a direction.
71//!
72//! U1. `v ← RN(2⁻²⁰⁰ w)` (rounded only when `v` is subnormal).
73//! U2. `τ ← w − 2²⁰⁰ v`, exact. `σ ← τ` if `τ ≠ 0`, else `σ ← δ`.
74//! U3. Step N5 on `(v, σ)`.
75//!
76//! **Algorithm I (the interval operations).** With `X = [a, b]`, `Y = [c,
77//! d]` non-empty (an empty operand gives `∅`):
78//!
79//! I1. \[`+`, `−`.\] `X + Y = [▽(a + c), △(b + d)]`, `X − Y = [▽(a − d),
80//!     △(b − c)]`.
81//! I2. \[`·`.\] By the signs of the operands, two products (four when both
82//!     intervals contain zero in their interior): the table below, the
83//!     first entry of each cell rounded `▽`, the second `△`.
84//! I3. \[`/`, `0 ∉ Y`.\] Likewise: for `c > 0`, `[a/d, b/c]`, `[a/c, b/c]`
85//!     or `[a/c, b/d]` as `X` is `≥ 0`, mixed or `≤ 0`; for `d < 0`,
86//!     `[b/d, a/c]`, `[b/d, a/d]` or `[b/c, a/d]`.
87//! I4. \[`/`, `0 ∈ Y`.\] The hull of `{x / y : x ∈ X, y ∈ Y, y ≠ 0}`: `[0,
88//!     0]` if `X = [0, 0]` and `Y ≠ [0, 0]`; a half-line when zero is an
89//!     endpoint of `Y` and `X` has one sign (`Y = [0, d]`: `[▽(a/d), +∞]`
90//!     for `a ≥ 0`, `[−∞, △(b/d)]` for `b ≤ 0`; `Y = [c, 0]`: `[−∞,
91//!     △(a/c)]` for `a ≥ 0`, `[▽(b/c), +∞]` for `b ≤ 0`); `[−∞, +∞]`
92//!     otherwise — in particular for `Y = [0, 0]`, where no quotient is
93//!     defined and the set is empty: "nothing is known" is returned rather
94//!     than `∅`, so that a division by an exact zero can never *prove*
95//!     anything downstream (invariant C3 of Chapter 11).
96//! I5. \[`√`, `x²`, `|x|`.\] `√X = [▽√max(a, 0), △√b]`, or `∅` if `b < 0`.
97//!     `X² = [▽a², △b²]` for `a ≥ 0`, `[▽b², △a²]` for `b ≤ 0`, `[0,
98//!     △max(a², b²)]` otherwise. `|X|` and `−X` are exact.
99//! I6. \[A point operand.\] `X ∘ y` for an `f64` `y` is `X ∘ [y, y]` with
100//!     the case of I2–I3 chosen by the sign of `y` (two directed
101//!     operations). A NaN or infinite `y` is not a real number: the result
102//!     is `[−∞, +∞]` (C3), never a panic.
103//!
104//! The table of step I2 (rows: the sign of `X = [a, b]`; columns: that of
105//! `Y = [c, d]`):
106//!
107//! | | `c ≥ 0` | `c < 0 < d` | `d ≤ 0` |
108//! |---|---|---|---|
109//! | `a ≥ 0` | `[ac, bd]` | `[bc, bd]` | `[bc, ad]` |
110//! | `a < 0 < b` | `[ad, bd]` | `[min(ad, bc), max(ac, bd)]` | `[bc, ac]` |
111//! | `b ≤ 0` | `[ad, bc]` | `[ad, ac]` | `[bd, ac]` |
112//!
113//! ## Proofs
114//! *(N-pre) The primitives never see `∞ − ∞`, `0/0`, `∞/∞` or a NaN.* A
115//! lower endpoint is never `+∞` and an upper one never `−∞` (I2), and
116//! Algorithm I adds lower to lower and upper to upper (for `−`, after
117//! negating the subtrahend); the table of I2 and step N1 remove `0 · ∞`;
118//! in I3 the divisor is never zero, and whenever the divisor can be
119//! infinite the dividend is an endpoint that the sign case makes finite
120//! (`a` in `a/d` with `a ≥ 0`; `b` in `b/c` with `b ≤ 0`; …).
121//!
122//! *(N) Steps N2–N5 return the directed rounding.* `v = RN(t)` for the
123//! exact `t = a ∘ b`, so `pred(v) ≤ t ≤ succ(v)`: `▽t` is `v` when `v ≤ t`
124//! and `pred(v)` otherwise, and that is the sign of `t − v`. It remains
125//! that `σ` has that sign.
126//!
127//! * `+`: Fast2Sum with `|hi| ≥ |lo|` returns the exact error for any
128//!   finite sum, subnormal or not (T1).
129//! * `·`: `|v| ≥ 2⁻⁹⁶⁸` gives `|a b| ≥ 2⁻⁹⁶⁸(1 − u) > 2⁻⁹⁶⁹`, the exact
130//!   range of 2ProdFMA (T2).
131//! * `/`: let `q = v` and `t = a − q b`. With `ulp` of a subnormal equal
132//!   to `η`, `t` is an integer multiple of `g = ulp(q) ulp(b)` and `|t| ≤
133//!   ½ ulp(q) |b| < 2⁵² g`, so `t ∈ F` as soon as `g ≥ η`. For normal `q`
134//!   and `b` that is `e_q + e_b ≥ −970`, implied by `|a| ≥ 2⁻⁹⁶⁸` (`e_q +
135//!   e_b ≥ e_a − 1`); a subnormal `q` forces `|b| > 2⁵⁴` and a subnormal
136//!   `b` forces `|q| > 2⁵⁴`, and `g ≥ η` again. So the FMA returns `t`
137//!   exactly, and `a/b − q = t/b`.
138//! * `√`: with `s = v`, `t = a − s²` is a multiple of `ulp(s)²` and `|t| ≤
139//!   ulp(s) s + ¼ ulp(s)² `, at most `2⁵³` such units; so `t ∈ F` when
140//!   `ulp(s)² ≥ η`, i.e. `a ≥ 2⁻⁹⁷⁰`. (The thresholds `2⁻⁹⁶⁸` and `2⁻⁹⁰⁰`
141//!   are sufficient, not sharp.)
142//!
143//! *(U) Algorithm U.* `2²⁰⁰ v` is exact (`|v| ≤ 2⁻⁷⁶⁷`). If `v` is normal,
144//! U1 was exact and `τ = 0`. Otherwise `2²⁰⁰ v` is `w` rounded to the grid
145//! `2⁻⁸⁷⁴ Z`, both are multiples of `ulp(w)` and `|τ| ≤ |w|`, so `τ ∈ F`
146//! and the subtraction is exact. The exact value is `2⁻²⁰⁰(w + δ)`, and
147//! `(w + δ) − 2²⁰⁰ v = τ + δ`: a nonzero `τ` is a multiple of `ulp(w) >
148//! |δ|` and decides the sign; if `τ = 0`, `δ` does. In step N6 the
149//! hypotheses hold: for the product, `v ≠ 0` gives `|a b| > η/2`, so
150//! `2²⁰⁰ |a b| > 2⁻⁸⁷⁵` is in the exact range of 2Prod, and `|s| < 2⁻⁴⁸³`
151//! makes `2²⁰⁰ s` exact; for the quotient, `|a′| ≥ 2⁻⁸⁷⁴` puts `a′ − w b`
152//! under the argument of (N) — when `w` underflows the residual may be
153//! rounded, but it is a nonzero multiple of `η ulp(b)` with `|b| > 2¹⁴⁸`,
154//! far above `η`: its sign survives, which is all U2 reads.
155//!
156//! *(I) Inclusion and tightness.* `+`, `−`, `·` and `/` (for `0 ∉ Y`) are
157//! monotone in each argument on the boxes that the sign cases delimit, so
158//! the exact range over `X × Y` is the interval between the two endpoint
159//! expressions of I1–I3; `▽` of the lower one and `△` of the upper one are
160//! by definition the tightest endpoints in `F ∪ {±∞}` (I3, with no
161//! exception for underflow or overflow: steps N3 and N6). When an operand
162//! endpoint is infinite, the corresponding expression is the limit, and N1
163//! returns it. I4 and I5 follow the same way; I6 is I2–I3 for `c = d`.
164//!
165//! ## Exceptional cases, in one place
166//! * **Overflow.** `▽` saturates at `Ω`, `△` goes to `+∞` (N3); a result
167//!   may be a half-line, never invalid and never empty.
168//! * **Subnormals and underflow.** Sums are exact there. Products and
169//!   quotients whose FMA residual could be rounded take step N6 and are
170//!   still the exact directed roundings (a result of magnitude below `η`
171//!   becomes `[0, η]` or `[−η, 0]`, keeping its sign).
172//! * **Zero in the divisor.** I4: a half-line or `[−∞, +∞]`; no panic.
173//! * **NaN.** No interval holds a NaN (I2), and no operation on valid
174//!   intervals produces one (N-pre). A NaN enters only through a
175//!   constructor or a point operand: [`Interval::new`] returns an error,
176//!   [`Interval::point`] and [`Interval::mid_rad`] panic, an operator
177//!   and `From<f64>` return `[−∞, +∞]`, [`Interval::enclose`] returns
178//!   `[−∞, +∞]`,
179//!   [`Interval::contains`] and the `certainly_*` predicates return
180//!   `false`.
181//! * **The empty set.** Stored as `[+∞, −∞]`; every arithmetic operation
182//!   with an empty operand returns `∅`; `hull` ignores it; `mid`, `width`,
183//!   `mag` and `mig` are NaN. **The `certainly_*` predicates are `false`
184//!   on `∅`**, although "every element of `∅` is `≤ b`" is vacuously
185//!   true: they are the last step of a certificate, and an empty enclosure
186//!   means that a hypothesis failed upstream, not that a claim was proved
187//!   (C3). `is_subset_of`, a set relation, is `true` for `∅ ⊆ Y`.
188//!
189//! ## Printing
190//! **Algorithm D (decimal output, `{}` and `{:e}`).** Input: a non-empty
191//! `X = [a, b]`, the precision `p` of the format, if any.
192//!
193//! D1. \[No precision.\] Print each endpoint as `f64` prints it: the
194//!     shortest decimal that reads back as the same `f64`. The text
195//!     *identifies* the interval (it is not an enclosure by decimals: the
196//!     shortest decimal of `a` may lie on either side of `a`).
197//! D2. \[Exact expansion.\] With a precision: write `|a|` exactly — an
198//!     `f64` has at most 1074 fractional and 767 significant decimal
199//!     digits, and the formatting of `f64` is exact at that length.
200//! D3. \[Directed truncation.\] Keep `p` fractional digits (`{}`) or `1 +
201//!     p` significant digits (`{:e}`); if a discarded digit is nonzero and
202//!     the direction points away from zero (`▽` for a negative `a`, `△`
203//!     for a positive `b`), add one unit in the last kept place, carrying
204//!     (in `{:e}` a carry out of the leading digit is `1.00…` with the
205//!     exponent one higher).
206//!
207//! (D) *The printed pair, read as exact decimals, contains `X`*, and each
208//! printed endpoint is within one unit of its last digit of the true one:
209//! truncation moves toward zero, the added unit moves past the value by
210//! less than one unit. An infinite endpoint prints as `-inf` or `inf`, `∅`
211//! as `∅`. With a precision, the only other flag honoured is `+`; the
212//! width and the fill are not.
213//!
214//! ## Invariants
215//! (I1) *Inclusion.* `x ∈ X`, `y ∈ Y` and `x ∘ y` defined imply `x ∘ y ∈ X
216//!      ∘ Y`.
217//! (I2) *Well-formed.* A non-empty interval has `lo ≤ hi`, no NaN, `lo <
218//!      +∞`, `hi > −∞`; `∅` is the pair `[+∞, −∞]` and nothing else.
219//!      [`Interval::check_invariants`]; a `debug_assert!` after every
220//!      operation.
221//! (I3) *Tightness.* `+`, `−`, `·`, `/` (divisor without zero), `√` and
222//!      `x²` return the hull of the exact range rounded outward to `F`:
223//!      each endpoint is the directed rounding of the exact one. In
224//!      particular an operation on points returns an interval of at most
225//!      **one ulp** (two adjacent `f64`), and a point when the result is
226//!      an `f64`. The tests check both against exact rationals.
227//!
228//! (I4) *Operator forms.* `X ∘= Y`, `X ∘= y`, `y ∘ X` return, bit for bit,
229//!      `X ∘ Y`, `X ∘ y` and `[y, y] ∘ X` (with `[−∞, +∞]` for a `y` that
230//!      is not a real number, as in step I6).
231//!
232//! ## Cost
233//! Per directed endpoint: one operation, one EFT or FMA and a branch — 4
234//! flops for a sum, 2 for a product, quotient or root, against 1 with a
235//! hardware rounding mode. No allocation.
236//!
237//! ## References
238//! Rump, Zimmermann, Boldo & Melquiond, "Computing predecessor and
239//! successor in rounding to nearest", BIT 49 (2009) — directed results
240//! from round-to-nearest ones; Boldo & Daumas, "Representable correcting
241//! terms for possibly underflowing floating point operations", ARITH-16
242//! (2003) — when the residuals of `/` and `√` are representable; Muller et
243//! al., *Handbook of Floating-Point Arithmetic*, 2nd ed. (2018), §4.3–4.4
244//! and §5.2; IEEE Std 1788-2015 (the set-based model: an infinite
245//! endpoint is not an element; division by an interval containing zero;
246//! `mid` of an unbounded interval); Hickey, Ju & van Emden, "Interval
247//! arithmetic: from principles to implementation", J. ACM 48 (2001) — the
248//! sign table of I2 and the convention `0 · ∞ = 0` for endpoints. **None
249//! of these was reread for this chapter**: the statements used are proved
250//! above (Proofs N, U, I) from invariants T1–T2 of Chapter 11.1, and the
251//! tests check every operation against exact rational arithmetic.
252
253#![allow(clippy::float_cmp)] // exact comparisons of endpoints are the subject
254
255use core::fmt;
256use core::ops::{Add, AddAssign, Div, DivAssign, Mul, MulAssign, Neg, Sub, SubAssign};
257
258use crate::dd::DoubleDouble;
259use crate::eft::{fast_two_sum, two_prod};
260
261/// `η`, the smallest positive subnormal.
262const ETA: f64 = f64::from_bits(1);
263/// `2⁻⁹⁶⁸`: at or above it (for `|RN(a b)|`, resp. for the dividend `|a|`)
264/// the FMA residual of step N4 is exact.
265const EXACT_RESIDUAL: f64 = f64::from_bits((1023 - 968) << 52);
266/// `2⁻⁹⁰⁰`: the same for the radicand (a round number above `2⁻⁹⁷⁰` whose
267/// scaling by `2²⁰⁰` is exact).
268const EXACT_SQRT_RESIDUAL: f64 = f64::from_bits((1023 - 900) << 52);
269/// `2²⁰⁰`, `2⁻²⁰⁰` and `2⁻¹⁰⁰`: the scalings of steps N6 and U.
270const UPSCALE: f64 = f64::from_bits((1023 + 200) << 52);
271const DOWNSCALE: f64 = f64::from_bits((1023 - 200) << 52);
272const DOWNSCALE_SQRT: f64 = f64::from_bits((1023 - 100) << 52);
273
274/// A rounding direction: `▽` or `△`.
275#[derive(Clone, Copy, Debug, PartialEq, Eq)]
276enum Dir {
277    Down,
278    Up,
279}
280
281/// Step N5: `v` moved one step in the direction `dir` when the exact value
282/// lies strictly on that side (`sigma` has the sign of `exact − v`).
283#[inline]
284fn step(v: f64, sigma: f64, dir: Dir) -> f64 {
285    debug_assert!(v.is_finite() && !sigma.is_nan(), "step({v:e}, {sigma:e})");
286    match dir {
287        Dir::Down if sigma < 0.0 => v.next_down(),
288        Dir::Up if sigma > 0.0 => v.next_up(),
289        _ => v,
290    }
291}
292
293/// Step N3: the directed rounding of a finite exact value whose nearest
294/// rounding `v` overflowed.
295#[inline]
296fn overflow(v: f64, dir: Dir) -> f64 {
297    debug_assert!(v.is_infinite());
298    match (dir, v > 0.0) {
299        (Dir::Down, true) => f64::MAX,
300        (Dir::Up, false) => f64::MIN,
301        _ => v,
302    }
303}
304
305/// Algorithm U: the directed rounding of `(w + δ) 2⁻²⁰⁰`.
306#[inline]
307fn descale(w: f64, delta: f64, dir: Dir) -> f64 {
308    let v = w * DOWNSCALE; // U1
309    let tau = w - v * UPSCALE; // U2, exact
310    step(v, if tau == 0.0 { delta } else { tau }, dir) // U3
311}
312
313/// Algorithm N for `a + b`.
314#[inline]
315fn add_dir(a: f64, b: f64, dir: Dir) -> f64 {
316    let v = a + b; // N2
317    debug_assert!(!v.is_nan(), "add_dir({a:e}, {b:e})");
318    if a.is_infinite() || b.is_infinite() {
319        return v; // N1
320    }
321    if v.is_infinite() {
322        return overflow(v, dir); // N3
323    }
324    // N4.
325    let (hi, lo) = if a.abs() >= b.abs() { (a, b) } else { (b, a) };
326    let (_, sigma) = fast_two_sum(hi, lo);
327    step(v, sigma, dir) // N5
328}
329
330/// Algorithm N for `a · b`.
331#[inline]
332fn mul_dir(a: f64, b: f64, dir: Dir) -> f64 {
333    debug_assert!(!a.is_nan() && !b.is_nan(), "mul_dir({a:e}, {b:e})");
334    if a == 0.0 || b == 0.0 {
335        return 0.0; // N1, 0 · ∞ = 0 included
336    }
337    let v = a * b; // N2
338    if a.is_infinite() || b.is_infinite() {
339        return v; // N1
340    }
341    if v.is_infinite() {
342        return overflow(v, dir); // N3
343    }
344    if v.abs() >= EXACT_RESIDUAL {
345        return step(v, a.mul_add(b, -v), dir); // N4, N5
346    }
347    // N6.
348    if v == 0.0 {
349        return match (dir, (a > 0.0) == (b > 0.0)) {
350            (Dir::Up, true) => ETA,
351            (Dir::Down, false) => -ETA,
352            _ => 0.0,
353        };
354    }
355    let (s, l) = if a.abs() <= b.abs() { (a, b) } else { (b, a) };
356    let (w, delta) = two_prod(s * UPSCALE, l);
357    descale(w, delta, dir)
358}
359
360/// Algorithm N for `a / b`, `b ≠ 0`.
361#[inline]
362fn div_dir(a: f64, b: f64, dir: Dir) -> f64 {
363    debug_assert!(
364        !a.is_nan() && !b.is_nan() && b != 0.0,
365        "div_dir({a:e}, {b:e})"
366    );
367    debug_assert!(a.is_finite() || b.is_finite(), "div_dir: ∞ / ∞");
368    if a == 0.0 || b.is_infinite() {
369        return 0.0; // N1
370    }
371    let v = a / b; // N2
372    if a.is_infinite() {
373        return v; // N1
374    }
375    if v.is_infinite() {
376        return overflow(v, dir); // N3
377    }
378    // The sign of `a/b − q` from `ρ = a − q b`.
379    let sigma = |rho: f64| if b > 0.0 { rho } else { -rho };
380    if a.abs() >= EXACT_RESIDUAL {
381        return step(v, sigma((-v).mul_add(b, a)), dir); // N4, N5
382    }
383    // N6.
384    let a2 = a * UPSCALE;
385    let w = a2 / b;
386    descale(w, sigma((-w).mul_add(b, a2)), dir)
387}
388
389/// Algorithm N for `√a`, `a ≥ 0` or `a = +∞`.
390#[inline]
391fn sqrt_dir(a: f64, dir: Dir) -> f64 {
392    debug_assert!(a >= 0.0, "sqrt_dir({a:e})");
393    if a == 0.0 {
394        return 0.0; // N1
395    }
396    if a.is_infinite() {
397        return a; // N1
398    }
399    // N6: both scalings are exact.
400    let (x, back) = if a < EXACT_SQRT_RESIDUAL {
401        (a * UPSCALE, DOWNSCALE_SQRT)
402    } else {
403        (a, 1.0)
404    };
405    let v = x.sqrt(); // N2
406    step(v, (-v).mul_add(v, x), dir) * back // N4, N5
407}
408
409/// A closed interval `[lo, hi]` with `f64` endpoints, or the empty set
410/// (invariants I1–I3). Operations round outward by computed directed
411/// rounding (Chapter 11.9).
412///
413/// An interval is a set of *real* numbers: an infinite endpoint means
414/// "unbounded on that side". Not `xingo_sparse::Real`: intervals have no
415/// total order and their operations no single rounding (D-0080, Q2). Not
416/// `PartialOrd` either: the comparisons are the named predicates below,
417/// whose meaning cannot be misread.
418///
419/// ```
420/// use xingo_extprec::Interval;
421/// let tenth = Interval::point(1.0) / 10.0; // encloses the real 1/10
422/// assert!(tenth.inf() < tenth.sup() && tenth.contains(0.1));
423/// let one = tenth * 10.0;
424/// assert!(one.contains(1.0) && one.certainly_within(1.0 + 1e-15));
425/// ```
426#[derive(Clone, Copy, Debug, PartialEq)]
427pub struct Interval {
428    lo: f64,
429    hi: f64,
430}
431
432/// `lo > hi`, or an endpoint is NaN, or `lo = +∞`, or `hi = −∞`.
433#[derive(Clone, Copy, Debug, PartialEq, Eq)]
434pub struct InvalidInterval;
435
436impl Interval {
437    /// `[−∞, +∞]`: "nothing is known" (invariant C3).
438    pub const ENTIRE: Self = Self {
439        lo: f64::NEG_INFINITY,
440        hi: f64::INFINITY,
441    };
442    /// The empty set (stored as `[+∞, −∞]`; every operation propagates it).
443    pub const EMPTY: Self = Self {
444        lo: f64::INFINITY,
445        hi: f64::NEG_INFINITY,
446    };
447    /// `[0, 0]`.
448    pub const ZERO: Self = Self { lo: 0.0, hi: 0.0 };
449
450    /// The interval of the pair, which the caller proved well-formed.
451    #[inline]
452    fn raw(lo: f64, hi: f64) -> Self {
453        let x = Self { lo, hi };
454        debug_assert!(
455            x.check_invariants().is_ok() && !x.is_empty(),
456            "[{lo:e}, {hi:e}]: {:?}",
457            x.check_invariants()
458        );
459        x
460    }
461
462    /// `[lo, hi]`.
463    ///
464    /// # Errors
465    /// [`InvalidInterval`] when (I2) fails.
466    pub fn new(lo: f64, hi: f64) -> Result<Self, InvalidInterval> {
467        // False for a NaN endpoint too.
468        if lo <= hi && lo < f64::INFINITY && hi > f64::NEG_INFINITY {
469            Ok(Self { lo, hi })
470        } else {
471            Err(InvalidInterval)
472        }
473    }
474
475    /// `[x, x]`. Panics on NaN — and on `±∞`, which is not a real number
476    /// (it would violate (I2)).
477    #[must_use]
478    pub fn point(x: f64) -> Self {
479        assert!(x.is_finite(), "Interval::point({x}): not a real number");
480        Self { lo: x, hi: x }
481    }
482
483    /// `[m − r, m + r]` rounded outward; `r ≥ 0` (`r = +∞` gives
484    /// [`Interval::ENTIRE`], and so does an infinite `m`). Panics if `m`
485    /// or `r` is NaN or `r < 0`.
486    #[must_use]
487    pub fn mid_rad(m: f64, r: f64) -> Self {
488        assert!(
489            !m.is_nan() && r >= 0.0,
490            "Interval::mid_rad({m}, {r}): NaN or a negative radius"
491        );
492        if m.is_infinite() || r.is_infinite() {
493            return Self::ENTIRE;
494        }
495        Self::raw(add_dir(m, -r, Dir::Down), add_dir(m, r, Dir::Up))
496    }
497
498    /// The tightest interval containing the double-double `x`: `[hi, hi]`
499    /// if `lo = 0`, else the two neighbours of `x` in `F`. An infinite or
500    /// NaN `x` — the trace of an overflow or of an invalid operation, not
501    /// a real number — gives [`Interval::ENTIRE`] (invariant C3).
502    #[must_use]
503    pub fn enclose(x: DoubleDouble) -> Self {
504        let (h, l) = (x.hi(), x.lo());
505        if !h.is_finite() || !l.is_finite() {
506            return Self::ENTIRE;
507        }
508        // (D1): `|l| ≤ ulp(h)/2`, so `h + l` lies between `h` and the
509        // neighbour of `h` on the side of `l`.
510        if l > 0.0 {
511            Self::raw(h, h.next_up())
512        } else if l < 0.0 {
513            Self::raw(h.next_down(), h)
514        } else {
515            Self::raw(h, h)
516        }
517    }
518
519    /// The lower endpoint (`+∞` for the empty set).
520    #[must_use]
521    pub const fn inf(self) -> f64 {
522        self.lo
523    }
524
525    /// The upper endpoint (`−∞` for the empty set).
526    #[must_use]
527    pub const fn sup(self) -> f64 {
528        self.hi
529    }
530
531    /// The empty set.
532    #[inline]
533    #[must_use]
534    pub fn is_empty(self) -> bool {
535        self.lo > self.hi
536    }
537
538    /// An `f64` in the interval nearest its midpoint (finite when the
539    /// interval is bounded; `0` for [`Interval::ENTIRE`]). For a
540    /// half-line, the finite `f64` farthest out (`±Ω`, as in IEEE 1788);
541    /// NaN for the empty set.
542    #[must_use]
543    pub fn mid(self) -> f64 {
544        if self.is_empty() {
545            return f64::NAN;
546        }
547        match (self.lo.is_finite(), self.hi.is_finite()) {
548            (false, false) => 0.0,
549            (false, true) => f64::MIN,
550            (true, false) => f64::MAX,
551            // `(lo + hi)/2`, or `lo/2 + hi/2` when the sum overflows:
552            // monotone rounding keeps either inside `[lo, hi]`.
553            (true, true) => f64::midpoint(self.lo, self.hi),
554        }
555    }
556
557    /// `sup − inf` rounded up (`+∞` when unbounded, NaN when empty).
558    #[must_use]
559    pub fn width(self) -> f64 {
560        if self.is_empty() {
561            return f64::NAN;
562        }
563        add_dir(self.hi, -self.lo, Dir::Up)
564    }
565
566    /// `max{|x| : x ∈ X}`, the magnitude (exact; `+∞` when unbounded, NaN
567    /// when empty).
568    #[must_use]
569    pub fn mag(self) -> f64 {
570        if self.is_empty() {
571            return f64::NAN;
572        }
573        self.lo.abs().max(self.hi.abs())
574    }
575
576    /// `min{|x| : x ∈ X}`, the mignitude (exact; NaN when empty).
577    #[must_use]
578    pub fn mig(self) -> f64 {
579        if self.is_empty() {
580            f64::NAN
581        } else if self.lo > 0.0 {
582            self.lo
583        } else if self.hi < 0.0 {
584            -self.hi
585        } else {
586            0.0
587        }
588    }
589
590    /// `x ∈ X` (`false` for a NaN or infinite `x`: the elements are real
591    /// numbers).
592    #[must_use]
593    pub fn contains(self, x: f64) -> bool {
594        x.is_finite() && self.lo <= x && x <= self.hi
595    }
596
597    /// `X ⊆ Y` (`∅` is a subset of every interval).
598    #[must_use]
599    pub fn is_subset_of(self, other: Self) -> bool {
600        self.is_empty() || (other.lo <= self.lo && self.hi <= other.hi)
601    }
602
603    /// Every element of `X` is `≤ b`: **certainly** `x ≤ b`. `false` for
604    /// the empty set and for a NaN `b` (Chapter 11.9: nothing was proved).
605    #[must_use]
606    pub fn certainly_le(self, b: f64) -> bool {
607        !self.is_empty() && self.hi <= b
608    }
609
610    /// Every element of `X` is `≥ a`: **certainly** `x ≥ a`. `false` for
611    /// the empty set and for a NaN `a`.
612    #[must_use]
613    pub fn certainly_ge(self, a: f64) -> bool {
614        !self.is_empty() && self.lo >= a
615    }
616
617    /// `X ⊆ [−t, t]`: **certainly** `|x| ≤ t` (a verified tolerance test).
618    /// `false` for the empty set and for a NaN `t`.
619    #[must_use]
620    pub fn certainly_within(self, t: f64) -> bool {
621        !self.is_empty() && -t <= self.lo && self.hi <= t
622    }
623
624    /// The hull `[min inf, max sup]` (the union's enclosure).
625    #[must_use]
626    pub fn hull(self, other: Self) -> Self {
627        // The stored form of `∅`, `[+∞, −∞]`, is the neutral element.
628        Self {
629            lo: self.lo.min(other.lo),
630            hi: self.hi.max(other.hi),
631        }
632    }
633
634    /// The intersection (possibly [`Interval::EMPTY`]).
635    #[must_use]
636    pub fn intersection(self, other: Self) -> Self {
637        let (lo, hi) = (self.lo.max(other.lo), self.hi.min(other.hi));
638        if lo <= hi {
639            Self { lo, hi }
640        } else {
641            Self::EMPTY
642        }
643    }
644
645    /// `{|x| : x ∈ X}`.
646    #[must_use]
647    pub fn abs(self) -> Self {
648        if self.is_empty() || self.lo >= 0.0 {
649            self
650        } else if self.hi <= 0.0 {
651            -self
652        } else {
653            Self::raw(0.0, (-self.lo).max(self.hi))
654        }
655    }
656
657    /// `{x² : x ∈ X}` (tighter than `X · X` when `0 ∈ X`).
658    #[must_use]
659    pub fn square(self) -> Self {
660        if self.is_empty() {
661            return self;
662        }
663        let (a, b) = (self.lo, self.hi);
664        if a >= 0.0 {
665            Self::raw(mul_dir(a, a, Dir::Down), mul_dir(b, b, Dir::Up))
666        } else if b <= 0.0 {
667            Self::raw(mul_dir(b, b, Dir::Down), mul_dir(a, a, Dir::Up))
668        } else {
669            let m = (-a).max(b);
670            Self::raw(0.0, mul_dir(m, m, Dir::Up))
671        }
672    }
673
674    /// `{√x : x ∈ X, x ≥ 0}` ([`Interval::EMPTY`] when `sup < 0`).
675    #[must_use]
676    pub fn sqrt(self) -> Self {
677        if self.is_empty() || self.hi < 0.0 {
678            return Self::EMPTY;
679        }
680        Self::raw(
681            sqrt_dir(self.lo.max(0.0), Dir::Down),
682            sqrt_dir(self.hi, Dir::Up),
683        )
684    }
685
686    /// Invariant (I2).
687    ///
688    /// # Errors
689    /// The text of the violated invariant.
690    pub fn check_invariants(self) -> Result<(), &'static str> {
691        if self.lo.is_nan() || self.hi.is_nan() {
692            return Err("I2: an endpoint is NaN");
693        }
694        if self.lo == f64::INFINITY && self.hi == f64::NEG_INFINITY {
695            return Ok(()); // ∅
696        }
697        if self.lo > self.hi {
698            return Err("I2: lo > hi in an interval that is not the stored empty set");
699        }
700        if self.lo == f64::INFINITY {
701            return Err("I2: the lower endpoint is +∞");
702        }
703        if self.hi == f64::NEG_INFINITY {
704            return Err("I2: the upper endpoint is −∞");
705        }
706        Ok(())
707    }
708}
709
710/// Step I1.
711impl Add for Interval {
712    type Output = Self;
713    fn add(self, rhs: Self) -> Self {
714        if self.is_empty() || rhs.is_empty() {
715            return Self::EMPTY;
716        }
717        Self::raw(
718            add_dir(self.lo, rhs.lo, Dir::Down),
719            add_dir(self.hi, rhs.hi, Dir::Up),
720        )
721    }
722}
723
724/// Step I1.
725impl Sub for Interval {
726    type Output = Self;
727    fn sub(self, rhs: Self) -> Self {
728        if self.is_empty() || rhs.is_empty() {
729            return Self::EMPTY;
730        }
731        Self::raw(
732            add_dir(self.lo, -rhs.hi, Dir::Down),
733            add_dir(self.hi, -rhs.lo, Dir::Up),
734        )
735    }
736}
737
738/// Step I2.
739impl Mul for Interval {
740    type Output = Self;
741    fn mul(self, rhs: Self) -> Self {
742        if self.is_empty() || rhs.is_empty() {
743            return Self::EMPTY;
744        }
745        let (a, b, c, d) = (self.lo, self.hi, rhs.lo, rhs.hi);
746        let dn = |x, y| mul_dir(x, y, Dir::Down);
747        let up = |x, y| mul_dir(x, y, Dir::Up);
748        let (lo, hi) = if a >= 0.0 {
749            if c >= 0.0 {
750                (dn(a, c), up(b, d))
751            } else if d <= 0.0 {
752                (dn(b, c), up(a, d))
753            } else {
754                (dn(b, c), up(b, d))
755            }
756        } else if b <= 0.0 {
757            if c >= 0.0 {
758                (dn(a, d), up(b, c))
759            } else if d <= 0.0 {
760                (dn(b, d), up(a, c))
761            } else {
762                (dn(a, d), up(a, c))
763            }
764        } else if c >= 0.0 {
765            (dn(a, d), up(b, d))
766        } else if d <= 0.0 {
767            (dn(b, c), up(a, c))
768        } else {
769            (dn(a, d).min(dn(b, c)), up(a, c).max(up(b, d)))
770        };
771        Self::raw(lo, hi)
772    }
773}
774
775/// Steps I3 and I4: when the divisor contains zero the result is
776/// [`Interval::ENTIRE`], or a half-line when zero is an endpoint of the
777/// divisor and the dividend has one sign — the hull of the quotients by
778/// the nonzero elements, never a panic. (`[0, 0] / Y` is `[0, 0]` unless
779/// `Y = [0, 0]`.)
780impl Div for Interval {
781    type Output = Self;
782    fn div(self, rhs: Self) -> Self {
783        if self.is_empty() || rhs.is_empty() {
784            return Self::EMPTY;
785        }
786        let (a, b, c, d) = (self.lo, self.hi, rhs.lo, rhs.hi);
787        let dn = |x, y| div_dir(x, y, Dir::Down);
788        let up = |x, y| div_dir(x, y, Dir::Up);
789        if c == 0.0 && d == 0.0 {
790            return Self::ENTIRE; // I4
791        }
792        if a == 0.0 && b == 0.0 {
793            return Self::ZERO;
794        }
795        if c > 0.0 {
796            // I3.
797            if a >= 0.0 {
798                Self::raw(dn(a, d), up(b, c))
799            } else if b <= 0.0 {
800                Self::raw(dn(a, c), up(b, d))
801            } else {
802                Self::raw(dn(a, c), up(b, c))
803            }
804        } else if d < 0.0 {
805            if a >= 0.0 {
806                Self::raw(dn(b, d), up(a, c))
807            } else if b <= 0.0 {
808                Self::raw(dn(b, c), up(a, d))
809            } else {
810                Self::raw(dn(b, d), up(a, d))
811            }
812        } else if c == 0.0 {
813            // I4, Y = [0, d] with d > 0.
814            if a >= 0.0 {
815                Self::raw(dn(a, d), f64::INFINITY)
816            } else if b <= 0.0 {
817                Self::raw(f64::NEG_INFINITY, up(b, d))
818            } else {
819                Self::ENTIRE
820            }
821        } else if d == 0.0 {
822            // I4, Y = [c, 0] with c < 0.
823            if a >= 0.0 {
824                Self::raw(f64::NEG_INFINITY, up(a, c))
825            } else if b <= 0.0 {
826                Self::raw(dn(b, c), f64::INFINITY)
827            } else {
828                Self::ENTIRE
829            }
830        } else {
831            Self::ENTIRE
832        }
833    }
834}
835
836/// With a point right operand (`[x, x]`, exact): half the work (step I6).
837/// A NaN or infinite `x` gives [`Interval::ENTIRE`].
838impl Add<f64> for Interval {
839    type Output = Self;
840    fn add(self, rhs: f64) -> Self {
841        if self.is_empty() {
842            return self;
843        }
844        if !rhs.is_finite() {
845            return Self::ENTIRE;
846        }
847        Self::raw(
848            add_dir(self.lo, rhs, Dir::Down),
849            add_dir(self.hi, rhs, Dir::Up),
850        )
851    }
852}
853
854/// With a point right operand (`[x, x]`, exact): half the work (step I6).
855/// A NaN or infinite `x` gives [`Interval::ENTIRE`].
856impl Sub<f64> for Interval {
857    type Output = Self;
858    fn sub(self, rhs: f64) -> Self {
859        self + (-rhs)
860    }
861}
862
863/// With a point right operand (`[x, x]`, exact): half the work (step I6).
864/// A NaN or infinite `x` gives [`Interval::ENTIRE`].
865impl Mul<f64> for Interval {
866    type Output = Self;
867    fn mul(self, rhs: f64) -> Self {
868        if self.is_empty() {
869            return self;
870        }
871        if !rhs.is_finite() {
872            return Self::ENTIRE;
873        }
874        let (a, b) = if rhs >= 0.0 {
875            (self.lo, self.hi)
876        } else {
877            (self.hi, self.lo)
878        };
879        Self::raw(mul_dir(a, rhs, Dir::Down), mul_dir(b, rhs, Dir::Up))
880    }
881}
882
883/// With a point right operand (`[x, x]`, exact): half the work (step I6).
884/// A NaN, infinite or zero `x` gives [`Interval::ENTIRE`].
885impl Div<f64> for Interval {
886    type Output = Self;
887    fn div(self, rhs: f64) -> Self {
888        if self.is_empty() {
889            return self;
890        }
891        if !rhs.is_finite() || rhs == 0.0 {
892            return Self::ENTIRE;
893        }
894        let (a, b) = if rhs > 0.0 {
895            (self.lo, self.hi)
896        } else {
897            (self.hi, self.lo)
898        };
899        Self::raw(div_dir(a, rhs, Dir::Down), div_dir(b, rhs, Dir::Up))
900    }
901}
902
903/// The assigning forms: `X ∘= Y` is `X = X ∘ Y`, `X ∘= y` is `X = X ∘ y`
904/// (invariant I4 of Chapter 11.9).
905macro_rules! assign_ops {
906    ($($tr:ident, $f:ident, $op:tt;)*) => {$(
907        impl $tr for Interval {
908            fn $f(&mut self, rhs: Self) {
909                *self = *self $op rhs;
910            }
911        }
912        impl $tr<f64> for Interval {
913            fn $f(&mut self, rhs: f64) {
914                *self = *self $op rhs;
915            }
916        }
917    )*};
918}
919assign_ops! {
920    AddAssign, add_assign, +;
921    SubAssign, sub_assign, -;
922    MulAssign, mul_assign, *;
923    DivAssign, div_assign, /;
924}
925
926/// The point `[y, y]` of a left scalar operand, or what the operation
927/// returns without computing: `∅` for an empty `x`, [`Interval::ENTIRE`]
928/// for a `y` that is not a real number (step I6).
929#[inline]
930fn left_point(y: f64, x: Interval) -> Result<Interval, Interval> {
931    if x.is_empty() {
932        Err(Interval::EMPTY)
933    } else if y.is_finite() {
934        Ok(Interval { lo: y, hi: y })
935    } else {
936        Err(Interval::ENTIRE)
937    }
938}
939
940/// With a point left operand: `y + X` is `[y, y] + X` (invariant I4). A
941/// NaN or infinite `y` gives [`Interval::ENTIRE`].
942impl Add<Interval> for f64 {
943    type Output = Interval;
944    fn add(self, rhs: Interval) -> Interval {
945        left_point(self, rhs).map_or_else(|r| r, |p| p + rhs)
946    }
947}
948
949/// With a point left operand: `y − X` is `[y, y] − X` (invariant I4). A
950/// NaN or infinite `y` gives [`Interval::ENTIRE`].
951impl Sub<Interval> for f64 {
952    type Output = Interval;
953    fn sub(self, rhs: Interval) -> Interval {
954        left_point(self, rhs).map_or_else(|r| r, |p| p - rhs)
955    }
956}
957
958/// With a point left operand: `y · X` is `[y, y] · X` (invariant I4). A
959/// NaN or infinite `y` gives [`Interval::ENTIRE`].
960impl Mul<Interval> for f64 {
961    type Output = Interval;
962    fn mul(self, rhs: Interval) -> Interval {
963        left_point(self, rhs).map_or_else(|r| r, |p| p * rhs)
964    }
965}
966
967/// With a point left operand: `y / X` is `[y, y] / X` (invariant I4; steps
968/// I3 and I4 when `X` contains zero). A NaN or infinite `y` gives
969/// [`Interval::ENTIRE`].
970impl Div<Interval> for f64 {
971    type Output = Interval;
972    fn div(self, rhs: Interval) -> Interval {
973        left_point(self, rhs).map_or_else(|r| r, |p| p / rhs)
974    }
975}
976
977/// `{−x : x ∈ X}`, exact.
978impl Neg for Interval {
979    type Output = Self;
980    fn neg(self) -> Self {
981        // `∅ = [+∞, −∞]` is its own negative.
982        Self {
983            lo: -self.hi,
984            hi: -self.lo,
985        }
986    }
987}
988
989/// The interval of one `f64`, **total**: `[x, x]` for a finite `x`, and
990/// [`Interval::ENTIRE`] for a NaN or an infinite `x`.
991///
992/// This differs from [`Interval::point`], which panics on a NaN or an
993/// infinity, on purpose: `From` must not fail (the standard library's
994/// contract for the trait), and "nothing is known" is what the operators
995/// already return for a scalar operand that is not a real number — so
996/// `Interval::from(y) ∘ X` equals `y ∘ X` for every `y` and every
997/// non-empty `X`. Use `point` when a non-real argument is a bug to be
998/// caught, `from` when it is data to be carried.
999impl From<f64> for Interval {
1000    fn from(x: f64) -> Self {
1001        if x.is_finite() {
1002            Self { lo: x, hi: x }
1003        } else {
1004            Self::ENTIRE
1005        }
1006    }
1007}
1008
1009impl fmt::Display for InvalidInterval {
1010    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1011        f.write_str("invalid interval: the endpoints are not lo <= hi with lo < +inf and hi > -inf")
1012    }
1013}
1014
1015impl core::error::Error for InvalidInterval {}
1016
1017/// Fractional digits that write any `f64` exactly (it is a multiple of
1018/// `2⁻¹⁰⁷⁴`).
1019const EXACT_FRACTION_DIGITS: usize = 1074;
1020/// Digits after the leading one that write any `f64` exactly in
1021/// scientific notation (767 significant digits at most; a round number
1022/// above it).
1023const EXACT_MANTISSA_DIGITS: usize = 800;
1024
1025/// Adds one unit in the last place of a string of ASCII decimal digits;
1026/// `true` if the carry leaves the leading digit (the digits are then all
1027/// zero).
1028fn increment(digits: &mut [u8]) -> bool {
1029    for d in digits.iter_mut().rev() {
1030        if *d == b'9' {
1031            *d = b'0';
1032        } else {
1033            *d += 1;
1034            return false;
1035        }
1036    }
1037    true
1038}
1039
1040/// Whether step D3 adds a unit: the discarded digits are not all zero and
1041/// the direction points away from zero.
1042fn away(x: f64, discarded: &[u8], dir: Dir) -> bool {
1043    discarded.iter().any(|&d| d != b'0') && ((x > 0.0) == (dir == Dir::Up))
1044}
1045
1046/// Steps D2 and D3 for `{:.p}`: `x` with `p` fractional digits, rounded in
1047/// the direction `dir`.
1048fn write_fixed(f: &mut fmt::Formatter<'_>, x: f64, p: usize, dir: Dir) -> fmt::Result {
1049    if !x.is_finite() || p >= EXACT_FRACTION_DIGITS {
1050        // Exact as `f64` prints it (`inf`, or zero padding).
1051        return fmt::Display::fmt(&x, f);
1052    }
1053    let exact = format!("{:.*}", EXACT_FRACTION_DIGITS, x.abs()); // D2
1054    let (int, frac) = exact.split_once('.').expect("a fractional part");
1055    let mut kept: Vec<u8> = int.bytes().chain(frac.bytes().take(p)).collect();
1056    let carry = away(x, &frac.as_bytes()[p..], dir) && increment(&mut kept); // D3
1057    let (int, frac) = kept.split_at(int.len());
1058    if x.is_sign_negative() {
1059        f.write_str("-")?;
1060    } else if f.sign_plus() {
1061        f.write_str("+")?;
1062    }
1063    if carry {
1064        f.write_str("1")?;
1065    }
1066    // ASCII digits.
1067    f.write_str(core::str::from_utf8(int).expect("ASCII digits"))?;
1068    if p > 0 {
1069        f.write_str(".")?;
1070        f.write_str(core::str::from_utf8(frac).expect("ASCII digits"))?;
1071    }
1072    Ok(())
1073}
1074
1075/// Steps D2 and D3 for `{:.pe}`: `x` with `1 + p` significant digits,
1076/// rounded in the direction `dir`.
1077fn write_exp(f: &mut fmt::Formatter<'_>, x: f64, p: usize, dir: Dir) -> fmt::Result {
1078    if !x.is_finite() || p >= EXACT_MANTISSA_DIGITS {
1079        return fmt::LowerExp::fmt(&x, f);
1080    }
1081    let exact = format!("{:.*e}", EXACT_MANTISSA_DIGITS, x.abs()); // D2
1082    let (mantissa, exponent) = exact.split_once('e').expect("an exponent");
1083    let mut exponent: i32 = exponent.parse().expect("a decimal exponent");
1084    let digits: Vec<u8> = mantissa.bytes().filter(|&c| c != b'.').collect();
1085    let (kept, discarded) = digits.split_at(1 + p);
1086    let mut kept = kept.to_vec();
1087    if away(x, discarded, dir) && increment(&mut kept) {
1088        // D3: 9.99… became 10.0…, that is 1.00… with the next exponent.
1089        kept[0] = b'1';
1090        exponent += 1;
1091    }
1092    if x.is_sign_negative() {
1093        f.write_str("-")?;
1094    } else if f.sign_plus() {
1095        f.write_str("+")?;
1096    }
1097    f.write_str(core::str::from_utf8(&kept[..1]).expect("ASCII digits"))?;
1098    if p > 0 {
1099        f.write_str(".")?;
1100        f.write_str(core::str::from_utf8(&kept[1..]).expect("ASCII digits"))?;
1101    }
1102    write!(f, "e{exponent}")
1103}
1104
1105/// `[a, b]`, or `∅` (Algorithm D of Chapter 11.9). Without a precision
1106/// each endpoint is the shortest text that reads back as the same `f64`
1107/// (with the flags of the formatter): the output identifies the interval.
1108/// **With a precision (`{:.3}`) the endpoints are rounded outward**: the
1109/// printed pair, read as exact decimals, contains the interval. The width
1110/// and the fill are then ignored.
1111impl fmt::Display for Interval {
1112    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1113        if self.is_empty() {
1114            return f.write_str("∅");
1115        }
1116        let p = f.precision();
1117        f.write_str("[")?;
1118        match p {
1119            None => fmt::Display::fmt(&self.lo, f)?,
1120            Some(p) => write_fixed(f, self.lo, p, Dir::Down)?,
1121        }
1122        f.write_str(", ")?;
1123        match p {
1124            None => fmt::Display::fmt(&self.hi, f)?,
1125            Some(p) => write_fixed(f, self.hi, p, Dir::Up)?,
1126        }
1127        f.write_str("]")
1128    }
1129}
1130
1131/// `[a, b]` in scientific notation (`{:e}`), or `∅`; as `Display`:
1132/// shortest round-trip endpoints without a precision, **outward-rounded**
1133/// endpoints with one (`{:.3e}`: four significant digits).
1134impl fmt::LowerExp for Interval {
1135    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1136        if self.is_empty() {
1137            return f.write_str("∅");
1138        }
1139        let p = f.precision();
1140        f.write_str("[")?;
1141        match p {
1142            None => fmt::LowerExp::fmt(&self.lo, f)?,
1143            Some(p) => write_exp(f, self.lo, p, Dir::Down)?,
1144        }
1145        f.write_str(", ")?;
1146        match p {
1147            None => fmt::LowerExp::fmt(&self.hi, f)?,
1148            Some(p) => write_exp(f, self.hi, p, Dir::Up)?,
1149        }
1150        f.write_str("]")
1151    }
1152}
1153
1154#[cfg(test)]
1155#[allow(clippy::disallowed_methods)] // L2.4 (Chapter 11.11): the tests may use the libm of `f64` (clippy.toml)
1156mod tests {
1157    use super::*;
1158
1159    const MAX: f64 = f64::MAX;
1160    const INF: f64 = f64::INFINITY;
1161
1162    fn iv(lo: f64, hi: f64) -> Interval {
1163        Interval::new(lo, hi).expect("a valid interval")
1164    }
1165
1166    #[test]
1167    fn constructors_enforce_i2() {
1168        assert_eq!(
1169            Interval::new(1.0, 2.0).map(|x| (x.inf(), x.sup())),
1170            Ok((1.0, 2.0))
1171        );
1172        for (lo, hi) in [
1173            (2.0, 1.0),
1174            (f64::NAN, 1.0),
1175            (1.0, f64::NAN),
1176            (INF, INF),
1177            (-INF, -INF),
1178            (INF, -INF),
1179        ] {
1180            assert_eq!(Interval::new(lo, hi), Err(InvalidInterval), "[{lo}, {hi}]");
1181        }
1182        assert_eq!(Interval::new(-INF, INF), Ok(Interval::ENTIRE));
1183        for x in [
1184            Interval::ENTIRE,
1185            Interval::EMPTY,
1186            Interval::ZERO,
1187            iv(-INF, 3.0),
1188        ] {
1189            assert_eq!(x.check_invariants(), Ok(()));
1190        }
1191        for (lo, hi) in [
1192            (2.0, 1.0),
1193            (f64::NAN, 1.0),
1194            (INF, INF),
1195            (-INF, -INF),
1196            (INF, 0.0),
1197        ] {
1198            assert!(
1199                Interval { lo, hi }.check_invariants().is_err(),
1200                "[{lo}, {hi}]"
1201            );
1202        }
1203        assert!(Interval::EMPTY.is_empty() && !Interval::ZERO.is_empty());
1204        assert_eq!(Interval::point(-0.0), Interval::ZERO);
1205    }
1206
1207    #[test]
1208    #[should_panic(expected = "not a real number")]
1209    fn point_rejects_nan() {
1210        let _ = Interval::point(f64::NAN);
1211    }
1212
1213    #[test]
1214    #[should_panic(expected = "not a real number")]
1215    fn point_rejects_infinity() {
1216        let _ = Interval::point(INF);
1217    }
1218
1219    #[test]
1220    #[should_panic(expected = "negative radius")]
1221    fn mid_rad_rejects_a_negative_radius() {
1222        let _ = Interval::mid_rad(0.0, -1.0);
1223    }
1224
1225    #[test]
1226    fn mid_rad_rounds_outward() {
1227        assert_eq!(Interval::mid_rad(1.0, 0.0), Interval::point(1.0));
1228        assert_eq!(Interval::mid_rad(1.0, 0.5), iv(0.5, 1.5));
1229        // 1 ± 2^-60 is not representable: one step out on each side.
1230        let x = Interval::mid_rad(1.0, 2f64.powi(-60));
1231        assert_eq!((x.inf(), x.sup()), (1.0_f64.next_down(), 1.0_f64.next_up()));
1232        assert_eq!(Interval::mid_rad(1.0, INF), Interval::ENTIRE);
1233        assert_eq!(Interval::mid_rad(-INF, 1.0), Interval::ENTIRE);
1234        assert_eq!(Interval::mid_rad(MAX, MAX), iv(0.0, INF));
1235    }
1236
1237    #[test]
1238    fn enclose_is_the_two_neighbours() {
1239        let u = 2f64.powi(-53);
1240        assert_eq!(
1241            Interval::enclose(DoubleDouble::from_f64(3.0)),
1242            Interval::point(3.0)
1243        );
1244        let up = Interval::enclose(DoubleDouble::from_sum(1.0, u * u));
1245        assert_eq!((up.inf(), up.sup()), (1.0, 1.0_f64.next_up()));
1246        let down = Interval::enclose(DoubleDouble::from_sum(1.0, -u * u));
1247        assert_eq!((down.inf(), down.sup()), (1.0_f64.next_down(), 1.0));
1248        let top = Interval::enclose(DoubleDouble::from_sum(MAX, 1.0));
1249        assert_eq!((top.inf(), top.sup()), (MAX, INF));
1250        assert_eq!(Interval::enclose(DoubleDouble::NAN), Interval::ENTIRE);
1251        assert_eq!(Interval::enclose(DoubleDouble::INFINITY), Interval::ENTIRE);
1252        assert_eq!(Interval::enclose(-DoubleDouble::INFINITY), Interval::ENTIRE);
1253    }
1254
1255    #[test]
1256    fn sums_round_outward_by_one_step() {
1257        let u = 2f64.powi(-53);
1258        // 1 + 2^-53 is a tie: RN gives 1, the exact value is above.
1259        let s = Interval::point(1.0) + u;
1260        assert_eq!((s.inf(), s.sup()), (1.0, 1.0_f64.next_up()));
1261        // 1 − 2^-53 is an f64; 1 − 2^-54 is a tie, rounded to 1.
1262        assert_eq!(
1263            Interval::point(1.0) - u,
1264            Interval::point(1.0_f64.next_down())
1265        );
1266        let s = Interval::point(1.0) - 0.5 * u;
1267        assert_eq!((s.inf(), s.sup()), (1.0_f64.next_down(), 1.0));
1268        // Exact sums stay points, subnormal ones included.
1269        assert_eq!(
1270            Interval::point(3.0) + Interval::point(4.0),
1271            Interval::point(7.0)
1272        );
1273        assert_eq!(Interval::point(ETA) + ETA, Interval::point(2.0 * ETA));
1274        assert_eq!(Interval::point(ETA) - ETA, Interval::ZERO);
1275        assert_eq!(iv(1.0, 2.0) - iv(1.0, 2.0), iv(-1.0, 1.0));
1276    }
1277
1278    #[test]
1279    fn overflow_saturates_the_inner_endpoint() {
1280        // N3: a lower endpoint never becomes +∞, an upper one never −∞.
1281        let s = Interval::point(MAX) + MAX;
1282        assert_eq!((s.inf(), s.sup()), (MAX, INF));
1283        let s = Interval::point(-MAX) - MAX;
1284        assert_eq!((s.inf(), s.sup()), (-INF, -MAX));
1285        let p = Interval::point(MAX) * 2.0;
1286        assert_eq!((p.inf(), p.sup()), (MAX, INF));
1287        let p = Interval::point(MAX) * Interval::point(-2.0);
1288        assert_eq!((p.inf(), p.sup()), (-INF, -MAX));
1289        let q = Interval::point(MAX) / 0.5;
1290        assert_eq!((q.inf(), q.sup()), (MAX, INF));
1291        let q = Interval::point(1.0) / Interval::point(-ETA);
1292        assert_eq!((q.inf(), q.sup()), (-INF, -MAX));
1293        // MAX + ulp/4 does not overflow in RN; the upper endpoint does.
1294        let s = Interval::point(MAX) + 2f64.powi(969);
1295        assert_eq!((s.inf(), s.sup()), (MAX, INF));
1296        assert_eq!(Interval::point(MAX).square().sup(), INF);
1297        assert_eq!(Interval::point(MAX).square().inf(), MAX);
1298    }
1299
1300    #[test]
1301    fn products_in_the_underflow_range_are_still_tight() {
1302        let x = 1.0 + f64::EPSILON;
1303        // Total underflow keeps the sign (step N6).
1304        let p = Interval::point(1e-200) * 1e-200;
1305        assert_eq!((p.inf(), p.sup()), (0.0, ETA));
1306        let p = Interval::point(1e-200) * -1e-200;
1307        assert_eq!((p.inf(), p.sup()), (-ETA, 0.0));
1308        // η/2 exactly: RN is 0 (tie to even).
1309        let p = Interval::point(ETA) * 0.5;
1310        assert_eq!((p.inf(), p.sup()), (0.0, ETA));
1311        // An exact subnormal product is a point.
1312        // 2^-500 · 2^-560 = 2^-1060 = 2^14 η.
1313        assert_eq!(
1314            Interval::point(2f64.powi(-500)) * 2f64.powi(-560),
1315            Interval::point(16384.0 * ETA)
1316        );
1317        assert_eq!(Interval::point(3.0 * ETA) * 1.0, Interval::point(3.0 * ETA));
1318        // (1 + 2^-52)² 2^-972: the FMA residual 2^-1076 rounds to zero and
1319        // would lose the sign; the product is just above RN.
1320        let a = x * 2f64.powi(-486);
1321        let p = Interval::point(a) * a;
1322        let v = a * a;
1323        assert_eq!(a.mul_add(a, -v), 0.0);
1324        assert_eq!((p.inf(), p.sup()), (v, v.next_up()));
1325        // 1.5 η rounds to 2η (tie to even): the exact value is below.
1326        let p = Interval::point(3.0 * ETA) * 0.5;
1327        assert_eq!((p.inf(), p.sup()), (ETA, 2.0 * ETA));
1328        // 2.5 η rounds to 2η: the exact value is above.
1329        let p = Interval::point(5.0 * ETA) * -0.5;
1330        assert_eq!((p.inf(), p.sup()), (-3.0 * ETA, -2.0 * ETA));
1331    }
1332
1333    #[test]
1334    fn quotients_round_outward_everywhere() {
1335        let t = Interval::point(1.0) / 3.0;
1336        assert_eq!(t.sup(), t.inf().next_up());
1337        assert!(t.inf() * 3.0 <= 1.0 && t.contains(1.0 / 3.0));
1338        assert_eq!(
1339            Interval::point(6.0) / Interval::point(-3.0),
1340            Interval::point(-2.0)
1341        );
1342        // Quotient underflow: η/3 is below η/2.
1343        let q = Interval::point(ETA) / 3.0;
1344        assert_eq!((q.inf(), q.sup()), (0.0, ETA));
1345        let q = Interval::point(-ETA) / 3.0;
1346        assert_eq!((q.inf(), q.sup()), (-ETA, 0.0));
1347        // 3η/2 = 1.5η: a tie rounded to 2η.
1348        let q = Interval::point(3.0 * ETA) / 2.0;
1349        assert_eq!((q.inf(), q.sup()), (ETA, 2.0 * ETA));
1350        // An exact subnormal quotient is a point.
1351        assert_eq!(Interval::point(6.0 * ETA) / 3.0, Interval::point(2.0 * ETA));
1352        // Tiny dividend, tiny divisor: an ordinary quotient through N6.
1353        let q = Interval::point(2f64.powi(-1000)) / (3.0 * 2f64.powi(-1000));
1354        assert_eq!(q, Interval::point(1.0) / 3.0);
1355        // q = (1 + 2^-52) 2^-1000 is RN(a / b) for b = 1 + 2^-52 and a = (1 +
1356        // 2^-51) 2^-1000, and a − q b = −2^-1104: the FMA residual rounds
1357        // to zero and would lose the sign. Step N6 keeps it.
1358        let (a, b) = (
1359            (1.0 + 2.0 * f64::EPSILON) * 2f64.powi(-1000),
1360            1.0 + f64::EPSILON,
1361        );
1362        let v = a / b;
1363        assert_eq!(v, b * 2f64.powi(-1000));
1364        assert_eq!((-v).mul_add(b, a), 0.0);
1365        let q = Interval::point(a) / b;
1366        assert_eq!((q.inf(), q.sup()), (v.next_down(), v));
1367        let q = Interval::point(a) / Interval::point(-b);
1368        assert_eq!((q.inf(), q.sup()), (-v, (-v).next_up()));
1369        // A quotient that underflows completely.
1370        let q = Interval::point(2f64.powi(-1000)) / -2f64.powi(1000);
1371        assert_eq!((q.inf(), q.sup()), (-ETA, 0.0));
1372    }
1373
1374    #[test]
1375    fn division_by_an_interval_with_zero() {
1376        let one_two = iv(1.0, 2.0);
1377        assert_eq!(one_two / iv(-1.0, 1.0), Interval::ENTIRE);
1378        assert_eq!(one_two / Interval::ZERO, Interval::ENTIRE);
1379        assert_eq!(Interval::ZERO / Interval::ZERO, Interval::ENTIRE);
1380        assert_eq!(one_two / 0.0, Interval::ENTIRE);
1381        assert_eq!(Interval::ZERO / iv(-1.0, 1.0), Interval::ZERO);
1382        assert_eq!(one_two / iv(0.0, 4.0), iv(0.25, INF));
1383        assert_eq!(-one_two / iv(0.0, 4.0), iv(-INF, -0.25));
1384        assert_eq!(one_two / iv(-4.0, 0.0), iv(-INF, -0.25));
1385        assert_eq!(-one_two / iv(-4.0, 0.0), iv(0.25, INF));
1386        assert_eq!(iv(-1.0, 2.0) / iv(0.0, 4.0), Interval::ENTIRE);
1387        assert_eq!(iv(0.0, 2.0) / iv(0.0, 4.0), iv(0.0, INF));
1388    }
1389
1390    #[test]
1391    fn infinite_endpoints_bound_sets_of_reals() {
1392        let pos = iv(0.0, INF);
1393        // 0 · ∞ = 0 for endpoints (step N1).
1394        assert_eq!(pos * Interval::ZERO, Interval::ZERO);
1395        assert_eq!(Interval::ENTIRE * 0.0, Interval::ZERO);
1396        assert_eq!(pos * iv(2.0, 3.0), pos);
1397        assert_eq!(pos * iv(-3.0, 2.0), Interval::ENTIRE);
1398        assert_eq!(pos + iv(1.0, 2.0), iv(1.0, INF));
1399        assert_eq!(pos - pos, Interval::ENTIRE);
1400        assert_eq!(iv(1.0, INF) / iv(2.0, INF), pos);
1401        assert_eq!(iv(-INF, -1.0) / iv(2.0, 4.0), iv(-INF, -0.25));
1402        assert_eq!(iv(4.0, INF).sqrt(), iv(2.0, INF));
1403        assert_eq!(iv(-INF, 3.0).square(), pos);
1404        assert_eq!(iv(-INF, 3.0).abs(), pos);
1405        assert_eq!(-iv(-INF, 3.0), iv(-3.0, INF));
1406        // A non-real point operand: nothing is known.
1407        for bad in [f64::NAN, INF, -INF] {
1408            assert_eq!(iv(1.0, 2.0) + bad, Interval::ENTIRE);
1409            assert_eq!(iv(1.0, 2.0) - bad, Interval::ENTIRE);
1410            assert_eq!(iv(1.0, 2.0) * bad, Interval::ENTIRE);
1411            assert_eq!(iv(1.0, 2.0) / bad, Interval::ENTIRE);
1412        }
1413    }
1414
1415    #[test]
1416    fn the_empty_set_propagates_and_proves_nothing() {
1417        let e = Interval::EMPTY;
1418        let x = iv(1.0, 2.0);
1419        for r in [e + x, x + e, e - x, x - e, e * x, x * e, e / x, x / e] {
1420            assert!(r.is_empty());
1421        }
1422        for r in [e + 1.0, e - 1.0, e * 1.0, e / 1.0, e / 0.0, e + f64::NAN] {
1423            assert!(r.is_empty());
1424        }
1425        assert!((-e).is_empty() && e.abs().is_empty() && e.square().is_empty());
1426        assert!(e.sqrt().is_empty() && iv(-2.0, -1.0).sqrt().is_empty());
1427        assert_eq!(e.hull(x), x);
1428        assert_eq!(x.hull(e), x);
1429        assert!(e.hull(e).is_empty() && e.intersection(x).is_empty());
1430        assert!(x.intersection(iv(3.0, 4.0)).is_empty());
1431        assert!(e.mid().is_nan() && e.width().is_nan() && e.mag().is_nan() && e.mig().is_nan());
1432        assert!(!e.contains(0.0));
1433        assert!(e.is_subset_of(x) && e.is_subset_of(e) && !x.is_subset_of(e));
1434        // Chapter 11.9: the predicates of a certificate are false on ∅.
1435        assert!(!e.certainly_le(INF) && !e.certainly_ge(-INF) && !e.certainly_within(INF));
1436        assert_eq!(e.check_invariants(), Ok(()));
1437        assert_eq!(e.to_string(), "∅");
1438    }
1439
1440    #[test]
1441    fn square_roots_are_tight() {
1442        assert_eq!(iv(4.0, 9.0).sqrt(), iv(2.0, 3.0));
1443        assert_eq!(iv(-4.0, 9.0).sqrt(), iv(0.0, 3.0));
1444        assert_eq!(Interval::ZERO.sqrt(), Interval::ZERO);
1445        let r = Interval::point(2.0).sqrt();
1446        assert_eq!(r.sup(), r.inf().next_up());
1447        assert!(r.inf() * r.inf() < 2.0 && r.sup() * r.sup() > 2.0);
1448        // Subnormal radicands: √η = 2^-537 exactly; √(2η) is irrational.
1449        assert_eq!(
1450            Interval::point(ETA).sqrt(),
1451            Interval::point(2f64.powi(-537))
1452        );
1453        let r = Interval::point(2.0 * ETA).sqrt();
1454        let two = Interval::point(2.0).sqrt();
1455        assert_eq!(
1456            (r.inf(), r.sup()),
1457            (two.inf() * 2f64.powi(-537), two.sup() * 2f64.powi(-537))
1458        );
1459        let r = Interval::point(MAX).sqrt();
1460        assert_eq!(r.sup(), r.inf().next_up());
1461    }
1462
1463    #[test]
1464    fn squares_know_about_zero() {
1465        assert_eq!(iv(-2.0, 3.0).square(), iv(0.0, 9.0));
1466        assert_eq!(iv(-3.0, 2.0).square(), iv(0.0, 9.0));
1467        assert_eq!(iv(-3.0, -2.0).square(), iv(4.0, 9.0));
1468        assert_eq!(iv(2.0, 3.0).square(), iv(4.0, 9.0));
1469        // X · X does not: it is wider.
1470        assert_eq!(iv(-2.0, 3.0) * iv(-2.0, 3.0), iv(-6.0, 9.0));
1471    }
1472
1473    #[test]
1474    fn the_sign_table_of_the_product() {
1475        let (p, m, n) = (iv(2.0, 3.0), iv(-2.0, 3.0), iv(-3.0, -2.0));
1476        assert_eq!(p * p, iv(4.0, 9.0));
1477        assert_eq!(p * m, iv(-6.0, 9.0));
1478        assert_eq!(p * n, iv(-9.0, -4.0));
1479        assert_eq!(m * p, iv(-6.0, 9.0));
1480        assert_eq!(m * m, iv(-6.0, 9.0));
1481        assert_eq!(m * n, iv(-9.0, 6.0));
1482        assert_eq!(n * p, iv(-9.0, -4.0));
1483        assert_eq!(n * m, iv(-9.0, 6.0));
1484        assert_eq!(n * n, iv(4.0, 9.0));
1485        assert_eq!(iv(-5.0, 1.0) * iv(-1.0, 7.0), iv(-35.0, 7.0));
1486        assert_eq!(p * -2.0, iv(-6.0, -4.0));
1487        assert_eq!(m * 2.0, iv(-4.0, 6.0));
1488        // The quotient's table.
1489        assert_eq!(iv(4.0, 8.0) / iv(2.0, 4.0), iv(1.0, 4.0));
1490        assert_eq!(iv(-8.0, 4.0) / iv(2.0, 4.0), iv(-4.0, 2.0));
1491        assert_eq!(iv(-8.0, -4.0) / iv(2.0, 4.0), iv(-4.0, -1.0));
1492        assert_eq!(iv(4.0, 8.0) / iv(-4.0, -2.0), iv(-4.0, -1.0));
1493        assert_eq!(iv(-8.0, 4.0) / iv(-4.0, -2.0), iv(-2.0, 4.0));
1494        assert_eq!(iv(-8.0, -4.0) / iv(-4.0, -2.0), iv(1.0, 4.0));
1495        assert_eq!(iv(-8.0, 4.0) / -2.0, iv(-2.0, 4.0));
1496    }
1497
1498    #[test]
1499    fn queries() {
1500        let x = iv(-1.0, 3.0);
1501        assert_eq!((x.mid(), x.width(), x.mag(), x.mig()), (1.0, 4.0, 3.0, 0.0));
1502        assert_eq!(iv(2.0, 3.0).mig(), 2.0);
1503        assert_eq!(iv(-3.0, -2.0).mig(), 2.0);
1504        assert_eq!(iv(-3.0, -2.0).mag(), 3.0);
1505        assert_eq!(Interval::ENTIRE.mid(), 0.0);
1506        assert_eq!(iv(1.0, INF).mid(), MAX);
1507        assert_eq!(iv(-INF, 1.0).mid(), -MAX);
1508        assert_eq!(iv(-MAX, MAX).mid(), 0.0);
1509        assert_eq!(iv(MAX, MAX).mid(), MAX);
1510        assert_eq!(iv(1.0, INF).width(), INF);
1511        assert_eq!(iv(-MAX, MAX).width(), INF);
1512        assert_eq!(Interval::ENTIRE.mag(), INF);
1513        // The width is rounded up.
1514        assert_eq!(iv(-2f64.powi(-60), 1.0).width(), 1.0_f64.next_up());
1515        assert!(x.contains(-1.0) && x.contains(3.0) && !x.contains(3.5));
1516        assert!(!x.contains(f64::NAN) && !Interval::ENTIRE.contains(INF));
1517        assert!(iv(0.0, 1.0).is_subset_of(x) && !x.is_subset_of(iv(0.0, 1.0)));
1518        assert!(x.is_subset_of(Interval::ENTIRE));
1519        assert!(x.certainly_le(3.0) && !x.certainly_le(2.9));
1520        assert!(x.certainly_ge(-1.0) && !x.certainly_ge(-0.9));
1521        assert!(x.certainly_within(3.0) && !x.certainly_within(2.9));
1522        assert!(!x.certainly_le(f64::NAN) && !x.certainly_ge(f64::NAN));
1523        assert!(!x.certainly_within(f64::NAN) && !x.certainly_within(-5.0));
1524        assert_eq!(x.hull(iv(5.0, 6.0)), iv(-1.0, 6.0));
1525        assert_eq!(x.intersection(iv(2.0, 6.0)), iv(2.0, 3.0));
1526        assert_eq!(x.intersection(iv(3.0, 6.0)), Interval::point(3.0));
1527        assert_eq!(x.abs(), iv(0.0, 3.0));
1528        assert_eq!(iv(-3.0, -1.0).abs(), iv(1.0, 3.0));
1529        assert_eq!(iv(1.0, 3.0).abs(), iv(1.0, 3.0));
1530    }
1531
1532    #[test]
1533    fn display() {
1534        assert_eq!(iv(-1.5, 2.0).to_string(), "[-1.5, 2]");
1535        assert_eq!(Interval::ENTIRE.to_string(), "[-inf, inf]");
1536        assert_eq!(Interval::point(0.1).to_string(), "[0.1, 0.1]");
1537        assert_eq!(format!("{:e}", iv(-1.5, 2000.0)), "[-1.5e0, 2e3]");
1538        assert_eq!(format!("{:e}", Interval::EMPTY), "∅");
1539        assert_eq!(format!("{:.2}", Interval::EMPTY), "∅");
1540    }
1541
1542    /// Algorithm D: with a precision the decimals round outward.
1543    #[test]
1544    fn display_with_a_precision_rounds_outward() {
1545        // f64 rounds 0.126 to 0.13 and 0.124 to 0.12; here the lower
1546        // endpoint goes down and the upper one up, whatever the digit.
1547        assert_eq!(format!("{:.2}", iv(0.124, 0.126)), "[0.12, 0.13]");
1548        assert_eq!(format!("{:.2}", iv(0.121, 0.129)), "[0.12, 0.13]");
1549        assert_eq!(format!("{:.2}", iv(-0.129, -0.121)), "[-0.13, -0.12]");
1550        assert_eq!(format!("{:.0}", iv(-0.5, 0.5)), "[-1, 1]");
1551        assert_eq!(format!("{:.0}", iv(1.0, 2.0)), "[1, 2]");
1552        // The decimal 0.1 is below the f64 0.1 = 0.1000000000000000055…
1553        assert_eq!(format!("{:.1}", Interval::point(0.1)), "[0.1, 0.2]");
1554        assert_eq!(format!("{:.3}", Interval::point(0.125)), "[0.125, 0.125]");
1555        assert_eq!(format!("{:.1}", iv(9.95, 9.96)), "[9.9, 10.0]");
1556        assert_eq!(format!("{:.1}", iv(-99.99, 99.99)), "[-100.0, 100.0]");
1557        // Zeros keep their sign, as f64 prints them.
1558        assert_eq!(format!("{:.2}", iv(-0.0, 0.0)), "[-0.00, 0.00]");
1559        assert_eq!(format!("{:.2}", iv(0.0, 0.0)), "[0.00, 0.00]");
1560        assert_eq!(format!("{:+.1}", iv(-1.0, 1.0)), "[-1.0, +1.0]");
1561        // Subnormals: the smallest positive one is far below 10^-3.
1562        assert_eq!(format!("{:.3}", iv(-ETA, ETA)), "[-0.001, 0.001]");
1563        assert_eq!(format!("{:.3}", iv(0.0, ETA)), "[0.000, 0.001]");
1564        assert_eq!(format!("{:.2}", Interval::ENTIRE), "[-inf, inf]");
1565        assert_eq!(format!("{:.1}", iv(1.0, INF)), "[1.0, inf]");
1566        // The whole expansion when the precision asks for it.
1567        let s = format!("{:.1100}", Interval::point(ETA));
1568        assert_eq!(s, format!("[{ETA:.1100}, {ETA:.1100}]"));
1569
1570        // Scientific notation.
1571        assert_eq!(format!("{:.2e}", iv(1234.0, 5678.0)), "[1.23e3, 5.68e3]");
1572        assert_eq!(
1573            format!("{:.2e}", iv(-5678.0, -1234.0)),
1574            "[-5.68e3, -1.23e3]"
1575        );
1576        assert_eq!(format!("{:.0e}", iv(1.5, 2.5)), "[1e0, 3e0]");
1577        assert_eq!(format!("{:.1e}", iv(0.0996, 9.96)), "[9.9e-2, 1.0e1]");
1578        assert_eq!(format!("{:.1e}", iv(-9.96, -0.0)), "[-1.0e1, -0.0e0]");
1579        assert_eq!(format!("{:.3e}", iv(0.0, 0.0)), "[0.000e0, 0.000e0]");
1580        assert_eq!(format!("{:.2e}", iv(-ETA, ETA)), "[-4.95e-324, 4.95e-324]");
1581        assert_eq!(format!("{:.2e}", iv(-MAX, MAX)), "[-1.80e308, 1.80e308]");
1582        assert_eq!(format!("{:.1e}", Interval::ENTIRE), "[-inf, inf]");
1583        assert_eq!(
1584            format!("{:.3e}", Interval::point(1.0)),
1585            "[1.000e0, 1.000e0]"
1586        );
1587    }
1588
1589    #[test]
1590    fn from_f64_is_total() {
1591        for x in [
1592            0.0,
1593            -0.0,
1594            0.1,
1595            -7.5,
1596            ETA,
1597            -ETA,
1598            MAX,
1599            -MAX,
1600            f64::MIN_POSITIVE,
1601        ] {
1602            let (p, f) = (Interval::point(x), Interval::from(x));
1603            assert_eq!(p.inf().to_bits(), f.inf().to_bits(), "{x:e}");
1604            assert_eq!(p.sup().to_bits(), f.sup().to_bits(), "{x:e}");
1605            let g: Interval = x.into();
1606            assert_eq!(g, f);
1607        }
1608        for x in [f64::NAN, INF, -INF] {
1609            assert_eq!(Interval::from(x), Interval::ENTIRE, "{x}");
1610            // The same answer as the operators with that scalar.
1611            assert_eq!(Interval::from(x) + iv(1.0, 2.0), x + iv(1.0, 2.0));
1612        }
1613    }
1614
1615    #[test]
1616    fn errors_are_errors() {
1617        let e: Box<dyn core::error::Error> = Box::new(InvalidInterval);
1618        assert!(e.to_string().starts_with("invalid interval"));
1619    }
1620
1621    /// Invariant (I4) on the cases of the sign tables and the exceptions.
1622    #[test]
1623    fn operator_forms_agree_bit_for_bit() {
1624        let same = |p: Interval, q: Interval| {
1625            p.inf().to_bits() == q.inf().to_bits() && p.sup().to_bits() == q.sup().to_bits()
1626        };
1627        let xs = [
1628            iv(2.0, 3.0),
1629            iv(-2.0, 3.0),
1630            iv(-3.0, -2.0),
1631            iv(0.0, 0.1),
1632            iv(-0.1, 0.0),
1633            Interval::ZERO,
1634            iv(1.0, INF),
1635            Interval::ENTIRE,
1636            Interval::EMPTY,
1637        ];
1638        let ys = [0.1, -0.3, 0.0, 7.0, MAX, ETA, f64::NAN, INF, -INF];
1639        for &x in &xs {
1640            for &z in &xs {
1641                let mut t = x;
1642                t += z;
1643                assert!(same(t, x + z));
1644                t = x;
1645                t -= z;
1646                assert!(same(t, x - z));
1647                t = x;
1648                t *= z;
1649                assert!(same(t, x * z));
1650                t = x;
1651                t /= z;
1652                assert!(same(t, x / z));
1653            }
1654            for &y in &ys {
1655                let mut t = x;
1656                t += y;
1657                assert!(same(t, x + y));
1658                t = x;
1659                t -= y;
1660                assert!(same(t, x - y));
1661                t = x;
1662                t *= y;
1663                assert!(same(t, x * y));
1664                t = x;
1665                t /= y;
1666                assert!(same(t, x / y));
1667                // A left scalar is the point [y, y]; not a real number:
1668                // ENTIRE (∅ for an empty X).
1669                let point = |op: fn(Interval, Interval) -> Interval| {
1670                    if x.is_empty() {
1671                        Interval::EMPTY
1672                    } else if y.is_finite() {
1673                        op(Interval::point(y), x)
1674                    } else {
1675                        Interval::ENTIRE
1676                    }
1677                };
1678                assert!(same(y + x, point(|p, q| p + q)), "{y} + {x:?}");
1679                assert!(same(y - x, point(|p, q| p - q)), "{y} - {x:?}");
1680                assert!(same(y * x, point(|p, q| p * q)), "{y} * {x:?}");
1681                assert!(same(y / x, point(|p, q| p / q)), "{y} / {x:?}");
1682            }
1683        }
1684        assert_eq!(1.0 - iv(0.25, 0.5), iv(0.5, 0.75));
1685        assert_eq!(1.0 / iv(2.0, 4.0), iv(0.25, 0.5));
1686        assert_eq!(1.0 / iv(0.0, 4.0), iv(0.25, INF));
1687        assert_eq!(1.0 / iv(-1.0, 1.0), Interval::ENTIRE);
1688        assert_eq!(0.0 / iv(-1.0, 1.0), Interval::ZERO);
1689    }
1690}