Skip to main content

xingo_extprec/
kernels.rs

1//! # Chapter 11.5 — Slice kernels: definitions, scalar reference, dispatch
2//!
3//! ## Purpose
4//! The inner loops of extended-precision linear algebra: compensated sums
5//! and dot products of `f64` data that return a double-double (Ogita, Rump
6//! & Oishi 2005), one of them with a *rigorous* error bound, and the
7//! double-double `dot`, `axpy` and small-block `gemm`. This chapter fixes,
8//! operation by operation, what each kernel computes, and holds the
9//! **scalar reference** implementation of that definition (the private
10//! module `reference`). The SIMD versions (Chapter 11.6, feature `simd`)
11//! return the same bits (invariant K1), so the order of accumulation is
12//! part of each definition, not an implementation detail. The public
13//! functions of this module choose between the two at run time
14//! (Algorithm X below).
15//!
16//! ## Notation
17//! `u = 2⁻⁵³`, `η = 2⁻¹⁰⁷⁴`, `γ_k = k u / (1 − k u)`. `2Sum` and `2Prod`
18//! are the error-free transformations of Chapter 11.1, `⊕ ⊖ ⊗` the
19//! double-double operations of Chapter 11.2 (Algorithms A2, M2, M1). `W =
20//! 4` is the number of accumulators — *lanes* — on every target: the width
21//! of AVX2; narrower targets emulate it, wider ones use it, so that there
22//! is one answer everywhere. Element `i` belongs to lane `i mod W`.
23//!
24//! ## Algorithms
25//! **Algorithm C (compensated accumulation: `sum2`, `dot2`, `dot2_err`).**
26//! Input `x ∈ Fⁿ` (and `y ∈ Fⁿ`). Output a double-double `r` (and `β`).
27//!
28//! C1. \[Lanes.\] `p_k ← 0`, `s_k ← 0`, `e_k ← 0` for `k = 0, …, W − 1`.
29//! C2. \[Accumulate.\] For `i = 0, …, n − 1`, with `k = i mod W`: form the
30//!     term — `sum2`: `(p_k, q) ← 2Sum(p_k, x_i)`, `t ← q`; `dot2` and
31//!     `dot2_err`: `(h, r) ← 2Prod(x_i, y_i)`, `(p_k, q) ← 2Sum(p_k, h)`,
32//!     `t ← RN(q + r)` — then `s_k ← RN(s_k + t)` and, for `dot2_err`,
33//!     `e_k ← RN(e_k + |t|)`.
34//! C3. \[Combine.\] `p ← p_0`, `s ← s_0`, `e ← e_0`. For `k = 1, …, W − 1`:
35//!     `(p, q) ← 2Sum(p, p_k)`; `s ← RN(s + RN(s_k + q))`; `e ← RN(e +
36//!     RN(e_k + |q|))`.
37//! C4. \[Result.\] `(r_h, r_ℓ) ← 2Sum(p, s)`, then step E of Chapter 11.2:
38//!     `r ← (r_h, r_ℓ)`, with `r_ℓ` replaced by `0` if it is not finite.
39//! C5. \[Bound, `dot2_err` only.\] If `n = 0`, `β ← 0`. If `2(n + 3)u ≥ 1`,
40//!     or `p`, `s`, `e`, `r` or the error term `r_ℓ` of the 2Sum of C4
41//!     *before* step E is not finite, `β ← +∞`. Otherwise, in `f64`
42//!     arithmetic, `δ ← (n + 3)u / (1 − 2(n + 3)u)` and `β ← ((δ e + 3η/u)
43//!     (1 + 8u))`.
44//!
45//! **Algorithm B (double-double BLAS: `dot`, `dot_mixed`, `axpy`,
46//! `gemm_sub`).**
47//!
48//! B1. \[`dot`, `dot_mixed`.\] `a_k ← 0`; for `i = 0, …, n − 1`: `a_k ← a_k
49//!     ⊕ (x_i ⊗ y_i)` with `k = i mod W`; return `((a_0 ⊕ a_1) ⊕ a_2) ⊕
50//!     a_3`. In `dot_mixed`, `y_i` is an `f64` and `⊗` is Algorithm M1.
51//! B2. \[`axpy`.\] `y_i ← y_i ⊕ (α ⊗ x_i)` for each `i` (no accumulation).
52//! B3. \[`gemm_sub`.\] For `j = 0, …, n − 1`, for `l = 0, …, k − 1`, for `i
53//!     = 0, …, m − 1`: `c_ij ← c_ij ⊖ (a_il ⊗ b_lj)`. Each `c_ij` receives
54//!     its `k` updates in increasing `l`; the loop over `i` — the *column
55//!     update* `c ← c ⊖ a ⊗ t` of one column of `C` by one column of `A`
56//!     and one scalar `t = b_lj` — is the one a SIMD version vectorizes.
57//!     The entries of `C` do not interact, so the loops over `j`, `l` and
58//!     `i` may be blocked for the cache in any way that keeps `l`
59//!     increasing for each `(i, j)`: the kernels run in blocks of
60//!     `BLOCK_ROWS` rows and `BLOCK_K` columns of `A`, the scheme of
61//!     `xingo_sparse::NaiveDense` (Chapter 5.16).
62//!
63//! B4. \[`dot4`, the step D of Algorithm W of Chapter 5.16 of
64//!     `xingo-sparse`; crate-private, for the solves of Chapter 11.7.\]
65//!     `a_k ← 0`; for the first `4⌊n/4⌋` elements `a_k ← a_k ⊕ (x_i ⊗
66//!     y_i)` with `k = i mod W`; `t ← 0` and `t ← t ⊕ (x_i ⊗ y_i)` for the
67//!     rest, in order; return `((a_0 ⊕ a_1) ⊕ (a_2 ⊕ a_3)) ⊕ t`. It differs
68//!     from B1 in the tail (one more accumulator instead of the lanes) and
69//!     in the combination (pairwise), the order of the generic solve of
70//!     `xingo-sparse`, whose bits it must return.
71//!
72//! **Algorithm X (dispatch).** For a call of a kernel `κ`:
73//!
74//! X1. \[Feature.\] Without the feature `simd`, run the reference `κ`.
75//! X2. \[Detect.\] On `aarch64`, if NEON is available (it always is), run
76//!     the SIMD `κ` of Chapter 11.6 with two-lane vectors; on `x86` and
77//!     `x86_64`, if AVX2 and FMA are available, run it with four-lane
78//!     vectors. The detection is `pulp`'s (cached after the first call).
79//! X3. \[Fallback.\] Otherwise run the reference `κ`.
80//!
81//! [`backend`] reports the choice of X1–X3. AVX-512 is deliberately not a
82//! backend: `W = 4` is the width of AVX2, and a wider accumulator would be
83//! a different kernel (another order of accumulation).
84//!
85//! ## Bounds
86//! Sum2 and Dot2 are analysed by Ogita, Rump & Oishi for the sequential
87//! order; their argument uses the order only through "a floating-point sum
88//! of `m` terms, in any order, errs by at most `γ_{m−1} Σ|terms|`" (their
89//! (2.4)) and so carries over to Algorithm C, with `n + 3` in place of `n`
90//! (the three `2Sum` of step C3 add three error terms). Barring overflow:
91//!
92//! * `sum2`: `|r − Σx_i| ≤ γ²_{n+3} Σ|x_i|` (their Proposition 4.5 has
93//!   `γ²_{n−1}` for the sequential order, plus `u|Σx_i|` for rounding the
94//!   result to one `f64`, which C4 does not do);
95//! * `dot2`: `|r − xᵀy| ≤ γ²_{n+5} |x|ᵀ|y| + n η/2` (their Proposition 5.5:
96//!   `γ²_n`, and `5nη` for the Dekker product in place of the FMA).
97//!
98//! **Proof of step C5.** Barring overflow, and with every `2Prod` exact,
99//! `xᵀy = p + Σ_i (q_i + r_i) + Σ_c q_c` exactly, where the `q_c` are the
100//! three errors of step C3. `s` is a floating-point sum, in some order, of
101//! the `N = n + 3` terms `t_i = RN(q_i + r_i)` and `q_c`, so with `E =
102//! Σ|t_i| + Σ|q_c|`:
103//! `|xᵀy − p − s| ≤ u Σ|t_i| + γ_{N−1} E ≤ γ_{n+3} E`. And `e` is a
104//! floating-point sum of the same `N` nonnegative magnitudes, so `E ≤ (1 +
105//! u)^{n+2} e`. Hence `|xᵀy − p − s| ≤ (n + 3)u / (1 − (2n + 5)u) · e`. A
106//! `2Prod` out of its exact range adds at most `η/2` (invariant T2 of
107//! Chapter 11.1): `n η/2` in all. Step C5 evaluates an upper bound of that
108//! in round-to-nearest: `δ` is computed from exact operands by one division
109//! (`δ ≥ (1 − u)` times the exact coefficient above, whose denominator is
110//! the larger `1 − (2n + 5)u`), the product `δ e` errs by at most a factor
111//! `(1 − u)` and `η/2`, the two remaining operations by `(1 − u)` each (the
112//! term `3η/u = 3 · 2⁻¹⁰²¹` keeps them out of the subnormal range), and `(1
113//! + 8u)(1 − u)⁴ ≥ 1`, `3η/u − η/2 ≥ n η/2 + η/2`.
114//!
115//! *Overflow.* The argument needs every operation exact or rounded as
116//! stated, and that is lost only by an overflow — of a sum, of a product,
117//! or of an *intermediate* step of a 2Sum whose first operand is `±Ω`
118//! (invariant T1 of Chapter 11.1: then the error term is `±∞` or NaN, and
119//! conversely a 2Sum whose error term is finite had no step overflow and
120//! is exact). In steps C2 and C3 every such value flows into `p`, `s` or
121//! `e` through additions and absolute values, none of which maps a
122//! non-finite value back to a finite one, and C5 tests the three. The one
123//! exception is step C4: its error term `r_ℓ` goes *only* into `r`, and step
124//! E replaces it by `0` — a non-finite value made finite — so `r` can be
125//! finite and wrong by up to `ulp(Ω)/2 = 2⁹⁷⁰` (`p = Ω − 2⁹⁷¹`, `s = −2⁹⁷⁰ −
126//! …`, found by review X0.3i). C5 therefore tests `r_ℓ` itself, before step
127//! E; with it finite the 2Sum is exact and `r = p + s`. (Until X0.3i C5
128//! tested only `r`, and (K2) was false in that corner.) This is Algorithm 5.8 and
129//! Corollary 5.9 of Ogita, Rump & Oishi adapted to the lanes, to the FMA
130//! product and to a double-double result (their bound has one more term,
131//! `u|res|`, for the final rounding to `f64`).
132//!
133//! The kernels of Algorithm B inherit the bounds of `⊕` and `⊗`: each
134//! term errs by at most `4u²` relative, each accumulation by `3u² + 13u³`.
135//!
136//! ## Invariants
137//! (K1) *One answer.* Every kernel is the fixed sequence of `f64`
138//!      operations above for a given `n`; the SIMD implementation returns
139//!      the same bits for **every** input — finite or not, normalized or
140//!      not — with one reservation: where a result is a NaN, both are NaN,
141//!      and the sign and payload of that NaN are not specified (Rust does
142//!      not specify them for `f64` arithmetic either). Chapter 11.6 has the
143//!      argument; the tests of this module compare the two implementations
144//!      bit for bit on random and on exceptional data. [`backend`] names
145//!      the implementation in use.
146//! (K2) *Rigour.* `dot2_err` returns `(r, β)` with `|xᵀy − r| ≤ β` for
147//!      every input; `β = +∞` when a hypothesis fails (invariant C3 of
148//!      Chapter 11), the overflow of an intermediate step of the 2Sum of C4
149//!      included (the proof of C5, "Overflow"). Checked against exact
150//!      rationals, near `Ω` too.
151//!
152//! ## References
153//! Ogita, Rump & Oishi, "Accurate sum and dot product", SIAM J. Sci.
154//! Comput. 26 (2005): Algorithm 4.4 (Sum2) and Proposition 4.5, Algorithm
155//! 5.3 (Dot2) and Proposition 5.5, Algorithm 5.8 (Dot2Err) and Corollary
156//! 5.9. Higham, *Accuracy and Stability of Numerical Algorithms* (2002),
157//! §4.2 (the order-independent bound). Chapter 5.16 of `xingo-sparse`
158//! (the blocked loop order of `gemm_sub`).
159
160use crate::dd::DoubleDouble;
161use crate::eft::two_sum;
162
163/// `W`, the number of lanes (the chapter).
164pub(crate) const LANES: usize = 4;
165
166/// Rows of `C` and `A` handled per block of step B3 (a cache-blocking
167/// size, not a numerical threshold; not tuned): `BLOCK_ROWS × BLOCK_K`
168/// double-doubles of `A` — 128 KiB — stay in cache while the columns of `C`
169/// pass over them.
170pub(crate) const BLOCK_ROWS: usize = 128;
171/// Columns of `A` (the summation index `l`) per block; see [`BLOCK_ROWS`].
172pub(crate) const BLOCK_K: usize = 64;
173
174/// `2⁻⁵³`.
175const U: f64 = 0.5 * f64::EPSILON;
176
177/// The state of Algorithm C: the lanes `p_k`, `s_k`, `e_k`.
178#[derive(Clone, Copy, Default)]
179pub(crate) struct Compensated {
180    pub(crate) p: [f64; LANES],
181    pub(crate) s: [f64; LANES],
182    pub(crate) e: [f64; LANES],
183}
184
185impl Compensated {
186    /// Step C2 for the term `h + r` (`r = 0` for a sum) of element `i`.
187    #[inline]
188    pub(crate) fn push(&mut self, i: usize, h: f64, r: f64) {
189        let k = i % LANES;
190        let (p, q) = two_sum(self.p[k], h);
191        let t = q + r;
192        self.p[k] = p;
193        self.s[k] += t;
194        self.e[k] += t.abs();
195    }
196
197    /// Step C3: `(p, s, e)`.
198    #[inline]
199    pub(crate) fn combine(&self) -> (f64, f64, f64) {
200        let (mut p, mut s, mut e) = (self.p[0], self.s[0], self.e[0]);
201        for k in 1..LANES {
202            let (pn, q) = two_sum(p, self.p[k]);
203            p = pn;
204            s += self.s[k] + q;
205            e += self.e[k] + q.abs();
206        }
207        (p, s, e)
208    }
209
210    /// Steps C3 and C4: the result `r`.
211    #[inline]
212    pub(crate) fn result(&self) -> DoubleDouble {
213        let (p, s, _) = self.combine();
214        DoubleDouble::from_sum(p, s)
215    }
216
217    /// Steps C3–C5 for `n` elements: the result `r` and the bound `β`.
218    #[inline]
219    pub(crate) fn result_with_bound(&self, n: usize) -> (DoubleDouble, f64) {
220        /// `3η/u = 3 · 2⁻¹⁰²¹`.
221        const UNDERFLOW: f64 = 6.0 * f64::MIN_POSITIVE;
222        /// `1 + 8u`.
223        const INFLATE: f64 = 1.0 + 4.0 * f64::EPSILON;
224        /// `2(n + 3)u < 1` iff `n + 3 < 2⁵²`.
225        const MAX_TERMS: u64 = 1 << 52;
226
227        let (p, s, e) = self.combine();
228        // C4; step E of `from_sum` hides a non-finite error term, which
229        // C5 must see (the proof of C5, "Overflow").
230        let (_, r_lo) = two_sum(p, s);
231        let r = DoubleDouble::from_sum(p, s);
232        // C5.
233        if n == 0 {
234            return (r, 0.0);
235        }
236        let terms = u64::try_from(n).map_or(u64::MAX, |n| n.saturating_add(3));
237        let finite =
238            p.is_finite() && s.is_finite() && e.is_finite() && r.is_finite() && r_lo.is_finite();
239        if terms >= MAX_TERMS || !finite {
240            return (r, f64::INFINITY);
241        }
242        #[allow(clippy::cast_precision_loss)] // exact: terms < 2^52
243        let a = terms as f64 * U;
244        let delta = a / (1.0 - 2.0 * a);
245        (r, (delta * e + UNDERFLOW) * INFLATE)
246    }
247}
248
249/// The column update of step B3, `c_i ← c_i ⊖ (a_i ⊗ t)` for every `i`:
250/// the one loop that the kernels of Algorithm B built on `gemm` vectorize
251/// (and the dense kernels of Chapter 11.7 with them). Implemented by the
252/// scalar [`reference::Reference`] and by the vectors of Chapter 11.6.
253pub(crate) trait ColumnUpdate: Copy {
254    /// `c ← c ⊖ a ⊗ t`; `c` and `a` have the same length.
255    fn column_sub(self, c: &mut [DoubleDouble], a: &[DoubleDouble], t: DoubleDouble);
256}
257
258/// Step B3 with the blocks of the chapter: `c_ij ← c_ij ⊖ Σ_l a_il ⊗
259/// t(j, l)` for the `m × k` block `a` and the `m × n` block `c`
260/// (column-major), `l` increasing for each entry.
261#[inline(always)] // into `pulp`'s `vectorize` (Chapter 11.6)
262#[allow(clippy::inline_always)]
263pub(crate) fn gemm_blocked<U: ColumnUpdate>(
264    update: U,
265    m: usize,
266    k: usize,
267    a: &[DoubleDouble],
268    c: &mut [DoubleDouble],
269    t: impl Fn(usize, usize) -> DoubleDouble,
270) {
271    debug_assert_eq!(a.len(), m * k, "gemm_blocked: A is not m × k");
272    debug_assert!(m == 0 || c.len().is_multiple_of(m), "gemm_blocked: C");
273    if m == 0 {
274        return;
275    }
276    let mut i0 = 0;
277    while i0 < m {
278        let i1 = (i0 + BLOCK_ROWS).min(m);
279        let mut l0 = 0;
280        while l0 < k {
281            let l1 = (l0 + BLOCK_K).min(k);
282            for (j, cj) in c.chunks_exact_mut(m).enumerate() {
283                let cj = &mut cj[i0..i1];
284                for l in l0..l1 {
285                    update.column_sub(cj, &a[l * m + i0..l * m + i1], t(j, l));
286                }
287            }
288            l0 = l1;
289        }
290        i0 = i1;
291    }
292}
293
294/// The scalar reference kernels: Algorithms C and B of the chapter, one
295/// `f64` operation at a time. They are the definition of the kernels, the
296/// oracle of the SIMD versions (invariant K1) and the fallback of the
297/// dispatch (Algorithm X).
298pub(crate) mod reference {
299    use super::{ColumnUpdate, Compensated, LANES, gemm_blocked};
300    use crate::dd::DoubleDouble;
301    use crate::eft::two_prod;
302
303    /// The scalar column update (step B3).
304    #[derive(Clone, Copy, Debug)]
305    pub(crate) struct Reference;
306
307    impl ColumnUpdate for Reference {
308        #[inline]
309        fn column_sub(self, c: &mut [DoubleDouble], a: &[DoubleDouble], t: DoubleDouble) {
310            debug_assert_eq!(c.len(), a.len(), "column_sub: the lengths differ");
311            for (ci, &ai) in c.iter_mut().zip(a) {
312                *ci -= ai * t;
313            }
314        }
315    }
316
317    /// Steps C1–C2 of `sum2`.
318    pub(crate) fn sum2(x: &[f64]) -> Compensated {
319        let mut acc = Compensated::default();
320        for (i, &xi) in x.iter().enumerate() {
321            acc.push(i, xi, 0.0);
322        }
323        acc
324    }
325
326    /// Steps C1–C2 of `dot2` and `dot2_err`.
327    pub(crate) fn dot2(x: &[f64], y: &[f64]) -> Compensated {
328        let mut acc = Compensated::default();
329        for (i, (&xi, &yi)) in x.iter().zip(y).enumerate() {
330            let (h, r) = two_prod(xi, yi);
331            acc.push(i, h, r);
332        }
333        acc
334    }
335
336    /// Step B1, double-double `y`.
337    pub(crate) fn dot(x: &[DoubleDouble], y: &[DoubleDouble]) -> DoubleDouble {
338        let mut acc = [DoubleDouble::ZERO; LANES];
339        for (i, (&xi, &yi)) in x.iter().zip(y).enumerate() {
340            acc[i % LANES] += xi * yi;
341        }
342        ((acc[0] + acc[1]) + acc[2]) + acc[3]
343    }
344
345    /// Step B4.
346    #[cfg_attr(not(feature = "sparse"), allow(dead_code))]
347    pub(crate) fn dot4(x: &[DoubleDouble], y: &[DoubleDouble]) -> DoubleDouble {
348        let mut acc = [DoubleDouble::ZERO; LANES];
349        let (cx, tx) = x.as_chunks::<LANES>();
350        let (cy, ty) = y.as_chunks::<LANES>();
351        for (p, q) in cx.iter().zip(cy) {
352            for k in 0..LANES {
353                acc[k] += p[k] * q[k];
354            }
355        }
356        let mut t = DoubleDouble::ZERO;
357        for (&p, &q) in tx.iter().zip(ty) {
358            t += p * q;
359        }
360        (acc[0] + acc[1]) + (acc[2] + acc[3]) + t
361    }
362
363    /// Step B1, `f64` `y`.
364    pub(crate) fn dot_mixed(x: &[DoubleDouble], y: &[f64]) -> DoubleDouble {
365        let mut acc = [DoubleDouble::ZERO; LANES];
366        for (i, (&xi, &yi)) in x.iter().zip(y).enumerate() {
367            acc[i % LANES] += xi * yi;
368        }
369        ((acc[0] + acc[1]) + acc[2]) + acc[3]
370    }
371
372    /// Step B2.
373    pub(crate) fn axpy(alpha: DoubleDouble, x: &[DoubleDouble], y: &mut [DoubleDouble]) {
374        for (yi, &xi) in y.iter_mut().zip(x) {
375            *yi += alpha * xi;
376        }
377    }
378
379    /// Step B3 (`b` is `k × n`, column-major).
380    pub(crate) fn gemm_sub(
381        m: usize,
382        k: usize,
383        a: &[DoubleDouble],
384        b: &[DoubleDouble],
385        c: &mut [DoubleDouble],
386    ) {
387        gemm_blocked(Reference, m, k, a, c, |j, l| b[l + j * k]);
388    }
389}
390
391/// Algorithm X, steps X1–X2: if a SIMD backend is compiled in and available,
392/// **returns from the enclosing function** with the value of `$simd`, an
393/// expression in which `$lanes` is the backend's four-lane arithmetic
394/// (`crate::simd::Lanes`), evaluated inside `pulp`'s `vectorize` (which
395/// enables the target features for the code inlined into it). Otherwise
396/// falls through to step X3, written after the macro call.
397macro_rules! dispatch {
398    (|$lanes:ident| $simd:expr) => {
399        #[cfg(all(feature = "simd", target_arch = "aarch64"))]
400        if let Some(token) = pulp::aarch64::Neon::try_new() {
401            let $lanes = $crate::simd::X2::new(token);
402            return pulp::Simd::vectorize(
403                token,
404                #[inline(always)]
405                || $simd,
406            );
407        }
408        #[cfg(all(feature = "simd", any(target_arch = "x86", target_arch = "x86_64")))]
409        if let Some(token) = pulp::x86::V3::try_new() {
410            let $lanes = $crate::simd::X4::new(token);
411            return pulp::Simd::vectorize(
412                token,
413                #[inline(always)]
414                || $simd,
415            );
416        }
417    };
418}
419// Chapter 11.7 dispatches its loops with the same macro.
420#[cfg(feature = "sparse")]
421pub(crate) use dispatch;
422
423/// `Σ xᵢ` of `f64` values as a double-double, as accurate as if summed
424/// in twice the working precision (Sum2 of Ogita, Rump & Oishi, over `W =
425/// 4` lanes: Algorithm C of Chapter 11.5): `|result − Σxᵢ| ≤ γ²_{n+3}
426/// Σ|xᵢ|` barring overflow. Overflow includes an intermediate step of a
427/// 2Sum whose first operand is `±Ω` (invariant T1 of Chapter 11.1): there
428/// the result may be finite with a relative error of order `u`.
429#[must_use]
430pub fn sum2(x: &[f64]) -> DoubleDouble {
431    dispatch!(|lanes| crate::simd::sum2(lanes, x).result());
432    reference::sum2(x).result()
433}
434
435/// `xᵀy` of `f64` vectors as a double-double (Dot2, over `W = 4` lanes:
436/// Algorithm C of Chapter 11.5): `|result − xᵀy| ≤ γ²_{n+5} |x|ᵀ|y| + n
437/// η/2` barring overflow. Overflow includes an intermediate step of a 2Sum
438/// whose first operand is `±Ω` (invariant T1 of Chapter 11.1): there the
439/// result may be finite with a relative error of order `u`; [`dot2_err`]
440/// reports that case with `β = +∞`. Panics if the lengths differ.
441#[must_use]
442pub fn dot2(x: &[f64], y: &[f64]) -> DoubleDouble {
443    assert_eq!(x.len(), y.len(), "dot2: the lengths differ");
444    dispatch!(|lanes| crate::simd::dot2::<_, false>(lanes, x, y).result());
445    reference::dot2(x, y).result()
446}
447
448/// As [`dot2`], with a rigorous bound: returns `(r, β)` with `|xᵀy −
449/// r| ≤ β` (Dot2Err; step C5 of Chapter 11.5 and its proof). `β = +∞`
450/// when a hypothesis fails (overflow — of an intermediate step of a 2Sum at
451/// `±Ω` too —, NaN, `2(n + 3)u ≥ 1`): invariant C3.
452/// Panics if the lengths differ.
453#[must_use]
454pub fn dot2_err(x: &[f64], y: &[f64]) -> (DoubleDouble, f64) {
455    assert_eq!(x.len(), y.len(), "dot2_err: the lengths differ");
456    dispatch!(|lanes| crate::simd::dot2::<_, true>(lanes, x, y).result_with_bound(x.len()));
457    reference::dot2(x, y).result_with_bound(x.len())
458}
459
460/// `xᵀy` of double-double vectors, over `W = 4` lanes combined left to
461/// right (step B1 of Chapter 11.5). Panics if the lengths differ.
462#[must_use]
463pub fn dot(x: &[DoubleDouble], y: &[DoubleDouble]) -> DoubleDouble {
464    assert_eq!(x.len(), y.len(), "dot: the lengths differ");
465    dispatch!(|lanes| crate::simd::dot(lanes, x, y));
466    reference::dot(x, y)
467}
468
469/// `xᵀy` with `x` double-double and `y` `f64` (a row of an `f64`
470/// matrix against an extended vector: the residual of a polished
471/// solution); the order of [`dot`]. Panics if the lengths differ.
472#[must_use]
473pub fn dot_mixed(x: &[DoubleDouble], y: &[f64]) -> DoubleDouble {
474    assert_eq!(x.len(), y.len(), "dot_mixed: the lengths differ");
475    dispatch!(|lanes| crate::simd::dot_mixed(lanes, x, y));
476    reference::dot_mixed(x, y)
477}
478
479/// `y ← y + α x`, element by element (step B2 of Chapter 11.5). Panics if
480/// the lengths differ.
481pub fn axpy(alpha: DoubleDouble, x: &[DoubleDouble], y: &mut [DoubleDouble]) {
482    assert_eq!(x.len(), y.len(), "axpy: the lengths differ");
483    dispatch!(|lanes| crate::simd::axpy(lanes, alpha, x, y));
484    reference::axpy(alpha, x, y);
485}
486
487/// `C ← C − A B` for small column-major blocks (`A` is `m × k`, `B` is
488/// `k × n`, `C` is `m × n`); the update of a supernodal block. Each entry
489/// of `C` receives its `k` updates in increasing column of `A` (step B3 of
490/// Chapter 11.5). Panics if a slice has the wrong length.
491pub fn gemm_sub(
492    m: usize,
493    k: usize,
494    n: usize,
495    a: &[DoubleDouble],
496    b: &[DoubleDouble],
497    c: &mut [DoubleDouble],
498) {
499    assert_eq!(a.len(), m * k, "gemm_sub: A is not m × k");
500    assert_eq!(b.len(), k * n, "gemm_sub: B is not k × n");
501    assert_eq!(c.len(), m * n, "gemm_sub: C is not m × n");
502    dispatch!(|lanes| gemm_blocked(lanes, m, k, a, c, |j, l| b[l + j * k]));
503    reference::gemm_sub(m, k, a, b, c);
504}
505
506/// The name of the implementation the dispatch selected (`"scalar"`,
507/// `"avx2"`, `"neon"`), for benchmarks and bug reports: Algorithm X of
508/// Chapter 11.5. `"scalar"` without the feature `simd`, or when the CPU
509/// has neither NEON nor AVX2 with FMA. (`"avx512"`, which the contract
510/// listed, is never returned: the chapter says why.)
511#[must_use]
512pub fn backend() -> &'static str {
513    #[cfg(all(feature = "simd", target_arch = "aarch64"))]
514    if pulp::aarch64::Neon::try_new().is_some() {
515        return "neon";
516    }
517    #[cfg(all(feature = "simd", any(target_arch = "x86", target_arch = "x86_64")))]
518    if pulp::x86::V3::try_new().is_some() {
519        return "avx2";
520    }
521    "scalar"
522}
523
524#[cfg(test)]
525#[allow(clippy::disallowed_methods)] // L2.4 (Chapter 11.11): the tests may use the libm of `f64` (clippy.toml)
526#[allow(clippy::float_cmp)] // the tests compare exact values
527mod tests {
528    use super::*;
529
530    type Dd = DoubleDouble;
531
532    #[test]
533    fn empty_inputs() {
534        assert_eq!(sum2(&[]), Dd::ZERO);
535        assert_eq!(dot2(&[], &[]), Dd::ZERO);
536        assert_eq!(dot2_err(&[], &[]), (Dd::ZERO, 0.0));
537        assert_eq!(dot(&[], &[]), Dd::ZERO);
538        assert_eq!(dot_mixed(&[], &[]), Dd::ZERO);
539        axpy(Dd::ONE, &[], &mut []);
540        gemm_sub(0, 0, 0, &[], &[], &mut []);
541        gemm_sub(0, 2, 3, &[], &[Dd::ONE; 6], &mut []);
542    }
543
544    /// Algorithm X: what `backend` must say on this build and this CPU.
545    #[test]
546    fn backend_names_the_dispatch() {
547        #[cfg(not(feature = "simd"))]
548        let expected = "scalar";
549        // NEON is part of the baseline of every aarch64 target of Rust.
550        #[cfg(all(feature = "simd", target_arch = "aarch64"))]
551        let expected = "neon";
552        #[cfg(all(feature = "simd", any(target_arch = "x86", target_arch = "x86_64")))]
553        let expected = if std::arch::is_x86_feature_detected!("avx2")
554            && std::arch::is_x86_feature_detected!("fma")
555        {
556            "avx2"
557        } else {
558            "scalar"
559        };
560        #[cfg(all(
561            feature = "simd",
562            not(any(target_arch = "aarch64", target_arch = "x86", target_arch = "x86_64"))
563        ))]
564        let expected = "scalar";
565        assert_eq!(backend(), expected);
566    }
567
568    /// The minimal case of review X0.3i (M1): in lane 0, the terms of 17
569    /// leave `p = Ω − 2⁹⁷¹` and `s = −2⁹⁷⁰ − …`, the 2Sum of step C4 rounds
570    /// `p + s` to `p` and its error term overflows (invariant T1 of Chapter
571    /// 11.1). Before the correction of C5, `β` was finite (`≈ 6.6e277`) and
572    /// `|xᵀy − r| = 2⁹⁷⁰`; now `β = +∞`, on both paths, and `r` keeps its
573    /// bits.
574    #[test]
575    fn dot2_err_refuses_when_the_two_sum_of_c4_overflows() {
576        use dashu_ratio::RBig;
577        let lane0 = [
578            0x7fef_ffff_ffff_fffe_u64,
579            0x7c90_0000_0000_0001,
580            0xfc8f_ffff_ffff_fffe,
581            0xfc8f_ffff_ffff_fffc,
582            0xf970_0000_0000_0000,
583        ];
584        let mut x = [0.0; 17];
585        for (k, bits) in lane0.iter().enumerate() {
586            x[4 * k] = f64::from_bits(*bits);
587        }
588        let y = [1.0; 17];
589        let exact = x.iter().fold(RBig::from(0), |acc, &v| {
590            acc + RBig::try_from(v).expect("finite")
591        });
592        let reference = reference::dot2(&x, &y).result_with_bound(17);
593        let dispatched = dot2_err(&x, &y);
594        for (r, beta) in [reference, dispatched] {
595            assert_eq!((r.hi().to_bits(), r.lo()), (0x7fef_ffff_ffff_fffe, 0.0));
596            let err = RBig::try_from(r.hi()).expect("finite") - exact.clone();
597            let err = if err < RBig::from(0) { -err } else { err };
598            assert!(err > RBig::from(0));
599            assert!(
600                beta == f64::INFINITY || err <= RBig::try_from(beta).expect("finite"),
601                "K2 fails: |xᵀy − r| = {:e} > β = {beta:e}",
602                err.to_f64().value()
603            );
604            assert_eq!(beta, f64::INFINITY);
605        }
606        // `r` is that of `dot2` (step C4 is shared).
607        assert_eq!(dot2(&x, &y), dispatched.0);
608    }
609
610    /// (K1) near `Ω`, where the 2Sums of steps C2–C4 overflow in their
611    /// intermediate steps: scalar and SIMD return the same bits (`β` of
612    /// `dot2_err` included), on every length 1 to 64.
613    #[test]
614    fn k1_near_omega() {
615        let mut state = 0x2545_f491_4f6c_dd1d_u64;
616        let mut next = move || {
617            state ^= state << 13;
618            state ^= state >> 7;
619            state ^= state << 17;
620            state
621        };
622        for n in 1..=64 {
623            for _ in 0..50 {
624                let x: Vec<f64> = (0..n)
625                    .map(|_| {
626                        let sign = if next() & 1 == 0 { 1.0 } else { -1.0 };
627                        let j = f64::from(u8::try_from(next() % 4).expect("small"));
628                        sign * match next() % 4 {
629                            0 => f64::from_bits(f64::MAX.to_bits() - next() % 4),
630                            1 => 2f64.powi(970) + j * 2f64.powi(918),
631                            2 => 2f64.powi(970) - j * 2f64.powi(918),
632                            _ => 0.0,
633                        }
634                    })
635                    .collect();
636                let y = vec![1.0; n];
637                assert!(
638                    same_dd(sum2(&x), reference::sum2(&x).result()),
639                    "sum2 {x:?}"
640                );
641                assert!(
642                    same_dd(dot2(&x, &y), reference::dot2(&x, &y).result()),
643                    "dot2 {x:?}"
644                );
645                let (r, beta) = dot2_err(&x, &y);
646                let (r0, beta0) = reference::dot2(&x, &y).result_with_bound(n);
647                assert!(same_dd(r, r0) && same(beta, beta0), "dot2_err {x:?}");
648            }
649        }
650    }
651
652    #[test]
653    fn sum2_survives_cancellation() {
654        // The plain f64 sum loses the small terms.
655        let x = [1e100, 1.0, -1e100, 2.0];
656        assert_eq!(x.iter().sum::<f64>(), 2.0);
657        assert_eq!(sum2(&x), Dd::from_f64(3.0));
658        let tiny = 2f64.powi(-60);
659        assert_eq!(sum2(&[1.0, tiny, -1.0]), Dd::from_f64(tiny));
660        // The result is the unrounded pair (p, s) of step C4.
661        assert_eq!(sum2(&[1.0, tiny]), Dd::from_parts(1.0, tiny));
662        // More terms than lanes.
663        let y: Vec<f64> = (1..=10).map(f64::from).collect();
664        assert_eq!(sum2(&y), Dd::from_f64(55.0));
665    }
666
667    #[test]
668    fn dot2_survives_cancellation() {
669        let big = 2f64.powi(60);
670        let x = [big, 1.0 + f64::EPSILON, -big];
671        let y = [big, 1.0 + f64::EPSILON, big];
672        assert_eq!(x.iter().zip(&y).map(|(a, b)| a * b).sum::<f64>(), 0.0);
673        // "As if in twice the working precision": the leading component is
674        // right, the error is within the bound of Dot2Err.
675        let exact = Dd::from_product(x[1], y[1]);
676        let r = dot2(&x, &y);
677        assert_eq!(r.hi(), exact.hi());
678        let (r_err, beta) = dot2_err(&x, &y);
679        assert_eq!(r_err, r);
680        assert!(beta.is_finite() && beta < 1e-10, "{beta:e}");
681        assert!((r - exact).abs().hi() <= beta);
682    }
683
684    #[test]
685    fn dot2_err_reports_failed_hypotheses() {
686        let (r, beta) = dot2_err(&[1e200, 1.0], &[1e200, 1.0]);
687        assert!(r.check_invariants().is_ok());
688        assert_eq!(beta, f64::INFINITY);
689        let (r, beta) = dot2_err(&[f64::NAN], &[1.0]);
690        assert!(r.is_nan());
691        assert_eq!(beta, f64::INFINITY);
692        // Exact data still have a positive bound: the underflow term.
693        let (r, beta) = dot2_err(&[1.0, 2.0], &[3.0, 4.0]);
694        assert_eq!(r, Dd::from_f64(11.0));
695        assert!(beta > 0.0 && beta < 1e-300);
696    }
697
698    #[test]
699    fn dd_kernels_follow_their_definitions() {
700        let x: Vec<Dd> = (1..=7).map(|i| Dd::ONE / f64::from(i)).collect();
701        let y: Vec<Dd> = (1..=7).map(|i| Dd::from_f64(f64::from(i)).sqrt()).collect();
702        let yf: Vec<f64> = y.iter().map(|v| v.hi()).collect();
703        // B1: lanes 0..4, then left to right.
704        let lanes = |term: &dyn Fn(usize) -> Dd| {
705            let mut a = [Dd::ZERO; 4];
706            for i in 0..7 {
707                a[i % 4] += term(i);
708            }
709            ((a[0] + a[1]) + a[2]) + a[3]
710        };
711        assert_eq!(reference::dot(&x, &y), lanes(&|i| x[i] * y[i]));
712        assert_eq!(dot(&x, &y), lanes(&|i| x[i] * y[i]));
713        assert_eq!(dot_mixed(&x, &yf), lanes(&|i| x[i] * yf[i]));
714        // B4: lanes over the first four, a fifth accumulator, pairwise.
715        let mut a = [Dd::ZERO; 4];
716        for i in 0..4 {
717            a[i] += x[i] * y[i];
718        }
719        let mut t = Dd::ZERO;
720        for i in 4..7 {
721            t += x[i] * y[i];
722        }
723        assert_eq!(reference::dot4(&x, &y), ((a[0] + a[1]) + (a[2] + a[3])) + t);
724        // B2.
725        let alpha = Dd::ONE / 7.0;
726        let mut z = y.clone();
727        axpy(alpha, &x, &mut z);
728        for i in 0..7 {
729            assert_eq!(z[i], y[i] + alpha * x[i]);
730        }
731        // B3 on a 2 × 3 times 3 × 2 product.
732        let a = &x[..6];
733        let b = &y[..6];
734        let mut c = vec![Dd::ONE; 4];
735        gemm_sub(2, 3, 2, a, b, &mut c);
736        for j in 0..2 {
737            for i in 0..2 {
738                let mut want = Dd::ONE;
739                for l in 0..3 {
740                    want -= a[i + 2 * l] * b[l + 3 * j];
741                }
742                assert_eq!(c[i + 2 * j], want);
743            }
744        }
745    }
746
747    #[test]
748    #[should_panic(expected = "the lengths differ")]
749    fn length_mismatch_panics() {
750        let _ = dot2(&[1.0], &[]);
751    }
752
753    // ---- Invariant (K1): the dispatched kernels against the reference ----
754
755    /// A deterministic generator (xorshift64*), so that every length is
756    /// tried with the same data on every run.
757    struct Rng(u64);
758
759    impl Rng {
760        fn next(&mut self) -> u64 {
761            self.0 ^= self.0 >> 12;
762            self.0 ^= self.0 << 25;
763            self.0 ^= self.0 >> 27;
764            self.0.wrapping_mul(0x2545_f491_4f6c_dd1d)
765        }
766
767        /// A random significand and sign with an exponent in `±span`.
768        fn scaled(&mut self, span: i32) -> f64 {
769            #[allow(clippy::cast_precision_loss)] // 53 random bits
770            let m = 1.0 + (self.next() >> 11) as f64 / (1_u64 << 53) as f64;
771            let e = i32::try_from(self.next() % (2 * u64::from(span.unsigned_abs()) + 1))
772                .expect("small")
773                - span;
774            let v = m * 2f64.powi(e);
775            if self.next() & 1 == 0 { v } else { -v }
776        }
777
778        fn special(&mut self) -> f64 {
779            const SPECIAL: [f64; 10] = [
780                0.0,
781                -0.0,
782                f64::INFINITY,
783                f64::NEG_INFINITY,
784                f64::NAN,
785                f64::MAX,
786                f64::MIN,
787                f64::MIN_POSITIVE,
788                5e-324,
789                -2.5e-310,
790            ];
791            SPECIAL[usize::try_from(self.next() % 10).expect("small")]
792        }
793
794        /// One `f64` of the given kind of data: 0 moderate (the declared
795        /// domain), 1 wide exponents (products overflow and underflow), 2
796        /// any bit pattern, 3 moderate with exceptional values mixed in.
797        fn f64(&mut self, kind: u8) -> f64 {
798            match kind {
799                0 => self.scaled(30),
800                1 => self.scaled(600),
801                2 => {
802                    if self.next().is_multiple_of(8) {
803                        self.special()
804                    } else {
805                        f64::from_bits(self.next())
806                    }
807                }
808                _ => {
809                    if self.next().is_multiple_of(16) {
810                        self.special()
811                    } else {
812                        self.scaled(30)
813                    }
814                }
815            }
816        }
817
818        /// A valid double-double (invariants D1, D2) of the given kind.
819        fn dd(&mut self, kind: u8) -> Dd {
820            let h = self.f64(kind);
821            let l = self.f64(0) * h * 2f64.powi(-84);
822            Dd::from_sum(h, l)
823        }
824
825        fn f64s(&mut self, kind: u8, n: usize) -> Vec<f64> {
826            (0..n).map(|_| self.f64(kind)).collect()
827        }
828
829        fn dds(&mut self, kind: u8, n: usize) -> Vec<Dd> {
830            (0..n).map(|_| self.dd(kind)).collect()
831        }
832    }
833
834    /// The same bits, or a NaN on both sides (invariant K1).
835    fn same(a: f64, b: f64) -> bool {
836        a.to_bits() == b.to_bits() || (a.is_nan() && b.is_nan())
837    }
838
839    fn same_dd(a: Dd, b: Dd) -> bool {
840        same(a.hi(), b.hi()) && same(a.lo(), b.lo())
841    }
842
843    fn same_dds(a: &[Dd], b: &[Dd]) -> bool {
844        a.len() == b.len() && a.iter().zip(b).all(|(&p, &q)| same_dd(p, q))
845    }
846
847    /// Step B4 through the dispatch (the solves of Chapter 11.7 call it
848    /// inside their own).
849    fn dot4(x: &[Dd], y: &[Dd]) -> Dd {
850        dispatch!(|lanes| crate::simd::dot4(lanes, x, y));
851        reference::dot4(x, y)
852    }
853
854    /// (K1) for the seven vector kernels on one data set; the name of the
855    /// first kernel that differs.
856    fn k1_vectors(kind: u8, n: usize, seed: u64) -> Result<(), String> {
857        let mut rng = Rng(seed | 1);
858        let (x, y) = (rng.f64s(kind, n), rng.f64s(kind, n));
859        let (p, q) = (rng.dds(kind, n), rng.dds(kind, n));
860        let alpha = rng.dd(kind);
861        let fail = |what: &str| Err(format!("{what}: kind {kind}, n = {n}, seed {seed}"));
862
863        if !same_dd(sum2(&x), reference::sum2(&x).result()) {
864            return fail("sum2");
865        }
866        if !same_dd(dot2(&x, &y), reference::dot2(&x, &y).result()) {
867            return fail("dot2");
868        }
869        let (r, beta) = dot2_err(&x, &y);
870        let (r0, beta0) = reference::dot2(&x, &y).result_with_bound(n);
871        if !same_dd(r, r0) || !same(beta, beta0) {
872            return fail("dot2_err");
873        }
874        if !same_dd(dot(&p, &q), reference::dot(&p, &q)) {
875            return fail("dot");
876        }
877        if !same_dd(dot_mixed(&p, &x), reference::dot_mixed(&p, &x)) {
878            return fail("dot_mixed");
879        }
880        if !same_dd(dot4(&p, &q), reference::dot4(&p, &q)) {
881            return fail("dot4");
882        }
883        let (mut z, mut z0) = (q.clone(), q.clone());
884        axpy(alpha, &p, &mut z);
885        reference::axpy(alpha, &p, &mut z0);
886        if !same_dds(&z, &z0) {
887            return fail("axpy");
888        }
889        for v in &z {
890            v.check_invariants()
891                .map_err(|e| format!("axpy: {e} (kind {kind}, n = {n}, seed {seed})"))?;
892        }
893        Ok(())
894    }
895
896    /// (K1) for `gemm_sub`, against the blocked reference and against the
897    /// plain triple loop of step B3.
898    fn k1_gemm(kind: u8, m: usize, k: usize, n: usize, seed: u64) -> Result<(), String> {
899        let mut rng = Rng(seed | 1);
900        let a = rng.dds(kind, m * k);
901        let b = rng.dds(kind, k * n);
902        let c = rng.dds(kind, m * n);
903        let (mut c1, mut c2, mut c3) = (c.clone(), c.clone(), c);
904        gemm_sub(m, k, n, &a, &b, &mut c1);
905        reference::gemm_sub(m, k, &a, &b, &mut c2);
906        for j in 0..n {
907            for l in 0..k {
908                for i in 0..m {
909                    c3[i + j * m] -= a[i + l * m] * b[l + j * k];
910                }
911            }
912        }
913        if same_dds(&c1, &c2) && same_dds(&c2, &c3) {
914            Ok(())
915        } else {
916            Err(format!(
917                "gemm_sub: kind {kind}, {m} × {k} × {n}, seed {seed}"
918            ))
919        }
920    }
921
922    /// Every length `0..=67` (all residues modulo `W`, with and without
923    /// chunks) and some large ones, on every kind of data.
924    #[test]
925    fn k1_every_length_and_kind() {
926        for kind in 0..4_u8 {
927            for n in (0..=67).chain([255, 256, 1000, 4099, 65_539]) {
928                let seeds = if n <= 67 { 6 } else { 2 };
929                for s in 0..seeds {
930                    let seed = 0x9e37_79b9_7f4a_7c15_u64
931                        .wrapping_mul(u64::from(kind) + 1)
932                        .wrapping_add((n as u64) << 8)
933                        .wrapping_add(s);
934                    k1_vectors(kind, n, seed).unwrap();
935                }
936            }
937        }
938    }
939
940    /// `gemm_sub` on shapes that are empty, smaller than a chunk, and
941    /// larger than a cache block in both directions.
942    #[test]
943    fn k1_gemm_shapes() {
944        let shapes = [
945            (0, 3, 2),
946            (3, 0, 2),
947            (3, 2, 0),
948            (1, 1, 1),
949            (3, 2, 5),
950            (4, 4, 4),
951            (7, 5, 3),
952            (67, 9, 4),
953            (BLOCK_ROWS + 5, 3, 2),
954            (9, BLOCK_K + 7, 2),
955            (2 * BLOCK_ROWS + 3, BLOCK_K + 1, 3),
956        ];
957        for kind in 0..4_u8 {
958            for (s, &(m, k, n)) in shapes.iter().enumerate() {
959                k1_gemm(kind, m, k, n, 77 + 1000 * u64::from(kind) + s as u64).unwrap();
960            }
961        }
962    }
963
964    /// The slow paths of Chapter 11.6 are taken and are right: a single
965    /// non-finite element, or one overflowing product, in each lane.
966    #[test]
967    fn k1_exceptional_values_in_each_lane() {
968        let bad = [
969            Dd::INFINITY,
970            -Dd::INFINITY,
971            Dd::NAN,
972            Dd::from_f64(f64::MAX),
973            Dd::from_f64(1e200),
974        ];
975        for (b, &v) in bad.iter().enumerate() {
976            for at in 0..12 {
977                let mut rng = Rng(1 + at as u64 + 100 * b as u64);
978                let mut p = rng.dds(0, 13);
979                let q = rng.dds(0, 13);
980                p[at] = v;
981                let big = Dd::from_f64(1e200);
982                for alpha in [Dd::ONE, big, Dd::ZERO] {
983                    let (mut z, mut z0) = (q.clone(), q.clone());
984                    axpy(alpha, &p, &mut z);
985                    reference::axpy(alpha, &p, &mut z0);
986                    assert!(same_dds(&z, &z0), "axpy, value {b} at {at}");
987                    let (mut c, mut c0) = (q.clone(), q.clone());
988                    gemm_sub(13, 1, 1, &p, &[alpha], &mut c);
989                    reference::gemm_sub(13, 1, &p, &[alpha], &mut c0);
990                    assert!(same_dds(&c, &c0), "gemm_sub, value {b} at {at}");
991                }
992                assert!(same_dd(dot(&p, &q), reference::dot(&p, &q)));
993                assert!(same_dd(dot(&p, &p), reference::dot(&p, &p)));
994                assert!(same_dd(dot4(&p, &q), reference::dot4(&p, &q)));
995                let y: Vec<f64> = q.iter().map(|d| d.hi() * 1e150).collect();
996                assert!(same_dd(dot_mixed(&p, &y), reference::dot_mixed(&p, &y)));
997                let x: Vec<f64> = p.iter().map(|d| d.hi()).collect();
998                assert!(same_dd(sum2(&x), reference::sum2(&x).result()));
999                assert!(same_dd(dot2(&x, &y), reference::dot2(&x, &y).result()));
1000                let (r, beta) = dot2_err(&x, &y);
1001                let (r0, beta0) = reference::dot2(&x, &y).result_with_bound(13);
1002                assert!(same_dd(r, r0) && same(beta, beta0));
1003            }
1004        }
1005    }
1006
1007    proptest::proptest! {
1008        #![proptest_config(proptest::prelude::ProptestConfig::with_cases(2000))]
1009        /// (K1), scalar × SIMD, bit for bit, on random lengths, kinds of
1010        /// data and seeds.
1011        #[test]
1012        fn k1_simd_equals_scalar(kind in 0_u8..4, n in 0_usize..=67, seed in proptest::prelude::any::<u64>()) {
1013            proptest::prop_assert_eq!(k1_vectors(kind, n, seed), Ok(()));
1014        }
1015
1016        #[test]
1017        fn k1_gemm_simd_equals_scalar(
1018            kind in 0_u8..4,
1019            m in 0_usize..40,
1020            k in 0_usize..7,
1021            n in 0_usize..5,
1022            seed in proptest::prelude::any::<u64>(),
1023        ) {
1024            proptest::prop_assert_eq!(k1_gemm(kind, m, k, n, seed), Ok(()));
1025        }
1026    }
1027}