xingo-extprec 0.1.3

Extended precision for numerical linear algebra: double-double arithmetic with proven error bounds, compensated kernels and rigorous interval enclosures of residuals
Documentation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
//! # Chapter 11.5 — Slice kernels: definitions, scalar reference, dispatch
//!
//! ## Purpose
//! The inner loops of extended-precision linear algebra: compensated sums
//! and dot products of `f64` data that return a double-double (Ogita, Rump
//! & Oishi 2005), one of them with a *rigorous* error bound, and the
//! double-double `dot`, `axpy` and small-block `gemm`. This chapter fixes,
//! operation by operation, what each kernel computes, and holds the
//! **scalar reference** implementation of that definition (the private
//! module `reference`). The SIMD versions (Chapter 11.6, feature `simd`)
//! return the same bits (invariant K1), so the order of accumulation is
//! part of each definition, not an implementation detail. The public
//! functions of this module choose between the two at run time
//! (Algorithm X below).
//!
//! ## Notation
//! `u = 2⁻⁵³`, `η = 2⁻¹⁰⁷⁴`, `γ_k = k u / (1 − k u)`. `2Sum` and `2Prod`
//! are the error-free transformations of Chapter 11.1, `⊕ ⊖ ⊗` the
//! double-double operations of Chapter 11.2 (Algorithms A2, M2, M1). `W =
//! 4` is the number of accumulators — *lanes* — on every target: the width
//! of AVX2; narrower targets emulate it, wider ones use it, so that there
//! is one answer everywhere. Element `i` belongs to lane `i mod W`.
//!
//! ## Algorithms
//! **Algorithm C (compensated accumulation: `sum2`, `dot2`, `dot2_err`).**
//! Input `x ∈ Fⁿ` (and `y ∈ Fⁿ`). Output a double-double `r` (and `β`).
//!
//! C1. \[Lanes.\] `p_k ← 0`, `s_k ← 0`, `e_k ← 0` for `k = 0, …, W − 1`.
//! C2. \[Accumulate.\] For `i = 0, …, n − 1`, with `k = i mod W`: form the
//!     term — `sum2`: `(p_k, q) ← 2Sum(p_k, x_i)`, `t ← q`; `dot2` and
//!     `dot2_err`: `(h, r) ← 2Prod(x_i, y_i)`, `(p_k, q) ← 2Sum(p_k, h)`,
//!     `t ← RN(q + r)` — then `s_k ← RN(s_k + t)` and, for `dot2_err`,
//!     `e_k ← RN(e_k + |t|)`.
//! C3. \[Combine.\] `p ← p_0`, `s ← s_0`, `e ← e_0`. For `k = 1, …, W − 1`:
//!     `(p, q) ← 2Sum(p, p_k)`; `s ← RN(s + RN(s_k + q))`; `e ← RN(e +
//!     RN(e_k + |q|))`.
//! C4. \[Result.\] `(r_h, r_ℓ) ← 2Sum(p, s)`, then step E of Chapter 11.2:
//!     `r ← (r_h, r_ℓ)`, with `r_ℓ` replaced by `0` if it is not finite.
//! C5. \[Bound, `dot2_err` only.\] If `n = 0`, `β ← 0`. If `2(n + 3)u ≥ 1`,
//!     or `p`, `s`, `e`, `r` or the error term `r_ℓ` of the 2Sum of C4
//!     *before* step E is not finite, `β ← +∞`. Otherwise, in `f64`
//!     arithmetic, `δ ← (n + 3)u / (1 − 2(n + 3)u)` and `β ← ((δ e + 3η/u)
//!     (1 + 8u))`.
//!
//! **Algorithm B (double-double BLAS: `dot`, `dot_mixed`, `axpy`,
//! `gemm_sub`).**
//!
//! B1. \[`dot`, `dot_mixed`.\] `a_k ← 0`; for `i = 0, …, n − 1`: `a_k ← a_k
//!     ⊕ (x_i ⊗ y_i)` with `k = i mod W`; return `((a_0 ⊕ a_1) ⊕ a_2) ⊕
//!     a_3`. In `dot_mixed`, `y_i` is an `f64` and `⊗` is Algorithm M1.
//! B2. \[`axpy`.\] `y_i ← y_i ⊕ (α ⊗ x_i)` for each `i` (no accumulation).
//! B3. \[`gemm_sub`.\] For `j = 0, …, n − 1`, for `l = 0, …, k − 1`, for `i
//!     = 0, …, m − 1`: `c_ij ← c_ij ⊖ (a_il ⊗ b_lj)`. Each `c_ij` receives
//!     its `k` updates in increasing `l`; the loop over `i` — the *column
//!     update* `c ← c ⊖ a ⊗ t` of one column of `C` by one column of `A`
//!     and one scalar `t = b_lj` — is the one a SIMD version vectorizes.
//!     The entries of `C` do not interact, so the loops over `j`, `l` and
//!     `i` may be blocked for the cache in any way that keeps `l`
//!     increasing for each `(i, j)`: the kernels run in blocks of
//!     `BLOCK_ROWS` rows and `BLOCK_K` columns of `A`, the scheme of
//!     `xingo_sparse::NaiveDense` (Chapter 5.16).
//!
//! B4. \[`dot4`, the step D of Algorithm W of Chapter 5.16 of
//!     `xingo-sparse`; crate-private, for the solves of Chapter 11.7.\]
//!     `a_k ← 0`; for the first `4⌊n/4⌋` elements `a_k ← a_k ⊕ (x_i ⊗
//!     y_i)` with `k = i mod W`; `t ← 0` and `t ← t ⊕ (x_i ⊗ y_i)` for the
//!     rest, in order; return `((a_0 ⊕ a_1) ⊕ (a_2 ⊕ a_3)) ⊕ t`. It differs
//!     from B1 in the tail (one more accumulator instead of the lanes) and
//!     in the combination (pairwise), the order of the generic solve of
//!     `xingo-sparse`, whose bits it must return.
//!
//! **Algorithm X (dispatch).** For a call of a kernel `κ`:
//!
//! X1. \[Feature.\] Without the feature `simd`, run the reference `κ`.
//! X2. \[Detect.\] On `aarch64`, if NEON is available (it always is), run
//!     the SIMD `κ` of Chapter 11.6 with two-lane vectors; on `x86` and
//!     `x86_64`, if AVX2 and FMA are available, run it with four-lane
//!     vectors. The detection is `pulp`'s (cached after the first call).
//! X3. \[Fallback.\] Otherwise run the reference `κ`.
//!
//! [`backend`] reports the choice of X1–X3. AVX-512 is deliberately not a
//! backend: `W = 4` is the width of AVX2, and a wider accumulator would be
//! a different kernel (another order of accumulation).
//!
//! ## Bounds
//! Sum2 and Dot2 are analysed by Ogita, Rump & Oishi for the sequential
//! order; their argument uses the order only through "a floating-point sum
//! of `m` terms, in any order, errs by at most `γ_{m−1} Σ|terms|`" (their
//! (2.4)) and so carries over to Algorithm C, with `n + 3` in place of `n`
//! (the three `2Sum` of step C3 add three error terms). Barring overflow:
//!
//! * `sum2`: `|r − Σx_i| ≤ γ²_{n+3} Σ|x_i|` (their Proposition 4.5 has
//!   `γ²_{n−1}` for the sequential order, plus `u|Σx_i|` for rounding the
//!   result to one `f64`, which C4 does not do);
//! * `dot2`: `|r − xᵀy| ≤ γ²_{n+5} |x|ᵀ|y| + n η/2` (their Proposition 5.5:
//!   `γ²_n`, and `5nη` for the Dekker product in place of the FMA).
//!
//! **Proof of step C5.** Barring overflow, and with every `2Prod` exact,
//! `xᵀy = p + Σ_i (q_i + r_i) + Σ_c q_c` exactly, where the `q_c` are the
//! three errors of step C3. `s` is a floating-point sum, in some order, of
//! the `N = n + 3` terms `t_i = RN(q_i + r_i)` and `q_c`, so with `E =
//! Σ|t_i| + Σ|q_c|`:
//! `|xᵀy − p − s| ≤ u Σ|t_i| + γ_{N−1} E ≤ γ_{n+3} E`. And `e` is a
//! floating-point sum of the same `N` nonnegative magnitudes, so `E ≤ (1 +
//! u)^{n+2} e`. Hence `|xᵀy − p − s| ≤ (n + 3)u / (1 − (2n + 5)u) · e`. A
//! `2Prod` out of its exact range adds at most `η/2` (invariant T2 of
//! Chapter 11.1): `n η/2` in all. Step C5 evaluates an upper bound of that
//! in round-to-nearest: `δ` is computed from exact operands by one division
//! (`δ ≥ (1 − u)` times the exact coefficient above, whose denominator is
//! the larger `1 − (2n + 5)u`), the product `δ e` errs by at most a factor
//! `(1 − u)` and `η/2`, the two remaining operations by `(1 − u)` each (the
//! term `3η/u = 3 · 2⁻¹⁰²¹` keeps them out of the subnormal range), and `(1
//! + 8u)(1 − u)⁴ ≥ 1`, `3η/u − η/2 ≥ n η/2 + η/2`.
//!
//! *Overflow.* The argument needs every operation exact or rounded as
//! stated, and that is lost only by an overflow — of a sum, of a product,
//! or of an *intermediate* step of a 2Sum whose first operand is `±Ω`
//! (invariant T1 of Chapter 11.1: then the error term is `±∞` or NaN, and
//! conversely a 2Sum whose error term is finite had no step overflow and
//! is exact). In steps C2 and C3 every such value flows into `p`, `s` or
//! `e` through additions and absolute values, none of which maps a
//! non-finite value back to a finite one, and C5 tests the three. The one
//! exception is step C4: its error term `r_ℓ` goes *only* into `r`, and step
//! E replaces it by `0` — a non-finite value made finite — so `r` can be
//! finite and wrong by up to `ulp(Ω)/2 = 2⁹⁷⁰` (`p = Ω − 2⁹⁷¹`, `s = −2⁹⁷⁰ −
//! …`, found by review X0.3i). C5 therefore tests `r_ℓ` itself, before step
//! E; with it finite the 2Sum is exact and `r = p + s`. (Until X0.3i C5
//! tested only `r`, and (K2) was false in that corner.) This is Algorithm 5.8 and
//! Corollary 5.9 of Ogita, Rump & Oishi adapted to the lanes, to the FMA
//! product and to a double-double result (their bound has one more term,
//! `u|res|`, for the final rounding to `f64`).
//!
//! The kernels of Algorithm B inherit the bounds of `⊕` and `⊗`: each
//! term errs by at most `4u²` relative, each accumulation by `3u² + 13u³`.
//!
//! ## Invariants
//! (K1) *One answer.* Every kernel is the fixed sequence of `f64`
//!      operations above for a given `n`; the SIMD implementation returns
//!      the same bits for **every** input — finite or not, normalized or
//!      not — with one reservation: where a result is a NaN, both are NaN,
//!      and the sign and payload of that NaN are not specified (Rust does
//!      not specify them for `f64` arithmetic either). Chapter 11.6 has the
//!      argument; the tests of this module compare the two implementations
//!      bit for bit on random and on exceptional data. [`backend`] names
//!      the implementation in use.
//! (K2) *Rigour.* `dot2_err` returns `(r, β)` with `|xᵀy − r| ≤ β` for
//!      every input; `β = +∞` when a hypothesis fails (invariant C3 of
//!      Chapter 11), the overflow of an intermediate step of the 2Sum of C4
//!      included (the proof of C5, "Overflow"). Checked against exact
//!      rationals, near `Ω` too.
//!
//! ## References
//! Ogita, Rump & Oishi, "Accurate sum and dot product", SIAM J. Sci.
//! Comput. 26 (2005): Algorithm 4.4 (Sum2) and Proposition 4.5, Algorithm
//! 5.3 (Dot2) and Proposition 5.5, Algorithm 5.8 (Dot2Err) and Corollary
//! 5.9. Higham, *Accuracy and Stability of Numerical Algorithms* (2002),
//! §4.2 (the order-independent bound). Chapter 5.16 of `xingo-sparse`
//! (the blocked loop order of `gemm_sub`).

use crate::dd::DoubleDouble;
use crate::eft::two_sum;

/// `W`, the number of lanes (the chapter).
pub(crate) const LANES: usize = 4;

/// Rows of `C` and `A` handled per block of step B3 (a cache-blocking
/// size, not a numerical threshold; not tuned): `BLOCK_ROWS × BLOCK_K`
/// double-doubles of `A` — 128 KiB — stay in cache while the columns of `C`
/// pass over them.
pub(crate) const BLOCK_ROWS: usize = 128;
/// Columns of `A` (the summation index `l`) per block; see [`BLOCK_ROWS`].
pub(crate) const BLOCK_K: usize = 64;

/// `2⁻⁵³`.
const U: f64 = 0.5 * f64::EPSILON;

/// The state of Algorithm C: the lanes `p_k`, `s_k`, `e_k`.
#[derive(Clone, Copy, Default)]
pub(crate) struct Compensated {
    pub(crate) p: [f64; LANES],
    pub(crate) s: [f64; LANES],
    pub(crate) e: [f64; LANES],
}

impl Compensated {
    /// Step C2 for the term `h + r` (`r = 0` for a sum) of element `i`.
    #[inline]
    pub(crate) fn push(&mut self, i: usize, h: f64, r: f64) {
        let k = i % LANES;
        let (p, q) = two_sum(self.p[k], h);
        let t = q + r;
        self.p[k] = p;
        self.s[k] += t;
        self.e[k] += t.abs();
    }

    /// Step C3: `(p, s, e)`.
    #[inline]
    pub(crate) fn combine(&self) -> (f64, f64, f64) {
        let (mut p, mut s, mut e) = (self.p[0], self.s[0], self.e[0]);
        for k in 1..LANES {
            let (pn, q) = two_sum(p, self.p[k]);
            p = pn;
            s += self.s[k] + q;
            e += self.e[k] + q.abs();
        }
        (p, s, e)
    }

    /// Steps C3 and C4: the result `r`.
    #[inline]
    pub(crate) fn result(&self) -> DoubleDouble {
        let (p, s, _) = self.combine();
        DoubleDouble::from_sum(p, s)
    }

    /// Steps C3–C5 for `n` elements: the result `r` and the bound `β`.
    #[inline]
    pub(crate) fn result_with_bound(&self, n: usize) -> (DoubleDouble, f64) {
        /// `3η/u = 3 · 2⁻¹⁰²¹`.
        const UNDERFLOW: f64 = 6.0 * f64::MIN_POSITIVE;
        /// `1 + 8u`.
        const INFLATE: f64 = 1.0 + 4.0 * f64::EPSILON;
        /// `2(n + 3)u < 1` iff `n + 3 < 2⁵²`.
        const MAX_TERMS: u64 = 1 << 52;

        let (p, s, e) = self.combine();
        // C4; step E of `from_sum` hides a non-finite error term, which
        // C5 must see (the proof of C5, "Overflow").
        let (_, r_lo) = two_sum(p, s);
        let r = DoubleDouble::from_sum(p, s);
        // C5.
        if n == 0 {
            return (r, 0.0);
        }
        let terms = u64::try_from(n).map_or(u64::MAX, |n| n.saturating_add(3));
        let finite =
            p.is_finite() && s.is_finite() && e.is_finite() && r.is_finite() && r_lo.is_finite();
        if terms >= MAX_TERMS || !finite {
            return (r, f64::INFINITY);
        }
        #[allow(clippy::cast_precision_loss)] // exact: terms < 2^52
        let a = terms as f64 * U;
        let delta = a / (1.0 - 2.0 * a);
        (r, (delta * e + UNDERFLOW) * INFLATE)
    }
}

/// The column update of step B3, `c_i ← c_i ⊖ (a_i ⊗ t)` for every `i`:
/// the one loop that the kernels of Algorithm B built on `gemm` vectorize
/// (and the dense kernels of Chapter 11.7 with them). Implemented by the
/// scalar [`reference::Reference`] and by the vectors of Chapter 11.6.
pub(crate) trait ColumnUpdate: Copy {
    /// `c ← c ⊖ a ⊗ t`; `c` and `a` have the same length.
    fn column_sub(self, c: &mut [DoubleDouble], a: &[DoubleDouble], t: DoubleDouble);
}

/// Step B3 with the blocks of the chapter: `c_ij ← c_ij ⊖ Σ_l a_il ⊗
/// t(j, l)` for the `m × k` block `a` and the `m × n` block `c`
/// (column-major), `l` increasing for each entry.
#[inline(always)] // into `pulp`'s `vectorize` (Chapter 11.6)
#[allow(clippy::inline_always)]
pub(crate) fn gemm_blocked<U: ColumnUpdate>(
    update: U,
    m: usize,
    k: usize,
    a: &[DoubleDouble],
    c: &mut [DoubleDouble],
    t: impl Fn(usize, usize) -> DoubleDouble,
) {
    debug_assert_eq!(a.len(), m * k, "gemm_blocked: A is not m × k");
    debug_assert!(m == 0 || c.len().is_multiple_of(m), "gemm_blocked: C");
    if m == 0 {
        return;
    }
    let mut i0 = 0;
    while i0 < m {
        let i1 = (i0 + BLOCK_ROWS).min(m);
        let mut l0 = 0;
        while l0 < k {
            let l1 = (l0 + BLOCK_K).min(k);
            for (j, cj) in c.chunks_exact_mut(m).enumerate() {
                let cj = &mut cj[i0..i1];
                for l in l0..l1 {
                    update.column_sub(cj, &a[l * m + i0..l * m + i1], t(j, l));
                }
            }
            l0 = l1;
        }
        i0 = i1;
    }
}

/// The scalar reference kernels: Algorithms C and B of the chapter, one
/// `f64` operation at a time. They are the definition of the kernels, the
/// oracle of the SIMD versions (invariant K1) and the fallback of the
/// dispatch (Algorithm X).
pub(crate) mod reference {
    use super::{ColumnUpdate, Compensated, LANES, gemm_blocked};
    use crate::dd::DoubleDouble;
    use crate::eft::two_prod;

    /// The scalar column update (step B3).
    #[derive(Clone, Copy, Debug)]
    pub(crate) struct Reference;

    impl ColumnUpdate for Reference {
        #[inline]
        fn column_sub(self, c: &mut [DoubleDouble], a: &[DoubleDouble], t: DoubleDouble) {
            debug_assert_eq!(c.len(), a.len(), "column_sub: the lengths differ");
            for (ci, &ai) in c.iter_mut().zip(a) {
                *ci -= ai * t;
            }
        }
    }

    /// Steps C1–C2 of `sum2`.
    pub(crate) fn sum2(x: &[f64]) -> Compensated {
        let mut acc = Compensated::default();
        for (i, &xi) in x.iter().enumerate() {
            acc.push(i, xi, 0.0);
        }
        acc
    }

    /// Steps C1–C2 of `dot2` and `dot2_err`.
    pub(crate) fn dot2(x: &[f64], y: &[f64]) -> Compensated {
        let mut acc = Compensated::default();
        for (i, (&xi, &yi)) in x.iter().zip(y).enumerate() {
            let (h, r) = two_prod(xi, yi);
            acc.push(i, h, r);
        }
        acc
    }

    /// Step B1, double-double `y`.
    pub(crate) fn dot(x: &[DoubleDouble], y: &[DoubleDouble]) -> DoubleDouble {
        let mut acc = [DoubleDouble::ZERO; LANES];
        for (i, (&xi, &yi)) in x.iter().zip(y).enumerate() {
            acc[i % LANES] += xi * yi;
        }
        ((acc[0] + acc[1]) + acc[2]) + acc[3]
    }

    /// Step B4.
    #[cfg_attr(not(feature = "sparse"), allow(dead_code))]
    pub(crate) fn dot4(x: &[DoubleDouble], y: &[DoubleDouble]) -> DoubleDouble {
        let mut acc = [DoubleDouble::ZERO; LANES];
        let (cx, tx) = x.as_chunks::<LANES>();
        let (cy, ty) = y.as_chunks::<LANES>();
        for (p, q) in cx.iter().zip(cy) {
            for k in 0..LANES {
                acc[k] += p[k] * q[k];
            }
        }
        let mut t = DoubleDouble::ZERO;
        for (&p, &q) in tx.iter().zip(ty) {
            t += p * q;
        }
        (acc[0] + acc[1]) + (acc[2] + acc[3]) + t
    }

    /// Step B1, `f64` `y`.
    pub(crate) fn dot_mixed(x: &[DoubleDouble], y: &[f64]) -> DoubleDouble {
        let mut acc = [DoubleDouble::ZERO; LANES];
        for (i, (&xi, &yi)) in x.iter().zip(y).enumerate() {
            acc[i % LANES] += xi * yi;
        }
        ((acc[0] + acc[1]) + acc[2]) + acc[3]
    }

    /// Step B2.
    pub(crate) fn axpy(alpha: DoubleDouble, x: &[DoubleDouble], y: &mut [DoubleDouble]) {
        for (yi, &xi) in y.iter_mut().zip(x) {
            *yi += alpha * xi;
        }
    }

    /// Step B3 (`b` is `k × n`, column-major).
    pub(crate) fn gemm_sub(
        m: usize,
        k: usize,
        a: &[DoubleDouble],
        b: &[DoubleDouble],
        c: &mut [DoubleDouble],
    ) {
        gemm_blocked(Reference, m, k, a, c, |j, l| b[l + j * k]);
    }
}

/// Algorithm X, steps X1–X2: if a SIMD backend is compiled in and available,
/// **returns from the enclosing function** with the value of `$simd`, an
/// expression in which `$lanes` is the backend's four-lane arithmetic
/// (`crate::simd::Lanes`), evaluated inside `pulp`'s `vectorize` (which
/// enables the target features for the code inlined into it). Otherwise
/// falls through to step X3, written after the macro call.
macro_rules! dispatch {
    (|$lanes:ident| $simd:expr) => {
        #[cfg(all(feature = "simd", target_arch = "aarch64"))]
        if let Some(token) = pulp::aarch64::Neon::try_new() {
            let $lanes = $crate::simd::X2::new(token);
            return pulp::Simd::vectorize(
                token,
                #[inline(always)]
                || $simd,
            );
        }
        #[cfg(all(feature = "simd", any(target_arch = "x86", target_arch = "x86_64")))]
        if let Some(token) = pulp::x86::V3::try_new() {
            let $lanes = $crate::simd::X4::new(token);
            return pulp::Simd::vectorize(
                token,
                #[inline(always)]
                || $simd,
            );
        }
    };
}
// Chapter 11.7 dispatches its loops with the same macro.
#[cfg(feature = "sparse")]
pub(crate) use dispatch;

/// `Σ xᵢ` of `f64` values as a double-double, as accurate as if summed
/// in twice the working precision (Sum2 of Ogita, Rump & Oishi, over `W =
/// 4` lanes: Algorithm C of Chapter 11.5): `|result − Σxᵢ| ≤ γ²_{n+3}
/// Σ|xᵢ|` barring overflow. Overflow includes an intermediate step of a
/// 2Sum whose first operand is `±Ω` (invariant T1 of Chapter 11.1): there
/// the result may be finite with a relative error of order `u`.
#[must_use]
pub fn sum2(x: &[f64]) -> DoubleDouble {
    dispatch!(|lanes| crate::simd::sum2(lanes, x).result());
    reference::sum2(x).result()
}

/// `xᵀy` of `f64` vectors as a double-double (Dot2, over `W = 4` lanes:
/// Algorithm C of Chapter 11.5): `|result − xᵀy| ≤ γ²_{n+5} |x|ᵀ|y| + n
/// η/2` barring overflow. Overflow includes an intermediate step of a 2Sum
/// whose first operand is `±Ω` (invariant T1 of Chapter 11.1): there the
/// result may be finite with a relative error of order `u`; [`dot2_err`]
/// reports that case with `β = +∞`. Panics if the lengths differ.
#[must_use]
pub fn dot2(x: &[f64], y: &[f64]) -> DoubleDouble {
    assert_eq!(x.len(), y.len(), "dot2: the lengths differ");
    dispatch!(|lanes| crate::simd::dot2::<_, false>(lanes, x, y).result());
    reference::dot2(x, y).result()
}

/// As [`dot2`], with a rigorous bound: returns `(r, β)` with `|xᵀy −
/// r| ≤ β` (Dot2Err; step C5 of Chapter 11.5 and its proof). `β = +∞`
/// when a hypothesis fails (overflow — of an intermediate step of a 2Sum at
/// `±Ω` too —, NaN, `2(n + 3)u ≥ 1`): invariant C3.
/// Panics if the lengths differ.
#[must_use]
pub fn dot2_err(x: &[f64], y: &[f64]) -> (DoubleDouble, f64) {
    assert_eq!(x.len(), y.len(), "dot2_err: the lengths differ");
    dispatch!(|lanes| crate::simd::dot2::<_, true>(lanes, x, y).result_with_bound(x.len()));
    reference::dot2(x, y).result_with_bound(x.len())
}

/// `xᵀy` of double-double vectors, over `W = 4` lanes combined left to
/// right (step B1 of Chapter 11.5). Panics if the lengths differ.
#[must_use]
pub fn dot(x: &[DoubleDouble], y: &[DoubleDouble]) -> DoubleDouble {
    assert_eq!(x.len(), y.len(), "dot: the lengths differ");
    dispatch!(|lanes| crate::simd::dot(lanes, x, y));
    reference::dot(x, y)
}

/// `xᵀy` with `x` double-double and `y` `f64` (a row of an `f64`
/// matrix against an extended vector: the residual of a polished
/// solution); the order of [`dot`]. Panics if the lengths differ.
#[must_use]
pub fn dot_mixed(x: &[DoubleDouble], y: &[f64]) -> DoubleDouble {
    assert_eq!(x.len(), y.len(), "dot_mixed: the lengths differ");
    dispatch!(|lanes| crate::simd::dot_mixed(lanes, x, y));
    reference::dot_mixed(x, y)
}

/// `y ← y + α x`, element by element (step B2 of Chapter 11.5). Panics if
/// the lengths differ.
pub fn axpy(alpha: DoubleDouble, x: &[DoubleDouble], y: &mut [DoubleDouble]) {
    assert_eq!(x.len(), y.len(), "axpy: the lengths differ");
    dispatch!(|lanes| crate::simd::axpy(lanes, alpha, x, y));
    reference::axpy(alpha, x, y);
}

/// `C ← C − A B` for small column-major blocks (`A` is `m × k`, `B` is
/// `k × n`, `C` is `m × n`); the update of a supernodal block. Each entry
/// of `C` receives its `k` updates in increasing column of `A` (step B3 of
/// Chapter 11.5). Panics if a slice has the wrong length.
pub fn gemm_sub(
    m: usize,
    k: usize,
    n: usize,
    a: &[DoubleDouble],
    b: &[DoubleDouble],
    c: &mut [DoubleDouble],
) {
    assert_eq!(a.len(), m * k, "gemm_sub: A is not m × k");
    assert_eq!(b.len(), k * n, "gemm_sub: B is not k × n");
    assert_eq!(c.len(), m * n, "gemm_sub: C is not m × n");
    dispatch!(|lanes| gemm_blocked(lanes, m, k, a, c, |j, l| b[l + j * k]));
    reference::gemm_sub(m, k, a, b, c);
}

/// The name of the implementation the dispatch selected (`"scalar"`,
/// `"avx2"`, `"neon"`), for benchmarks and bug reports: Algorithm X of
/// Chapter 11.5. `"scalar"` without the feature `simd`, or when the CPU
/// has neither NEON nor AVX2 with FMA. (`"avx512"`, which the contract
/// listed, is never returned: the chapter says why.)
#[must_use]
pub fn backend() -> &'static str {
    #[cfg(all(feature = "simd", target_arch = "aarch64"))]
    if pulp::aarch64::Neon::try_new().is_some() {
        return "neon";
    }
    #[cfg(all(feature = "simd", any(target_arch = "x86", target_arch = "x86_64")))]
    if pulp::x86::V3::try_new().is_some() {
        return "avx2";
    }
    "scalar"
}

#[cfg(test)]
#[allow(clippy::disallowed_methods)] // L2.4 (Chapter 11.11): the tests may use the libm of `f64` (clippy.toml)
#[allow(clippy::float_cmp)] // the tests compare exact values
mod tests {
    use super::*;

    type Dd = DoubleDouble;

    #[test]
    fn empty_inputs() {
        assert_eq!(sum2(&[]), Dd::ZERO);
        assert_eq!(dot2(&[], &[]), Dd::ZERO);
        assert_eq!(dot2_err(&[], &[]), (Dd::ZERO, 0.0));
        assert_eq!(dot(&[], &[]), Dd::ZERO);
        assert_eq!(dot_mixed(&[], &[]), Dd::ZERO);
        axpy(Dd::ONE, &[], &mut []);
        gemm_sub(0, 0, 0, &[], &[], &mut []);
        gemm_sub(0, 2, 3, &[], &[Dd::ONE; 6], &mut []);
    }

    /// Algorithm X: what `backend` must say on this build and this CPU.
    #[test]
    fn backend_names_the_dispatch() {
        #[cfg(not(feature = "simd"))]
        let expected = "scalar";
        // NEON is part of the baseline of every aarch64 target of Rust.
        #[cfg(all(feature = "simd", target_arch = "aarch64"))]
        let expected = "neon";
        #[cfg(all(feature = "simd", any(target_arch = "x86", target_arch = "x86_64")))]
        let expected = if std::arch::is_x86_feature_detected!("avx2")
            && std::arch::is_x86_feature_detected!("fma")
        {
            "avx2"
        } else {
            "scalar"
        };
        #[cfg(all(
            feature = "simd",
            not(any(target_arch = "aarch64", target_arch = "x86", target_arch = "x86_64"))
        ))]
        let expected = "scalar";
        assert_eq!(backend(), expected);
    }

    /// The minimal case of review X0.3i (M1): in lane 0, the terms of 17
    /// leave `p = Ω − 2⁹⁷¹` and `s = −2⁹⁷⁰ − …`, the 2Sum of step C4 rounds
    /// `p + s` to `p` and its error term overflows (invariant T1 of Chapter
    /// 11.1). Before the correction of C5, `β` was finite (`≈ 6.6e277`) and
    /// `|xᵀy − r| = 2⁹⁷⁰`; now `β = +∞`, on both paths, and `r` keeps its
    /// bits.
    #[test]
    fn dot2_err_refuses_when_the_two_sum_of_c4_overflows() {
        use dashu_ratio::RBig;
        let lane0 = [
            0x7fef_ffff_ffff_fffe_u64,
            0x7c90_0000_0000_0001,
            0xfc8f_ffff_ffff_fffe,
            0xfc8f_ffff_ffff_fffc,
            0xf970_0000_0000_0000,
        ];
        let mut x = [0.0; 17];
        for (k, bits) in lane0.iter().enumerate() {
            x[4 * k] = f64::from_bits(*bits);
        }
        let y = [1.0; 17];
        let exact = x.iter().fold(RBig::from(0), |acc, &v| {
            acc + RBig::try_from(v).expect("finite")
        });
        let reference = reference::dot2(&x, &y).result_with_bound(17);
        let dispatched = dot2_err(&x, &y);
        for (r, beta) in [reference, dispatched] {
            assert_eq!((r.hi().to_bits(), r.lo()), (0x7fef_ffff_ffff_fffe, 0.0));
            let err = RBig::try_from(r.hi()).expect("finite") - exact.clone();
            let err = if err < RBig::from(0) { -err } else { err };
            assert!(err > RBig::from(0));
            assert!(
                beta == f64::INFINITY || err <= RBig::try_from(beta).expect("finite"),
                "K2 fails: |xᵀy − r| = {:e} > β = {beta:e}",
                err.to_f64().value()
            );
            assert_eq!(beta, f64::INFINITY);
        }
        // `r` is that of `dot2` (step C4 is shared).
        assert_eq!(dot2(&x, &y), dispatched.0);
    }

    /// (K1) near `Ω`, where the 2Sums of steps C2–C4 overflow in their
    /// intermediate steps: scalar and SIMD return the same bits (`β` of
    /// `dot2_err` included), on every length 1 to 64.
    #[test]
    fn k1_near_omega() {
        let mut state = 0x2545_f491_4f6c_dd1d_u64;
        let mut next = move || {
            state ^= state << 13;
            state ^= state >> 7;
            state ^= state << 17;
            state
        };
        for n in 1..=64 {
            for _ in 0..50 {
                let x: Vec<f64> = (0..n)
                    .map(|_| {
                        let sign = if next() & 1 == 0 { 1.0 } else { -1.0 };
                        let j = f64::from(u8::try_from(next() % 4).expect("small"));
                        sign * match next() % 4 {
                            0 => f64::from_bits(f64::MAX.to_bits() - next() % 4),
                            1 => 2f64.powi(970) + j * 2f64.powi(918),
                            2 => 2f64.powi(970) - j * 2f64.powi(918),
                            _ => 0.0,
                        }
                    })
                    .collect();
                let y = vec![1.0; n];
                assert!(
                    same_dd(sum2(&x), reference::sum2(&x).result()),
                    "sum2 {x:?}"
                );
                assert!(
                    same_dd(dot2(&x, &y), reference::dot2(&x, &y).result()),
                    "dot2 {x:?}"
                );
                let (r, beta) = dot2_err(&x, &y);
                let (r0, beta0) = reference::dot2(&x, &y).result_with_bound(n);
                assert!(same_dd(r, r0) && same(beta, beta0), "dot2_err {x:?}");
            }
        }
    }

    #[test]
    fn sum2_survives_cancellation() {
        // The plain f64 sum loses the small terms.
        let x = [1e100, 1.0, -1e100, 2.0];
        assert_eq!(x.iter().sum::<f64>(), 2.0);
        assert_eq!(sum2(&x), Dd::from_f64(3.0));
        let tiny = 2f64.powi(-60);
        assert_eq!(sum2(&[1.0, tiny, -1.0]), Dd::from_f64(tiny));
        // The result is the unrounded pair (p, s) of step C4.
        assert_eq!(sum2(&[1.0, tiny]), Dd::from_parts(1.0, tiny));
        // More terms than lanes.
        let y: Vec<f64> = (1..=10).map(f64::from).collect();
        assert_eq!(sum2(&y), Dd::from_f64(55.0));
    }

    #[test]
    fn dot2_survives_cancellation() {
        let big = 2f64.powi(60);
        let x = [big, 1.0 + f64::EPSILON, -big];
        let y = [big, 1.0 + f64::EPSILON, big];
        assert_eq!(x.iter().zip(&y).map(|(a, b)| a * b).sum::<f64>(), 0.0);
        // "As if in twice the working precision": the leading component is
        // right, the error is within the bound of Dot2Err.
        let exact = Dd::from_product(x[1], y[1]);
        let r = dot2(&x, &y);
        assert_eq!(r.hi(), exact.hi());
        let (r_err, beta) = dot2_err(&x, &y);
        assert_eq!(r_err, r);
        assert!(beta.is_finite() && beta < 1e-10, "{beta:e}");
        assert!((r - exact).abs().hi() <= beta);
    }

    #[test]
    fn dot2_err_reports_failed_hypotheses() {
        let (r, beta) = dot2_err(&[1e200, 1.0], &[1e200, 1.0]);
        assert!(r.check_invariants().is_ok());
        assert_eq!(beta, f64::INFINITY);
        let (r, beta) = dot2_err(&[f64::NAN], &[1.0]);
        assert!(r.is_nan());
        assert_eq!(beta, f64::INFINITY);
        // Exact data still have a positive bound: the underflow term.
        let (r, beta) = dot2_err(&[1.0, 2.0], &[3.0, 4.0]);
        assert_eq!(r, Dd::from_f64(11.0));
        assert!(beta > 0.0 && beta < 1e-300);
    }

    #[test]
    fn dd_kernels_follow_their_definitions() {
        let x: Vec<Dd> = (1..=7).map(|i| Dd::ONE / f64::from(i)).collect();
        let y: Vec<Dd> = (1..=7).map(|i| Dd::from_f64(f64::from(i)).sqrt()).collect();
        let yf: Vec<f64> = y.iter().map(|v| v.hi()).collect();
        // B1: lanes 0..4, then left to right.
        let lanes = |term: &dyn Fn(usize) -> Dd| {
            let mut a = [Dd::ZERO; 4];
            for i in 0..7 {
                a[i % 4] += term(i);
            }
            ((a[0] + a[1]) + a[2]) + a[3]
        };
        assert_eq!(reference::dot(&x, &y), lanes(&|i| x[i] * y[i]));
        assert_eq!(dot(&x, &y), lanes(&|i| x[i] * y[i]));
        assert_eq!(dot_mixed(&x, &yf), lanes(&|i| x[i] * yf[i]));
        // B4: lanes over the first four, a fifth accumulator, pairwise.
        let mut a = [Dd::ZERO; 4];
        for i in 0..4 {
            a[i] += x[i] * y[i];
        }
        let mut t = Dd::ZERO;
        for i in 4..7 {
            t += x[i] * y[i];
        }
        assert_eq!(reference::dot4(&x, &y), ((a[0] + a[1]) + (a[2] + a[3])) + t);
        // B2.
        let alpha = Dd::ONE / 7.0;
        let mut z = y.clone();
        axpy(alpha, &x, &mut z);
        for i in 0..7 {
            assert_eq!(z[i], y[i] + alpha * x[i]);
        }
        // B3 on a 2 × 3 times 3 × 2 product.
        let a = &x[..6];
        let b = &y[..6];
        let mut c = vec![Dd::ONE; 4];
        gemm_sub(2, 3, 2, a, b, &mut c);
        for j in 0..2 {
            for i in 0..2 {
                let mut want = Dd::ONE;
                for l in 0..3 {
                    want -= a[i + 2 * l] * b[l + 3 * j];
                }
                assert_eq!(c[i + 2 * j], want);
            }
        }
    }

    #[test]
    #[should_panic(expected = "the lengths differ")]
    fn length_mismatch_panics() {
        let _ = dot2(&[1.0], &[]);
    }

    // ---- Invariant (K1): the dispatched kernels against the reference ----

    /// A deterministic generator (xorshift64*), so that every length is
    /// tried with the same data on every run.
    struct Rng(u64);

    impl Rng {
        fn next(&mut self) -> u64 {
            self.0 ^= self.0 >> 12;
            self.0 ^= self.0 << 25;
            self.0 ^= self.0 >> 27;
            self.0.wrapping_mul(0x2545_f491_4f6c_dd1d)
        }

        /// A random significand and sign with an exponent in `±span`.
        fn scaled(&mut self, span: i32) -> f64 {
            #[allow(clippy::cast_precision_loss)] // 53 random bits
            let m = 1.0 + (self.next() >> 11) as f64 / (1_u64 << 53) as f64;
            let e = i32::try_from(self.next() % (2 * u64::from(span.unsigned_abs()) + 1))
                .expect("small")
                - span;
            let v = m * 2f64.powi(e);
            if self.next() & 1 == 0 { v } else { -v }
        }

        fn special(&mut self) -> f64 {
            const SPECIAL: [f64; 10] = [
                0.0,
                -0.0,
                f64::INFINITY,
                f64::NEG_INFINITY,
                f64::NAN,
                f64::MAX,
                f64::MIN,
                f64::MIN_POSITIVE,
                5e-324,
                -2.5e-310,
            ];
            SPECIAL[usize::try_from(self.next() % 10).expect("small")]
        }

        /// One `f64` of the given kind of data: 0 moderate (the declared
        /// domain), 1 wide exponents (products overflow and underflow), 2
        /// any bit pattern, 3 moderate with exceptional values mixed in.
        fn f64(&mut self, kind: u8) -> f64 {
            match kind {
                0 => self.scaled(30),
                1 => self.scaled(600),
                2 => {
                    if self.next().is_multiple_of(8) {
                        self.special()
                    } else {
                        f64::from_bits(self.next())
                    }
                }
                _ => {
                    if self.next().is_multiple_of(16) {
                        self.special()
                    } else {
                        self.scaled(30)
                    }
                }
            }
        }

        /// A valid double-double (invariants D1, D2) of the given kind.
        fn dd(&mut self, kind: u8) -> Dd {
            let h = self.f64(kind);
            let l = self.f64(0) * h * 2f64.powi(-84);
            Dd::from_sum(h, l)
        }

        fn f64s(&mut self, kind: u8, n: usize) -> Vec<f64> {
            (0..n).map(|_| self.f64(kind)).collect()
        }

        fn dds(&mut self, kind: u8, n: usize) -> Vec<Dd> {
            (0..n).map(|_| self.dd(kind)).collect()
        }
    }

    /// The same bits, or a NaN on both sides (invariant K1).
    fn same(a: f64, b: f64) -> bool {
        a.to_bits() == b.to_bits() || (a.is_nan() && b.is_nan())
    }

    fn same_dd(a: Dd, b: Dd) -> bool {
        same(a.hi(), b.hi()) && same(a.lo(), b.lo())
    }

    fn same_dds(a: &[Dd], b: &[Dd]) -> bool {
        a.len() == b.len() && a.iter().zip(b).all(|(&p, &q)| same_dd(p, q))
    }

    /// Step B4 through the dispatch (the solves of Chapter 11.7 call it
    /// inside their own).
    fn dot4(x: &[Dd], y: &[Dd]) -> Dd {
        dispatch!(|lanes| crate::simd::dot4(lanes, x, y));
        reference::dot4(x, y)
    }

    /// (K1) for the seven vector kernels on one data set; the name of the
    /// first kernel that differs.
    fn k1_vectors(kind: u8, n: usize, seed: u64) -> Result<(), String> {
        let mut rng = Rng(seed | 1);
        let (x, y) = (rng.f64s(kind, n), rng.f64s(kind, n));
        let (p, q) = (rng.dds(kind, n), rng.dds(kind, n));
        let alpha = rng.dd(kind);
        let fail = |what: &str| Err(format!("{what}: kind {kind}, n = {n}, seed {seed}"));

        if !same_dd(sum2(&x), reference::sum2(&x).result()) {
            return fail("sum2");
        }
        if !same_dd(dot2(&x, &y), reference::dot2(&x, &y).result()) {
            return fail("dot2");
        }
        let (r, beta) = dot2_err(&x, &y);
        let (r0, beta0) = reference::dot2(&x, &y).result_with_bound(n);
        if !same_dd(r, r0) || !same(beta, beta0) {
            return fail("dot2_err");
        }
        if !same_dd(dot(&p, &q), reference::dot(&p, &q)) {
            return fail("dot");
        }
        if !same_dd(dot_mixed(&p, &x), reference::dot_mixed(&p, &x)) {
            return fail("dot_mixed");
        }
        if !same_dd(dot4(&p, &q), reference::dot4(&p, &q)) {
            return fail("dot4");
        }
        let (mut z, mut z0) = (q.clone(), q.clone());
        axpy(alpha, &p, &mut z);
        reference::axpy(alpha, &p, &mut z0);
        if !same_dds(&z, &z0) {
            return fail("axpy");
        }
        for v in &z {
            v.check_invariants()
                .map_err(|e| format!("axpy: {e} (kind {kind}, n = {n}, seed {seed})"))?;
        }
        Ok(())
    }

    /// (K1) for `gemm_sub`, against the blocked reference and against the
    /// plain triple loop of step B3.
    fn k1_gemm(kind: u8, m: usize, k: usize, n: usize, seed: u64) -> Result<(), String> {
        let mut rng = Rng(seed | 1);
        let a = rng.dds(kind, m * k);
        let b = rng.dds(kind, k * n);
        let c = rng.dds(kind, m * n);
        let (mut c1, mut c2, mut c3) = (c.clone(), c.clone(), c);
        gemm_sub(m, k, n, &a, &b, &mut c1);
        reference::gemm_sub(m, k, &a, &b, &mut c2);
        for j in 0..n {
            for l in 0..k {
                for i in 0..m {
                    c3[i + j * m] -= a[i + l * m] * b[l + j * k];
                }
            }
        }
        if same_dds(&c1, &c2) && same_dds(&c2, &c3) {
            Ok(())
        } else {
            Err(format!(
                "gemm_sub: kind {kind}, {m} × {k} × {n}, seed {seed}"
            ))
        }
    }

    /// Every length `0..=67` (all residues modulo `W`, with and without
    /// chunks) and some large ones, on every kind of data.
    #[test]
    fn k1_every_length_and_kind() {
        for kind in 0..4_u8 {
            for n in (0..=67).chain([255, 256, 1000, 4099, 65_539]) {
                let seeds = if n <= 67 { 6 } else { 2 };
                for s in 0..seeds {
                    let seed = 0x9e37_79b9_7f4a_7c15_u64
                        .wrapping_mul(u64::from(kind) + 1)
                        .wrapping_add((n as u64) << 8)
                        .wrapping_add(s);
                    k1_vectors(kind, n, seed).unwrap();
                }
            }
        }
    }

    /// `gemm_sub` on shapes that are empty, smaller than a chunk, and
    /// larger than a cache block in both directions.
    #[test]
    fn k1_gemm_shapes() {
        let shapes = [
            (0, 3, 2),
            (3, 0, 2),
            (3, 2, 0),
            (1, 1, 1),
            (3, 2, 5),
            (4, 4, 4),
            (7, 5, 3),
            (67, 9, 4),
            (BLOCK_ROWS + 5, 3, 2),
            (9, BLOCK_K + 7, 2),
            (2 * BLOCK_ROWS + 3, BLOCK_K + 1, 3),
        ];
        for kind in 0..4_u8 {
            for (s, &(m, k, n)) in shapes.iter().enumerate() {
                k1_gemm(kind, m, k, n, 77 + 1000 * u64::from(kind) + s as u64).unwrap();
            }
        }
    }

    /// The slow paths of Chapter 11.6 are taken and are right: a single
    /// non-finite element, or one overflowing product, in each lane.
    #[test]
    fn k1_exceptional_values_in_each_lane() {
        let bad = [
            Dd::INFINITY,
            -Dd::INFINITY,
            Dd::NAN,
            Dd::from_f64(f64::MAX),
            Dd::from_f64(1e200),
        ];
        for (b, &v) in bad.iter().enumerate() {
            for at in 0..12 {
                let mut rng = Rng(1 + at as u64 + 100 * b as u64);
                let mut p = rng.dds(0, 13);
                let q = rng.dds(0, 13);
                p[at] = v;
                let big = Dd::from_f64(1e200);
                for alpha in [Dd::ONE, big, Dd::ZERO] {
                    let (mut z, mut z0) = (q.clone(), q.clone());
                    axpy(alpha, &p, &mut z);
                    reference::axpy(alpha, &p, &mut z0);
                    assert!(same_dds(&z, &z0), "axpy, value {b} at {at}");
                    let (mut c, mut c0) = (q.clone(), q.clone());
                    gemm_sub(13, 1, 1, &p, &[alpha], &mut c);
                    reference::gemm_sub(13, 1, &p, &[alpha], &mut c0);
                    assert!(same_dds(&c, &c0), "gemm_sub, value {b} at {at}");
                }
                assert!(same_dd(dot(&p, &q), reference::dot(&p, &q)));
                assert!(same_dd(dot(&p, &p), reference::dot(&p, &p)));
                assert!(same_dd(dot4(&p, &q), reference::dot4(&p, &q)));
                let y: Vec<f64> = q.iter().map(|d| d.hi() * 1e150).collect();
                assert!(same_dd(dot_mixed(&p, &y), reference::dot_mixed(&p, &y)));
                let x: Vec<f64> = p.iter().map(|d| d.hi()).collect();
                assert!(same_dd(sum2(&x), reference::sum2(&x).result()));
                assert!(same_dd(dot2(&x, &y), reference::dot2(&x, &y).result()));
                let (r, beta) = dot2_err(&x, &y);
                let (r0, beta0) = reference::dot2(&x, &y).result_with_bound(13);
                assert!(same_dd(r, r0) && same(beta, beta0));
            }
        }
    }

    proptest::proptest! {
        #![proptest_config(proptest::prelude::ProptestConfig::with_cases(2000))]
        /// (K1), scalar × SIMD, bit for bit, on random lengths, kinds of
        /// data and seeds.
        #[test]
        fn k1_simd_equals_scalar(kind in 0_u8..4, n in 0_usize..=67, seed in proptest::prelude::any::<u64>()) {
            proptest::prop_assert_eq!(k1_vectors(kind, n, seed), Ok(()));
        }

        #[test]
        fn k1_gemm_simd_equals_scalar(
            kind in 0_u8..4,
            m in 0_usize..40,
            k in 0_usize..7,
            n in 0_usize..5,
            seed in proptest::prelude::any::<u64>(),
        ) {
            proptest::prop_assert_eq!(k1_gemm(kind, m, k, n, seed), Ok(()));
        }
    }
}