Skip to main content

Module eft

Module eft 

Source
Expand description

§Chapter 11.1 — Error-free transformations

§Purpose

The three primitives of the crate. Each rewrites the exact result of one f64 operation as a pair of f64 values: the rounded result and the rounding error, which — the fact everything else rests on — is itself an f64.

§Notation

F is the set of f64 values, RN(·) rounding to nearest (ties to even), u = 2⁻⁵³, η = 2⁻¹⁰⁷⁴ the smallest positive subnormal, Ω the largest finite f64. For binary64 the precision is p = 53 and the minimal exponent e_min = −1022.

§Algorithms

Algorithm S (TwoSum; Knuth, after Møller). Input a, b ∈ F.

S1. s ← RN(a + b). S2. a′ ← RN(s − b); b′ ← RN(s − a′). S3. δ_a ← RN(a − a′); δ_b ← RN(b − b′). S4. e ← RN(δ_a + δ_b). Return (s, e).

Six operations, no branch, no condition on the operands.

Algorithm F (Fast2Sum; Dekker). Input a, b ∈ F with e_a ≥ e_b (the exponents; a zero has the least one), which holds in particular when |a| ≥ |b| or a = 0 — the form in which the requirement is usually stated. The weaker form matters: under cancellation the additions of Chapter 11.2 call F with |a| < |b| in the same binade (a = −2⁻⁵², b ≈ −1.23 · 2⁻⁵² in a test of this crate), where the proofs of Joldes, Muller & Popescu rely on the exponent condition.

F1. s ← RN(a + b). F2. z ← RN(s − a). F3. e ← RN(b − z). Return (s, e).

Algorithm P (2ProdFMA). Input a, b ∈ F.

P1. p ← RN(a b). P2. e ← RN(a b − p), one fused multiply-add. Return (p, e).

§Invariants

(T1) Sums. If s is finite, Algorithm F returns s = RN(a + b) and s + e = a + b exactly, and so does Algorithm S unless |a| = Ω — also when subnormal numbers occur: an f64 addition whose result is subnormal is exact, so the rounding error of a sum is always representable. The exception: with a = ±Ω step S2 can overflow although S1 did not (a′ = RN(a + δ) for the rounding error δ of S1, which reaches ulp(Ω)/2: a = Ω, b = −3 · 2⁹⁷⁰), and e is then not finite. DoubleDouble::from_sum and the additions of Chapter 11.2 detect it (their step E). (T2) Products. If p is finite and a b = 0 or |a b| ≥ 2⁻⁹⁶⁹, Algorithm P returns p = RN(a b) and p + e = a b exactly. The exact condition is e_a + e_b ≥ e_min + p − 1 = −970 on the exponents of a and b (the error a b − p is a multiple of 2^(e_a + e_b − 2p + 2), which must be at least η); |a b| ≥ 2⁻⁹⁶⁹ implies it, and it can fail for any smaller bound. Otherwise e is the rounded error and |a b − (p + e)| ≤ η/2. (T3) Normalized. In (T1), and in (T2) when the product is exact, |e| ≤ ulp(s)/2 (resp. ulp(p)/2) and RN(s + e) = s: the pair is a normalized double-double (invariant D1 of Chapter 11.2). When the error of a product is rounded (below the range of (T2)) it may become exactly ±ulp(p)/2 with p odd, and (p, e) is then not normalized: DoubleDouble::from_product adds one Fast2Sum, which is exact there (T1). (T4) Non-finite. If s (resp. p) is infinite or NaN, e is NaN or infinite and carries no information; the callers of this crate test the leading component (invariant D2).

§References

Møller, “Quasi double-precision in floating point addition”, BIT 5 (1965); Knuth, TAOCP vol. 2, §4.2.2, Theorem B; Dekker, “A floating-point technique for extending the available precision”, Numer. Math. 18 (1971); Ogita, Rump & Oishi, “Accurate sum and dot product”, SIAM J. Sci. Comput. 26 (2005), Theorem 3.4 and Algorithm 3.5 (TwoProductFMA); Joldes, Muller & Popescu, ACM TOMS 44 (2017), Algorithms 1–3 (the condition of (T2) is that of their Fast2Mult); Muller et al., Handbook of Floating-Point Arithmetic, 2nd ed. (2018), §4.3–4.4.

Functions§

exponent_field 🔒
The binary exponent field of x, subnormals and zeros sharing the least one.
fast_two_sum
As two_sum in 3 flops, requires |a| ≥ |b| or a = 0 (Dekker’s Fast2Sum); the requirement is a debug_assert!.
two_prod
(p, e) with p = fl(a · b) and p + e = a · b exactly, by one fused multiply-add. Exact when a b = 0 or |a b| ≥ 2⁻⁹⁶⁹ and p does not overflow; otherwise |a b − (p + e)| ≤ η.
two_sum
(s, e) with s = fl(a + b) and s + e = a + b exactly (Knuth’s TwoSum: 6 flops, no branch, no condition on the operands). Exact unless s overflows — or a = ±Ω, where an intermediate difference can overflow and leave e non-finite (invariant T1 of Chapter 11.1).