xingo-extprec
Website: https://strategicprojects.github.io/xingo-extprec/ (overview, bounds, measured cost, API reference).
Extended precision for numerical linear algebra, in pure Rust:
double-double numbers whose every operation has a proven error bound,
compensated sums and dot products, rigorous interval enclosures of
residuals A x − b and a rigorous bound of the error ‖x − A⁻¹b‖∞ of
an approximate solution, computed in ordinary round-to-nearest arithmetic. It is
the extended-precision layer of Xingó,
a linear and mixed-integer programming solver, and depends on nothing in it
except, optionally, its sparse linear algebra crate
xingo-sparse.
A solver computes in f64 and must sometimes know how wrong it is. A
residual recomputed in the arithmetic that produced the solution is itself
rounding noise, and a feasibility claim |a_iᵀx − b_i| ≤ 10⁻⁹ checked
that way proves nothing. Between f64 and exact rational arithmetic there
is a cheap intermediate step, and this crate is that step:
- more precision —
DoubleDouble, an unevaluated sum of twof64(about 32 decimal digits, 106 bits of significand), at a few nanoseconds per operation, in which residuals are computed, solutions are polished by iterative refinement, and the LU and LDLᵀ ofxingo-sparserun unchanged; - rigour — an interval
[r̲, r̄] ∋ a_iᵀx − b_ithat is a theorem about the storedf64data, obtained from error-free transformations and a running error bound, without touching the processor's rounding mode.
It is not an arbitrary-precision library (see
dashu for that), has no quad-double, no
complex numbers, and bounds the error of one approximate solution of a
square system with point data, not the solution sets of interval linear
systems (see "Scope" below).
Four entry points
1. DoubleDouble — the field operations, sqrt, comparisons,
correctly rounded decimal conversions, the elementary functions of f64
(same names, same special cases) and the 19 constants of
core::f64::consts. The algorithms are those of Joldes, Muller & Popescu
(2017), whose relative error bounds are proven; the addition is always the
accurate one (the "sloppy" addition of the QD library has an unbounded
relative error under cancellation, which is exactly the case of a residual).
use DoubleDouble;
// 1 + 10⁻¹⁶ is 1 in f64, not in double-double.
let big = from_f64;
assert_eq!;
assert_eq!;
// Decimal conversions are correctly rounded; `Display` prints 31 digits,
// so a decimal of at most 31 digits comes back as the same text.
let x: DoubleDouble = "0.1000000000000000000000000000001".parse?;
assert_eq!;
let third = ONE / 3.0;
assert_eq!;
// Elementary functions, each with a declared and proven bound: 8u² for exp.
let u2 = ONE.ldexp;
let e = ONE.exp;
assert!;
# Ok::
2. Compensated kernels — kernels::sum2, dot2 and dot2_err (Ogita,
Rump & Oishi 2005) take f64 slices and return a double-double as accurate
as if computed in twice the working precision; dot2_err also returns a
rigorous bound β on its own error. The double-double dot, dot_mixed,
axpy and a small-block gemm_sub complete the set. The SIMD versions
(feature simd) return the bits of the scalar reference, input by input.
use ;
let x = ;
let y = ;
let naive: f64 = x.iter.zip.map.sum;
assert_eq!; // the 1 is lost
assert_eq!;
// |xᵀy − r| ≤ β, a theorem about the f64 data.
let = dot2_err;
assert!;
3. Interval — closed intervals with f64 endpoints whose + − ·,
/ (by an interval without zero) and sqrt return the tightest
representable enclosure of the exact range, underflow included.
Directed rounding is computed from the error-free transformations
instead of set in hardware: Rust has no sound way to change the rounding
mode, and this crate has no unsafe.
use Interval;
let tenth = point; // the f64 nearest to 0.1, exactly
let s = tenth + tenth + tenth;
assert!;
assert!; // the exact sum is not an f64
assert!;
4. verify (feature sparse) — Algorithm V encloses every residual
a_iᵀx − b_i of a sparse system (CsrMatrix or CscMatrix of
xingo-sparse) for an f64 or a double-double x, at about 25 flops per
nonzero (about 115 for a double-double x, whose residual is summed as if
in three times the working precision, so that its enclosure is a few ulps
wide even at double-double level); Algorithm P polishes x by iterative refinement with
double-double residuals around an f64 solve the caller already has (an
LU, say). The polished residual is then certified by Algorithm V.
Algorithm E (forward_error_bound) turns an enclosed residual into a
theorem about the solution: from at most n transposed solves (at most
2n with the default refinement; the BTRAN of the same LU) it proves that a square A
is nonsingular and bounds ‖x − A⁻¹b‖∞ and every |x_p − (A⁻¹b)_p|,
whatever the solve returns — a wrong one can only prevent the
certificate.
use ;
use DoubleDouble;
use CsrMatrix;
// A = [1 2; 3 4] by rows, b = A (1/3, 1/3).
let a = from_raw_parts?;
let b = ;
let mut solve = ;
let mut x = ;
x.copy_from_slice;
solve;
// Certified residual of the f64 solution: every row's interval contains
// the exact a_iᵀx − b_i of the stored data.
let r = residual?;
assert!;
// Polish in double-double around the same f64 solve, then certify.
let mut xd = x.map;
let report = polish?;
assert_eq!;
assert!;
# Ok::
use ;
use CsrMatrix;
// The same A = [1 2; 3 4] and b = A (1/3, 1/3), an f64 solution x.
let a = from_raw_parts?;
let b = ;
let x = ;
// A⁻ᵀ c in f64 (in practice the BTRAN of an LU of A).
let mut solve_transpose = ;
let r = residual?;
let e = forward_error_bound?;
// A theorem: A is nonsingular and ‖x − A⁻¹b‖∞ ≤ e.norm_inf for the stored
// data (b₂ is the f64 nearest 7/3, so A⁻¹b is not (1/3, 1/3) exactly).
assert!;
assert!;
assert_eq!;
# Ok::
With the feature sparse, DoubleDouble implements xingo_sparse::Real,
so Lu<DoubleDouble>, SupernodalLdl<DoubleDouble> and every container of
xingo-sparse exist without one line of duplicated code, and DdDense is
the DenseKernel of the supernodal LDLᵀ in double-double, with SIMD and the
bits of the generic kernel. The programs in examples/
(dd_profile, dd_bench, ft_limit) reproduce the measurements recorded
in the solver's decision log; they print Markdown tables.
Proven error bounds
Every bound below is a theorem, not a fit to a measurement, and every row
is data the code exposes: DoubleDouble::ERROR_BOUNDS (operations) and
DoubleDouble::FUNCTION_BOUNDS (elementary functions). u = 2⁻⁵³, so
u² = 2⁻¹⁰⁶. The bounds are relative and hold barring overflow and
underflow: for the operations, operands in the "safe range" of Chapter
11.2 (every product formed by two_prod at least 2⁻⁹⁶⁹ in magnitude, or
zero; outside it the result is still normalized, with an absolute error of
order 2⁻¹⁰⁷⁴); for the functions, results of magnitude in [2⁻⁹⁶⁸, Ω]
(below, plus 2⁻¹⁰⁷⁴). The tests check every row against exact
arithmetic.
| operation | algorithm | relative error | source of the proof |
|---|---|---|---|
dd + f64 |
DWPlusFP | 2u²/(1 − 2u) |
Joldes, Muller & Popescu 2017 |
dd + dd |
AccurateDWPlusDW | 3u²/(1 − 4u) |
Joldes, Muller & Popescu 2017 |
dd · f64 |
DWTimesFP3 | 2u² |
Joldes, Muller & Popescu 2017 |
dd · dd |
DWTimesDW3 | 4u² |
Muller & Rideau 2022 (Coq) |
dd² |
DWPow2 | 3u² |
Hubrecht & Melquiond 2026 (Gappa, binary64) |
dd / f64 |
DWDivFP3 | 3u² |
Joldes, Muller & Popescu 2017 |
dd / dd |
DWDivDW2 | 15u² + 56u³ |
Joldes, Muller & Popescu 2017 |
√dd |
SQRTDWtoDW | 25/8 u² |
Lefèvre, Louvet, Muller, Picot & Rideau 2023 |
Each units_of_u2 of ERROR_BOUNDS is an f64 at least the full
expression above, so that units_of_u2 · u² is itself a rigorous bound:
2, 4, 3, 3 and 3.125 exactly, and the three expressions with
higher-order terms rounded up — 2 + 2⁻⁵⁰, 3 + 2⁻⁴⁹, 15 + 2⁻⁴⁷ (a test
checks each row in exact rational arithmetic). The division is DWDivDW2, not the DWDivDW3 with the better
bound 9.8u²: a quotient through a rounded reciprocal loses the exact
quotients (53/53 ≠ 1, (q·y)/y ≠ q for 4 600 of the 39 601 integer pairs
below 200), which DWDivDW2 keeps.
| function | declared bound (u² relative, plus absolute floor) |
proven in Chapter 11.11 |
|---|---|---|
exp, exp2, exp_m1, ln, ln_1p, atan |
8u² |
4.6–7.7 |
log2, log10 |
12u² |
11.7 |
powi(x, n) |
`(15 + 4 | n |
powf(x, y) |
`(16 + 11 | y ln x |
sin, cos, sin_cos |
8u² + 2⁻²⁰⁰ absolute |
6.9u² + 2⁻³¹⁵ |
tan |
`(32 + 2⁻⁹⁴ | tan x |
asin, acos, atan2, sinh, cosh, tanh, asinh, acosh, atanh |
32u² |
15.1–26.4 |
The circular functions reduce their argument by Payne–Hanek in integer
arithmetic for every |x| > π/4, so the bound holds on the whole real
line (sin(2⁹⁶⁰) included). In a validation outside the test suite,
against an oracle the implementation does not use (mpmath at 3 000 bits,
256 000 samples over the 23 functions), no bound was violated and the
worst error was 30 % of its declared bound.
Features
sparse(default) — brings inxingo-sparse0.4 or 0.5 (pure Rust, no dependency of its own withdefault-features = false, which is how this crate asks for it):impl xingo_sparse::Real for DoubleDouble, the dense kernelDdDenseand the moduleverify.simd(default) — the kernels on vector registers throughpulp0.22 (pure Rust, MIT; safe run-time dispatch): NEON on aarch64, AVX2 + FMA on x86_64 CPUs that have them, the scalar reference elsewhere. Same results bit for bit with or without it (invariant K1); only the speed changes.kernels::backend()names the path taken.- Without both (
default-features = false) the crate has no dependency at all:DoubleDoublewith its elementary functions, the error-free transformations, the scalar kernels andIntervalremain.
Guarantees
- Deterministic, the same bits everywhere. Every operation is a fixed
sequence of
f64operations: no data-dependent choice of algorithm, no reassociation, no threads. The SIMD kernels return the bits of the scalar ones (where a result is a NaN both are NaN; its sign and payload are not specified). Requires IEEE 754 binary64 with round-to-nearest and a correctly roundedfma, which Rust guarantees on every tier-1 target (f64::mul_addfalls back to a correct software FMA where the CPU has none: slow, never wrong). - No libm calls. The precision of
f64::exp,ln,sin, … is unspecified by the standard library and may differ between platforms, so none of them is called by this crate (aclippy.tomlrule forbids them): the seeds of the elementary functions are tables, and only+ − × ÷ √ fma round truncoff64are used. (pulp, with thesimdfeature, depends on thelibmcrate; the kernels use only its additions, multiplications and FMAs.) - No
unsafe(#![forbid(unsafe_code)]);pulphas its own, behind a safe API. - A certificate never claims more than it proved. When a hypothesis of
a bound fails (overflow, a NaN or an infinity in the data, a length with
2(n + 3)u ≥ 1) the result isInterval::ENTIRE, a bound of+∞or an error, never a finite interval. Thecertainly_*predicates arefalseon the empty set. - What a certificate means. The enclosures are statements about the
f64data as stored. That a decimal0.1in an input file became thef64nearest to it is outside this crate.
Scope
In: the error-free transformations two_sum, fast_two_sum, two_prod;
DoubleDouble with its field operations, sqrt, comparisons, decimal
conversions, 23 elementary functions and 19 constants; the compensated and
double-double slice kernels; Interval with + − · /, sqrt, square,
abs, hull, intersection and the verified predicates; rigorous residual
enclosures, polishing and a rigorous bound of the error of an approximate
solution (Algorithm E) over the containers of xingo-sparse; the
DenseKernel DdDense.
Out, by decision: arbitrary precision; complex scalars; f32; a
QuadDouble (the name is reserved; a basis that double-double does not
resolve would reopen it — none of the 93 Netlib optimal bases needed it);
elementary functions of intervals (they would need enclosures, not bounds);
correctly rounded elementary functions; interval linear algebra (interval
LU, Krawczyk, verified solution sets of interval systems à la
verifylss); error bounds in the 2-norm; the QD library's "sloppy"
addition.
Not in 0.1, and additive when they come: arithmetic operators with an
f64 on the left (f64 + DoubleDouble) and the assignment operators with
an f64 (x += 1.0) for DoubleDouble (Interval has both); floor,
ceil, round, trunc, signum, total_cmp.
How it was verified
- Exact oracles. Every operation, kernel and elementary function is
tested against two exact oracles in the suite, and the 23 elementary
functions were checked once more, outside the suite, against
mpmath(256 000 points, then 130 000 adversarial ones in the subnormal regime and a directed search of 10⁶ points per family: no violation). - Independent review of the proofs. Before 0.1 the proofs of Chapter
11.11 were re-derived line by line by three independent reviews, each
with a directed search against
mpmath. They found three defects (acosandacoshof1 ∓ δandatanhof±(1 − δ)with a tiny trailing componentδ); the subnormal tests found a fourth (atan2with a subnormal result). All four were fixed before release. Each proven constant is honest up to a factor1 + 2⁻⁸⁰(the neglected products of errors), and every declared constant exceeds it by far more (the smallest margin islog2andlog10: 12 declared, 11.7 proven). - No argument near a multiple of
π/2. A computation in integers (tests/reduction_bound.rs: continued fractions, and lattice reduction where the two components of the argument are far apart, every case checked exactly) shows that no double-double aboveπ/4lies within2⁻¹²⁹of a multiple ofπ/2(Lemma D of Chapter 11.11; the closest found lies at2⁻¹²⁴). The lemma and its program were reviewed independently, and the certificate recomputed with separate code. So the bound oftanproven in the chapter holds for every argument. - Subnormal regime. All 23 elementary functions are tested against the
oracle below
2⁻⁹⁶⁸, at directed points and in property tests: subnormal arguments, normal ones with a subnormal trailing component (1 ± δwithδdown to2⁻¹⁰⁷⁴), and results that underflow (exp,exp2,exp_m1,powi,powf,atan2). forward_error_bound. An independent reviewer checked 262 000 adversarial cases in exact arithmetic (singular, nearly singular and badly scaled matrices; solves that return garbage): no singular matrix certified, no bound below the true error. The review found one defect in an older kernel,dot2_err, in an overflow corner; it was fixed before release. In the Xingó solver the function certifies the optimal bases of all 93 Netlib LPs; on dense test matrices it certified up toκ(A) ≈ 10¹⁶with refinement (≈ 10¹⁴without) — a measurement, not a guarantee in either direction.- Platforms. The suite, with the golden bits of the elementary
functions and the SIMD kernels compared bit for bit with the scalar
reference, runs in the CI of the mirror on x86_64 Linux, x86_64 Windows,
aarch64 Linux and macOS (NEON), i686 Linux (32 bits), s390x Linux
(big-endian, under QEMU) and
wasm32-wasip1(under wasmtime), and was run by hand on x86_64 Linux with AVX2 + FMA (a Xeon E5 v4) and on x86_64 macOS under emulation (the scalar path).
Known limitations
What is still open in 0.1. The ones that can be closed have an issue.
- The proofs are not machine-checked. They are first-order analyses written in the chapters of the sources, reviewed and tested, not verified by a proof assistant (#2).
- Platforms not run: x86 CPUs without SSE2. Big-endian and
WebAssembly run in the CI, but neither has a SIMD backend, so they
check the scalar path only; s390x runs under emulation (QEMU), not on
hardware, and on WebAssembly the
should_panictests are skipped by the test harness (panic = abort). - The bounds hold in the safe range (no overflow; every
two_prodproduct of magnitude at least2⁻⁹⁶⁹, or zero). Below it the operations stay normalized with an absolute error of order2⁻¹⁰⁷⁴, and the elementary functions addη = 2⁻¹⁰⁷⁴to their bounds. An operand of magnitudeΩcounts as overflow (#6). forward_error_boundcovers one square system with point data, in the ∞-norm and by component: no solution sets of interval systems, no 2-norm bounds, no non-square systems. It needs up to2ntransposed solves and is quadratic innwhen they are dense (21 s atn = 10⁴), so it does not reachn ≫ 10⁵(#4).- The costs were measured on two machines, neither of them idle; the kernel and factorization rows on one only (#7).
Measured cost
On an Apple M2 Pro (NEON), release builds, medians recorded in the solver's benchmark log (on x86_64 only the elementary functions, below, were measured):
| what | cost |
|---|---|
dd · dd, dd + dd, dd / dd, √dd (throughput) |
1.9, 2.8, 3.4, 1.4 ns |
SIMD over the scalar reference: sum2, dot2, dot, dot_mixed |
1.9–2.1× faster |
… axpy, gemm_sub, dot2_err |
1.65–1.84×, 1.63–1.66×, 1.3–1.4× |
dot2 (SIMD) against the naive f64 dot product, n ≥ 1 024 |
0.8–0.9× the time |
supernodal LDLᵀ factorization in double-double, DdDense over the generic kernel |
1.47–1.67× faster (1.00× when the factorization is simplicial; solves unchanged) |
double-double over f64: LDLᵀ factorization / solve |
6–11× / 10–16× |
double-double over f64: LU factorization / FTRAN |
1.7–1.9× / 5–8× |
In the Xingó solver, certifying the residuals of the optimal basis of each
of the 93 Netlib LPs by intervals takes 0.18 % of the solve time in total
(--exact-check=interval), and all 93 come out certified. Bounding the
error of the basic solution by forward_error_bound certifies all 93 too,
in 15 s for both an f64 and a polished solution (the dual simplex takes
about 30 s), with ε equal to the error measured against the polished
point to three digits — and, for the polished solution, ε̂ equal to its
own true error to three digits as well (it was up to 7.7 · 10⁴ times
larger in 0.1.2; #5).
An elementary function takes 190–760 ns per call on the M2 Pro (exp 233,
ln 427, sin 344, atan 196, powf 758) and 310–1 030 ns on a Xeon
E5-2699 v4 with AVX2 (exp 361, ln 595, sin 596, atan 312, powf
1 033); three runs on each machine. sin_cos shares the reduction, not the
kernels. The example elementary_bench (cargo run --release --example elementary_bench, no feature needed) prints the same rows on any machine.
polish stops on a per-row test |r_i| ≤ τ (Σ_j |a_ij x_j| + |b_i|); on
bases with degenerate rows it often ends Stagnated, which is harmless (9
of the 93 Netlib bases).
Design notes
- Literate. Every module is a chapter: notation, the algorithm in
numbered steps, invariants (each a
debug_assert!or acheck_invariants()), proofs of the bounds, references. The crate documentation is the text: start at the crate root on docs.rs (Chapter 11, with the sections "Corrections to the approved contract", which list what the implementation found wrong in its own contract). Most chapters, the proofs of Chapters 11.2 and 11.11 among them, are the documentation of private modules, so docs.rs builds with--document-private-items; private items are marked as such. - Read, not copied. The QD library (Hida, Li & Bailey),
twofloatandinariwere studied as references, INTLAB'sverifylssas the boundary of the scope; the code is written from the papers. The exact oracles of the tests aredashu(MIT OR Apache-2.0), a development dependency only. - Errors, not panics, on data: a dimension mismatch is a
VerifyError, an unreadable decimal aParseDoubleDoubleError, an inverted interval anInvalidInterval. Panics are reserved for contract violations (slices of different lengths in a kernel, a NaN endpoint inInterval::point).
Minimum supported Rust version
1.90 (edition 2024), tested in CI together with stable.
Repository, issues and citation
The crate is developed inside the Xingó monorepo
(StrategicProjects/xingo,
directory crates/extprec), where every change is validated together with
the solver that uses it. This stand-alone repository,
StrategicProjects/xingo-extprec,
is a read-only mirror of that directory (git subtree split, full history),
updated at every release; it exists so that the library can be archived and
cited on its own. Issues and pull requests about the crate are welcome in
either repository. Each release of the mirror is archived on Zenodo: the
concept DOI 10.5281/zenodo.24354162
always resolves to the latest version, each release has its own DOI on its
release page, and CITATION.cff has the citation metadata.
Authorship, credits and disclaimer
xingo-extprec is written and maintained by André Leite as the
extended-precision layer of the Xingó
solver, developed at StrategicProjects.
The algorithms are those of their authors, implemented here from the
published papers: Dekker and Knuth (error-free transformations), Joldes,
Muller & Popescu and Muller & Rideau (double-word arithmetic and its
bounds), Lefèvre, Louvet, Muller, Picot & Rideau (the double-word square
root), Hubrecht & Melquiond (the double-word square), Ogita, Rump & Oishi
(compensated sums and dot products), Rump, Zimmermann, Boldo & Melquiond
(predecessor and successor in rounding to nearest), Tang (table-driven
exponential), Payne & Hanek (argument reduction), Kahan (the correction of
ln_1p). The QD library of Hida, Li & Bailey, twofloat, inari and
INTLAB were studied as references; dashu (MIT OR Apache-2.0) is the exact
oracle of the tests and pulp (MIT) the optional SIMD dependency. Each chapter of the sources lists its references.
This is an independent project: it is not affiliated with, maintained by or
endorsed by the authors of the QD library, twofloat, inari, INTLAB,
pulp or dashu, and it includes no code from them (pulp is linked only
through the optional simd feature). All names and trademarks belong to
their owners. The software is provided "as is", without warranty of any
kind, under the licenses below.
License
Licensed under either of the Apache License, Version 2.0 or the MIT license, at your option.