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}