Skip to main content

Crate xingo_extprec

Crate xingo_extprec 

Source
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:

  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).

operationalgorithmrelative errorflops
dd + f64DWPlusFP (JMP Alg. 4)≤ 2u²/(1 − 2u) < 2u² + 5u³10
dd + ddAccurateDWPlusDW (JMP Alg. 6)≤ 3u²/(1 − 4u) < 3u² + 13u³20
dd · f64DWTimesFP3 (JMP Alg. 9, FMA)≤ 2u²6
dd · ddDWTimesDW3 (JMP Alg. 12, FMA)≤ 4u² (MR; JMP proved 5u²)9
dd²DWPow2 (two-FMA product specialized)≤ 3u² (Hubrecht & Melquiond 2026, binary64)6
dd / f64DWDivFP3 (JMP Alg. 15)≤ 3u²10
dd / ddDWDivDW2 (JMP Alg. 17)≤ 15u² + 56u³18
√ddSQRTDWtoDW (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.

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 of xingo-sparse in 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-sparse for double-double blocks, with the results of NaiveDense bit for bit (Chapter 11.7): gemm_sub, syrk_sub and the triangular solves run the column update of crate::kernels::gemm_sub on SIMD registers (feature simd), and so does potrf (left-looking since xingo-sparse 0.4.0); sytrf is that of NaiveDense. With it SupernodalLdl<DoubleDouble, DdDense> spends its time in SIMD.
DoubleDouble
A double-double number: the exact sum hi + lo of two f64, normalized (invariant D1). About 106 bits of significand (32 decimal digits), the exponent range of f64.
ErrorBound
The proven relative error bound of one operation of DoubleDouble, as a multiple of u² = 2⁻¹⁰⁶: an f64 that is at least the full proven expression of the chapter’s table (rounded up where the expression has higher-order terms), so that units_of_u2 · u² is itself a rigorous bound.
FunctionBound
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] with f64 endpoints, or the empty set (invariants I1–I3). Operations round outward by computed directed rounding (Chapter 11.9).
InvalidInterval
lo > hi, or an endpoint is NaN, or lo = +∞, or hi = −∞.
ParseDoubleDoubleError
A decimal string that is not a number.

Functions§

fast_two_sum
As two_sum in 3 flops, requires |a| ≥ |b| or a = 0 (Dekker’s Fast2Sum); the requirement is a debug_assert!.
two_prod
(p, e) with p = fl(a · b) and p + e = a · b exactly, by one fused multiply-add. Exact when a b = 0 or |a b| ≥ 2⁻⁹⁶⁹ and p does not overflow; otherwise |a b − (p + e)| ≤ η.
two_sum
(s, e) with s = fl(a + b) and s + e = a + b exactly (Knuth’s TwoSum: 6 flops, no branch, no condition on the operands). Exact unless s overflows — or a = ±Ω, where an intermediate difference can overflow and leave e non-finite (invariant T1 of Chapter 11.1).