xingo_statla/cholesky.rs
1//! # Chapter 12.2 — Cholesky with rank-1 update and downdate
2//!
3//! ## Purpose
4//! A covariance, information or Gram matrix `A` changes by `± x xᵀ` — an
5//! observation enters or leaves a recursive least-squares fit, a Kalman
6//! filter absorbs a measurement, a Gaussian-process refit drops a point —
7//! and its upper Cholesky factor `R` (`RᵀR = A`) must follow in `O(n²)`
8//! instead of the `O(n³)` of a refactorization. [`Cholesky`] keeps `R`
9//! under `update` (`A + x xᵀ`) and `downdate` (`A − x xᵀ`), with solves,
10//! the whitening `R⁻ᵀ b` and the log-determinant.
11//!
12//! ## Notation
13//! `A ∈ T^{n×n}` symmetric positive definite (only its upper triangle is
14//! read); `R` upper triangular with `r_jj > 0`; `x ∈ T^n`; `u` the unit
15//! roundoff of `T`; `A_t` the matrix the sequence of operations defines.
16//! A rotation `G = (c, s)` acts as `(p, q) ↦ (c p + s q, c q − s p)`
17//! (Chapter 12.0.4).
18//!
19//! ## Algorithm F (factor)
20//! F1. \[Check.\] `A` square, its upper triangle finite, the options valid.
21//! F2. \[Factor.\] Copy the upper triangle into the lower triangle of a
22//! block `W` (`w_ij = a_ji`, `i ≥ j`) and run `K::potrf` (Algorithm P of
23//! Chapter 5.16): `W = L Lᵀ`; a nonpositive pivot at `j` is
24//! [`StatlaError::NotPositiveDefinite`]` { column: j }`.
25//! F3. \[Pivot test.\] Reject column `j` unless `l_jj² > pivot_tol · a_jj`
26//! (and `l_jj` is finite and positive, whatever the kernel).
27//! F4. \[Transpose.\] `R ← Lᵀ`, strict lower triangle zero.
28//!
29//! ## Algorithm U (update, `A + x xᵀ`; LINPACK `dchud`)
30//! U0. \[Check.\] `x.len() = n` and `x` finite — the only failures, checked
31//! before any write (H3).
32//! U1. \[Loop.\] For `j = 0, …, n − 1`: `ξ ← x_j`; apply the rotations `G_0
33//! … G_{j−1}` already found to the pairs `(r_ij, ξ)`, `i = 0, …, j − 1`,
34//! in that order: `(r_ij, ξ) ← G_i (r_ij, ξ)`.
35//! U2. \[Rotate.\] Find `G_j` with `G_j (r_jj, ξ) = (ρ, 0)`, `ρ ≥ 0`
36//! (Algorithm G of 12.0.4, the safe `hypot`); `r_jj ← ρ`.
37//! Cost `2n²` flops (`≈ 3n²` with the scaling of G2). Since `ρ ≥ r_jj >
38//! 0`, (H1) is kept.
39//!
40//! ## Algorithm C (downdate, `A − x xᵀ`; LINPACK `dchdd`, Saunders 1972)
41//! C0. \[Check.\] `x.len() = n`, `x` finite.
42//! C1. \[Solve.\] `Rᵀ a = x` (forward substitution).
43//! C2. \[Test.\] `α² ← 1 − ‖a‖²` (‖a‖ by Algorithm N); if `α²` is not
44//! finite or `α² ≤ downdate_tol`, return
45//! [`StatlaError::DowndateIndefinite`] — **before any change to `R`**
46//! (H3 for free). (`RᵀR − xxᵀ = Rᵀ(I − aaᵀ)R` is positive definite iff
47//! `‖a‖ < 1`.)
48//! C3. \[Rotations.\] `α ← √α²`; for `i = n − 1, …, 0`: `μ ← α + |a_i|`,
49//! `α̂ ← α/μ`, `b ← a_i/μ`, `ν ← √(α̂² + b²)`, `c_i ← α̂/ν`, `s_i ← b/ν`,
50//! `α ← μν`.
51//! C3′. \[Diagonal first.\] The new diagonal is `r_jj ← c_j r_jj` (step C4
52//! at `i = j`, where `ξ = 0`). If one of them is not finite and
53//! positive (only an underflow can do that), return
54//! `DowndateIndefinite` with the margin of C2 — still before any
55//! write. *An addition of this edition to LINPACK's algorithm.*
56//! C4. \[Apply.\] For each column `j`: `ξ ← 0`; for `i = j, …, 0`: `(r_ij,
57//! ξ) ← (c_i r_ij − s_i ξ, c_i ξ + s_i r_ij)`.
58//! C5. \[Signs.\] Flip the rows with `r_ii < 0` (none, after C3′; kept as
59//! the contract states it, so that (H1) does not rest on C3′ alone).
60//! Cost `≈ 3n²` flops plus the `n²` of C1. Backward stable in the mixed
61//! sense of Stewart (1979). The forward error against a refactorization
62//! grows like `κ₂(R̃) u` — the error of any algorithm, because two
63//! refactorizations of `A_t` perturbed at the level `u` already differ by
64//! that much (pilot s01, table A).
65//!
66//! ## Solves and the determinant
67//! `solve`: `Rᵀy = b` forward, then `Rx = y` backward (both
68//! column-oriented on `R`). `solve_upper_t`: the forward half only, `b ←
69//! R⁻ᵀb`, so `‖R⁻ᵀb‖² = bᵀA⁻¹b`. `log2_det_parts`: `det R = Π r_jj = m ·
70//! 2^e` with `m ∈ [1, 2)`, accumulated by splitting each `r_jj = f_j 2^{k_j}`
71//! with powers of two read off the `f64` bits (exact scalings), so it
72//! neither overflows nor underflows for any `n`; then `ln det A = 2(ln m +
73//! e ln 2)` in the caller's precision.
74//!
75//! ## Invariants
76//! (H1) `R` upper triangular (strict lower triangle exactly zero),
77//! `r_jj > 0`, every entry finite — [`Cholesky::check_invariants`],
78//! `debug_assert!` after each of F, U, C.
79//! (H2) `‖RᵀR − A_t‖_F ≤ c_H · n · u · ‖A_t‖_F` after any sequence; `c_H =
80//! 8` in the tests (`tests/cholesky.rs`, against `A_t` and `RᵀR` in
81//! double-double; the norm along the path when downdates cancel more
82//! than half of `A`).
83//! (H3) A failed `update`/`downdate` leaves `R` bit for bit unchanged:
84//! U0 and C0–C3′ read `R` and write only local vectors.
85//!
86//! ## Acceptance (L3.2, S9 of D-0127) and what was measured
87//! In `f64` and `DoubleDouble`, `n ≤ 200`, `κ(A_t)` from `10` to `10¹²`
88//! (`tests/cholesky.rs`, proptests and fixed seeds):
89//! (i) `update∘downdate` and `downdate∘update` within `10 n u` of the
90//! original factor (relative Frobenius);
91//! (ii) backward error (H2) `≤ c_H n u` at every `κ`;
92//! (iii) forward error against a refactorization of `A_t` `≤ 10⁻¹²` where
93//! `κ(A_t) ≤ 10⁸`, and elsewhere `≤ 10×` the distance between two
94//! refactorizations of `A_t` perturbed at the level `u`;
95//! (iv) a failed operation leaves the factor bit for bit unchanged.
96//!
97//! **What holds.** (i), (ii), (iv) per instance with wide margins
98//! (`upd∘dd`, `dd∘upd` `≤ 4.9 n u` at `n = 3`, `≤ 0.05 n u` for `n ≥ 50`).
99//! (iii) as worded does **not** hold per instance: the forward error of
100//! the downdate is governed by `1 − ‖a‖²`, not by `κ` alone — `n = 2`,
101//! `κ = 10⁶` gave `9.4·10⁻¹²`; at `κ = 10⁸`, `n = 100`, 10 of 200 seeds
102//! exceed `10⁻¹²`; the per-instance ratio to the distance between two
103//! refactorizations reaches 40–150 for `n ≤ 3`. The tests enforce what was
104//! measured to hold — per instance `fwd ≤ 8 κ u` (the first-order bound of
105//! any algorithm working from `R`), and the pilot's aggregate form (the
106//! maximum over 20 seeds at `n = 100, 200`: `≤ 10⁻¹²` where `κ ≤ 10⁶`, `≤
107//! 10×` the maximum distance everywhere) — and keep the literal criterion
108//! as an ignored test (question Q-L32-2 of task L3.2, settled this way by
109//! D-0132). The measured
110//! values are in `.claude/scratch/l32/l32-tables.md`; the example
111//! `accuracy` regenerates them.
112//!
113//! ## References
114//! LINPACK Users' Guide (1979), ch. 10 (`dchud`, `dchdd`); Saunders (1972);
115//! Stewart, J. IMA 23 (1979); Gill, Golub, Murray & Saunders, Math. Comp.
116//! 28 (1974); Higham (2002), Theorem 10.3 (backward error of Cholesky);
117//! pilot s01 (`.claude/scratch/s01/s01-pilot`). All cited from memory.
118
119use xingo_sparse::{DenseBlock, DenseError, DenseKernel, NaiveDense, Real};
120
121use crate::real::{is_exact_zero, le_exact, lt};
122use crate::small::{Rot, axpy_sub, check_finite, check_len, dot, givens, norm2};
123use crate::{MatMut, MatRef, StatlaError};
124
125/// Options of [`Cholesky`]: every threshold of chapter 12.2 lives here.
126#[derive(Clone, Copy, Debug, PartialEq)]
127pub struct CholOptions {
128 /// Step F3: a pivot `d_j` is rejected unless `d_j > pivot_tol · a_jj`
129 /// (default `0`: reject only nonpositive pivots, as LAPACK `potrf`).
130 pub pivot_tol: f64,
131 /// Step C2: the downdate is rejected unless `1 − ‖a‖² > downdate_tol`
132 /// (default `0`, LINPACK's test). A positive value refuses downdates
133 /// whose result is too ill conditioned to be trusted (forward error ≈
134 /// `u / margin`; pilot table A).
135 pub downdate_tol: f64,
136}
137
138impl Default for CholOptions {
139 fn default() -> Self {
140 Self {
141 pivot_tol: 0.0,
142 downdate_tol: 0.0,
143 }
144 }
145}
146
147impl CholOptions {
148 /// Both thresholds finite and nonnegative (a negative `downdate_tol`
149 /// would let C3 take the square root of a nonpositive `α²`).
150 fn validate(&self) -> Result<(), StatlaError> {
151 let ok = |v: f64| v.is_finite() && le_exact(0.0, v);
152 if !ok(self.pivot_tol) {
153 return Err(StatlaError::InvalidArgument {
154 what: "CholOptions::pivot_tol must be finite and >= 0",
155 });
156 }
157 if !ok(self.downdate_tol) {
158 return Err(StatlaError::InvalidArgument {
159 what: "CholOptions::downdate_tol must be finite and >= 0",
160 });
161 }
162 Ok(())
163 }
164}
165
166/// The upper Cholesky factor `R` of a symmetric positive definite `A =
167/// RᵀR`, kept up to date under `A ← A ± x xᵀ` (Chapter 12.2: Algorithms
168/// F, U, C).
169///
170/// ```
171/// use xingo_statla::{CholOptions, Cholesky, MatRef};
172/// // A = [[4, 2], [2, 3]] (upper triangle read).
173/// let a = [4.0, 0.0, 2.0, 3.0];
174/// let mut c = Cholesky::factor(MatRef::new(2, 2, 2, &a)?, &CholOptions::default())?;
175/// c.update(&[1.0, 1.0])?; // A + x xᵀ = [[5, 3], [3, 4]]
176/// let info = c.downdate(&[1.0, 1.0])?; // back to A
177/// assert!(info.margin > 0.0 && info.margin <= 1.0);
178/// let mut b = [6.0, 5.0]; // A · (1, 1)
179/// c.solve(&mut b)?;
180/// assert!((b[0] - 1.0).abs() < 1e-14 && (b[1] - 1.0).abs() < 1e-14);
181/// assert!(c.downdate(&[3.0, 0.0]).is_err()); // A − 9 e₀e₀ᵀ is indefinite
182/// # Ok::<(), xingo_statla::StatlaError>(())
183/// ```
184#[derive(Clone, Debug)]
185pub struct Cholesky<T: Real = f64, K: DenseKernel<T> = NaiveDense> {
186 r: DenseBlock<T>,
187 // Kept with the factor (the kernel it was built with); read again by
188 // the operations of v0.2 that refactor trailing blocks (S8).
189 #[allow(dead_code)]
190 kernel: K,
191 opts: CholOptions,
192}
193
194/// What a successful downdate saw.
195#[derive(Clone, Copy, Debug, PartialEq)]
196#[non_exhaustive]
197pub struct DowndateInfo {
198 /// `1 − ‖a‖²` of step C2, in `(downdate_tol, 1]`: near `0` means the
199 /// result is nearly singular and its forward error is large.
200 pub margin: f64,
201}
202
203impl<T: Real> Cholesky<T, NaiveDense> {
204 /// Factor the symmetric positive definite `A` (upper triangle read)
205 /// with the reference kernel.
206 ///
207 /// # Errors
208 /// [`StatlaError::InvalidArgument`] (not square, invalid options),
209 /// [`StatlaError::NonFinite`], [`StatlaError::NotPositiveDefinite`].
210 pub fn factor(a: MatRef<'_, T>, opts: &CholOptions) -> Result<Self, StatlaError> {
211 Self::factor_with(a, NaiveDense, opts)
212 }
213}
214
215impl<T: Real, K: DenseKernel<T>> Cholesky<T, K> {
216 /// As [`Cholesky::factor`] with the dense kernel `kernel`.
217 ///
218 /// # Errors
219 /// As [`Cholesky::factor`].
220 pub fn factor_with(
221 a: MatRef<'_, T>,
222 kernel: K,
223 opts: &CholOptions,
224 ) -> Result<Self, StatlaError> {
225 // F1.
226 opts.validate()?;
227 let n = a.rows();
228 if a.cols() != n {
229 return Err(StatlaError::InvalidArgument {
230 what: "Cholesky::factor: matrix not square",
231 });
232 }
233 let mut w = DenseBlock::zeros(n, n);
234 for j in 0..n {
235 let col = a.col(j).unwrap_or(&[]);
236 for (i, &v) in col.iter().enumerate().take(j + 1) {
237 if !v.is_finite() {
238 return Err(StatlaError::NonFinite {
239 what: "a",
240 index: i + j * n,
241 });
242 }
243 // F2: w_ji = a_ij for i ≤ j (lower triangle of W).
244 w.data[j + i * n] = v;
245 }
246 }
247 // F2.
248 kernel.potrf(&mut w).map_err(|e| match e {
249 DenseError::NotPositiveDefinite { position } => {
250 StatlaError::NotPositiveDefinite { column: position }
251 }
252 DenseError::Dimension => StatlaError::InvalidArgument {
253 what: "Cholesky::factor: the kernel rejected the dimensions",
254 },
255 })?;
256 // F3.
257 let tol = T::from_f64(opts.pivot_tol);
258 for j in 0..n {
259 let l = w.data[j + j * n];
260 let ajj = a.get(j, j).unwrap_or(T::ZERO);
261 if !l.is_finite() || !lt(T::ZERO, l) || le_exact(l * l, tol * ajj) {
262 return Err(StatlaError::NotPositiveDefinite { column: j });
263 }
264 }
265 // F4.
266 let mut r = DenseBlock::zeros(n, n);
267 for j in 0..n {
268 for i in 0..=j {
269 r.data[i + j * n] = w.data[j + i * n];
270 }
271 }
272 let c = Self {
273 r,
274 kernel,
275 opts: *opts,
276 };
277 debug_assert_eq!(c.check_invariants(), Ok(()), "(H1) after factor");
278 Ok(c)
279 }
280
281 /// Adopt an existing upper factor (for instance the `R` of a
282 /// [`crate::Qr`]: the Q-less QR of streaming regression *is* this type).
283 ///
284 /// # Errors
285 /// [`StatlaError::InvalidArgument`] if `r` is not square upper
286 /// triangular with positive diagonal (or the options are invalid);
287 /// [`StatlaError::NonFinite`].
288 pub fn from_upper(
289 r: DenseBlock<T>,
290 kernel: K,
291 opts: &CholOptions,
292 ) -> Result<Self, StatlaError> {
293 opts.validate()?;
294 let n = r.rows;
295 if r.cols != n || r.data.len() != n.saturating_mul(n) {
296 return Err(StatlaError::InvalidArgument {
297 what: "Cholesky::from_upper: not a square block",
298 });
299 }
300 check_finite("r", &r.data)?;
301 let c = Self {
302 r,
303 kernel,
304 opts: *opts,
305 };
306 c.check_invariants()
307 .map_err(|what| StatlaError::InvalidArgument { what })?;
308 Ok(c)
309 }
310
311 /// Order `n`.
312 #[must_use]
313 pub fn n(&self) -> usize {
314 self.r.rows
315 }
316
317 /// `R` (the strict lower triangle of the view is zero).
318 #[must_use]
319 pub fn upper(&self) -> MatRef<'_, T> {
320 MatRef::from_block(&self.r)
321 }
322
323 /// `R`, owned.
324 #[must_use]
325 pub fn into_upper(self) -> DenseBlock<T> {
326 self.r
327 }
328
329 /// `A ← A + x xᵀ` (Algorithm U).
330 ///
331 /// # Errors
332 /// [`StatlaError::Dimension`], [`StatlaError::NonFinite`]; the factor
333 /// is unchanged on error (H3).
334 pub fn update(&mut self, x: &[T]) -> Result<(), StatlaError> {
335 let n = self.n();
336 // U0.
337 check_len("x", n, x.len())?;
338 check_finite("x", x)?;
339 let mut rots = vec![Rot::IDENTITY; n];
340 let r = &mut self.r.data;
341 for j in 0..n {
342 // U1.
343 let mut xi = x[j];
344 let col = &mut r[j * n..(j + 1) * n];
345 for (rij, g) in col[..j].iter_mut().zip(&rots[..j]) {
346 let (p, q) = g.apply(*rij, xi);
347 *rij = p;
348 xi = q;
349 }
350 // U2.
351 let (g, rho) = givens(col[j], xi);
352 rots[j] = g;
353 col[j] = rho;
354 }
355 debug_assert_eq!(self.check_invariants(), Ok(()), "(H1) after update");
356 Ok(())
357 }
358
359 /// `A ← A − x xᵀ` (Algorithm C).
360 ///
361 /// # Errors
362 /// [`StatlaError::Dimension`], [`StatlaError::NonFinite`],
363 /// [`StatlaError::DowndateIndefinite`]; unchanged on error (H3).
364 pub fn downdate(&mut self, x: &[T]) -> Result<DowndateInfo, StatlaError> {
365 let n = self.n();
366 // C0.
367 check_len("x", n, x.len())?;
368 check_finite("x", x)?;
369 // C1.
370 let mut a = x.to_vec();
371 self.forward(&mut a);
372 // C2.
373 let nu = norm2(&a);
374 let alpha2 = T::ONE - nu * nu;
375 if !alpha2.is_finite() {
376 return Err(StatlaError::DowndateIndefinite {
377 margin: f64::NEG_INFINITY,
378 });
379 }
380 let margin = alpha2.to_f64();
381 if le_exact(alpha2, T::from_f64(self.opts.downdate_tol)) {
382 return Err(StatlaError::DowndateIndefinite { margin });
383 }
384 // C3.
385 let mut alpha = alpha2.sqrt();
386 let mut rots = vec![Rot::IDENTITY; n];
387 for i in (0..n).rev() {
388 let mu = alpha + a[i].abs();
389 let ah = alpha / mu;
390 let b = a[i] / mu;
391 let nu = (ah * ah + b * b).sqrt();
392 rots[i] = Rot {
393 c: ah / nu,
394 s: b / nu,
395 };
396 alpha = mu * nu;
397 }
398 // C3′.
399 for (j, g) in rots.iter().enumerate() {
400 let d = g.c * self.r.data[j + j * n];
401 if !d.is_finite() || !lt(T::ZERO, d) {
402 return Err(StatlaError::DowndateIndefinite { margin });
403 }
404 }
405 // C4.
406 let r = &mut self.r.data;
407 for j in 0..n {
408 let col = &mut r[j * n..(j + 1) * n];
409 let mut xi = T::ZERO;
410 for i in (0..=j).rev() {
411 let g = rots[i];
412 let rij = col[i];
413 col[i] = g.c * rij - g.s * xi;
414 xi = g.c * xi + g.s * rij;
415 }
416 }
417 // C5.
418 for i in 0..n {
419 if lt(self.r.data[i + i * n], T::ZERO) {
420 for j in i..n {
421 self.r.data[i + j * n] = -self.r.data[i + j * n];
422 }
423 }
424 }
425 debug_assert_eq!(self.check_invariants(), Ok(()), "(H1) after downdate");
426 Ok(DowndateInfo { margin })
427 }
428
429 /// `b ← R⁻ᵀ b` without checks (`b.len() = n`).
430 fn forward(&self, b: &mut [T]) {
431 let n = self.n();
432 for j in 0..n {
433 let col = &self.r.data[(j * n)..=(j * n + j)];
434 let s = b[j] - dot(&col[..j], &b[..j]);
435 b[j] = s / col[j];
436 }
437 }
438
439 /// `b ← R⁻¹ b` without checks.
440 fn backward(&self, b: &mut [T]) {
441 let n = self.n();
442 for j in (0..n).rev() {
443 let col = &self.r.data[(j * n)..=(j * n + j)];
444 let xj = b[j] / col[j];
445 b[j] = xj;
446 axpy_sub(xj, &col[..j], &mut b[..j]);
447 }
448 }
449
450 /// `b ← A⁻¹ b`.
451 ///
452 /// # Errors
453 /// [`StatlaError::Dimension`].
454 pub fn solve(&self, b: &mut [T]) -> Result<(), StatlaError> {
455 check_len("b", self.n(), b.len())?;
456 self.forward(b);
457 self.backward(b);
458 Ok(())
459 }
460
461 /// `B ← A⁻¹ B` for a block of right-hand sides.
462 ///
463 /// # Errors
464 /// [`StatlaError::Dimension`].
465 pub fn solve_block(&self, mut b: MatMut<'_, T>) -> Result<(), StatlaError> {
466 let cols = b.as_ref().cols();
467 check_len("b (rows)", self.n(), b.as_ref().rows())?;
468 for j in 0..cols {
469 if let Some(col) = b.col_mut(j) {
470 self.forward(col);
471 self.backward(col);
472 }
473 }
474 Ok(())
475 }
476
477 /// `b ← R⁻ᵀ b` (whitening: `‖R⁻ᵀ b‖² = bᵀA⁻¹b`, a Mahalanobis
478 /// distance).
479 ///
480 /// # Errors
481 /// [`StatlaError::Dimension`].
482 pub fn solve_upper_t(&self, b: &mut [T]) -> Result<(), StatlaError> {
483 check_len("b", self.n(), b.len())?;
484 self.forward(b);
485 Ok(())
486 }
487
488 /// `ln det A = 2 Σ ln r_jj`, returned as `(m, e)` with `det R = Π r_jj
489 /// = m · 2^e` exactly split, `m ∈ [1, 2)` (`(1, 0)` for `n = 0`): no `ln`
490 /// in [`Real`], so the caller forms `ln det A = 2 (ln m + e ln 2)` in
491 /// its own precision (`log₂ det R = log₂ m + e`).
492 #[must_use]
493 pub fn log2_det_parts(&self) -> (T, i64) {
494 let n = self.n();
495 let two = T::from_f64(2.0);
496 let half = T::from_f64(0.5);
497 let mut m = T::ONE;
498 let mut e: i64 = 0;
499 for j in 0..n {
500 let d = self.r.data[j + j * n];
501 let (f, k) = split_pow2(d);
502 m *= f;
503 e += k;
504 while le_exact(two, m) {
505 m *= half;
506 e += 1;
507 }
508 while lt(m, T::ONE) && lt(T::ZERO, m) {
509 m *= two;
510 e -= 1;
511 }
512 }
513 (m, e)
514 }
515
516 /// Invariant (H1).
517 ///
518 /// # Errors
519 /// The text of the violated invariant.
520 pub fn check_invariants(&self) -> Result<(), &'static str> {
521 let n = self.r.rows;
522 if self.r.cols != n || self.r.data.len() != n * n {
523 return Err("(H1) R is not a consistent square block");
524 }
525 for j in 0..n {
526 for i in 0..n {
527 let v = self.r.data[i + j * n];
528 if !v.is_finite() {
529 return Err("(H1) R has a non-finite entry");
530 }
531 if i > j && !is_exact_zero(v) {
532 return Err("(H1) R is not upper triangular");
533 }
534 if i == j && !lt(T::ZERO, v) {
535 return Err("(H1) R has a nonpositive diagonal entry");
536 }
537 }
538 }
539 Ok(())
540 }
541}
542
543/// `d = f · 2^k` with `2^k` the power of two of `d`'s `f64` value (exact
544/// scalings); `f ≈ [1, 2)` up to the rounding of `to_f64`, normalized by
545/// the caller.
546fn split_pow2<T: Real>(d: T) -> (T, i64) {
547 let bits = d.to_f64().to_bits();
548 let exp = i64::try_from((bits >> 52) & 0x7ff).unwrap_or(0);
549 if exp == 0 || exp == 0x7ff {
550 return (d, 0); // subnormal (normalized by the caller's loop) or not finite
551 }
552 let k = exp - 1023;
553 // 2^-k as f64: exact for k in −1022..=1023 (2^-1023 is subnormal but exact).
554 let inv = match u64::try_from(1023 - k) {
555 Ok(0) | Err(_) => f64::from_bits(1 << 51), // 2^-1023, subnormal and exact
556 Ok(b) => f64::from_bits(b << 52),
557 };
558 (d * T::from_f64(inv), k)
559}