Know how wrong a floating-point result is.
Double-double numbers whose every operation and elementary function has a proven error bound, compensated kernels, intervals without touching the rounding mode, and certified residuals and solution errors of sparse systems. Pure Rust, written as a book, deterministic to the bit.
Four entry points, one layer
Not an arbitrary-precision library and not interval linear algebra: the cheap step between f64 and exact rationals that a solver needs to measure, polish and certify its own results.
DoubleDouble
An unevaluated sum of two f64, about 32 decimal digits. Field operations by the algorithms of Joldes, Muller & Popescu, whose bounds are proven; always the accurate addition, never the "sloppy" one whose error is unbounded under cancellation. Correctly rounded Display and FromStr, the 23 elementary functions of f64 with its special cases, the 19 constants of f64::consts.
Compensated kernels
sum2, dot2 and dot2_err (Ogita, Rump & Oishi) return an f64 sum or dot product as accurate as if computed in twice the precision, dot2_err with a rigorous bound on its own error; the double-double dot, axpy and gemm_sub. SIMD (NEON, AVX2) with the bits of the scalar reference.
Interval
Closed intervals with f64 endpoints, each operation the tightest representable enclosure of the exact range. Directed rounding is computed from error-free transformations, not set in hardware: Rust has no sound way to change the rounding mode, and the crate has no unsafe. Exact under underflow too.
verify
An interval that contains each residual a_iᵀx − b_i of a sparse system of xingo-sparse, at about 25 flops per nonzero; polish refines x in double-double around the caller's f64 solve; forward_error_bound proves A nonsingular and bounds the error ‖x − A⁻¹b‖∞, component by component, from at most n to 2n transposed solves (Theorem E). With the feature sparse, Lu<DoubleDouble> and SupernodalLdl<DoubleDouble> run unchanged.
Without the default features sparse and simd the crate has no dependency at all: DoubleDouble with its functions, the scalar kernels and Interval remain. With or without simd the results are the same, bit for bit.
Proven, then measured
Every bound is a theorem the code exposes as data (DoubleDouble::ERROR_BOUNDS, DoubleDouble::FUNCTION_BOUNDS) and the tests check against exact arithmetic. The numbers below come from the decision log of the solver this crate was built for.
Elementary functions: declared, proven, observed
Relative error in units of u² = 2⁻¹⁰⁶, as a fraction of the declared bound (the number at the right). Upper bar: the bound the proof gives. Lower bar: the worst error observed in 10⁵ samples of the family.
Ten of the 23 functions; the others are in the same range. In a separate validation against mpmath at 3 000 bits (256 000 samples, an oracle the implementation does not use), no bound was violated and the worst error was 30 % of its bound. sin and cos carry an absolute floor of 2⁻²⁰⁰ on the whole real line (Payne–Hanek reduction).
Operations: bound and worst observed error
Relative error in units of u²; the worst of 20 000 samples against exact rationals.
| Operation | Algorithm | Bound | Observed |
|---|---|---|---|
dd + f64 | DWPlusFP | 2/(1 − 2u) | 1.00 |
dd + dd | AccurateDWPlusDW | 3/(1 − 4u) | 1.98 |
dd · f64 | DWTimesFP3 | 2 | 1.38 |
dd · dd | DWTimesDW3 | 4 | 2.93 |
dd² | DWPow2 | 3 | 2.86 |
dd / f64 | DWDivFP3 | 3 | 2.56 |
dd / dd | DWDivDW2 | 15 + 56u | 6.17 |
√dd | SQRTDWtoDW | 25/8 | 2.69 |
The division keeps DWDivDW2 instead of DWDivDW3 and its better bound (9.8): a quotient through a rounded reciprocal lost 53/53 = 1 and 4 600 of the 39 601 integer quotients (q·y)/y = q, which DWDivDW2 returns exactly.
93 of 93 Netlib bases certified
The residual of the optimal basis of every Netlib LP, enclosed by verify, with no unbounded enclosure: largest certified ‖r‖∞ 1.2 × 10⁻¹² relative to max(1, ‖z‖∞) in f64, 6.8 × 10⁻²² after polishing. In the solver, --exact-check=interval adds 0.18 % to the solve time of the 93. The error of every basic solution is bounded too (forward_error_bound): 93 of 93 certified, in 15 s.
SIMD with the same bits
On NEON, 1.9–2.1× faster than the scalar reference for sum2, dot2, dot; 1.6–1.8× for axpy and gemm_sub; 1.3–1.4× for dot2_err. DdDense speeds the supernodal LDLᵀ factorization in double-double 1.47–1.67×.
What it costs
1.4–3.4 ns per double-double operation; 190–760 ns per elementary function (exp 233, sin 344, ln 427). Over f64: LU factorization 1.7–1.9×, LDLᵀ factorization 6–11×. Apple M2 Pro; on a Xeon E5-2699 v4 the elementary functions take 310–1 030 ns.
Written as a book
Every module is a chapter: purpose, notation, the algorithm in numbered steps, invariants, the proofs of the bounds, references. The crate documentation is the text, every chapter included (docs.rs builds it with the private items, where most chapters live), starting at Chapter 11 with the corrections the implementation made to its own contract.
Invariants that run
Each invariant of a chapter is a debug_assert! or a check_invariants(); property-based tests replay them against exact rational and dyadic oracles (dashu, a development dependency only).
Deterministic
Every operation is a fixed sequence of f64 operations: no data-dependent choice of algorithm, no reassociation, no threads. Golden bits in the tests pin the elementary functions.
No libm calls
The precision of f64::exp, ln, sin, … is unspecified and may differ between platforms; a lint rule forbids them in the crate. The seeds are tables; only + − × ÷ √ fma and rounding to integers are used.
Never claims more than it proved
When a hypothesis of a bound fails (overflow, a NaN, too long a vector) the answer is Interval::ENTIRE, a bound of +∞ or an error, never a finite interval. The certainly_* predicates are false on the empty set.
No unsafe, no C
#![forbid(unsafe_code)]. Both dependencies are optional and pure Rust: xingo-sparse and pulp (MIT). Nothing GPL or LGPL is used or linked, and there is no C binding to build.
Read, not copied
The QD library, twofloat and inari were studied as references; the code is written from the papers: Dekker, Knuth, Joldes–Muller–Popescu, Muller–Rideau, Lefèvre–Louvet–Muller–Picot–Rideau, Ogita–Rump–Oishi, Rump–Zimmermann–Boldo–Melquiond.
Install & run
Rust 1.90 or later. The README's examples are compiled as doc-tests, so they cannot drift from the API; changes between versions are in the changelog.
$ cargo add xingo-extprec # everything, with SIMD
$ cargo add xingo-sparse --no-default-features # the matrices verify reads
$ cargo add xingo-extprec --no-default-features # no dependency
// decimal in, decimal out: 31 digits, correctly rounded
use xingo_extprec::DoubleDouble;
let x: DoubleDouble =
"0.1000000000000000000000000000001".parse()?;
assert_eq!(x.to_string(),
"0.1000000000000000000000000000001");
let third = DoubleDouble::ONE / 3.0;
assert_eq!(third.to_string(),
"0.3333333333333333333333333333333");
// within 8u² of e, by Theorem E
let e = DoubleDouble::ONE.exp();
// certify, polish, certify again
use xingo_extprec::verify::*;
let r = residual(&a, &x, &b)?; // R_i ∋ a_iᵀx − b_i
let mut xd = x.map(DoubleDouble::from_f64);
polish(&a, &b, &mut xd,
&mut solve, // your f64 LU
&PolishOptions::default())?;
let rd = residual_of_dd(&a, &xd, &b)?;
assert!(norm_inf_bound(&rd) <= 1e-25);
// and a theorem about the solution itself
let e = forward_error_bound(&a, &rd,
&mut solve_transpose, // your BTRAN
&ForwardErrorOptions::default())?;
assert!(e.is_certified()); // ‖xd − A⁻¹b‖∞ ≤ e.norm_inf
Three measurement programs ship with the crate: cargo run --release --example dd_profile, dd_bench k8 and ft_limit. They print the Markdown tables recorded in the solver's decision log.
How it was verified
What was checked before 0.1, and by whom.
Exact oracles
Every operation, kernel and elementary function is tested against two exact oracles. The 23 elementary functions were checked again against mpmath: 256 000 points, 130 000 adversarial ones in the subnormal regime and a directed search of 10⁶ points per family, with no violation.
Independent review
The proofs of the elementary functions were re-derived line by line by three independent reviews. They and the subnormal tests found four defects (acos, acosh, atanh next to ±1; atan2 with a subnormal result), all fixed before release.
Error bound of a solution
forward_error_bound was checked on 262 000 adversarial cases in exact arithmetic: no singular matrix certified, no bound below the true error. It certifies the optimal bases of all 93 Netlib LPs.
No argument near kπ/2
A computation in integers (continued fractions and lattice reduction, every case checked exactly) shows that no double-double above π/4 lies within 2⁻¹²⁹ of a multiple of π/2; the closest found lies at 2⁻¹²⁴. An independent review recomputed the certificate with separate code. So the sharper bound of tan holds for every argument.
Subnormal regime
All 23 elementary functions are tested against the oracle below 2⁻⁹⁶⁸: subnormal arguments, subnormal trailing components and results that underflow.
Seven platforms in CI
x86_64 Linux and Windows, aarch64 Linux and macOS (NEON), i686 Linux, s390x Linux (big-endian, under QEMU) and WebAssembly (wasmtime); x86_64 on stable and on the MSRV; AVX2 + FMA run by hand. The SIMD kernels are compared bit for bit with the scalar reference.
A defect the review caught
The review of the new bound found an older kernel, dot2_err, returning too small a bound in an overflow corner. It now answers +∞ there; no other bit changed.
Known limitations of 0.1
What is still open. The ones that can be closed have an issue.
| The proofs are written and reviewed, not checked by a proof assistant (#2). |
| Big-endian and WebAssembly run in CI on the scalar path only (no SIMD backend there), s390x under emulation rather than on hardware; x86 CPUs without SSE2 were not run. |
| The bounds hold in the "safe range" (no overflow; every exact product at least 2⁻⁹⁶⁹ in magnitude, or zero); below it there is an added absolute error of order 2⁻¹⁰⁷⁴. An operand of the largest magnitude counts as overflow (#6). |
forward_error_bound covers one square system with point data, in the ∞-norm. It needs up to 2n solves and is quadratic in n when they are dense (21 s at n = 10⁴), so it does not reach n ≫ 10⁵ (#4). |
No QuadDouble, no elementary functions of intervals, no interval linear algebra (Krawczyk, verifylss), no correctly rounded elementary functions, no complex scalars, no f32. |
| The costs were measured on two machines, neither of them idle; the kernel and factorization costs on one only (#7). |
Authorship, credits and disclaimer
Who wrote this, whose work it stands on, and what it does not claim.
Authorship
xingo-extprec is written and maintained by André Leite as the extended-precision layer of the Xingó solver, developed at StrategicProjects. It is developed inside the Xingó monorepo and mirrored, at every release, to its own repository, where issues and pull requests are welcome. To cite it, use the Zenodo DOI or the repository's CITATION.cff.
Disclaimer
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 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 terms of the MIT and Apache-2.0 licenses.
Credits
The algorithms are those of their authors, implemented here from the published papers. Each chapter of the sources lists its references.
- Dekker and Knuth — error-free transformations
- Joldes, Muller & Popescu and Muller & Rideau — double-word arithmetic and its bounds
- Lefèvre, Louvet, Muller, Picot & Rideau — double-word square root
- Hubrecht & Melquiond — 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 - Hida, Li & Bailey (QD),
twofloat,inariand INTLAB — studied as references - dashu — the exact oracle of the tests
- pulp — the optional SIMD dependency