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