xingo_extprec/eft.rs
1//! # Chapter 11.1 — Error-free transformations
2//!
3//! ## Purpose
4//! The three primitives of the crate. Each rewrites the exact result of one
5//! `f64` operation as a pair of `f64` values: the rounded result and the
6//! rounding error, which — the fact everything else rests on — is itself an
7//! `f64`.
8//!
9//! ## Notation
10//! `F` is the set of `f64` values, `RN(·)` rounding to nearest (ties to
11//! even), `u = 2⁻⁵³`, `η = 2⁻¹⁰⁷⁴` the smallest positive subnormal, `Ω` the
12//! largest finite `f64`. For binary64 the precision is `p = 53` and the
13//! minimal exponent `e_min = −1022`.
14//!
15//! ## Algorithms
16//! **Algorithm S (TwoSum; Knuth, after Møller).** Input `a, b ∈ F`.
17//!
18//! S1. `s ← RN(a + b)`.
19//! S2. `a′ ← RN(s − b)`; `b′ ← RN(s − a′)`.
20//! S3. `δ_a ← RN(a − a′)`; `δ_b ← RN(b − b′)`.
21//! S4. `e ← RN(δ_a + δ_b)`. Return `(s, e)`.
22//!
23//! Six operations, no branch, no condition on the operands.
24//!
25//! **Algorithm F (Fast2Sum; Dekker).** Input `a, b ∈ F` with `e_a ≥ e_b`
26//! (the exponents; a zero has the least one), which holds in particular
27//! when `|a| ≥ |b|` or `a = 0` — the form in which the requirement is
28//! usually stated. The weaker form matters: under cancellation the
29//! additions of Chapter 11.2 call F with `|a| < |b|` in the same binade
30//! (`a = −2⁻⁵²`, `b ≈ −1.23 · 2⁻⁵²` in a test of this crate), where the
31//! proofs of Joldes, Muller & Popescu rely on the exponent condition.
32//!
33//! F1. `s ← RN(a + b)`.
34//! F2. `z ← RN(s − a)`.
35//! F3. `e ← RN(b − z)`. Return `(s, e)`.
36//!
37//! **Algorithm P (2ProdFMA).** Input `a, b ∈ F`.
38//!
39//! P1. `p ← RN(a b)`.
40//! P2. `e ← RN(a b − p)`, one fused multiply-add. Return `(p, e)`.
41//!
42//! ## Invariants
43//! (T1) *Sums.* If `s` is finite, Algorithm F returns `s = RN(a + b)` and
44//! `s + e = a + b` exactly, and so does Algorithm S unless `|a| = Ω`
45//! — also when subnormal numbers occur: an `f64` addition whose
46//! result is subnormal is exact, so the rounding error of a sum is
47//! always representable. The exception: with `a = ±Ω` step S2 can
48//! overflow although S1 did not (`a′ = RN(a + δ)` for the rounding
49//! error `δ` of S1, which reaches `ulp(Ω)/2`: `a = Ω`, `b = −3 ·
50//! 2⁹⁷⁰`), and `e` is then not finite. `DoubleDouble::from_sum` and
51//! the additions of Chapter 11.2 detect it (their step E).
52//! (T2) *Products.* If `p` is finite and `a b = 0` or `|a b| ≥ 2⁻⁹⁶⁹`,
53//! Algorithm P returns `p = RN(a b)` and `p + e = a b` exactly. The
54//! exact condition is `e_a + e_b ≥ e_min + p − 1 = −970` on the
55//! exponents of `a` and `b` (the error `a b − p` is a multiple of
56//! `2^(e_a + e_b − 2p + 2)`, which must be at least `η`); `|a b| ≥
57//! 2⁻⁹⁶⁹` implies it, and it can fail for any smaller bound. Otherwise
58//! `e` is the *rounded* error and `|a b − (p + e)| ≤ η/2`.
59//! (T3) *Normalized.* In (T1), and in (T2) when the product is exact, `|e|
60//! ≤ ulp(s)/2` (resp. `ulp(p)/2`) and `RN(s + e) = s`: the pair is a
61//! normalized double-double (invariant D1 of Chapter 11.2). When the
62//! error of a product is *rounded* (below the range of (T2)) it may
63//! become exactly `±ulp(p)/2` with `p` odd, and `(p, e)` is then not
64//! normalized: `DoubleDouble::from_product` adds one Fast2Sum, which
65//! is exact there (T1).
66//! (T4) *Non-finite.* If `s` (resp. `p`) is infinite or NaN, `e` is NaN or
67//! infinite and carries no information; the callers of this crate
68//! test the leading component (invariant D2).
69//!
70//! ## References
71//! Møller, "Quasi double-precision in floating point addition", BIT 5
72//! (1965); Knuth, TAOCP vol. 2, §4.2.2, Theorem B; Dekker, "A
73//! floating-point technique for extending the available precision", Numer.
74//! Math. 18 (1971); Ogita, Rump & Oishi, "Accurate sum and dot product",
75//! SIAM J. Sci. Comput. 26 (2005), Theorem 3.4 and Algorithm 3.5
76//! (TwoProductFMA); Joldes, Muller & Popescu, ACM TOMS 44 (2017),
77//! Algorithms 1–3 (the condition of (T2) is that of their Fast2Mult);
78//! Muller et al., *Handbook of Floating-Point Arithmetic*, 2nd ed. (2018),
79//! §4.3–4.4.
80
81/// `(s, e)` with `s = fl(a + b)` and `s + e = a + b` exactly (Knuth's
82/// TwoSum: 6 flops, no branch, no condition on the operands). Exact unless
83/// `s` overflows — or `a = ±Ω`, where an intermediate difference can
84/// overflow and leave `e` non-finite (invariant T1 of Chapter 11.1).
85#[inline]
86#[must_use]
87pub fn two_sum(a: f64, b: f64) -> (f64, f64) {
88 let s = a + b; // S1
89 let a1 = s - b; // S2
90 let b1 = s - a1;
91 let da = a - a1; // S3
92 let db = b - b1;
93 (s, da + db) // S4
94}
95
96/// The binary exponent field of `x`, subnormals and zeros sharing the
97/// least one.
98#[inline]
99fn exponent_field(x: f64) -> u64 {
100 ((x.to_bits() >> 52) & 0x7ff).max(1)
101}
102
103/// As [`two_sum`] in 3 flops, **requires** `|a| ≥ |b|` or `a = 0` (Dekker's
104/// Fast2Sum); the requirement is a `debug_assert!`.
105///
106/// Precisely, the algorithm is exact whenever the exponent of `a` is at
107/// least that of `b` (Algorithm F of Chapter 11.1), and that — the weaker
108/// condition, which `|a| ≥ |b|` implies — is what the assertion tests.
109#[inline]
110#[must_use]
111#[allow(clippy::float_cmp)] // the precondition is an exact comparison
112pub fn fast_two_sum(a: f64, b: f64) -> (f64, f64) {
113 // A non-finite operand passes: those cases are the callers' business
114 // (T4).
115 debug_assert!(
116 a == 0.0
117 || b == 0.0
118 || !a.is_finite()
119 || !b.is_finite()
120 || exponent_field(a) >= exponent_field(b),
121 "fast_two_sum requires |a| >= |b| or a = 0 (a = {a:e}, b = {b:e})"
122 );
123 let s = a + b; // F1
124 let z = s - a; // F2
125 (s, b - z) // F3
126}
127
128/// `(p, e)` with `p = fl(a · b)` and `p + e = a · b` exactly, by one fused
129/// multiply-add. Exact when `a b = 0` or `|a b| ≥ 2⁻⁹⁶⁹` and `p` does not
130/// overflow; otherwise `|a b − (p + e)| ≤ η`.
131#[inline]
132#[must_use]
133pub fn two_prod(a: f64, b: f64) -> (f64, f64) {
134 let p = a * b; // P1
135 (p, a.mul_add(b, -p)) // P2
136}
137
138#[cfg(test)]
139#[allow(clippy::disallowed_methods)] // L2.4 (Chapter 11.11): the tests may use the libm of `f64` (clippy.toml)
140#[allow(clippy::float_cmp)] // the tests compare exact values
141mod tests {
142 use super::*;
143
144 const U: f64 = 1.110_223_024_625_156_5e-16; // 2^-53
145
146 #[test]
147 fn two_sum_recovers_the_rounding_error() {
148 // 1 + 2^-53 rounds to 1 (tie to even); the error is 2^-53.
149 assert_eq!(two_sum(1.0, U), (1.0, U));
150 assert_eq!(two_sum(U, 1.0), (1.0, U));
151 // No condition on the order or the signs.
152 assert_eq!(two_sum(1e16, -1.0), (1e16, -1.0));
153 assert_eq!(two_sum(3.0, 4.0), (7.0, 0.0));
154 // Subnormal sums are exact (T1).
155 let eta = f64::from_bits(1);
156 assert_eq!(two_sum(eta, eta), (2.0 * eta, 0.0));
157 }
158
159 #[test]
160 fn fast_two_sum_agrees_with_two_sum_when_ordered() {
161 // The last pair has |a| < |b| in the same binade: still exact.
162 for (a, b) in [
163 (1.0, U),
164 (1e16, -1.0),
165 (-8.0, 0.1),
166 (0.0, 5.0),
167 (0.3, 0.3),
168 (1.0, 1.75),
169 ] {
170 assert_eq!(fast_two_sum(a, b), two_sum(a, b));
171 }
172 }
173
174 #[test]
175 #[cfg(debug_assertions)]
176 #[should_panic(expected = "fast_two_sum requires")]
177 fn fast_two_sum_asserts_its_precondition() {
178 let _ = fast_two_sum(1.0, 2.0);
179 }
180
181 #[test]
182 fn two_prod_recovers_the_rounding_error() {
183 // (1 + 2^-52)^2 = 1 + 2^-51 + 2^-104.
184 let x = 1.0 + f64::EPSILON;
185 let (p, e) = two_prod(x, x);
186 assert_eq!(p, 1.0 + 2.0 * f64::EPSILON);
187 assert_eq!(e, f64::EPSILON * f64::EPSILON);
188 assert_eq!(two_prod(3.0, 4.0), (12.0, 0.0));
189 assert_eq!(two_prod(0.0, 5.0), (0.0, 0.0));
190 }
191
192 #[test]
193 fn two_prod_threshold_is_two_to_minus_969() {
194 // a = b = (1 + 2^-52) 2^-485: e_a + e_b = -970, the last exact case;
195 // a b ≈ 2^-970 (1 + 2^-51), below 2^-969 — the bound of the docs is
196 // sufficient, not necessary.
197 let x = 1.0 + f64::EPSILON;
198 let a = x * 2f64.powi(-485);
199 let (p, e) = two_prod(a, a);
200 assert_eq!(p, (1.0 + 2.0 * f64::EPSILON) * 2f64.powi(-970));
201 assert_eq!(e, f64::from_bits(1)); // 2^-104 · 2^-970 = η: exact
202 // One exponent lower the error 2^-1075 is not representable.
203 let b = x * 2f64.powi(-486);
204 let (p, e) = two_prod(a, b);
205 assert_eq!(p, (1.0 + 2.0 * f64::EPSILON) * 2f64.powi(-971));
206 assert_eq!(e, 0.0); // η/2 rounds to even: |a b − (p + e)| = η/2
207 }
208
209 #[test]
210 fn non_finite_sums_have_no_error_term() {
211 let (s, e) = two_sum(f64::MAX, f64::MAX);
212 assert!(s.is_infinite() && !e.is_finite());
213 let (p, e) = two_prod(f64::MAX, 2.0);
214 assert!(p.is_infinite() && !e.is_finite());
215 }
216}