Skip to main content

Module dd

Module dd 

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

  1. (s_h, s_ℓ) ← 2Sum(x_h, y).
  2. v ← RN(x_ℓ + s_ℓ).
  3. (z_h, z_ℓ) ← Fast2Sum(s_h, v).

Algorithm A2 (dd + dd; AccurateDWPlusDW, JMP Algorithm 6).

  1. (s_h, s_ℓ) ← 2Sum(x_h, y_h); (t_h, t_ℓ) ← 2Sum(x_ℓ, y_ℓ).
  2. c ← RN(s_ℓ + t_h); (v_h, v_ℓ) ← Fast2Sum(s_h, c).
  3. w ← RN(t_ℓ + v_ℓ); (z_h, z_ℓ) ← Fast2Sum(v_h, w).

Algorithm M1 (dd · f64; DWTimesFP3, JMP Algorithm 9).

  1. (c_h, c_ℓ1) ← 2Prod(x_h, y).
  2. c_ℓ3 ← RN(c_ℓ1 + x_ℓ y) (one FMA).
  3. (z_h, z_ℓ) ← Fast2Sum(c_h, c_ℓ3).

Algorithm M2 (dd · dd; DWTimesDW3, JMP Algorithm 12).

  1. (c_h, c_ℓ1) ← 2Prod(x_h, y_h).
  2. t_ℓ0 ← RN(x_ℓ y_ℓ); t_ℓ1 ← RN(x_h y_ℓ + t_ℓ0); c_ℓ2 ← RN(t_ℓ1 + x_ℓ y_h) (two FMAs).
  3. 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.

  1. (c_h, c_ℓ1) ← 2Prod(x_h, x_h).
  2. c ← RN(2 x_h x_ℓ + c_ℓ1) (one FMA; 2 x_h is exact).
  3. (z_h, z_ℓ) ← Fast2Sum(c_h, c).

Algorithm M4 (DWTimesFP1, JMP Algorithm 7). Used inside D2 only.

  1. (c_h, c_ℓ1) ← 2Prod(x_h, y); c_ℓ2 ← RN(x_ℓ y).
  2. (t_h, t_ℓ1) ← Fast2Sum(c_h, c_ℓ2); t_ℓ2 ← RN(t_ℓ1 + c_ℓ1).
  3. (z_h, z_ℓ) ← Fast2Sum(t_h, t_ℓ2).

Algorithm D1 (dd / f64; DWDivFP3, JMP Algorithm 15).

  1. t_h ← RN(x_h / y); (π_h, π_ℓ) ← 2Prod(t_h, y).
  2. δ_h ← RN(x_h − π_h); δ′ ← RN(δ_h − π_ℓ); δ ← RN(δ′ + x_ℓ).
  3. t_ℓ ← RN(δ / y); (z_h, z_ℓ) ← Fast2Sum(t_h, t_ℓ).

Algorithm D2 (dd / dd; DWDivDW2, JMP Algorithm 17).

  1. t_h ← RN(x_h / y_h); (r_h, r_ℓ) ← M4(y, t_h).
  2. π_h ← RN(x_h − r_h); δ_ℓ ← RN(x_ℓ − r_ℓ); δ ← RN(π_h + δ_ℓ).
  3. 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.

  1. s_h ← RN(√x_h).
  2. ρ₁ ← RN(x_h − s_h²) (one FMA; exact); ρ₂ ← RN(x_ℓ + ρ₁).
  3. 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:

operationalgorithmboundsourceflops
dd + f64A12u²/(1 − 2u) < 2u² + 5u³JMP §3 (DWPlusFP)10
dd + ddA23u²/(1 − 4u) < 3u² + 13u³JMP Thm 3.120
dd · f64M12u²JMP (DWTimesFP3)6
dd · ddM24u²MR (JMP proved 5u²)9
dd²M33u²Hubrecht & Melquiond 2026, §IV-B (binary64; see below)6
dd / f64D13u²JMP (DWDivFP3)10
dd / ddD215u² + 56u³JMP (DWDivDW2)18
√ddR25/8 u²LLMPR Theorem 3.68

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§

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.

Functions§

finish 🔒
Step E: the exceptional results (the chapter). g is the f64 result of the operation on the leading components.
scale_f64 🔒
x · 2ᵏ for an f64, 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.