Expand description
§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:
- 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 ofxingo-sparsecan be instantiated unchanged; - rigour — an enclosure
[r̲, r̄] ∋ a_iᵀx − b_ithat is a theorem about thef64data, 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
- The EFTs
two_sum,fast_two_sum,two_prodas public functions. 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.impl xingo_sparse::Real for DoubleDouble(featuresparse), so thatLu<DoubleDouble>,SupernodalLdl<DoubleDouble>and the containers exist without one line of duplicated code.- Slice kernels,
kernels: compensatedf64 → DoubleDoublesums and dot products (Ogita, Rump & Oishi 2005) and the double-doubledot,axpyand small-blockgemm; scalar reference and SIMD (pulp) versions with the same results bit for bit. Interval: outward-rounded interval arithmetic onf64endpoints without changing the rounding mode.verify(featuresparse): rigorous enclosures of residualsA x − bover the containers ofxingo-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 thatAis nonsingular, from the caller’s transposed solve (Algorithm E, Theorem E).- The elementary functions of
DoubleDouble(Chapter 11.11), with the names and special cases off64—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 ofcore::f64::consts(DoubleDouble::PI, …). Nof64transcendental function ofstdis 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 throughunsafeintrinsics. Here: portable, nounsafe, 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-sparsedepends optionally onxingo-extprec”. The contract proposes the opposite direction (question E1):verifyneeds the containers ofxingo-sparse, so the D-0081 direction would be a cycle; withxingo-extprec → xingo-sparsetheimpl Reallives here (orphan rule satisfied),xingo-sparsestays free of this dependency, and its vestigial contract featureextprecis dropped. - D-0081 names
malachiteordashuas the exact oracle of the tests.malachiteis LGPL-3.0, which CLAUDE.md forbids; the oracle isdashu(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(featuresparse, on by default), against D-0081’s recommendation. Proposed: yes. - E2 — reword requirement (R1) of
xingo_sparse::Realas above (a patch release ofxingo-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 needsunsafehere 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 single2⁻¹⁰⁴. Proposed: yes. - E7 — no elementary functions beyond
sqrt;Display/FromStrare faithful (error≤ 1unit 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 —
dashuas the dev-only exact oracle;pulp(MIT) as the only runtime dependency besidesxingo-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 is2u²/(1 − 2u), not2u²(it is asymptotically optimal; JMP report2u² − 6u³attained).dd · dd: the4u²of DWTimesDW3 is Muller & Rideau’s (2022), who formalized the proofs in Coq and improved JMP’s5u².dd / dd: DWDivDW2 costs 18 flops, not 31; 31 flops and9,8u²are DWDivDW3’s. The contract’s remark “a cheaper variant is9,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 constant25/8could not be checked against the paper in L2.2a; L2.2b read the author version (HAL hal-03482567v2): it is their Theorem 3.6, forx ≥ 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, notn 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 thedebug_assert!tests the exponent condition (Chapter 11.1).two_sumis not exact “unlesssoverflows” only: witha = ±Ω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_productandfrom_strrenormalize (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}withNlarge 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 forf64),impl Displayandimpl ErrorforParseDoubleDoubleError, and the row"dd²"ofERROR_BOUNDS.
§Corrections to the approved contract (L2.2b)
kernels::backendnever returns"avx512": the kernels haveW = 4lanes 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 ofNaiveDense” andgemm_sub/syrk_sub“throughkernels::gemm_sub”. The solves use the vectorized column update too, and all three go through the column update ofkernels::gemm_sub, not that function (itsBis transposed with respect to the trait’s). The results are those ofNaiveDensebit for bit either way (Chapter 11.7).- Not added to the contract’s surface: the
LuOptionsprofile forLu<DoubleDouble>(Chapter 11.8). The choice ratified on 2026-11-15 (decision log D-0111) is a constructor generic in the scalar inxingo-sparse; it exists sincexingo-sparse0.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
simdis on by default, as in the contract;pulpis 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 / Intervalwith 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]isENTIRE(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] / Yis[0, 0]forY ≠ [0, 0].- The empty set and the predicates.
certainly_le,certainly_geandcertainly_withinarefalseon∅(the contract’s wording, “every element ofX…”, is vacuously true there): invariant (C3).verify::norm_inf_boundreturns+∞if an interval is empty. - Non-real arguments.
Interval::pointpanics on±∞as well as on NaN;Interval::mid_radpanics on a NaN or a negative radius and returnsENTIREfor an infinite midpoint;Interval::encloseof an infinite or NaN double-double isENTIRE; an operator with a NaN or infinitef64operand returnsENTIRE;midof a half-line is±Ω. Display. Without a precision the endpoints are printed asf64(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 “twotwo_prodper entry, the bound gains the second-order terms”. No new bound is needed:Σ a_ij (h_j + ℓ_j) − b_iis a dot product off64vectors of length2k + 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 + △(ℓ + β))]forr = h + ℓ, notenclose(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 ofPolishOptions::tolchanges. 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::iterationscounts the corrections kept.polishreports a non-square matrix asVerifyError::Dimension. - Added to the contract’s surface, ratified 2026-11-16 (decision log
D-0114):
impl Display + ErrorforInvalidIntervalandverify::VerifyError;impl LowerExp for Interval({:e}, same rounding rule asDisplay);AddAssign,SubAssign,MulAssign,DivAssignforIntervalwith anIntervaland with anf64; the operators with the scalar on the left,f64 ∘ Interval; and a totalimpl From<f64> for Interval(ENTIREfor a NaN or an infinity, whereInterval::pointpanics).
§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π/2in five parts below2⁵²: the subtractions of Cody–Waite in double-double arithmetic err relative to their own results, which are aboutk 2⁻⁵³, and the floor2⁻²⁰⁰of the declared bound could not be proven for them. The bound is the contract’s. - Algorithms.
expis table-driven (2^(j/64), Tang) instead ofmhalvings and squarings, whose error grows withmin the proof;lnreduces byc = 1 + j/64withjtruncated (no cancellation) and sums the series ofln(1 + z)instead of2 atanhof a quotient (D2’s15u²would not fit8u²), with two extra tables for the cases wheree ln 2andln ycancel;exp_m1reduces small arguments exactly byN/64;atanuses a table of 144 points by binade instead ofj/32;ln_1padds Kahan’s correction with anf64addend whose rounding is proven (Lemma S). The private tables differ accordingly, plus3π/4foratan2(±∞, −∞). powf. The growth coefficient is11, not8: the proof gives10.7(the logarithm’s own bound is multiplied by|y ln x|).taninFUNCTION_BOUNDS. The floor2⁻²⁰⁰(1 + tan²x)is written as the growth term2⁻⁹⁴ G u²|tan x|withG = |tan x|(the string"|tan x|") plus the absolute2⁻²⁰⁰.- The second oracle works on dyadic rationals over
dashu-int(outward rounding after each operation) rather than ondashu-ratio; it is equally independent ofdashu-floatand 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 “< 1iff 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,< 1when certified,≥ 1when not contracting, the value reached (0if no row) when not finite.- NaN or
±∞inA(the contract’s special cases) cannot occur:CsrMatrixrefuses 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::Luis 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 ownReither way. - Step E2 also discards a correction whose sum
h_i + d_ioverflows (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;rkeeps 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.
Modules§
- big 🔒
- Chapter 11.3 — Natural numbers for the decimal conversions
- dd 🔒
- Chapter 11.2 — Double-double arithmetic
- decimal 🔒
- Chapter 11.4 — Decimal formatting and parsing
- dense 🔒
- Chapter 11.7 —
DdDense: the dense kernel ofxingo-sparsein double-double - eft 🔒
- Chapter 11.1 — Error-free transformations
- elementary 🔒
- Chapter 11.11 — Elementary functions of double-doubles
- interval 🔒
- Chapter 11.9 — Intervals by computed directed rounding
- kernels
- Chapter 11.5 — Slice kernels: definitions, scalar reference, dispatch
- profile 🔒
- Chapter 11.8 — Thresholds for double-double: the measurements behind Rule P
- simd 🔒
- Chapter 11.6 — SIMD kernels (
pulp) - verify
- Chapter 11.10 — Verified residuals and polishing
Structs§
- DdDense
- The dense kernel of
xingo-sparsefor double-double blocks, with the results ofNaiveDensebit for bit (Chapter 11.7):gemm_sub,syrk_suband the triangular solves run the column update ofcrate::kernels::gemm_subon SIMD registers (featuresimd), and so doespotrf(left-looking sincexingo-sparse0.4.0);sytrfis that ofNaiveDense. With itSupernodalLdl<DoubleDouble, DdDense>spends its time in SIMD. - Double
Double - A double-double number: the exact sum
hi + loof twof64, normalized (invariant D1). About 106 bits of significand (32 decimal digits), the exponent range off64. - Error
Bound - The proven relative error bound of one operation of
DoubleDouble, as a multiple ofu² = 2⁻¹⁰⁶: anf64that is at least the full proven expression of the chapter’s table (rounded up where the expression has higher-order terms), so thatunits_of_u2 · u²is itself a rigorous bound. - Function
Bound - The declared error bound of one elementary function of
DoubleDouble:|z − f(x)| ≤ (units_of_u2 + growth_units_of_u2 · G) u² |f(x)| + absolute, for results of magnitude in [2⁻⁹⁶⁸, Ω] (below:+ η). - Interval
- A closed interval
[lo, hi]withf64endpoints, or the empty set (invariants I1–I3). Operations round outward by computed directed rounding (Chapter 11.9). - Invalid
Interval lo > hi, or an endpoint is NaN, orlo = +∞, orhi = −∞.- Parse
Double Double Error - A decimal string that is not a number.
Functions§
- fast_
two_ sum - As
two_sumin 3 flops, requires|a| ≥ |b|ora = 0(Dekker’s Fast2Sum); the requirement is adebug_assert!. - two_
prod (p, e)withp = fl(a · b)andp + e = a · bexactly, by one fused multiply-add. Exact whena b = 0or|a b| ≥ 2⁻⁹⁶⁹andpdoes not overflow; otherwise|a b − (p + e)| ≤ η.- two_sum
(s, e)withs = fl(a + b)ands + e = a + bexactly (Knuth’s TwoSum: 6 flops, no branch, no condition on the operands). Exact unlesssoverflows — ora = ±Ω, where an intermediate difference can overflow and leaveenon-finite (invariant T1 of Chapter 11.1).