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};