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}