Skip to main content

xingo_extprec/
dd.rs

1//! # Chapter 11.2 — Double-double arithmetic
2//!
3//! ## Purpose
4//! [`DoubleDouble`]: the field operations, the square root and the
5//! comparisons of numbers `x = x_h + x_ℓ` held as two `f64`. Each operation
6//! is a short, fixed sequence of `f64` operations built from the error-free
7//! transformations of Chapter 11.1, with a relative error bound that was
8//! *proven* in the literature; the bounds are data
9//! ([`DoubleDouble::ERROR_BOUNDS`]) and the tests check every operation
10//! against them in exact rational arithmetic.
11//!
12//! ## Notation
13//! As in Chapters 11 and 11.1: `RN`, `u = 2⁻⁵³`, `η = 2⁻¹⁰⁷⁴`. A pair `(h,
14//! ℓ)` is *normalized* when `h = RN(h + ℓ)`. `2Sum`, `Fast2Sum` and `2Prod`
15//! are Algorithms S, F and P of Chapter 11.1. "JMP" is Joldes, Muller &
16//! Popescu (2017), "MR" Muller & Rideau (2022), "LLMPR" Lefèvre, Louvet,
17//! Muller, Picot & Rideau (2023).
18//!
19//! ## Algorithms
20//! Inputs are normalized pairs `x = (x_h, x_ℓ)`, `y = (y_h, y_ℓ)` or an
21//! `f64` `y`; the output is the pair `(z_h, z_ℓ)`. Subtraction is addition
22//! of the (exact) negation.
23//!
24//! **Algorithm A1 (`dd + f64`; DWPlusFP, JMP Algorithm 4).**
25//!
26//! 1. `(s_h, s_ℓ) ← 2Sum(x_h, y)`.
27//! 2. `v ← RN(x_ℓ + s_ℓ)`.
28//! 3. `(z_h, z_ℓ) ← Fast2Sum(s_h, v)`.
29//!
30//! **Algorithm A2 (`dd + dd`; AccurateDWPlusDW, JMP Algorithm 6).**
31//!
32//! 1. `(s_h, s_ℓ) ← 2Sum(x_h, y_h)`; `(t_h, t_ℓ) ← 2Sum(x_ℓ, y_ℓ)`.
33//! 2. `c ← RN(s_ℓ + t_h)`; `(v_h, v_ℓ) ← Fast2Sum(s_h, c)`.
34//! 3. `w ← RN(t_ℓ + v_ℓ)`; `(z_h, z_ℓ) ← Fast2Sum(v_h, w)`.
35//!
36//! **Algorithm M1 (`dd · f64`; DWTimesFP3, JMP Algorithm 9).**
37//!
38//! 1. `(c_h, c_ℓ1) ← 2Prod(x_h, y)`.
39//! 2. `c_ℓ3 ← RN(c_ℓ1 + x_ℓ y)` (one FMA).
40//! 3. `(z_h, z_ℓ) ← Fast2Sum(c_h, c_ℓ3)`.
41//!
42//! **Algorithm M2 (`dd · dd`; DWTimesDW3, JMP Algorithm 12).**
43//!
44//! 1. `(c_h, c_ℓ1) ← 2Prod(x_h, y_h)`.
45//! 2. `t_ℓ0 ← RN(x_ℓ y_ℓ)`; `t_ℓ1 ← RN(x_h y_ℓ + t_ℓ0)`; `c_ℓ2 ← RN(t_ℓ1 +
46//!    x_ℓ y_h)` (two FMAs).
47//! 3. `c_ℓ3 ← RN(c_ℓ1 + c_ℓ2)`; `(z_h, z_ℓ) ← Fast2Sum(c_h, c_ℓ3)`.
48//!
49//! **Algorithm M3 (`dd²`; DWPow2).** The specialization of the two-FMA
50//! product (JMP Algorithm 11) to equal operands.
51//!
52//! 1. `(c_h, c_ℓ1) ← 2Prod(x_h, x_h)`.
53//! 2. `c ← RN(2 x_h x_ℓ + c_ℓ1)` (one FMA; `2 x_h` is exact).
54//! 3. `(z_h, z_ℓ) ← Fast2Sum(c_h, c)`.
55//!
56//! **Algorithm M4 (DWTimesFP1, JMP Algorithm 7).** Used inside D2 only.
57//!
58//! 1. `(c_h, c_ℓ1) ← 2Prod(x_h, y)`; `c_ℓ2 ← RN(x_ℓ y)`.
59//! 2. `(t_h, t_ℓ1) ← Fast2Sum(c_h, c_ℓ2)`; `t_ℓ2 ← RN(t_ℓ1 + c_ℓ1)`.
60//! 3. `(z_h, z_ℓ) ← Fast2Sum(t_h, t_ℓ2)`.
61//!
62//! **Algorithm D1 (`dd / f64`; DWDivFP3, JMP Algorithm 15).**
63//!
64//! 1. `t_h ← RN(x_h / y)`; `(π_h, π_ℓ) ← 2Prod(t_h, y)`.
65//! 2. `δ_h ← RN(x_h − π_h)`; `δ′ ← RN(δ_h − π_ℓ)`; `δ ← RN(δ′ + x_ℓ)`.
66//! 3. `t_ℓ ← RN(δ / y)`; `(z_h, z_ℓ) ← Fast2Sum(t_h, t_ℓ)`.
67//!
68//! **Algorithm D2 (`dd / dd`; DWDivDW2, JMP Algorithm 17).**
69//!
70//! 1. `t_h ← RN(x_h / y_h)`; `(r_h, r_ℓ) ← M4(y, t_h)`.
71//! 2. `π_h ← RN(x_h − r_h)`; `δ_ℓ ← RN(x_ℓ − r_ℓ)`; `δ ← RN(π_h + δ_ℓ)`.
72//! 3. `t_ℓ ← RN(δ / y_h)`; `(z_h, z_ℓ) ← Fast2Sum(t_h, t_ℓ)`.
73//!
74//! D2 keeps exact quotients exact: when `x / y` is an `f64` `q` (in
75//! particular `x/x = 1`, `(q y)/y = q`, and `(a b)/b = a` for `x` the
76//! exact product of two `f64`), `t_h` is `q` or a neighbour of it, the
77//! residual `x − y t_h` is formed without error and `t_ℓ` is exactly `q −
78//! t_h`. A division through a reciprocal (DWDivDW3, JMP Algorithm 18:
79//! bound `9,8u²`, 31 flops) does not have this property, which is why it
80//! is not used here (Chapter 11, "Why not DWDivDW3"). The property is
81//! tested, not proven, for the cases named.
82//!
83//! **Algorithm R (`√dd`; SQRTDWtoDW, LLMPR Algorithm 8).** For `x > 0`.
84//!
85//! 1. `s_h ← RN(√x_h)`.
86//! 2. `ρ₁ ← RN(x_h − s_h²)` (one FMA; exact); `ρ₂ ← RN(x_ℓ + ρ₁)`.
87//! 3. `s_ℓ ← RN(ρ₂ / (2 s_h))`; `(z_h, z_ℓ) ← Fast2Sum(s_h, s_ℓ)`.
88//!
89//! **Step E (exceptional results), the last step of every algorithm.** Let
90//! `g` be the plain `f64` result of the operation on the leading components
91//! (`x_h + y_h`, `x_h y_h`, `x_h / y_h`, `√x_h`). If `z_h` is finite,
92//! return `(z_h, z_ℓ)` — with `z_ℓ` replaced by `0` if it is not finite
93//! (possible only in `from_sum`, invariant T1). If `z_h` is NaN, or `g` is
94//! not finite, return `(g, 0)`: the IEEE result (`∞ − ∞` is NaN, `1/0 =
95//! ∞`, `x/∞ = 0`, …), or the plain `f64` result when an intermediate
96//! quantity overflowed although the result did not (operands within a
97//! factor of four of `Ω`). Otherwise (`z_h` infinite with `g` finite: the
98//! low-order terms carried the sum over `Ω`) return `(z_h, 0)`.
99//!
100//! ## Bounds, and where they hold
101//! Let **the safe range** be: finite operands that are zero or of magnitude
102//! in `[2⁻⁴⁸⁰, 2⁴⁸⁰]`. There no operation overflows and every `2Prod` is in
103//! its exact range (invariant T2: the products formed are near `x_h y_h`,
104//! `x_h` or `y_h t_h ≈ x_h`, all of magnitude at least `2⁻⁹⁶⁰`). In the
105//! safe range the relative error `|z − z*| / |z*|` of the result `z`
106//! against the exact `z*` is at most:
107//!
108//! | operation | algorithm | bound | source | flops |
109//! |---|---|---|---|---|
110//! | `dd + f64` | A1 | `2u²/(1 − 2u) < 2u² + 5u³` | JMP §3 (DWPlusFP) | 10 |
111//! | `dd + dd` | A2 | `3u²/(1 − 4u) < 3u² + 13u³` | JMP Thm 3.1 | 20 |
112//! | `dd · f64` | M1 | `2u²` | JMP (DWTimesFP3) | 6 |
113//! | `dd · dd` | M2 | `4u²` | MR (JMP proved `5u²`) | 9 |
114//! | `dd²` | M3 | `3u²` | Hubrecht & Melquiond 2026, §IV-B (binary64; see below) | 6 |
115//! | `dd / f64` | D1 | `3u²` | JMP (DWDivFP3) | 10 |
116//! | `dd / dd` | D2 | `15u² + 56u³` | JMP (DWDivDW2) | 18 |
117//! | `√dd` | R | `25/8 u²` | LLMPR Theorem 3.6 | 8 |
118//!
119//! **The square root's constant.** LLMPR, Theorem 3.6 (read in the author
120//! version, HAL hal-03482567v2; the proof is in their supplementary
121//! material and formalized in Coq): "if `x = (x_h, x_ℓ)` is a double-word
122//! number, `p ≥ 5`, `x ≥ 2^(2k)` where `k` is an integer larger than or
123//! equal to `(e_min + p)/2`, and no overflow or underflow occurs, then the
124//! relative error of Algorithm 8 is bounded by `(25/8) u²`, and that bound
125//! is asymptotically optimal". For binary64 the condition is `x ≥ 2⁻⁹⁶⁸`,
126//! which the safe range implies. A first-order analysis, written before
127//! the text could be read, reproduces the constant. Take `1 ≤ x_h < 2`
128//! (`ulp(x_h) = 2u`). Then `|s_h − √x_h| ≤ u`, `ρ₁` is exact with `|ρ₁| ≤
129//! 2u√x_h`, and `r = x − s_h² = x_ℓ + ρ₁` has `|r| ≤ (2√x_h + 1)u < 4u`.
130//! Three errors remain, relative to `√x`: rounding `ρ₂` (`≤ 2u²` absolute,
131//! `u²/x_h` after the division by `2 s_h`), rounding `s_ℓ` (`|s_ℓ| < 2u`,
132//! hence `≤ u²` absolute, `u²/√x_h`), and the truncation of the Newton
133//! step, `r² / (8 x_h²) ≤ (2√x_h + 1)² u² / (8 x_h²)`. Their sum is
134//! largest as `x_h → 1`: `1 + 1 + 9/8 = 25/8`. For `2 ≤ x_h < 4` the same
135//! count gives at most `2,44 u²`. The tests check `25/8` against exact
136//! arithmetic (largest error observed on 20 000 random operands: `2,69
137//! u²`).
138//!
139//! **The square's constant.** Hubrecht & Melquiond (2026, §IV-B) bound the
140//! relative error of exactly the code of M3 by `3u²`: a proof generated by
141//! the tool Gappa for binary64 with round-to-nearest-even and an
142//! *unbounded exponent range* (so it says nothing about underflow or
143//! overflow, which the safe range excludes), for an operand `x_h = RN(x)`,
144//! `x_ℓ = x − x_h`. Their statement is about `c_h + c` before the final
145//! Fast2Sum, which is error-free here (`|c| ≤ |c_h|`). It is not a theorem
146//! for a general precision. The tests check `3u²` against exact
147//! arithmetic (largest error observed: `2,86 u²`).
148//!
149//! The additions never leave the model of the proofs when subnormal
150//! numbers occur (invariant T1): their bounds hold on the whole finite
151//! range short of overflow, where an operand of magnitude `Ω` counts as
152//! overflow: an intermediate step of its 2Sum can overflow and step E then
153//! returns the rounded `f64` sum (measured: relative error `2⁵² u²`).
154//! Outside the safe range the other operations
155//! lose the bound — a `2Prod` that underflows contributes an absolute error
156//! of order `η` — but keep the invariants below.
157//!
158//! The sloppy addition of the QD library (11 flops) is not offered: its
159//! relative error is unbounded for operands of opposite signs (JMP §3).
160//!
161//! ## Invariants
162//! (D1) *Normalized.* Every finite value satisfies `h = RN(h + ℓ)` (hence
163//!      `|ℓ| ≤ ulp(h)/2`); `h = ±0` implies `ℓ = 0`.
164//! (D2) *Non-finite.* If `h` is infinite then `ℓ = 0`; the value is
165//!      "infinite" or "NaN" as `h` says, and the operations follow IEEE on
166//!      `h` (step E).
167//! (D3) *Order.* The derived lexicographic order on `(h, ℓ)` is the order
168//!      of the values `h + ℓ`, total on the non-NaN values.
169//! (D4) *Conversions.* `from_f64` is exact; `to_f64` is `h`, the `f64`
170//!      nearest to the value.
171//! (D5) *Determinism.* Every operation is the fixed sequence of `f64`
172//!      operations above, followed by step E: no data-dependent choice of
173//!      algorithm, no reassociation, the same bits on every platform.
174//!
175//! [`DoubleDouble::check_invariants`] tests (D1) and (D2);
176//! [`DoubleDouble::from_parts`] asserts them in debug builds.
177//!
178//! ## Comparisons
179//! This module compares `f64` values exactly (`==`, `<`): exactness is its
180//! subject, as tolerances are the subject of `xingo_core::Tolerances`. No
181//! tolerance appears anywhere in the crate.
182//!
183//! ## References
184//! Joldes, Muller & Popescu, "Tight and rigorous error bounds for basic
185//! building blocks of double-word arithmetic", ACM TOMS 44(2) (2017).
186//! Muller & Rideau, "Formalization of double-word arithmetic, and comments
187//! on 'Tight and rigorous error bounds for basic building blocks of
188//! double-word arithmetic'", ACM TOMS 48(1) (2022). Lefèvre, Louvet,
189//! Muller, Picot & Rideau, "Accurate calculation of Euclidean norms using
190//! double-word arithmetic", ACM TOMS 49(1) (2023). Stloukal & Jézéquel,
191//! "Lord of the Precision, the Two Floats: double-word arithmetic for
192//! complex numbers", arXiv:2611.08371 (2026). Hubrecht & Melquiond,
193//! "Verifying code that uses error-free transformations", 33rd IEEE
194//! Symposium on Computer Arithmetic (ARITH 2026). Hida, Li & Bailey,
195//! "Algorithms for quad-double precision floating point arithmetic",
196//! ARITH-15 (2001) — read, not copied.
197
198#![allow(clippy::float_cmp)] // exact comparisons are the subject (see "Comparisons")
199
200use core::iter::Sum;
201use core::ops::{Add, AddAssign, Div, DivAssign, Mul, MulAssign, Neg, Sub, SubAssign};
202
203use crate::eft::{fast_two_sum, two_prod, two_sum};
204
205/// A double-double number: the exact sum `hi + lo` of two `f64`, normalized
206/// (invariant D1). About 106 bits of significand (32 decimal digits), the
207/// exponent range of `f64`.
208///
209/// `#[repr(C)]` with `hi` first: a slice `&[DoubleDouble]` is an array of
210/// `(hi, lo)` pairs, the layout the SIMD kernels read.
211#[derive(Clone, Copy, Debug, Default, PartialEq, PartialOrd)]
212#[repr(C)]
213pub struct DoubleDouble {
214    hi: f64,
215    lo: f64,
216}
217
218/// The proven relative error bound of one operation of [`DoubleDouble`],
219/// as a multiple of `u² = 2⁻¹⁰⁶`: an `f64` that is **at least** the full
220/// proven expression of the chapter's table (rounded up where the
221/// expression has higher-order terms), so that `units_of_u2 · u²` is itself
222/// a rigorous bound.
223#[derive(Clone, Copy, Debug, PartialEq)]
224#[non_exhaustive]
225pub struct ErrorBound {
226    /// The operation, as written in the chapter's table (`"dd + dd"`, …).
227    pub operation: &'static str,
228    /// `c` in "relative error `≤ c u²`", with `c` at least the proven
229    /// expression (see [`DoubleDouble::ERROR_BOUNDS`]).
230    pub units_of_u2: f64,
231}
232
233/// Step E: the exceptional results (the chapter). `g` is the `f64` result
234/// of the operation on the leading components.
235#[inline]
236fn finish(zh: f64, zl: f64, g: f64) -> DoubleDouble {
237    if zh.is_finite() {
238        // `zl` is finite after a Fast2Sum; after a bare 2Sum it is not when
239        // an operand is ±Ω (invariant T1 of Chapter 11.1).
240        DoubleDouble {
241            hi: zh,
242            lo: if zl.is_finite() { zl } else { 0.0 },
243        }
244    } else if zh.is_nan() || !g.is_finite() {
245        DoubleDouble { hi: g, lo: 0.0 }
246    } else {
247        DoubleDouble { hi: zh, lo: 0.0 }
248    }
249}
250
251/// Algorithm M4 (DWTimesFP1), without step E: its caller, D2, ends in one.
252#[inline]
253fn times_fp1(x: DoubleDouble, y: f64) -> (f64, f64) {
254    let (ch, cl1) = two_prod(x.hi, y);
255    let cl2 = x.lo * y;
256    let (th, tl1) = fast_two_sum(ch, cl2);
257    let tl2 = tl1 + cl1;
258    fast_two_sum(th, tl2)
259}
260
261/// `x · 2ᵏ` for an `f64`, by at most three multiplications by powers of
262/// two; exact unless the result is subnormal or overflows.
263#[inline]
264fn scale_f64(mut x: f64, k: i32) -> f64 {
265    // 2^1000 and 2^-1000.
266    const UP: f64 = f64::from_bits((1023 + 1000) << 52);
267    const DOWN: f64 = f64::from_bits((1023 - 1000) << 52);
268    // Beyond ±2200 every nonzero finite value overflows or vanishes.
269    let mut k = k.clamp(-2200, 2200);
270    while k > 1000 {
271        x *= UP;
272        k -= 1000;
273    }
274    while k < -1000 {
275        x *= DOWN;
276        k += 1000;
277    }
278    let biased = u64::try_from(1023 + k).expect("|k| <= 1000");
279    x * f64::from_bits(biased << 52)
280}
281
282impl DoubleDouble {
283    /// Zero.
284    pub const ZERO: Self = Self { hi: 0.0, lo: 0.0 };
285    /// One.
286    pub const ONE: Self = Self { hi: 1.0, lo: 0.0 };
287    /// `2⁻¹⁰⁴`, the "machine epsilon" (`Real::EPSILON`).
288    pub const EPSILON: Self = Self {
289        hi: 4.930_380_657_631_324e-32,
290        lo: 0.0,
291    };
292    /// Positive infinity (invariant D2).
293    pub const INFINITY: Self = Self {
294        hi: f64::INFINITY,
295        lo: 0.0,
296    };
297    /// A NaN (invariant D2).
298    pub const NAN: Self = Self {
299        hi: f64::NAN,
300        lo: 0.0,
301    };
302    // The 19 stable constants of `core::f64::consts` (Chapter 11.11, L2.4):
303    // each is the nearest double-double `(RN(c), RN(c − RN(c)))`, relative
304    // error at most `u²(1 + u)`, checked bit for bit by the tests against two
305    // independent oracles.
306    /// `π`, the nearest double-double: `3.141592653589793e0 + 1.2246467991473532e-16`.
307    pub const PI: Self = Self {
308        hi: f64::from_bits(0x4009_21fb_5444_2d18),
309        lo: f64::from_bits(0x3ca1_a626_3314_5c07),
310    };
311    /// `2π`, the nearest double-double: `6.283185307179586e0 + 2.4492935982947064e-16`.
312    pub const TAU: Self = Self {
313        hi: f64::from_bits(0x4019_21fb_5444_2d18),
314        lo: f64::from_bits(0x3cb1_a626_3314_5c07),
315    };
316    /// `π/2`, the nearest double-double: `1.5707963267948966e0 + 6.123233995736766e-17`.
317    pub const FRAC_PI_2: Self = Self {
318        hi: f64::from_bits(0x3ff9_21fb_5444_2d18),
319        lo: f64::from_bits(0x3c91_a626_3314_5c07),
320    };
321    /// `π/3`, the nearest double-double: `1.0471975511965979e0 + -1.072081766451091e-16`.
322    pub const FRAC_PI_3: Self = Self {
323        hi: f64::from_bits(0x3ff0_c152_382d_7366),
324        lo: f64::from_bits(0xbc9e_e691_3347_c2a6),
325    };
326    /// `π/4`, the nearest double-double: `7.853981633974483e-1 + 3.061616997868383e-17`.
327    pub const FRAC_PI_4: Self = Self {
328        hi: f64::from_bits(0x3fe9_21fb_5444_2d18),
329        lo: f64::from_bits(0x3c81_a626_3314_5c07),
330    };
331    /// `π/6`, the nearest double-double: `5.235987755982989e-1 + -5.360408832255455e-17`.
332    pub const FRAC_PI_6: Self = Self {
333        hi: f64::from_bits(0x3fe0_c152_382d_7366),
334        lo: f64::from_bits(0xbc8e_e691_3347_c2a6),
335    };
336    /// `π/8`, the nearest double-double: `3.9269908169872414e-1 + 1.5308084989341915e-17`.
337    pub const FRAC_PI_8: Self = Self {
338        hi: f64::from_bits(0x3fd9_21fb_5444_2d18),
339        lo: f64::from_bits(0x3c71_a626_3314_5c07),
340    };
341    /// `1/π`, the nearest double-double: `3.183098861837907e-1 + -1.9678676675182486e-17`.
342    pub const FRAC_1_PI: Self = Self {
343        hi: f64::from_bits(0x3fd4_5f30_6dc9_c883),
344        lo: f64::from_bits(0xbc76_b01e_c541_7056),
345    };
346    /// `2/π`, the nearest double-double: `6.366197723675814e-1 + -3.935735335036497e-17`.
347    pub const FRAC_2_PI: Self = Self {
348        hi: f64::from_bits(0x3fe4_5f30_6dc9_c883),
349        lo: f64::from_bits(0xbc86_b01e_c541_7056),
350    };
351    /// `2/√π`, the nearest double-double: `1.1283791670955126e0 + 1.533545961316588e-17`.
352    pub const FRAC_2_SQRT_PI: Self = Self {
353        hi: f64::from_bits(0x3ff2_0dd7_5042_9b6d),
354        lo: f64::from_bits(0x3c71_ae3a_914f_ed80),
355    };
356    /// `√2`, the nearest double-double: `1.4142135623730951e0 + -9.667293313452913e-17`.
357    pub const SQRT_2: Self = Self {
358        hi: f64::from_bits(0x3ff6_a09e_667f_3bcd),
359        lo: f64::from_bits(0xbc9b_dd34_13b2_6456),
360    };
361    /// `1/√2`, the nearest double-double: `7.071067811865476e-1 + -4.833646656726457e-17`.
362    pub const FRAC_1_SQRT_2: Self = Self {
363        hi: f64::from_bits(0x3fe6_a09e_667f_3bcd),
364        lo: f64::from_bits(0xbc8b_dd34_13b2_6456),
365    };
366    /// `e`, the nearest double-double: `2.718281828459045e0 + 1.4456468917292502e-16`.
367    pub const E: Self = Self {
368        hi: f64::from_bits(0x4005_bf0a_8b14_5769),
369        lo: f64::from_bits(0x3ca4_d57e_e2b1_013a),
370    };
371    /// `log₂ e`, the nearest double-double: `1.4426950408889634e0 + 2.0355273740931033e-17`.
372    pub const LOG2_E: Self = Self {
373        hi: f64::from_bits(0x3ff7_1547_652b_82fe),
374        lo: f64::from_bits(0x3c77_77d0_ffda_0d24),
375    };
376    /// `log₂ 10`, the nearest double-double: `3.321928094887362e0 + 1.661617516973592e-16`.
377    pub const LOG2_10: Self = Self {
378        hi: f64::from_bits(0x400a_934f_0979_a371),
379        lo: f64::from_bits(0x3ca7_f249_5fb7_fa6d),
380    };
381    /// `log₁₀ e`, the nearest double-double: `4.342944819032518e-1 + 1.098319650216765e-17`.
382    pub const LOG10_E: Self = Self {
383        hi: f64::from_bits(0x3fdb_cb7b_1526_e50e),
384        lo: f64::from_bits(0x3c69_5355_baaa_fad3),
385    };
386    /// `log₁₀ 2`, the nearest double-double: `3.010299956639812e-1 + -2.8037281277851704e-18`.
387    pub const LOG10_2: Self = Self {
388        hi: f64::from_bits(0x3fd3_4413_509f_79ff),
389        lo: f64::from_bits(0xbc49_dc1d_a994_fd21),
390    };
391    /// `ln 2`, the nearest double-double: `6.931471805599453e-1 + 2.3190468138462996e-17`.
392    pub const LN_2: Self = Self {
393        hi: f64::from_bits(0x3fe6_2e42_fefa_39ef),
394        lo: f64::from_bits(0x3c7a_bc9e_3b39_803f),
395    };
396    /// `ln 10`, the nearest double-double: `2.302585092994046e0 + -2.1707562233822494e-16`.
397    pub const LN_10: Self = Self {
398        hi: f64::from_bits(0x4002_6bb1_bbb5_5516),
399        lo: f64::from_bits(0xbcaf_48ad_494e_a3e9),
400    };
401    /// The bounds of the chapter's table, for the tests and for callers
402    /// that propagate errors. The subtractions have the bounds of the
403    /// additions; `1 / dd` is `dd / dd`. Each `units_of_u2` is an `f64` at
404    /// least the proven expression, with `u = 2⁻⁵³`:
405    ///
406    /// | operation | proven bound | `units_of_u2` |
407    /// |---|---|---|
408    /// | `dd + f64` | `2u²/(1 − 2u)` | `2 + 2⁻⁵⁰` (the expression rounded up) |
409    /// | `dd + dd` | `3u²/(1 − 4u)` | `3 + 2⁻⁴⁹` (rounded up) |
410    /// | `dd · f64` | `2u²` | `2` (exact) |
411    /// | `dd · dd` | `4u²` | `4` (exact) |
412    /// | `dd²` | `3u²` | `3` (exact) |
413    /// | `dd / f64` | `3u²` | `3` (exact) |
414    /// | `dd / dd` | `15u² + 56u³` | `15 + 2⁻⁴⁷` (rounded up) |
415    /// | `√dd` | `(25/8) u²` | `3.125` (exact) |
416    ///
417    /// The test `error_bounds_dominate_the_proven_expressions` checks each
418    /// row in exact rational arithmetic.
419    pub const ERROR_BOUNDS: &'static [ErrorBound] = &[
420        ErrorBound {
421            operation: "dd + f64",
422            // 2/(1 − 2u) = 2 + 2⁻⁵¹ + …, rounded up: 2 + 2⁻⁵⁰.
423            units_of_u2: f64::from_bits(0x4000_0000_0000_0002),
424        },
425        ErrorBound {
426            operation: "dd + dd",
427            // 3/(1 − 4u) = 3 + 3·2⁻⁵¹ + …, rounded up: 3 + 2⁻⁴⁹.
428            units_of_u2: f64::from_bits(0x4008_0000_0000_0004),
429        },
430        ErrorBound {
431            operation: "dd · f64",
432            units_of_u2: 2.0,
433        },
434        ErrorBound {
435            operation: "dd · dd",
436            units_of_u2: 4.0,
437        },
438        ErrorBound {
439            operation: "dd²",
440            units_of_u2: 3.0,
441        },
442        ErrorBound {
443            operation: "dd / f64",
444            units_of_u2: 3.0,
445        },
446        ErrorBound {
447            operation: "dd / dd",
448            // 15 + 56u = 15 + 3.5·2⁻⁴⁹, rounded up: 15 + 2⁻⁴⁷.
449            units_of_u2: f64::from_bits(0x402e_0000_0000_0004),
450        },
451        ErrorBound {
452            operation: "√dd",
453            units_of_u2: 3.125,
454        },
455    ];
456
457    /// The value of an `f64`, exactly.
458    #[must_use]
459    pub const fn from_f64(x: f64) -> Self {
460        Self { hi: x, lo: 0.0 }
461    }
462
463    /// `a + b` exactly, for any two `f64` ([`two_sum`]).
464    #[inline]
465    #[must_use]
466    pub fn from_sum(a: f64, b: f64) -> Self {
467        let (s, e) = two_sum(a, b);
468        finish(s, e, s)
469    }
470
471    /// `a · b` exactly, for any two `f64` in the range of [`two_prod`]
472    /// (outside it: within `η/2`, and still normalized).
473    #[inline]
474    #[must_use]
475    pub fn from_product(a: f64, b: f64) -> Self {
476        let (p, e) = two_prod(a, b);
477        // A no-op in the exact range of `two_prod`; below it the rounded
478        // error term can be exactly half an ulp of `p` on the wrong side
479        // of the tie (invariant T3), and this exact sum renormalizes.
480        let (zh, zl) = fast_two_sum(p, e);
481        finish(zh, zl, p)
482    }
483
484    /// The pair `(hi, lo)` as given, **requires** it normalized (D1); a
485    /// `debug_assert!`. For deserialization and tests.
486    ///
487    /// The requirement is unchecked in release builds, and every bound of
488    /// this chapter assumes it: use [`DoubleDouble::from_sum`] for an
489    /// arbitrary pair.
490    #[inline]
491    #[must_use]
492    pub fn from_parts(hi: f64, lo: f64) -> Self {
493        let x = Self { hi, lo };
494        debug_assert!(
495            x.check_invariants().is_ok(),
496            "from_parts({hi:e}, {lo:e}): {:?}",
497            x.check_invariants()
498        );
499        x
500    }
501
502    /// The pair `(hi, lo)` as given, unchecked: for the SIMD kernels, which
503    /// store pairs computed by the algorithms of this chapter (Chapter
504    /// 11.6), and for the literal tables of Chapter 11.11.
505    #[inline]
506    pub(crate) const fn from_raw(hi: f64, lo: f64) -> Self {
507        Self { hi, lo }
508    }
509
510    /// The leading component: the `f64` nearest to the value (D4).
511    #[must_use]
512    pub const fn hi(self) -> f64 {
513        self.hi
514    }
515
516    /// The trailing component, `|lo| ≤ ulp(hi)/2`.
517    #[must_use]
518    pub const fn lo(self) -> f64 {
519        self.lo
520    }
521
522    /// The nearest `f64` (the leading component).
523    #[must_use]
524    pub const fn to_f64(self) -> f64 {
525        self.hi
526    }
527
528    /// `|x|`, exact.
529    #[inline]
530    #[must_use]
531    pub fn abs(self) -> Self {
532        if self.hi.is_sign_negative() {
533            -self
534        } else {
535            self
536        }
537    }
538
539    /// `√x`; NaN for negative `x`, `±0` for `±0`.
540    #[inline]
541    #[must_use]
542    pub fn sqrt(self) -> Self {
543        if self.hi == 0.0 {
544            return self;
545        }
546        // Algorithm R.
547        let sh = self.hi.sqrt();
548        let rho1 = (-sh).mul_add(sh, self.hi);
549        let rho2 = self.lo + rho1;
550        let sl = rho2 / (2.0 * sh);
551        let (zh, zl) = fast_two_sum(sh, sl);
552        finish(zh, zl, sh)
553    }
554
555    /// `1 / x`.
556    #[inline]
557    #[must_use]
558    pub fn recip(self) -> Self {
559        Self::ONE / self
560    }
561
562    /// `x²`, cheaper than `x · x` (one product fewer), same bound.
563    #[inline]
564    #[must_use]
565    pub fn square(self) -> Self {
566        // Algorithm M3.
567        let (ch, cl1) = two_prod(self.hi, self.hi);
568        let c = (2.0 * self.hi).mul_add(self.lo, cl1);
569        let (zh, zl) = fast_two_sum(ch, c);
570        finish(zh, zl, ch)
571    }
572
573    /// `x · 2ᵏ`, exact barring overflow and underflow.
574    #[inline]
575    #[must_use]
576    pub fn ldexp(self, k: i32) -> Self {
577        let h = scale_f64(self.hi, k);
578        let l = scale_f64(self.lo, k);
579        // Exact scalings keep the pair normalized; when a component became
580        // subnormal the sum is exact (T1) and renormalizes it.
581        let (zh, zl) = fast_two_sum(h, l);
582        finish(zh, zl, h)
583    }
584
585    /// Neither infinite nor NaN.
586    #[inline]
587    #[must_use]
588    pub fn is_finite(self) -> bool {
589        self.hi.is_finite()
590    }
591
592    /// NaN (D2).
593    #[inline]
594    #[must_use]
595    pub fn is_nan(self) -> bool {
596        self.hi.is_nan()
597    }
598
599    /// The larger value, with the NaN rule of `f64::max`.
600    #[inline]
601    #[must_use]
602    pub fn max(self, other: Self) -> Self {
603        if self.is_nan() || self < other {
604            other
605        } else {
606            self
607        }
608    }
609
610    /// The smaller value, with the NaN rule of `f64::min`.
611    #[inline]
612    #[must_use]
613    pub fn min(self, other: Self) -> Self {
614        if self.is_nan() || other < self {
615            other
616        } else {
617            self
618        }
619    }
620
621    /// Invariants (D1) and (D2).
622    ///
623    /// # Errors
624    /// The text of the violated invariant.
625    pub fn check_invariants(self) -> Result<(), &'static str> {
626        if self.hi.is_nan() {
627            return Ok(());
628        }
629        if self.hi.is_infinite() {
630            return if self.lo == 0.0 {
631                Ok(())
632            } else {
633                Err("D2: an infinite value has a nonzero trailing component")
634            };
635        }
636        if !self.lo.is_finite() {
637            return Err("D1: a finite value has a non-finite trailing component");
638        }
639        if self.hi == 0.0 && self.lo != 0.0 {
640            return Err("D1: a zero leading component with a nonzero trailing one");
641        }
642        if self.hi + self.lo != self.hi {
643            return Err("D1: the pair is not normalized, hi != fl(hi + lo)");
644        }
645        Ok(())
646    }
647}
648
649impl Add for DoubleDouble {
650    type Output = Self;
651    #[inline]
652    fn add(self, rhs: Self) -> Self {
653        // Algorithm A2.
654        let (sh, sl) = two_sum(self.hi, rhs.hi);
655        let (th, tl) = two_sum(self.lo, rhs.lo);
656        let c = sl + th;
657        let (vh, vl) = fast_two_sum(sh, c);
658        let w = tl + vl;
659        let (zh, zl) = fast_two_sum(vh, w);
660        finish(zh, zl, sh)
661    }
662}
663
664/// Mixed operation with an `f64` right operand: the cheaper algorithm of
665/// the chapter's table, not a promotion.
666impl Add<f64> for DoubleDouble {
667    type Output = Self;
668    #[inline]
669    fn add(self, rhs: f64) -> Self {
670        // Algorithm A1.
671        let (sh, sl) = two_sum(self.hi, rhs);
672        let v = self.lo + sl;
673        let (zh, zl) = fast_two_sum(sh, v);
674        finish(zh, zl, sh)
675    }
676}
677
678impl Sub for DoubleDouble {
679    type Output = Self;
680    #[inline]
681    fn sub(self, rhs: Self) -> Self {
682        self + (-rhs)
683    }
684}
685
686/// Mixed operation with an `f64` right operand: the cheaper algorithm of
687/// the chapter's table, not a promotion.
688impl Sub<f64> for DoubleDouble {
689    type Output = Self;
690    #[inline]
691    fn sub(self, rhs: f64) -> Self {
692        self + (-rhs)
693    }
694}
695
696impl Mul for DoubleDouble {
697    type Output = Self;
698    #[inline]
699    fn mul(self, rhs: Self) -> Self {
700        // Algorithm M2.
701        let (ch, cl1) = two_prod(self.hi, rhs.hi);
702        let tl0 = self.lo * rhs.lo;
703        let tl1 = self.hi.mul_add(rhs.lo, tl0);
704        let cl2 = self.lo.mul_add(rhs.hi, tl1);
705        let cl3 = cl1 + cl2;
706        let (zh, zl) = fast_two_sum(ch, cl3);
707        finish(zh, zl, ch)
708    }
709}
710
711/// Mixed operation with an `f64` right operand: the cheaper algorithm of
712/// the chapter's table, not a promotion.
713impl Mul<f64> for DoubleDouble {
714    type Output = Self;
715    #[inline]
716    fn mul(self, rhs: f64) -> Self {
717        // Algorithm M1.
718        let (ch, cl1) = two_prod(self.hi, rhs);
719        let cl3 = self.lo.mul_add(rhs, cl1);
720        let (zh, zl) = fast_two_sum(ch, cl3);
721        finish(zh, zl, ch)
722    }
723}
724
725impl Div for DoubleDouble {
726    type Output = Self;
727    #[inline]
728    fn div(self, rhs: Self) -> Self {
729        // Algorithm D2.
730        let th = self.hi / rhs.hi;
731        let (rh, rl) = times_fp1(rhs, th);
732        let pih = self.hi - rh;
733        let dl = self.lo - rl;
734        let d = pih + dl;
735        let tl = d / rhs.hi;
736        let (zh, zl) = fast_two_sum(th, tl);
737        finish(zh, zl, th)
738    }
739}
740
741/// Mixed operation with an `f64` right operand: the cheaper algorithm of
742/// the chapter's table, not a promotion.
743impl Div<f64> for DoubleDouble {
744    type Output = Self;
745    #[inline]
746    fn div(self, rhs: f64) -> Self {
747        // Algorithm D1.
748        let th = self.hi / rhs;
749        let (pih, pil) = two_prod(th, rhs);
750        let dh = self.hi - pih;
751        let dt = dh - pil;
752        let d = dt + self.lo;
753        let tl = d / rhs;
754        let (zh, zl) = fast_two_sum(th, tl);
755        finish(zh, zl, th)
756    }
757}
758
759macro_rules! assign {
760    ($tra:ident, $fa:ident, $op:tt) => {
761        impl $tra for DoubleDouble {
762            #[inline]
763            fn $fa(&mut self, rhs: Self) {
764                *self = *self $op rhs;
765            }
766        }
767    };
768}
769assign!(AddAssign, add_assign, +);
770assign!(SubAssign, sub_assign, -);
771assign!(MulAssign, mul_assign, *);
772assign!(DivAssign, div_assign, /);
773
774impl Neg for DoubleDouble {
775    type Output = Self;
776    #[inline]
777    fn neg(self) -> Self {
778        Self {
779            hi: -self.hi,
780            lo: -self.lo,
781        }
782    }
783}
784
785/// Left to right from [`DoubleDouble::ZERO`] (requirement R3 of `Real`).
786impl Sum for DoubleDouble {
787    fn sum<I: Iterator<Item = Self>>(iter: I) -> Self {
788        iter.fold(Self::ZERO, |acc, x| acc + x)
789    }
790}
791
792impl From<f64> for DoubleDouble {
793    fn from(x: f64) -> Self {
794        Self::from_f64(x)
795    }
796}
797
798/// `Real` for double-double (requirements R1 as reworded in E2, R2–R4 by
799/// invariants D3–D5): the containers and factorizations of `xingo-sparse`
800/// instantiate in `DoubleDouble` unchanged.
801#[cfg(feature = "sparse")]
802impl xingo_sparse::Real for DoubleDouble {
803    const ZERO: Self = Self::ZERO;
804    const ONE: Self = Self::ONE;
805    const EPSILON: Self = Self::EPSILON;
806    #[inline]
807    fn from_f64(x: f64) -> Self {
808        Self::from_f64(x)
809    }
810    #[inline]
811    fn to_f64(self) -> f64 {
812        self.hi
813    }
814    #[inline]
815    fn abs(self) -> Self {
816        Self::abs(self)
817    }
818    #[inline]
819    fn sqrt(self) -> Self {
820        Self::sqrt(self)
821    }
822    #[inline]
823    fn recip(self) -> Self {
824        Self::recip(self)
825    }
826    #[inline]
827    fn mul_add(self, a: Self, b: Self) -> Self {
828        self * a + b
829    }
830    #[inline]
831    fn is_finite(self) -> bool {
832        Self::is_finite(self)
833    }
834    #[inline]
835    fn max(self, other: Self) -> Self {
836        Self::max(self, other)
837    }
838    #[inline]
839    fn min(self, other: Self) -> Self {
840        Self::min(self, other)
841    }
842}
843
844#[cfg(test)]
845#[allow(clippy::disallowed_methods)] // L2.4 (Chapter 11.11): the tests may use the libm of `f64` (clippy.toml)
846mod tests {
847    use super::*;
848
849    const U: f64 = 1.110_223_024_625_156_5e-16; // 2^-53
850    type Dd = DoubleDouble;
851
852    fn dd(hi: f64, lo: f64) -> Dd {
853        Dd::from_parts(hi, lo)
854    }
855
856    #[test]
857    fn constants() {
858        assert_eq!(Dd::EPSILON.hi(), 2f64.powi(-104));
859        assert_eq!(Dd::ZERO + Dd::ONE, Dd::ONE);
860        assert!(Dd::NAN.is_nan() && !Dd::INFINITY.is_finite());
861        assert_eq!(Dd::default(), Dd::ZERO);
862        assert_eq!(Dd::ERROR_BOUNDS.len(), 8);
863    }
864
865    #[test]
866    fn textbook_cases() {
867        // 1 + 2^-80 is not an f64 but is a double-double.
868        let tiny = 2f64.powi(-80);
869        let x = Dd::ONE + tiny;
870        assert_eq!((x.hi(), x.lo()), (1.0, tiny));
871        assert_eq!(x - Dd::ONE, Dd::from_f64(tiny));
872        assert_eq!(x - 1.0, Dd::from_f64(tiny));
873        // (1 + 2^-30)(1 − 2^-30) = 1 − 2^-60 needs 61 bits.
874        let e = 2f64.powi(-30);
875        assert_eq!(
876            Dd::from_f64(1.0 + e) * Dd::from_f64(1.0 - e),
877            dd(1.0, -2f64.powi(-60))
878        );
879        assert_eq!(Dd::from_f64(1.0 + e) * (1.0 - e), dd(1.0, -2f64.powi(-60)));
880        // Exact small integers.
881        let six = Dd::from_f64(2.0) * Dd::from_f64(3.0);
882        assert_eq!(six, Dd::from_f64(6.0));
883        assert_eq!(six / 3.0, Dd::from_f64(2.0));
884        assert_eq!(six / Dd::from_f64(3.0), Dd::from_f64(2.0));
885        assert_eq!(Dd::from_f64(9.0).sqrt(), Dd::from_f64(3.0));
886        assert_eq!(Dd::from_f64(3.0).square(), Dd::from_f64(9.0));
887        assert_eq!(Dd::from_f64(4.0).recip(), Dd::from_f64(0.25));
888        // 1/3: the trailing component is the error of the f64 quotient.
889        let third = Dd::ONE / 3.0;
890        assert_eq!(third.hi(), 1.0 / 3.0);
891        assert_eq!(third.lo(), (1.0 / 3.0) * U / 2.0);
892        assert_eq!(Dd::ONE / Dd::from_f64(3.0), third);
893        // Exact quotients stay exact (the reason for Algorithm D2).
894        assert_eq!(Dd::from_f64(53.0) / Dd::from_f64(53.0), Dd::ONE);
895        assert_eq!(third / third, Dd::ONE);
896        // √2 squared is 2 to the last bit of 106.
897        let r = Dd::from_f64(2.0).sqrt();
898        let err = (r.square() - 2.0).abs();
899        assert!(err <= Dd::EPSILON * 8.0, "{err:?}");
900    }
901
902    #[test]
903    fn exact_constructors() {
904        assert_eq!(Dd::from_sum(1.0, U), dd(1.0, U));
905        let x = 1.0 + f64::EPSILON;
906        assert_eq!(
907            Dd::from_product(x, x),
908            dd(1.0 + 2.0 * f64::EPSILON, f64::EPSILON * f64::EPSILON)
909        );
910        assert_eq!(Dd::from(0.5), Dd::from_f64(0.5));
911        assert_eq!(Dd::from_f64(0.1).to_f64().to_bits(), 0.1_f64.to_bits());
912        assert!(Dd::from_sum(f64::MAX, f64::MAX).check_invariants().is_ok());
913        // The spurious overflow of 2Sum at Ω (invariant T1): the leading
914        // component survives.
915        let b = -3.0 * 2f64.powi(970);
916        assert!(!two_sum(f64::MAX, b).1.is_finite());
917        assert_eq!(Dd::from_sum(f64::MAX, b), Dd::from_f64(f64::MAX + b));
918        assert_eq!(Dd::from_f64(f64::MAX) + b, Dd::from_f64(f64::MAX + b));
919        assert_eq!(Dd::from_sum(f64::MAX, f64::MAX), Dd::INFINITY);
920        assert_eq!(Dd::from_product(f64::MAX, -2.0), -Dd::INFINITY);
921    }
922
923    #[test]
924    fn assignments_and_sum() {
925        let mut x = Dd::from_f64(1.5);
926        x += Dd::ONE;
927        x -= Dd::from_f64(0.5);
928        x *= Dd::from_f64(4.0);
929        x /= Dd::from_f64(2.0);
930        assert_eq!(x, Dd::from_f64(4.0));
931        let tiny = 2f64.powi(-70);
932        let s: Dd = [1.0, tiny, -1.0].into_iter().map(Dd::from_f64).sum();
933        assert_eq!(s, Dd::from_f64(tiny));
934        assert_eq!(core::iter::empty::<Dd>().sum::<Dd>(), Dd::ZERO);
935    }
936
937    #[test]
938    fn order_abs_max_min() {
939        let tiny = 2f64.powi(-80);
940        let a = Dd::ONE - tiny;
941        let b = Dd::ONE;
942        let c = Dd::ONE + tiny;
943        assert!(a < b && b < c && a < c);
944        assert!(c > a);
945        assert_eq!((-c).abs(), c);
946        assert_eq!(Dd::from_f64(-0.0).abs().hi().to_bits(), 0.0_f64.to_bits());
947        assert_eq!(a.max(c), c);
948        assert_eq!(a.min(c), a);
949        assert_eq!(Dd::NAN.max(a), a);
950        assert_eq!(a.max(Dd::NAN), a);
951        assert_eq!(Dd::NAN.min(a), a);
952        assert_eq!(a.min(Dd::NAN), a);
953        assert!(Dd::NAN.partial_cmp(&a).is_none());
954        assert!(-Dd::INFINITY < a && a < Dd::INFINITY);
955    }
956
957    #[test]
958    fn non_finite_values_follow_ieee() {
959        let inf = Dd::INFINITY;
960        let one = Dd::ONE;
961        assert_eq!(inf + one, inf);
962        assert_eq!(inf + 1.0, inf);
963        assert_eq!(one - inf, -inf);
964        assert!((inf - inf).is_nan());
965        assert_eq!(inf * one, inf);
966        assert_eq!(inf * -2.0, -inf);
967        assert!((inf * Dd::ZERO).is_nan());
968        assert_eq!(one / Dd::ZERO, inf);
969        assert_eq!(-one / 0.0, -inf);
970        assert!((Dd::ZERO / Dd::ZERO).is_nan());
971        assert_eq!(one / inf, Dd::ZERO);
972        assert_eq!(one / f64::INFINITY, Dd::ZERO);
973        assert!((inf / inf).is_nan());
974        assert_eq!(inf.sqrt(), inf);
975        assert!((-one).sqrt().is_nan());
976        assert_eq!(inf.square(), inf);
977        assert_eq!(Dd::ZERO.recip(), inf);
978        assert!((Dd::NAN + one).is_nan() && (one * Dd::NAN).is_nan());
979        assert!((Dd::NAN / one).is_nan() && Dd::NAN.sqrt().is_nan());
980        // Overflow gives a well-formed infinity.
981        let big = Dd::from_f64(f64::MAX);
982        for z in [
983            big + big,
984            big * big,
985            big / Dd::from_f64(1e-300),
986            big.square(),
987        ] {
988            assert_eq!(z, inf);
989            assert!(z.check_invariants().is_ok());
990        }
991        assert_eq!(inf.ldexp(-5), inf);
992        assert_eq!(big.ldexp(1), inf);
993    }
994
995    #[test]
996    fn signed_zero_square_roots() {
997        assert_eq!(Dd::ZERO.sqrt().hi().to_bits(), 0.0_f64.to_bits());
998        assert_eq!(
999            Dd::from_f64(-0.0).sqrt().hi().to_bits(),
1000            (-0.0_f64).to_bits()
1001        );
1002    }
1003
1004    #[test]
1005    fn ldexp_is_exact() {
1006        let x = Dd::ONE / 3.0;
1007        let y = x.ldexp(700);
1008        assert_eq!(
1009            (y.hi(), y.lo()),
1010            (x.hi() * 2f64.powi(700), x.lo() * 2f64.powi(700))
1011        );
1012        assert_eq!(y.ldexp(-700), x);
1013        assert_eq!(x.ldexp(1500).ldexp(-1500), Dd::INFINITY);
1014        assert_eq!(x.ldexp(-900).ldexp(900), x);
1015        assert_eq!(x.ldexp(i32::MIN), Dd::ZERO);
1016        assert_eq!(x.ldexp(i32::MAX), Dd::INFINITY);
1017        assert_eq!(Dd::ZERO.ldexp(i32::MAX), Dd::ZERO);
1018        // Into the subnormal range the pair stays normalized.
1019        assert!(x.ldexp(-1060).check_invariants().is_ok());
1020    }
1021
1022    #[test]
1023    fn check_invariants_rejects_bad_pairs() {
1024        let bad = |hi, lo| Dd { hi, lo }.check_invariants().is_err();
1025        assert!(bad(1.0, 1.0)); // not normalized
1026        assert!(bad(1.0, f64::EPSILON)); // lo = ulp(hi): hi + lo != hi
1027        assert!(bad(0.0, 1e-300));
1028        assert!(bad(f64::INFINITY, 1.0));
1029        assert!(bad(1.0, f64::NAN));
1030        assert!(Dd { hi: 1.0, lo: U }.check_invariants().is_ok()); // the tie
1031        assert!(
1032            Dd {
1033                hi: f64::NAN,
1034                lo: 3.0
1035            }
1036            .check_invariants()
1037            .is_ok()
1038        );
1039    }
1040
1041    #[test]
1042    #[cfg(debug_assertions)]
1043    #[should_panic(expected = "from_parts")]
1044    fn from_parts_asserts_normalization() {
1045        let _ = Dd::from_parts(1.0, 1.0);
1046    }
1047
1048    #[cfg(feature = "sparse")]
1049    #[test]
1050    fn real_is_implemented() {
1051        use xingo_sparse::Real;
1052        fn third<T: Real>() -> T {
1053            T::ONE / T::from_f64(3.0)
1054        }
1055        let t = third::<Dd>();
1056        assert_eq!(t, Dd::ONE / 3.0);
1057        assert_eq!(Real::to_f64(t).to_bits(), (1.0_f64 / 3.0).to_bits());
1058        assert_eq!(<Dd as Real>::EPSILON, Dd::EPSILON);
1059        assert_eq!(
1060            Real::mul_add(t, Dd::from_f64(3.0), Dd::ONE),
1061            t * Dd::from_f64(3.0) + Dd::ONE
1062        );
1063        assert_eq!(Real::abs(-t), t);
1064        assert_eq!(Real::recip(Dd::from_f64(8.0)), Dd::from_f64(0.125));
1065        assert_eq!(Real::sqrt(Dd::from_f64(16.0)), Dd::from_f64(4.0));
1066        assert!(Real::is_finite(t) && !Real::is_finite(Dd::INFINITY));
1067        assert_eq!(Real::max(t, Dd::ONE), Dd::ONE);
1068        assert_eq!(Real::min(t, Dd::ONE), t);
1069    }
1070}