Skip to main content

xingo_sparse/
real.rs

1//! # Chapter 5.6 — Scalars and comparisons
2//!
3//! ## Purpose
4//! The containers and the factorization are written once, for any scalar
5//! type `T` that behaves like a real number with rounding: `f64` today,
6//! double-double and quad-double from `xingo-extprec` (trilha L2). This
7//! chapter fixes that interface, [`Real`], and the *only* functions of the
8//! crate that compare scalar values (Chapter 5, §5.C).
9//!
10//! ## Notation
11//! `T` is the scalar type, `ε_T` its machine epsilon ([`Real::EPSILON`]).
12//! For finite `a`, `b` and a tolerance `ε ≥ 0` let `s(a, b) = max(1, |a|,
13//! |b|)` (the scale of `xingo_core::Tolerances`, Chapter 1.3). Then
14//!
15//! * `lt(a, b)` — `a < b` exactly, written `b − a > 0·s(a, b)` for finite
16//!   values and `a < b` otherwise: the definition of
17//!   `Tolerances::lt(a, b, 0.0)`, kept *as an expression*, so that the
18//!   `f64` instance performs the very operations of the first edition;
19//! * `le(a, b, ε)` — `¬ lt_ε(b, a)`; `approx_eq(a, b, ε)` — `|a − b| ≤
20//!   ε·s(a, b)`, exact when a value is infinite;
21//! * `is_zero(x, ε)` — `|x| ≤ ε` (a drop test); `is_exact_zero(x)` —
22//!   `x = 0` (a structural test: is the entry stored?).
23//!
24//! ## Requirements on `T`
25//! (R1) The field operations are the correctly rounded ones of `T` (no
26//!      fused or reassociated arithmetic is assumed anywhere).
27//! (R2) `PartialOrd` is a total order on the values that occur: NaN never
28//!      enters a factorization (debug builds assert it in the comparisons).
29//! (R3) `Sum` adds in iteration order starting from the type's additive
30//!      identity for sums — for `f64`, the standard library's
31//!      `Iterator::sum`, which the first edition used; requiring it keeps
32//!      the order of every dot product of the solves unchanged.
33//! (R4) `from_f64(to_f64(x))` is `x` for `f64`; for the extended types
34//!      `to_f64` is the nearest `f64` and `from_f64` exact.
35//!
36//! ## Why a trait of this size
37//! A threshold LU needs the field operations, `abs`, `max` and a total
38//! order (pivot search and tests), `is_finite` (input validation), and the
39//! conversion of `f64` thresholds into `T`. `sqrt`, `recip` and `mul_add`
40//! are in the contract for the KKT solver (L1.5) and are unused by the LU;
41//! they are part of the trait so that implementors see the whole
42//! interface once. faer's `RealField` is the model, without its SIMD
43//! surface (D-0080, Q1).
44//!
45//! ## References
46//! Knuth, TAOCP vol. 2, §4.2.2; Higham, *Accuracy and Stability of
47//! Numerical Algorithms* (2002), ch. 1–2; faer's `RealField` (read, not
48//! copied); Chapter 1.3 of the solver (`Tolerances`).
49
50use core::fmt::Debug;
51use core::iter::Sum;
52use core::ops::{Add, AddAssign, Div, Mul, MulAssign, Neg, Sub, SubAssign};
53
54/// The scalar type of every container and factorization of the crate.
55///
56/// Implemented for `f64`; `xingo-extprec` implements it for its extended
57/// types (trilha L2). A total order is required (pivot search and pivot
58/// tests), so intervals are not `Real` (D-0080, Q2). See the module
59/// documentation for the requirements (R1)–(R4).
60pub trait Real:
61    Copy
62    + Debug
63    + PartialOrd
64    + Add<Output = Self>
65    + Sub<Output = Self>
66    + Mul<Output = Self>
67    + Div<Output = Self>
68    + Neg<Output = Self>
69    + AddAssign
70    + SubAssign
71    + MulAssign
72    + Sum
73    + 'static
74{
75    /// The additive identity.
76    const ZERO: Self;
77    /// The multiplicative identity.
78    const ONE: Self;
79    /// Machine epsilon of the type (`2⁻⁵²` for `f64`).
80    const EPSILON: Self;
81    /// The value of an `f64` (exact for `f64` and the extended types).
82    fn from_f64(x: f64) -> Self;
83    /// The nearest `f64` (lossy for the extended types).
84    fn to_f64(self) -> f64;
85    /// `|x|`.
86    #[must_use]
87    fn abs(self) -> Self;
88    /// `√x`.
89    #[must_use]
90    fn sqrt(self) -> Self;
91    /// `1 / x`.
92    #[must_use]
93    fn recip(self) -> Self;
94    /// `self · a + b` with a single rounding where the type allows.
95    #[must_use]
96    fn mul_add(self, a: Self, b: Self) -> Self;
97    /// `true` iff the value is neither infinite nor NaN.
98    fn is_finite(self) -> bool;
99    /// The larger of two values, with the NaN rule of `f64::max`.
100    #[must_use]
101    fn max(self, other: Self) -> Self;
102    /// The smaller of two values, with the NaN rule of `f64::min`.
103    #[must_use]
104    fn min(self, other: Self) -> Self;
105}
106
107impl Real for f64 {
108    const ZERO: Self = 0.0;
109    const ONE: Self = 1.0;
110    const EPSILON: Self = f64::EPSILON;
111    #[inline]
112    fn from_f64(x: f64) -> Self {
113        x
114    }
115    #[inline]
116    fn to_f64(self) -> f64 {
117        self
118    }
119    #[inline]
120    fn abs(self) -> Self {
121        f64::abs(self)
122    }
123    #[inline]
124    fn sqrt(self) -> Self {
125        f64::sqrt(self)
126    }
127    #[inline]
128    fn recip(self) -> Self {
129        f64::recip(self)
130    }
131    #[inline]
132    fn mul_add(self, a: Self, b: Self) -> Self {
133        f64::mul_add(self, a, b)
134    }
135    #[inline]
136    fn is_finite(self) -> bool {
137        f64::is_finite(self)
138    }
139    #[inline]
140    fn max(self, other: Self) -> Self {
141        f64::max(self, other)
142    }
143    #[inline]
144    fn min(self, other: Self) -> Self {
145        f64::min(self, other)
146    }
147}
148
149/// A second scalar for the tests of the generic code (Chapter 5.17 among
150/// others): `f32`, with the inherent methods, as `f64` above. Not part of
151/// the public API — the extended types of `xingo-extprec` are the intended
152/// second instance.
153#[cfg(test)]
154impl Real for f32 {
155    const ZERO: Self = 0.0;
156    const ONE: Self = 1.0;
157    const EPSILON: Self = f32::EPSILON;
158    #[inline]
159    #[allow(clippy::cast_possible_truncation)] // the nearest f32 is the contract (R4)
160    fn from_f64(x: f64) -> Self {
161        x as f32
162    }
163    #[inline]
164    fn to_f64(self) -> f64 {
165        f64::from(self)
166    }
167    #[inline]
168    fn abs(self) -> Self {
169        f32::abs(self)
170    }
171    #[inline]
172    fn sqrt(self) -> Self {
173        f32::sqrt(self)
174    }
175    #[inline]
176    fn recip(self) -> Self {
177        f32::recip(self)
178    }
179    #[inline]
180    fn mul_add(self, a: Self, b: Self) -> Self {
181        f32::mul_add(self, a, b)
182    }
183    #[inline]
184    fn is_finite(self) -> bool {
185        f32::is_finite(self)
186    }
187    #[inline]
188    fn max(self, other: Self) -> Self {
189        f32::max(self, other)
190    }
191    #[inline]
192    fn min(self, other: Self) -> Self {
193        f32::min(self, other)
194    }
195}
196
197// The comparisons of the crate. This is the one place where scalar values
198// meet `<`, `>` or `==` (Chapter 5, §5.C); the definitions are those of
199// `xingo_core::Tolerances` (Chapter 1.3), generic in `T`.
200
201/// The scale `s(a, b) = max(1, |a|, |b|)`.
202#[inline]
203fn scale<T: Real>(a: T, b: T) -> T {
204    T::ONE.max(a.abs()).max(b.abs())
205}
206
207/// `a < b` exactly (`Tolerances::lt(a, b, 0.0)`).
208#[inline]
209pub(crate) fn lt<T: Real>(a: T, b: T) -> bool {
210    lt_eps(a, b, T::ZERO)
211}
212
213/// Strict tolerant order `a <_ε b`: `b − a > ε·s(a, b)`; exact when a
214/// value is infinite.
215#[inline]
216pub(crate) fn lt_eps<T: Real>(a: T, b: T, eps: T) -> bool {
217    debug_assert!(!is_nan(a) && !is_nan(b), "lt called with NaN");
218    if a.is_finite() && b.is_finite() {
219        b - a > eps * scale(a, b)
220    } else {
221        a < b
222    }
223}
224
225/// Tolerant order `a ≤_ε b`, defined as `¬(b <_ε a)`.
226#[inline]
227#[cfg_attr(not(test), allow(dead_code))] // the tests' oracles use it
228pub(crate) fn le<T: Real>(a: T, b: T, eps: T) -> bool {
229    !lt_eps(b, a, eps)
230}
231
232/// `a ≤ b` exactly, without the scale (for ratios in `[0, 1]` such as
233/// densities, where the two definitions coincide).
234#[inline]
235pub(crate) fn le_exact<T: Real>(a: T, b: T) -> bool {
236    debug_assert!(!is_nan(a) && !is_nan(b), "le_exact called with NaN");
237    a <= b
238}
239
240/// `|a − b| ≤ ε·s(a, b)`; exact when a value is infinite.
241#[inline]
242pub(crate) fn approx_eq<T: Real>(a: T, b: T, eps: T) -> bool {
243    debug_assert!(!is_nan(a) && !is_nan(b), "approx_eq called with NaN");
244    if a.is_finite() && b.is_finite() {
245        (a - b).abs() <= eps * scale(a, b)
246    } else {
247        a == b
248    }
249}
250
251/// `|x| ≤ ε`: `x` is negligible for the drop tolerance `ε`.
252#[inline]
253pub(crate) fn is_zero<T: Real>(x: T, eps: T) -> bool {
254    debug_assert!(!is_nan(x), "is_zero called with NaN");
255    x.abs() <= eps
256}
257
258/// `x = 0` exactly (or `−0`): a structural test.
259#[inline]
260pub(crate) fn is_exact_zero<T: Real>(x: T) -> bool {
261    x == T::ZERO
262}
263
264/// `x` is NaN (it is not equal to itself).
265#[inline]
266#[allow(clippy::eq_op)] // the NaN test is x ≠ x
267pub(crate) fn is_nan<T: Real>(x: T) -> bool {
268    x != x
269}
270
271#[cfg(test)]
272mod tests {
273    use super::*;
274
275    #[test]
276    fn comparisons_match_their_definitions() {
277        assert!(lt(1.0, 2.0) && !lt(2.0, 2.0) && !lt(3.0, 2.0));
278        assert!(lt(f64::NEG_INFINITY, -1e308) && !lt(f64::INFINITY, f64::INFINITY));
279        assert!(le(2.0, 2.0, 0.0) && le(2.0 + 1e-13, 2.0, 1e-12));
280        assert!(approx_eq(1e6, 1e6 + 1e-7, 1e-12));
281        assert!(approx_eq(f64::INFINITY, f64::INFINITY, 0.0));
282        assert!(!approx_eq(1e308, f64::INFINITY, 1e-9));
283        assert!(is_zero(1e-13, 1e-12) && !is_zero(1e-11, 1e-12));
284        assert!(is_exact_zero(-0.0) && !is_exact_zero(f64::MIN_POSITIVE));
285        assert!(is_nan(f64::NAN) && !is_nan(1.0));
286    }
287
288    #[test]
289    fn f64_is_real() {
290        fn roundtrip<T: Real>(x: f64) -> f64 {
291            T::from_f64(x).to_f64()
292        }
293        assert!(approx_eq(roundtrip::<f64>(0.1), 0.1, 0.0));
294        assert!(approx_eq(Real::abs(-2.0_f64), 2.0, 0.0));
295        assert!(approx_eq(Real::mul_add(2.0_f64, 3.0, 1.0), 7.0, 0.0));
296        assert!(approx_eq(Real::sqrt(4.0_f64), 2.0, 0.0));
297        assert!(approx_eq(Real::recip(4.0_f64), 0.25, 0.0));
298        assert!(approx_eq(Real::min(4.0_f64, 1.0), 1.0, 0.0));
299        assert!(approx_eq(<f64 as Real>::EPSILON, f64::EPSILON, 0.0));
300        let s: f64 = [1.0, 2.0, 3.0].into_iter().sum();
301        assert!(approx_eq(s, 6.0, 0.0));
302    }
303}