Skip to main content

xingo_extprec/
lib.rs

1//! # Chapter 11 — `xingo-extprec`: extended precision and rigorous enclosures
2//!
3//! **Status: complete for v0.1.** The contract of the crate was ratified on
4//! 2026-11-15 (decision log of the Xingó solver, D-0081 and D-0109;
5//! questions E1–E8 below all answered "yes" as proposed). Labels such as
6//! L2.2a are tasks of the solver's plan (see "History" at the end), and
7//! D-xxxx are entries of its decision log. Implemented here: the error-free
8//! transformations (Chapter 11.1), [`DoubleDouble`] with `impl
9//! xingo_sparse::Real` (Chapter 11.2), its decimal conversions (Chapters
10//! 11.3 and 11.4), the kernels — definitions, scalar reference and
11//! run-time dispatch (Chapter 11.5), SIMD through `pulp` (Chapter 11.6) —
12//! the dense kernel [`DdDense`] (Chapter 11.7), the profile of
13//! `LuOptions` for double-double (Chapter 11.8), [`Interval`] (Chapter
14//! 11.9), the module [`verify`] — rigorous residuals, polishing and a
15//! rigorous bound of the error of a solution (Chapter 11.10; the last added
16//! by task X0.3, decision log D-0125) — and the elementary functions of [`DoubleDouble`] with
17//! proven bounds, [`DoubleDouble::FUNCTION_BOUNDS`] (Chapter 11.11; the
18//! contract of L2.4 is decision log D-0121). The sections "Corrections to the approved
19//! contract" list what the implementation found wrong in it.
20//!
21//! ## Purpose
22//! A solver computes in `f64` and must sometimes know *how wrong* it is. A
23//! basis solve `B x = b` on an ill-conditioned basis returns an `x` whose
24//! residual, recomputed in `f64`, is itself rounding noise; a feasibility
25//! claim `|a_iᵀx − b_i| ≤ 10⁻⁹` checked in the arithmetic that produced `x`
26//! proves nothing. Between `f64` and exact rational arithmetic (the
27//! solver's `--exact-check`) there is a cheap intermediate step with two parts:
28//!
29//! 1. **more precision** — double-double numbers (an unevaluated sum of two
30//!    `f64`, about 32 decimal digits) at 10–25 flops per operation, in
31//!    which residuals can be computed and solutions *polished* by iterative
32//!    refinement, and in which the LU of `xingo-sparse` can be instantiated
33//!    unchanged;
34//! 2. **rigour** — an enclosure `[r̲, r̄] ∋ a_iᵀx − b_i` that is a theorem
35//!    about the `f64` data, obtained in ordinary round-to-nearest arithmetic
36//!    from error-free transformations and a running error bound.
37//!
38//! This crate provides both, independent of the solver and publishable on
39//! its own.
40//!
41//! ## Notation
42//! `F` is the set of `f64` values, `fl(·)` rounding to nearest (ties to
43//! even), `u = 2⁻⁵³` the unit roundoff, `ulp(a)` the unit in the last place
44//! of `a ∈ F`, `η = 2⁻¹⁰⁷⁴` the smallest positive subnormal. A
45//! *double-double* is a pair `(h, ℓ) ∈ F²` with value `h + ℓ` (exact sum).
46//! `u_dd = 2⁻¹⁰⁶ = u²`. An *interval* is a pair `[a, b]`, `a ≤ b`, of
47//! elements of `F ∪ {±∞}` and stands for `{x ∈ R : a ≤ x ≤ b}`.
48//!
49//! An **error-free transformation** (EFT) writes the exact result of an
50//! `f64` operation as an `f64` pair: `two_sum(a, b) = (s, e)` with `s =
51//! fl(a + b)` and `s + e = a + b` exactly (Knuth; 6 flops, no branch);
52//! `two_prod(a, b) = (p, e)` with `p = fl(a b)` and `p + e = a b` exactly
53//! (one multiplication and one fused multiply-add). They are the only
54//! primitives of the crate; everything else is built from them.
55//!
56//! ## Scope of v0.1
57//! 1. The EFTs [`two_sum`], [`fast_two_sum`], [`two_prod`] as public
58//!    functions.
59//! 2. [`DoubleDouble`]: field operations, `sqrt`, comparisons, conversions,
60//!    decimal formatting and parsing; the algorithms of Joldes, Muller &
61//!    Popescu (2017), whose relative error bounds are *proven* (and partly
62//!    machine-checked), in preference to the QD library's, whose bounds are
63//!    stated without proof and are wrong for the "sloppy" addition.
64//! 3. `impl xingo_sparse::Real for DoubleDouble` (feature `sparse`), so
65//!    that `Lu<DoubleDouble>`, `SupernodalLdl<DoubleDouble>` and the
66//!    containers exist without one line of duplicated code.
67//! 4. Slice kernels, [`kernels`]: compensated `f64 → DoubleDouble` sums and
68//!    dot products (Ogita, Rump & Oishi 2005) and the double-double `dot`,
69//!    `axpy` and small-block `gemm`; scalar reference and SIMD (`pulp`)
70//!    versions with the same results bit for bit.
71//! 5. [`Interval`]: outward-rounded interval arithmetic on `f64` endpoints
72//!    *without* changing the rounding mode.
73//! 6. [`verify`] (feature `sparse`): rigorous enclosures of residuals
74//!    `A x − b` over the containers of `xingo-sparse`, the polishing
75//!    step (iterative refinement with double-double residuals) around a
76//!    caller-supplied solve, and a rigorous bound of the error `‖x −
77//!    A⁻¹b‖∞` (and by component) of one approximate solution of a square
78//!    system, with a proof that `A` is nonsingular, from the caller's
79//!    transposed solve (Algorithm E, Theorem E).
80//! 7. The elementary functions of [`DoubleDouble`] (Chapter 11.11), with
81//!    the names and special cases of `f64` — `exp`, `exp2`, `exp_m1`,
82//!    `ln`, `ln_1p`, `log2`, `log10`, `powi`, `powf`, `sin`, `cos`, `tan`,
83//!    `sin_cos`, `asin`, `acos`, `atan`, `atan2`, `sinh`, `cosh`, `tanh`,
84//!    `asinh`, `acosh`, `atanh` — each with a declared error bound proven in
85//!    the chapter ([`DoubleDouble::FUNCTION_BOUNDS`], [`FunctionBound`]),
86//!    and the 19 constants of `core::f64::consts` (`DoubleDouble::PI`, …).
87//!    No `f64` transcendental function of `std` is used (their precision is
88//!    unspecified); the same bits on every platform.
89//!
90//! ## Out of scope (D-0081, restated)
91//! Arbitrary precision (MPFR-like); complex scalars; `f32`; elementary
92//! functions of intervals (D-0121: they would need enclosures, not bounds);
93//! correctly rounded elementary functions; interval *linear algebra*
94//! (interval LU, Krawczyk, verified solution *sets* of interval linear
95//! systems: Rump's `verifylss` on interval data) — v0.1 bounds the error of
96//! **one** approximate solution of **one** square system with point data
97//! (Algorithm E), not solution sets; error bounds in the 2-norm;
98//! `QuadDouble` (question E4).
99//!
100//! ## Algorithms and their bounds
101//! All bounds hold in the absence of overflow and of underflow in the
102//! EFTs (precisely: every `two_prod` product `a b` satisfies `|a b| ≥
103//! 2⁻⁹⁶⁹` or is zero — Chapter 11.1, invariant T2; Chapter 11.2 states the
104//! "safe range" of operands in which this is guaranteed); outside that
105//! range the operations still return a normalized pair, with an absolute
106//! error of order `η`, and the *interval* functions account for it
107//! explicitly (invariant I2). JMP is Joldes, Muller & Popescu (2017), MR
108//! Muller & Rideau (2022), LLMPR Lefèvre, Louvet, Muller, Picot & Rideau
109//! (2023); the flop counts are those of JMP's Table 1 (FMA available).
110//!
111//! | operation | algorithm | relative error | flops |
112//! |---|---|---|---|
113//! | `dd + f64` | DWPlusFP (JMP Alg. 4) | `≤ 2u²/(1 − 2u) < 2u² + 5u³` | 10 |
114//! | `dd + dd` | AccurateDWPlusDW (JMP Alg. 6) | `≤ 3u²/(1 − 4u) < 3u² + 13u³` | 20 |
115//! | `dd · f64` | DWTimesFP3 (JMP Alg. 9, FMA) | `≤ 2u²` | 6 |
116//! | `dd · dd` | DWTimesDW3 (JMP Alg. 12, FMA) | `≤ 4u²` (MR; JMP proved `5u²`) | 9 |
117//! | `dd²` | DWPow2 (two-FMA product specialized) | `≤ 3u²` (Hubrecht & Melquiond 2026, binary64) | 6 |
118//! | `dd / f64` | DWDivFP3 (JMP Alg. 15) | `≤ 3u²` | 10 |
119//! | `dd / dd` | DWDivDW2 (JMP Alg. 17) | `≤ 15u² + 56u³` | 18 |
120//! | `√dd` | SQRTDWtoDW (LLMPR Alg. 8): a Newton step on `fl(√h)` | `≤ 25/8 u²` (LLMPR Thm 3.6) | 8 |
121//!
122//! The addition is the *accurate* one: the QD library's default "sloppy"
123//! addition (11 flops) has unbounded relative error when the operands have
124//! opposite signs (JMP §3), and a residual `b − A x` is exactly that case.
125//! No sloppy variant is exposed (question E5).
126//!
127//! **Consequence for the plan.** L2.2's acceptance criterion read "a
128//! relative error of at most 2⁻¹⁰⁴ in the kernels". `2⁻¹⁰⁴ = 4 u²` holds for `+`, `−`, `·` and
129//! `√`, **not for the division**: DWDivDW2 is proven to `15u² + 56u³`
130//! (`3,75 · 2⁻¹⁰⁴`), and the best proven bound of a double-word division
131//! is `9,8 u²` (DWDivDW3, JMP Alg. 18: 31 flops instead of 18, through a
132//! double-word reciprocal). The contract therefore states one bound per
133//! operation ([`DoubleDouble::ERROR_BOUNDS`]) and L2.2 is accepted against
134//! *those* (question E6).
135//!
136//! **Why not DWDivDW3.** It was implemented and measured (2026-11-15), and
137//! DWDivDW2 was kept (ratified; decision log D-0109). DWDivDW3 computes `x · (1/y)`, and a rounded
138//! reciprocal loses the *exact* quotients: `53/53` came out as `1 −
139//! 6,2 · 10⁻³³`; of the 39 601 quotients `(q y)/y` with integers `1 ≤ q, y
140//! < 200`, 4 600 were not `q`; `(a b)/b ≠ a` for about 30 % of random
141//! `f64` pairs and `x/x ≠ 1` for 45 % of random double-doubles. DWDivDW2,
142//! which corrects the `f64` quotient with an exact residual, returns all
143//! of these exactly (Chapter 11.2; the tests pin it). The average error
144//! was also larger (`0,32u²` against `0,12u²` on `f64`-valued operands,
145//! `0,56u²` against `0,48u²` on general ones; the largest observed,
146//! `4,4u²` against `5,1u²`, is the only figure in its favour), and the
147//! scaled residual of `Lu<DoubleDouble>` rose from about `1,5` to `74`
148//! units of `n ε` (order 300). A better worst-case bound did not pay for
149//! that.
150//!
151//! **Intervals without the rounding mode.** Rust offers no sound way to
152//! change the floating-point rounding mode (LLVM assumes round-to-nearest;
153//! `fesetround` through FFI is undefined behaviour in the presence of
154//! constant folding), and this crate has no `unsafe` (D-0006 allows it only
155//! in `xingo-sparse`). Directed rounding is therefore *computed*: for `∘ ∈
156//! {+, −, ·}` the EFT gives `x ∘ y = s + e` exactly, so `▽(x ∘ y) = s` if
157//! `e ≥ 0` and `pred(s)` otherwise, and symmetrically `△`; the result is
158//! the *correctly rounded* directed value, as tight as hardware directed
159//! rounding, at 2–4 times the cost of a plain operation. Division and
160//! square root use the FMA residual (`e = fma(−q, y, x)` has the sign of
161//! `x − q y` exactly). When an EFT is not exact (underflow) the operation
162//! is redone scaled by `2²⁰⁰`, where it is, so the endpoints are the
163//! directed roundings there too (Chapter 11.9, step N6; the contract had
164//! "one further step outward"). This is the design of Rump, Zimmermann,
165//! Boldo & Melquiond (2009) and of the IEEE 1788 reference notes; `inari`
166//! (read, not used) takes the other route, MXCSR through `unsafe`.
167//!
168//! **Residual enclosures.** For `f64` vectors `x`, `y` of length `n`,
169//! Dot2Err (Ogita, Rump & Oishi 2005, Alg. 5.8) returns in round-to-nearest
170//! a double-double `r` and an `f64` bound `β` with `|xᵀy − r| ≤ β`, valid
171//! whenever `2 n u < 1` and no overflow occurs, underflow included in `β`
172//! (their Corollary 5.9; [`kernels::dot2_err`] is that algorithm over four
173//! accumulators, with its own proof in Chapter 11.5 and the hypothesis
174//! `2(n + 3)u < 1`). `verify::residual` applies it row by row (Chapter
175//! 11.10): the enclosure of `a_iᵀx − b_i` costs about 25 flops per nonzero,
176//! against 2 for the plain residual and thousands for a rational one.
177//!
178//! ## What a certificate means
179//! (C1) The enclosures are statements about the **`f64` model**: the
180//!      matrix and vectors as stored. That a decimal `0.1` in an MPS file
181//!      became the `f64` nearest to it is outside this crate (the rational
182//!      check of the solver's `--exact-check` starts from the decimal text).
183//! (C2) An enclosure is rigorous under IEEE 754 binary64 arithmetic with
184//!      round-to-nearest and a correctly rounded `fma` — what Rust
185//!      guarantees on every tier-1 target (`f64::mul_add` falls back to a
186//!      correct software FMA where the CPU has none; slow, never wrong).
187//! (C3) `verify` never claims more than it proved: when a hypothesis of a
188//!      bound fails (overflow, `n u ≥ 1`, NaN in the data) the result is
189//!      [`Interval::ENTIRE`] or an error, never a finite interval.
190//!
191//! ## Invariants (each becomes a `debug_assert!` or `check_invariants()`)
192//! (D1) *Normalized.* Every finite [`DoubleDouble`] `(h, ℓ)` satisfies `h =
193//!      fl(h + ℓ)` (hence `|ℓ| ≤ ulp(h)/2`); `h = ±0` implies `ℓ = 0`.
194//! (D2) *Non-finite.* If `h` is infinite or NaN then `ℓ = 0` when `h` is
195//!      infinite and the value is "infinite"/"NaN" as `h` says; operations
196//!      follow IEEE on `h`. (`∞ − ∞` is NaN, etc.)
197//! (D3) *Order.* The derived lexicographic order on `(h, ℓ)` is the order
198//!      of the values `h + ℓ` (true for normalized pairs), total on
199//!      non-NaN values: requirement (R2) of `xingo_sparse::Real`.
200//! (D4) *Conversions.* `from_f64` is exact; `to_f64` is `h`, the `f64`
201//!      nearest to `h + ℓ` by (D1): requirement (R4).
202//! (D5) *Determinism.* Every operation is a fixed sequence of `f64`
203//!      operations: no data-dependent algorithm choice, no reassociation,
204//!      the same bits on every platform (C2).
205//! (K1) *Kernels.* The SIMD kernels return, bit for bit, the results of
206//!      the scalar reference kernels of the same name: the summation order
207//!      is part of the contract of each kernel (stated in its docs), not
208//!      an implementation detail. (Where a result is a NaN both are NaN;
209//!      its sign and payload are not specified: Chapter 11.5.)
210//! (I1) *Inclusion.* For intervals `X`, `Y` and `∘` an operation: `x ∈ X,
211//!      y ∈ Y ⇒ x ∘ y ∈ X ∘ Y` whenever `x ∘ y` is defined.
212//! (I2) *Well-formed.* `lo ≤ hi`, neither is NaN, `lo < +∞`, `hi > −∞`; the
213//!      empty set is a separate value ([`Interval::EMPTY`]).
214//! (I3) *Tightness.* `+`, `−`, `·`, `/` (divisor not containing zero) and
215//!      `sqrt` return the *hull of the exact range rounded outward to
216//!      `F`*: the tightest representable interval.
217//! (V1) *Residuals.* `verify::residual(A, x, b)[i] ∋ a_iᵀx − b_i` for the
218//!      stored `f64` values (C1), for every row.
219//! (E1) *Errors.* A certified `verify::forward_error_bound` is Theorem E:
220//!      `A` is nonsingular and `‖x − A⁻¹b‖∞ ≤ ε`, `|x_p − (A⁻¹b)_p| ≤ ε_p`,
221//!      for the stored data and whatever the solve the caller supplied.
222//!
223//! (Chapter 11.9 restates and proves I1–I3; Chapter 11.10, V1 and E1–E4.)
224//!
225//! ## How `xingo_sparse::Real` is met, and one amendment to it
226//! `Real` (Chapter 5.6) asks (R1) "the field operations are the correctly
227//! rounded ones of `T`". Double-double operations are not correctly
228//! rounded; they are *faithful with a proven relative bound*. The generic
229//! code of `xingo-sparse` uses (R1) only through tolerances scaled by
230//! `T::EPSILON`, so the proposal is to **reword (R1)** there as "each
231//! field operation is a deterministic function of its operands with
232//! relative error at most `c_T · EPSILON`, `c_T ≤ 4`" (true for `f64` with
233//! `c = 1/2`) — a documentation change in `xingo-sparse`, no API change
234//! (question E2). `Real::EPSILON` for double-double is `2⁻¹⁰⁴`, the QD
235//! library's convention. `Real::mul_add(a, b)` is `self · a + b` with two
236//! roundings (the trait says "a single rounding where the type allows").
237//! `Sum` adds left to right from `ZERO` (R3).
238//!
239//! ## Divergences from the references (to review)
240//! * **QD (Hida, Li & Bailey 2001).** Same representation; the algorithms
241//!   are JMP 2017's (proven bounds, FMA-based products) and the addition
242//!   is always the accurate one. *Read, not copied* (QD is BSD-like, but
243//!   the code here is written from the papers).
244//! * **`twofloat`** (BSD-3). Double-double without a shared trait with the
245//!   sparse containers and with the sloppy addition as `+`. Not used.
246//! * **`inari`** (MIT). IEEE 1788 intervals with decorations, x86-64 and
247//!   AArch64 only, rounding mode through `unsafe` intrinsics. Here:
248//!   portable, no `unsafe`, no decorations, only the operations a residual
249//!   needs. Not used.
250//! * **INTLAB / `verifylss` (Rump).** Verified solution *sets* of interval
251//!   linear systems are out of scope for v0.1 (above). The bound of the
252//!   error of one solution by an approximate inverse (Rump 2010, §10, cited
253//!   from memory) is in, as Algorithm E: the inverse is never formed, each
254//!   row is one transposed solve of the caller, and the proof is Chapter
255//!   11.10's own.
256//! * **D-0081** recommended "`xingo-sparse` depends optionally on
257//!   `xingo-extprec`". The contract proposes the **opposite direction**
258//!   (question E1): `verify` needs the containers of `xingo-sparse`, so
259//!   the D-0081 direction would be a cycle; with `xingo-extprec →
260//!   xingo-sparse` the `impl Real` lives here (orphan rule satisfied),
261//!   `xingo-sparse` stays free of this dependency, and its vestigial
262//!   contract feature `extprec` is dropped.
263//! * **D-0081** names `malachite` or `dashu` as the exact oracle of the
264//!   tests. `malachite` is LGPL-3.0, which CLAUDE.md forbids; the oracle is
265//!   **`dashu`** (MIT OR Apache-2.0), a dev-dependency (question E8).
266//!
267//! ## Questions of the review (all approved as proposed, 2026-11-15)
268//! * **E1** — dependency direction `xingo-extprec → xingo-sparse` (feature
269//!   `sparse`, on by default), against D-0081's recommendation. *Proposed:
270//!   yes.*
271//! * **E2** — reword requirement (R1) of `xingo_sparse::Real` as above (a
272//!   patch release of `xingo-sparse`, documentation only). *Proposed: yes.*
273//! * **E3** — intervals by computed directed rounding, no `unsafe`, 2–4×
274//!   the cost of hardware rounding modes. *Proposed: yes; the alternative
275//!   needs `unsafe` here and an amendment of D-0006.*
276//! * **E4** — `QuadDouble`: D-0081 says "if viable", L2.3 "if the cost
277//!   pays". It roughly triples the surface (renormalization of four
278//!   components, no proven bounds in the literature for the QD
279//!   algorithms). *Proposed: not in v0.1; the name is reserved and a
280//!   measured need (a basis that double-double does not resolve) reopens
281//!   it.*
282//! * **E5** — no sloppy addition in the public API. *Proposed: yes.*
283//! * **E6** — L2.2's criterion becomes "each operation within its bound of
284//!   [`DoubleDouble::ERROR_BOUNDS`], checked against exact rationals",
285//!   instead of a single `2⁻¹⁰⁴`. *Proposed: yes.*
286//! * **E7** — no elementary functions beyond `sqrt`; `Display`/`FromStr`
287//!   are faithful (error `≤ 1` unit of the 32nd digit), not correctly
288//!   rounded. *Proposed: yes.* **Superseded:** the elementary functions
289//!   were added by task L2.4 (decision log D-0121, Chapter 11.11), and the
290//!   conversions are correctly rounded (L2.2a, below).
291//! * **E8** — `dashu` as the dev-only exact oracle; `pulp` (MIT) as the
292//!   only runtime dependency besides `xingo-sparse`. *Proposed: yes.*
293//!
294//! ## Corrections to the approved contract (L2.2a)
295//! The table of bounds of the contract was written from memory (D-0109,
296//! E6); L2.2a checked it against the texts and changed, in this chapter:
297//!
298//! * `dd + f64`: the bound is `2u²/(1 − 2u)`, not `2u²` (it is
299//!   asymptotically optimal; JMP report `2u² − 6u³` attained).
300//! * `dd · dd`: the `4u²` of DWTimesDW3 is Muller & Rideau's (2022), who
301//!   formalized the proofs in Coq and improved JMP's `5u²`.
302//! * `dd / dd`: DWDivDW2 costs 18 flops, not 31; 31 flops and `9,8u²` are
303//!   DWDivDW3's. The contract's remark "a cheaper variant is `9,8u²`" was
304//!   backwards: the *more expensive* algorithm has the better bound. The
305//!   division stays DWDivDW2 (see "Why not DWDivDW3" above).
306//! * `√dd`: the algorithm is SQRTDWtoDW of LLMPR. Its constant `25/8`
307//!   could not be checked against the paper in L2.2a; L2.2b read the
308//!   author version (HAL hal-03482567v2): it is their Theorem 3.6, for `x
309//!   ≥ 2⁻⁹⁶⁸` barring overflow and underflow, asymptotically optimal
310//!   (Chapter 11.2). The tests check it against exact arithmetic.
311//! * `dd²` gained its own row (DWPow2, `3u²`). Cited at second hand in
312//!   L2.2a; L2.2b read the source (Hubrecht & Melquiond, ARITH 2026,
313//!   §IV-B): a machine-generated (Gappa) proof for binary64 with an
314//!   unbounded exponent range (Chapter 11.2).
315//! * Dot2Err needs `2 n u < 1`, not `n u < 1`; and the bounds of Sum2 and
316//!   Dot2 are restated for the four-lane order of the kernels (`γ²_{n+3}`
317//!   and `γ²_{n+5}` instead of `γ²_{n−1}` and `γ²_n`; Chapter 11.5).
318//! * [`fast_two_sum`]: the requirement that matters is on the *exponents*
319//!   (`e_a ≥ e_b`), which `|a| ≥ |b|` implies. The accurate addition calls
320//!   it with `|a| < |b|` in one binade under cancellation, so the
321//!   `debug_assert!` tests the exponent condition (Chapter 11.1).
322//! * [`two_sum`] is not exact "unless `s` overflows" only: with `a = ±Ω`
323//!   an intermediate difference can overflow (Chapter 11.1, invariant T1).
324//! * Invariant (D1) needs care below the range of [`two_prod`]: a rounded
325//!   error term can be exactly half an ulp on the wrong side of the tie.
326//!   `from_product` and `from_str` renormalize (one exact Fast2Sum).
327//! * `Display`: "the shortest of at most 32 significant digits that parses
328//!   back to the same value" does not exist in general — a double-double
329//!   is not a 106-bit number (its trailing component may lie arbitrarily
330//!   far below the leading one). The default output is the value correctly
331//!   rounded to **31** digits (ratified 2026-11-15, decision log D-0109,
332//!   instead of the contract's 32): a decimal of at most 31 digits that was read
333//!   comes back as the same text, which 32 digits cannot give (`10³¹ <
334//!   2¹⁰⁶ < 10³²`). `{:.N}` and `{:.Ne}` with `N` large give the exact
335//!   expansion (Chapter 11.4, invariant P3). All conversions are correctly
336//!   rounded, which is stronger than the "faithful" of question E7.
337//! * Added to the contract's surface, ratified (decision log D-0109): `impl
338//!   LowerExp for DoubleDouble` (`{:e}`, as for `f64`), `impl Display` and
339//!   `impl Error` for [`ParseDoubleDoubleError`], and the row `"dd²"` of
340//!   `ERROR_BOUNDS`.
341//!
342//! ## Corrections to the approved contract (L2.2b)
343//! * [`kernels::backend`] never returns `"avx512"`: the kernels have `W =
344//!   4` lanes on every target, which is the width of AVX2; an eight-lane
345//!   accumulation would be a different kernel (Chapter 11.5, Algorithm X).
346//!   The backends are `"scalar"`, `"neon"` and `"avx2"`
347//!   (ratified 2026-11-15, decision log D-0111).
348//! * Invariant (K1) holds for every input, finite or not, with the one
349//!   reservation about the bits of a NaN stated above.
350//! * [`DdDense`]: the contract has the triangular solves "those of
351//!   `NaiveDense`" and `gemm_sub`/`syrk_sub` "through `kernels::gemm_sub`".
352//!   The solves use the vectorized column update too, and all three go
353//!   through the column update of `kernels::gemm_sub`, not that function
354//!   (its `B` is transposed with respect to the trait's). The results are
355//!   those of `NaiveDense` bit for bit either way (Chapter 11.7).
356//! * Not added to the contract's surface: the `LuOptions` profile for
357//!   `Lu<DoubleDouble>` (Chapter 11.8). The choice ratified on 2026-11-15
358//!   (decision log D-0111) is a constructor generic in the scalar in `xingo-sparse`; it
359//!   exists since `xingo-sparse` 0.4.0 (`LuOptions::for_scalar::<T>()`,
360//!   task L1.8, D-0113), and the hidden, provisional constructor this
361//!   crate carried until then is gone.
362//! * The feature `simd` is on by default, as in the contract; `pulp` is
363//!   0.22.3, the version the workspace already locks through faer.
364//!
365//! ## Corrections to the approved contract (L2.3)
366//! * **Underflow.** The contract moved an endpoint "one further step
367//!   outward" when an EFT is not exact. Chapter 11.9 instead recovers the
368//!   exact sign of the residual by scaling (step N6), so (I3) holds without
369//!   exception: every endpoint of `+ − · / √ x²` is the directed rounding
370//!   of the exact one, for all operands.
371//! * **`Interval / Interval` with zero in the divisor.** As in the
372//!   contract (`ENTIRE`, or a half-line when zero is an endpoint), with two
373//!   cases it left open: `X / [0, 0]` is `ENTIRE` (the set of quotients is
374//!   empty; `∅` would be the set-theoretic answer, but an exact zero
375//!   divisor must not be able to prove anything), and `[0, 0] / Y` is `[0,
376//!   0]` for `Y ≠ [0, 0]`.
377//! * **The empty set and the predicates.** `certainly_le`, `certainly_ge`
378//!   and `certainly_within` are `false` on `∅` (the contract's wording,
379//!   "every element of `X` …", is vacuously true there): invariant (C3).
380//!   `verify::norm_inf_bound` returns `+∞` if an interval is empty.
381//! * **Non-real arguments.** [`Interval::point`] panics on `±∞` as well as
382//!   on NaN; [`Interval::mid_rad`] panics on a NaN or a negative radius
383//!   and returns `ENTIRE` for an infinite midpoint; [`Interval::enclose`]
384//!   of an infinite or NaN double-double is `ENTIRE`; an operator with a
385//!   NaN or infinite `f64` operand returns `ENTIRE`; `mid` of a half-line
386//!   is `±Ω`.
387//! * **`Display`.** Without a precision the endpoints are printed as
388//!   `f64` (shortest round trip: the text identifies the interval); with a
389//!   precision they are rounded **outward**, so the printed pair contains
390//!   the interval (Chapter 11.9, Algorithm D; ratified, decision log D-0114).
391//! * **Algorithm V for a double-double `x`.** The contract announced "two
392//!   `two_prod` per entry, the bound gains the second-order terms". No new
393//!   bound is needed: `Σ a_ij (h_j + ℓ_j) − b_i` *is* a dot product of
394//!   `f64` vectors of length `2k + 1`, to which Dot2Err applies as it
395//!   stands (Chapter 11.10). Dot2Err's bound, however, is of the order of
396//!   a *polished* residual itself; since task X0.5 the enclosure is
397//!   narrowed by steps V4–V7 (two passes of VecSum and an a posteriori
398//!   bound of the rest: three times the working precision), intersected
399//!   with the Dot2Err one (issue #5 of the mirror).
400//! * **Step V3.** The enclosure is `[▽(h + ▽(ℓ − β)), △(h + △(ℓ + β))]`
401//!   for `r = h + ℓ`, not `enclose(r) + [−β, β]`: the same theorem, one to
402//!   two ulps narrower.
403//! * **Algorithm P, convergence.** The contract stopped at `‖r‖∞ ≤ τ
404//!   (‖A‖∞‖x‖∞ + ‖b‖∞)`. On the Netlib bases that global scale declared
405//!   badly scaled models converged with a true residual far above
406//!   double-double level, so the test is now **per row** (ratified
407//!   2026-11-16, decision log D-0114): `|r_i| ≤ τ (Σ_j |a_ij x_j| + |b_i|)` in every
408//!   row, its right-hand side rounded against convergence (Chapter 11.10).
409//!   Progress (`PolishOptions::min_progress`) stays in the norm `‖r‖∞`,
410//!   as in the contract: measuring it on the row scale too was tried and
411//!   measured worse (Chapter 11.10 keeps the numbers). Same signature and
412//!   fields; the meaning of `PolishOptions::tol` changes. With the row
413//!   test, *stagnated* is a common and harmless outcome on bases with
414//!   degenerate rows (9 of the 93 of Netlib).
415//! * **Algorithm P.** Step P2 is made precise (five tests, in order), and
416//!   a correction after which the residual is larger, or not finite, is
417//!   **undone**: the residual never increases. `PolishReport::iterations`
418//!   counts the corrections kept. `polish` reports a non-square matrix as
419//!   `VerifyError::Dimension`.
420//! * Added to the contract's surface, ratified 2026-11-16 (decision log
421//!   D-0114):
422//!   `impl Display + Error` for [`InvalidInterval`] and
423//!   `verify::VerifyError`; `impl LowerExp for Interval` (`{:e}`, same
424//!   rounding rule as `Display`); `AddAssign`, `SubAssign`, `MulAssign`,
425//!   `DivAssign` for `Interval` with an `Interval` and with an `f64`; the
426//!   operators with the scalar on the left, `f64 ∘ Interval`; and a total
427//!   `impl From<f64> for Interval` (`ENTIRE` for a NaN or an infinity,
428//!   where `Interval::point` panics).
429//!
430//! ## Corrections to the approved contract (L2.4, D-0121)
431//! Chapter 11.11 states each in place; in short:
432//!
433//! * **Argument reduction of the circular functions.** Payne–Hanek in
434//!   integer arithmetic for every `|x| > π/4`, instead of Cody–Waite with
435//!   `π/2` in five parts below `2⁵²`: the subtractions of Cody–Waite in
436//!   double-double arithmetic err relative to their own results, which are
437//!   about `k 2⁻⁵³`, and the floor `2⁻²⁰⁰` of the declared bound could not
438//!   be proven for them. The bound is the contract's.
439//! * **Algorithms.** `exp` is table-driven (`2^(j/64)`, Tang) instead of
440//!   `m` halvings and squarings, whose error grows with `m` in the proof;
441//!   `ln` reduces by `c = 1 + j/64` with `j` truncated (no cancellation) and
442//!   sums the series of `ln(1 + z)` instead of `2 atanh` of a quotient (D2's
443//!   `15u²` would not fit `8u²`), with two extra tables for the cases where
444//!   `e ln 2` and `ln y` cancel; `exp_m1` reduces small arguments exactly by
445//!   `N/64`; `atan` uses a table of 144 points by binade instead of `j/32`;
446//!   `ln_1p` adds Kahan's correction with an `f64` addend whose rounding is
447//!   proven (Lemma S). The private tables differ accordingly, plus `3π/4`
448//!   for `atan2(±∞, −∞)`.
449//! * **`powf`.** The growth coefficient is `11`, not `8`: the proof gives
450//!   `10.7` (the logarithm's own bound is multiplied by `|y ln x|`).
451//! * **`tan` in `FUNCTION_BOUNDS`.** The floor `2⁻²⁰⁰(1 + tan²x)` is written
452//!   as the growth term `2⁻⁹⁴ G u²|tan x|` with `G = |tan x|` (the string
453//!   `"|tan x|"`) plus the absolute `2⁻²⁰⁰`.
454//! * **The second oracle** works on dyadic rationals over `dashu-int`
455//!   (outward rounding after each operation) rather than on `dashu-ratio`;
456//!   it is equally independent of `dashu-float` and much faster.
457//!
458//! ## Corrections to the approved contract (X0.3, D-0125)
459//! Chapter 11.10 states each in place; ratified (decision log D-0125 and
460//! D-0126):
461//!
462//! * **`ForwardErrorBound::contraction`.** The contract's field
463//!   documentation read "`< 1` iff certified", but its own steps E5–E6
464//!   end *not finite* after every row contracted (an unbounded residual, or
465//!   a bound that overflows). The field follows the steps: `α` over the
466//!   rows examined, `< 1` when certified, `≥ 1` when not contracting, the
467//!   value reached (`0` if no row) when not finite.
468//! * **NaN or `±∞` in `A`** (the contract's special cases) cannot occur:
469//!   `CsrMatrix` refuses non-finite values. The same path, `β = +∞` in
470//!   step E3 and *not contracting*, is reached by an overflowing product.
471//! * **Invariant E4** needs a closure that is a function of its argument.
472//!   The BTRAN of `xingo_sparse::Lu` is not, by design: it chooses between
473//!   its hypersparse and dense paths by a moving average of the density of
474//!   the previous results, so two equal calls can sum in different orders
475//!   (on one Netlib basis, share1b, a second call returned other bits); the
476//!   same sequence of calls gives the same bits. Each result is a theorem
477//!   for its own `R` either way.
478//! * **Step E2** also discards a correction whose sum `h_i + d_i`
479//!   overflows (the contract kept it, and step E3 then refused the row).
480//! * **`kernels::dot2_err`** (found by the review of X0.3): invariant K2
481//!   failed when an intermediate step of the last 2Sum (step C4 of Chapter
482//!   11.5) overflowed at `±Ω`: step E made the error term finite and `β`
483//!   stayed finite and false. `β` is now `+∞` there; `r` keeps its bits
484//!   (Chapter 11.5, the proof of C5, "Overflow").
485//!
486//! ## History
487//! The crate was built in the tasks L2.1–L2.5 of the Xingó solver's plan.
488//! L2.1 wrote and ratified the contract (decision log D-0109). L2.2a
489//! implemented the EFTs, `DoubleDouble`, `impl Real`, the scalar kernels,
490//! the proptests against `dashu`, and `Lu<DoubleDouble>` and
491//! `SupernodalLdl<DoubleDouble>` as integration tests. L2.2b added the
492//! `pulp` kernels, `DdDense` and the measurements behind the `LuOptions`
493//! profile for double-double (D-0111). L2.3 added `Interval`, `verify` and
494//! polishing, with residual certificates on the Netlib bases (an
495//! integration test of `xingo-simplex`, which this crate does not depend
496//! on; D-0114). L2.5 used the enclosures in the solver's `--exact-check`,
497//! before its rational check (D-0120). L2.4, last, added the elementary
498//! functions (Chapter 11.11; D-0121 and D-0122). Task X0.3, before the
499//! first release, wrote the contract of a rigorous bound of the error of a
500//! solution after a pilot of three methods on the Netlib bases (decision
501//! log D-0125) and implemented the approved one, Algorithm E
502//! (`verify::forward_error_bound`, Chapter 11.10). Version 0.1.0 is the
503//! state after all of these.
504//!
505//! ## References
506//! Dekker, "A floating-point technique for extending the available
507//! precision", Numer. Math. 18 (1971). Knuth, TAOCP vol. 2, §4.2.2.
508//! Hida, Li & Bailey, "Algorithms for quad-double precision floating
509//! point arithmetic", ARITH-15 (2001). Ogita, Rump & Oishi, "Accurate sum
510//! and dot product", SIAM J. Sci. Comput. 26 (2005). Joldes, Muller &
511//! Popescu, "Tight and rigorous error bounds for basic building blocks of
512//! double-word arithmetic", ACM TOMS 44 (2017). Muller & Rideau,
513//! "Formalization of double-word arithmetic, and comments on 'Tight and
514//! rigorous error bounds for basic building blocks of double-word
515//! arithmetic'", ACM TOMS 48 (2022). Stloukal & Jézéquel, "Lord of the
516//! Precision, the Two Floats: double-word arithmetic for complex numbers",
517//! arXiv:2611.08371 (2026), §3 (it restates the algorithms and bounds
518//! used here). Hubrecht & Melquiond, "Verifying code that uses error-free
519//! transformations", 33rd IEEE Symposium on Computer Arithmetic (ARITH
520//! 2026), §IV-B (DWPow2). Lefèvre, Louvet, Muller,
521//! Picot & Rideau, "Accurate calculation of Euclidean norms using
522//! double-word arithmetic", ACM TOMS 49 (2023). Rump, "Verification
523//! methods: rigorous results using floating-point arithmetic", Acta
524//! Numerica 19 (2010). Rump, Zimmermann, Boldo & Melquiond, "Computing
525//! predecessor and successor in rounding to nearest", BIT 49 (2009).
526//! Higham, *Accuracy and Stability of Numerical Algorithms* (2002), ch.
527//! 4 and 12. IEEE Std 1788-2015. Muller et al., *Handbook of
528//! Floating-Point Arithmetic*, 2nd ed. (2018), ch. 4 and 14.
529
530// Without the feature `sparse`, `verify` and `DdDense` do not exist: the
531// chapter's links to them point to the documentation built with every
532// feature (docs.rs) instead of breaking.
533// (The blank line ends the last paragraph, so that the definitions are read
534// as link references.)
535#![cfg_attr(
536    not(feature = "sparse"),
537    doc = "",
538    doc = "[`verify`]: https://docs.rs/xingo-extprec/latest/xingo_extprec/verify/index.html",
539    doc = "[`DdDense`]: https://docs.rs/xingo-extprec/latest/xingo_extprec/struct.DdDense.html"
540)]
541#![forbid(unsafe_code)]
542
543mod big;
544mod dd;
545mod decimal;
546#[cfg(feature = "sparse")]
547mod dense;
548mod eft;
549mod elementary;
550mod interval;
551pub mod kernels;
552#[cfg(feature = "sparse")]
553mod profile;
554#[cfg(feature = "simd")]
555mod simd;
556#[cfg(feature = "sparse")]
557pub mod verify;
558
559/// The code blocks of the crate's README, compiled and run as doc-tests
560/// (`cargo test --doc`) so that the README never drifts from the API, as in
561/// `xingo-sparse`. The README is not the root documentation — this chapter
562/// is. Its last example uses `verify`, hence the feature `sparse`.
563#[cfg(all(doctest, feature = "sparse"))]
564#[doc = include_str!("../README.md")]
565pub struct ReadmeDoctests;
566
567pub use dd::{DoubleDouble, ErrorBound};
568pub use decimal::ParseDoubleDoubleError;
569#[cfg(feature = "sparse")]
570pub use dense::DdDense;
571pub use eft::{fast_two_sum, two_prod, two_sum};
572pub use elementary::FunctionBound;
573pub use interval::{Interval, InvalidInterval};