Expand description
§Chapter 11.2 — Double-double arithmetic
§Purpose
DoubleDouble: the field operations, the square root and the
comparisons of numbers x = x_h + x_ℓ held as two f64. Each operation
is a short, fixed sequence of f64 operations built from the error-free
transformations of Chapter 11.1, with a relative error bound that was
proven in the literature; the bounds are data
(DoubleDouble::ERROR_BOUNDS) and the tests check every operation
against them in exact rational arithmetic.
§Notation
As in Chapters 11 and 11.1: RN, u = 2⁻⁵³, η = 2⁻¹⁰⁷⁴. A pair (h, ℓ) is normalized when h = RN(h + ℓ). 2Sum, Fast2Sum and 2Prod
are Algorithms S, F and P of Chapter 11.1. “JMP” is Joldes, Muller &
Popescu (2017), “MR” Muller & Rideau (2022), “LLMPR” Lefèvre, Louvet,
Muller, Picot & Rideau (2023).
§Algorithms
Inputs are normalized pairs x = (x_h, x_ℓ), y = (y_h, y_ℓ) or an
f64 y; the output is the pair (z_h, z_ℓ). Subtraction is addition
of the (exact) negation.
Algorithm A1 (dd + f64; DWPlusFP, JMP Algorithm 4).
(s_h, s_ℓ) ← 2Sum(x_h, y).v ← RN(x_ℓ + s_ℓ).(z_h, z_ℓ) ← Fast2Sum(s_h, v).
Algorithm A2 (dd + dd; AccurateDWPlusDW, JMP Algorithm 6).
(s_h, s_ℓ) ← 2Sum(x_h, y_h);(t_h, t_ℓ) ← 2Sum(x_ℓ, y_ℓ).c ← RN(s_ℓ + t_h);(v_h, v_ℓ) ← Fast2Sum(s_h, c).w ← RN(t_ℓ + v_ℓ);(z_h, z_ℓ) ← Fast2Sum(v_h, w).
Algorithm M1 (dd · f64; DWTimesFP3, JMP Algorithm 9).
(c_h, c_ℓ1) ← 2Prod(x_h, y).c_ℓ3 ← RN(c_ℓ1 + x_ℓ y)(one FMA).(z_h, z_ℓ) ← Fast2Sum(c_h, c_ℓ3).
Algorithm M2 (dd · dd; DWTimesDW3, JMP Algorithm 12).
(c_h, c_ℓ1) ← 2Prod(x_h, y_h).t_ℓ0 ← RN(x_ℓ y_ℓ);t_ℓ1 ← RN(x_h y_ℓ + t_ℓ0);c_ℓ2 ← RN(t_ℓ1 + x_ℓ y_h)(two FMAs).c_ℓ3 ← RN(c_ℓ1 + c_ℓ2);(z_h, z_ℓ) ← Fast2Sum(c_h, c_ℓ3).
Algorithm M3 (dd²; DWPow2). The specialization of the two-FMA
product (JMP Algorithm 11) to equal operands.
(c_h, c_ℓ1) ← 2Prod(x_h, x_h).c ← RN(2 x_h x_ℓ + c_ℓ1)(one FMA;2 x_his exact).(z_h, z_ℓ) ← Fast2Sum(c_h, c).
Algorithm M4 (DWTimesFP1, JMP Algorithm 7). Used inside D2 only.
(c_h, c_ℓ1) ← 2Prod(x_h, y);c_ℓ2 ← RN(x_ℓ y).(t_h, t_ℓ1) ← Fast2Sum(c_h, c_ℓ2);t_ℓ2 ← RN(t_ℓ1 + c_ℓ1).(z_h, z_ℓ) ← Fast2Sum(t_h, t_ℓ2).
Algorithm D1 (dd / f64; DWDivFP3, JMP Algorithm 15).
t_h ← RN(x_h / y);(π_h, π_ℓ) ← 2Prod(t_h, y).δ_h ← RN(x_h − π_h);δ′ ← RN(δ_h − π_ℓ);δ ← RN(δ′ + x_ℓ).t_ℓ ← RN(δ / y);(z_h, z_ℓ) ← Fast2Sum(t_h, t_ℓ).
Algorithm D2 (dd / dd; DWDivDW2, JMP Algorithm 17).
t_h ← RN(x_h / y_h);(r_h, r_ℓ) ← M4(y, t_h).π_h ← RN(x_h − r_h);δ_ℓ ← RN(x_ℓ − r_ℓ);δ ← RN(π_h + δ_ℓ).t_ℓ ← RN(δ / y_h);(z_h, z_ℓ) ← Fast2Sum(t_h, t_ℓ).
D2 keeps exact quotients exact: when x / y is an f64 q (in
particular x/x = 1, (q y)/y = q, and (a b)/b = a for x the
exact product of two f64), t_h is q or a neighbour of it, the
residual x − y t_h is formed without error and t_ℓ is exactly q − t_h. A division through a reciprocal (DWDivDW3, JMP Algorithm 18:
bound 9,8u², 31 flops) does not have this property, which is why it
is not used here (Chapter 11, “Why not DWDivDW3”). The property is
tested, not proven, for the cases named.
Algorithm R (√dd; SQRTDWtoDW, LLMPR Algorithm 8). For x > 0.
s_h ← RN(√x_h).ρ₁ ← RN(x_h − s_h²)(one FMA; exact);ρ₂ ← RN(x_ℓ + ρ₁).s_ℓ ← RN(ρ₂ / (2 s_h));(z_h, z_ℓ) ← Fast2Sum(s_h, s_ℓ).
Step E (exceptional results), the last step of every algorithm. Let
g be the plain f64 result of the operation on the leading components
(x_h + y_h, x_h y_h, x_h / y_h, √x_h). If z_h is finite,
return (z_h, z_ℓ) — with z_ℓ replaced by 0 if it is not finite
(possible only in from_sum, invariant T1). If z_h is NaN, or g is
not finite, return (g, 0): the IEEE result (∞ − ∞ is NaN, 1/0 = ∞, x/∞ = 0, …), or the plain f64 result when an intermediate
quantity overflowed although the result did not (operands within a
factor of four of Ω). Otherwise (z_h infinite with g finite: the
low-order terms carried the sum over Ω) return (z_h, 0).
§Bounds, and where they hold
Let the safe range be: finite operands that are zero or of magnitude
in [2⁻⁴⁸⁰, 2⁴⁸⁰]. There no operation overflows and every 2Prod is in
its exact range (invariant T2: the products formed are near x_h y_h,
x_h or y_h t_h ≈ x_h, all of magnitude at least 2⁻⁹⁶⁰). In the
safe range the relative error |z − z*| / |z*| of the result z
against the exact z* is at most:
| operation | algorithm | bound | source | flops |
|---|---|---|---|---|
dd + f64 | A1 | 2u²/(1 − 2u) < 2u² + 5u³ | JMP §3 (DWPlusFP) | 10 |
dd + dd | A2 | 3u²/(1 − 4u) < 3u² + 13u³ | JMP Thm 3.1 | 20 |
dd · f64 | M1 | 2u² | JMP (DWTimesFP3) | 6 |
dd · dd | M2 | 4u² | MR (JMP proved 5u²) | 9 |
dd² | M3 | 3u² | Hubrecht & Melquiond 2026, §IV-B (binary64; see below) | 6 |
dd / f64 | D1 | 3u² | JMP (DWDivFP3) | 10 |
dd / dd | D2 | 15u² + 56u³ | JMP (DWDivDW2) | 18 |
√dd | R | 25/8 u² | LLMPR Theorem 3.6 | 8 |
The square root’s constant. LLMPR, Theorem 3.6 (read in the author
version, HAL hal-03482567v2; the proof is in their supplementary
material and formalized in Coq): “if x = (x_h, x_ℓ) is a double-word
number, p ≥ 5, x ≥ 2^(2k) where k is an integer larger than or
equal to (e_min + p)/2, and no overflow or underflow occurs, then the
relative error of Algorithm 8 is bounded by (25/8) u², and that bound
is asymptotically optimal”. For binary64 the condition is x ≥ 2⁻⁹⁶⁸,
which the safe range implies. A first-order analysis, written before
the text could be read, reproduces the constant. Take 1 ≤ x_h < 2
(ulp(x_h) = 2u). Then |s_h − √x_h| ≤ u, ρ₁ is exact with |ρ₁| ≤ 2u√x_h, and r = x − s_h² = x_ℓ + ρ₁ has |r| ≤ (2√x_h + 1)u < 4u.
Three errors remain, relative to √x: rounding ρ₂ (≤ 2u² absolute,
u²/x_h after the division by 2 s_h), rounding s_ℓ (|s_ℓ| < 2u,
hence ≤ u² absolute, u²/√x_h), and the truncation of the Newton
step, r² / (8 x_h²) ≤ (2√x_h + 1)² u² / (8 x_h²). Their sum is
largest as x_h → 1: 1 + 1 + 9/8 = 25/8. For 2 ≤ x_h < 4 the same
count gives at most 2,44 u². The tests check 25/8 against exact
arithmetic (largest error observed on 20 000 random operands: 2,69 u²).
The square’s constant. Hubrecht & Melquiond (2026, §IV-B) bound the
relative error of exactly the code of M3 by 3u²: a proof generated by
the tool Gappa for binary64 with round-to-nearest-even and an
unbounded exponent range (so it says nothing about underflow or
overflow, which the safe range excludes), for an operand x_h = RN(x),
x_ℓ = x − x_h. Their statement is about c_h + c before the final
Fast2Sum, which is error-free here (|c| ≤ |c_h|). It is not a theorem
for a general precision. The tests check 3u² against exact
arithmetic (largest error observed: 2,86 u²).
The additions never leave the model of the proofs when subnormal
numbers occur (invariant T1): their bounds hold on the whole finite
range short of overflow, where an operand of magnitude Ω counts as
overflow: an intermediate step of its 2Sum can overflow and step E then
returns the rounded f64 sum (measured: relative error 2⁵² u²).
Outside the safe range the other operations
lose the bound — a 2Prod that underflows contributes an absolute error
of order η — but keep the invariants below.
The sloppy addition of the QD library (11 flops) is not offered: its relative error is unbounded for operands of opposite signs (JMP §3).
§Invariants
(D1) Normalized. Every finite value satisfies h = RN(h + ℓ) (hence
|ℓ| ≤ ulp(h)/2); h = ±0 implies ℓ = 0.
(D2) Non-finite. If h is infinite then ℓ = 0; the value is
“infinite” or “NaN” as h says, and the operations follow IEEE on
h (step E).
(D3) Order. The derived lexicographic order on (h, ℓ) is the order
of the values h + ℓ, total on the non-NaN values.
(D4) Conversions. from_f64 is exact; to_f64 is h, the f64
nearest to the value.
(D5) Determinism. Every operation is the fixed sequence of f64
operations above, followed by step E: no data-dependent choice of
algorithm, no reassociation, the same bits on every platform.
DoubleDouble::check_invariants tests (D1) and (D2);
DoubleDouble::from_parts asserts them in debug builds.
§Comparisons
This module compares f64 values exactly (==, <): exactness is its
subject, as tolerances are the subject of xingo_core::Tolerances. No
tolerance appears anywhere in the crate.
§References
Joldes, Muller & Popescu, “Tight and rigorous error bounds for basic building blocks of double-word arithmetic”, ACM TOMS 44(2) (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(1) (2022). Lefèvre, Louvet, Muller, Picot & Rideau, “Accurate calculation of Euclidean norms using double-word arithmetic”, ACM TOMS 49(1) (2023). Stloukal & Jézéquel, “Lord of the Precision, the Two Floats: double-word arithmetic for complex numbers”, arXiv:2611.08371 (2026). Hubrecht & Melquiond, “Verifying code that uses error-free transformations”, 33rd IEEE Symposium on Computer Arithmetic (ARITH 2026). Hida, Li & Bailey, “Algorithms for quad-double precision floating point arithmetic”, ARITH-15 (2001) — read, not copied.
Macros§
- assign 🔒
Structs§
- 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.
Functions§
- finish 🔒
- Step E: the exceptional results (the chapter).
gis thef64result of the operation on the leading components. - scale_
f64 🔒 x · 2ᵏfor anf64, by at most three multiplications by powers of two; exact unless the result is subnormal or overflows.- times_
fp1 🔒 - Algorithm M4 (DWTimesFP1), without step E: its caller, D2, ends in one.