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_sumin 3 flops, requires|a| ≥ |b|ora = 0(Dekker’s Fast2Sum); the requirement is adebug_assert!. - two_
prod (p, e)withp = fl(a · b)andp + e = a · bexactly, by one fused multiply-add. Exact whena b = 0or|a b| ≥ 2⁻⁹⁶⁹andpdoes not overflow; otherwise|a b − (p + e)| ≤ η.- two_sum
(s, e)withs = fl(a + b)ands + e = a + bexactly (Knuth’s TwoSum: 6 flops, no branch, no condition on the operands). Exact unlesssoverflows — ora = ±Ω, where an intermediate difference can overflow and leaveenon-finite (invariant T1 of Chapter 11.1).