Expand description
§Chapter 11.11 — Elementary functions of double-doubles
§Purpose
The elementary functions of DoubleDouble (task L2.4; contract
ratified as D-0121): the exponentials, logarithms and powers, the
circular functions and their inverses, the hyperbolic functions and
their inverses — the names and special cases of f64 — and the 19
constants of core::f64::consts. Each function has a declared error
bound, a row of DoubleDouble::FUNCTION_BOUNDS, and each bound is
proven below: the four kernels (exponential, logarithm, sine and
cosine, arctangent) directly, the other functions by composition. No
bound was fitted to a measurement; the tests measure against two
independent oracles and report the largest errors seen.
§Notation
As in Chapters 11.1 and 11.2: RN is rounding to nearest even, u = 2⁻⁵³, u² = 2⁻¹⁰⁶, η = 2⁻¹⁰⁷⁴, Ω the largest finite f64.
MAX_dd = (Ω, ℓ), with ℓ the largest f64 below ulp(Ω)/2, is the
largest finite double-double. The operations A1 (dd + f64), A2 (dd + dd), M1 (dd · f64), M2 (dd · dd), M3 (dd²), D1 (dd / f64), D2
(dd / dd) and R (√dd) are those of Chapter 11.2, with their proven
relative bounds 2u², 3u², 2u², 4u², 3u², 3u², 15u²,
25/8 u² (first-order constants; the exact expressions are in that
chapter). A table entry is the nearest double-double of its value,
with relative error at most u²(1 + u). “x ∈ dd” means a normalized
double-double (invariant D1).
§How the bounds are stated
A function f with declared constants (c, c₂, G, A) (one row of
DoubleDouble::FUNCTION_BOUNDS) returns, for every finite argument
whose result f(x) has magnitude in [2⁻⁹⁶⁸, Ω], a value z with
|z − f(x)| ≤ (c + c₂·G) u² |f(x)| + A,and for results of smaller magnitude the same plus η (the trailing
component loses bits to the subnormal range; Chapter 11.2, “safe
range”). G is |n| in powi, |y ln x| in powf, |tan x| in
tan (where c₂ = 2⁻⁹⁴ turns A(1 + tan²x) into this form) and absent
elsewhere; A is 2⁻²⁰⁰ for the circular functions and their pair
and 0 elsewhere. Nothing is correctly rounded.
§How the bounds are proved (the error calculus)
For a computed ẑ of an exact z write ε(ẑ) ≤ c for |ẑ − z| ≤ c u² |z|, and work to first order in u²: every product of two such
errors is below (64u²)² < 2⁻¹⁹⁹, and a proof that sums at most a few
hundred of them at a constant of at most a few hundred u² is changed by
less than one part in 2⁸⁰. Each proven constant c* is therefore
honest up to the factor 1 + 2⁻⁸⁰, and every declared constant exceeds
its c* by more than that. The rules, all from Chapter 11.2:
- (C1) Sums. If
ε(â) ≤ α,ε(b̂) ≤ β, A2 returnsŝwithε(ŝ) ≤ w_a α + w_b β + 3, wherew_a = |a|/|a + b|,w_b = |b|/|a + b|are the weights (both at most 1 whenaandbhave the same sign; their sum is the cancellation factor otherwise). With an exactf64b, A1 givesw_a α + 2. - (C2) Products and quotients. M2:
α + β + 4; M1 (exactf64factor):α + 2; M3:2α + 3; D2:α + β + 15; D1:α + 3; R:α/2 + 25/8. Range. These constants are theorems only where the operation’s own hypotheses hold (Chapter 11.2): everytwo_prodit forms at least2⁻⁹⁶⁹in magnitude or exact (T2), no overflow, and for R an operandv ≥ 2⁻⁹⁶⁸(LLMPR). Outside, a product or a quotient leaves an absolute error up toηand R a relative one up tou. Every proof below therefore says, for each operation whose operands or result can be that small or that large, why it does not matter (a term whose weight in the result is below2⁻⁴⁰⁰, or a result itself below2⁻⁹⁶⁸, whereηis allowed) or treats the case by a separate step (Lemma W, the second form ofatanh). - (C3) Exact steps add nothing: negation,
ldexp(in the normal range),DoubleDouble::from_sum,DoubleDouble::from_productin its range, Sterbenz subtractionsa − boff64withb/2 ≤ a ≤ 2b, and the operations whose result the text shows to be exact. - (C4) Arguments. If
fis evaluated atâinstead ofaby an algorithm withε ≤ φagainstf(â), then againstf(a)the bound isφ + κ ε(â), whereκbounds the condition number|a f′(a)/f(a)|betweenaandâ; or, in absolute terms,|f(â) − f(a)| ≤ |â − a| max|f′|. Theε(â)is the one of (C2), so (C4) inherits its range hypotheses: anâcomputed outside them carries the absolute errorη(or, after R, the relativeu) intof. - (C5) A tiny addend (Lemma S). If
b ∈ Fand|b| ≤ 2⁻¹⁰ u |a_h|, A1 returnsa + bwith absolute error at mostu²|a_h|(1 + 2⁻⁹). Proof.|b| < ulp(a_h)/2, so step 1 of A1 is(s_h, s_ℓ) = (a_h, b), exactly; step 2 roundsv = a_ℓ + b,|v| ≤ (u + 2⁻¹⁰u)|a_h|, with error at mostu|v|; step 3 is exact (Chapter 11.1, T1). ∎ - (C6) Horner (Lemma H). Let
Q = q₀,q_k = c_k + s q_{k+1}(k = M − 1, …, 0),q_M = c_M, be evaluated with A2 and M2 from table coefficients (ε ≤ σ_k,σ_k ∈ {0, 1}) and a computedŝwithε(ŝ) ≤ ε_s, and suppose|s q_{k+1}| ≤ ρ |q_k|and|c_k| ≤ (1 + ρ)|q_k|for everyk(the terms of an alternating or decreasing series with ratio at mostρ). Thenε(q_k) ≤ (1 + ρ)σ_k + ρ(ε_s + 4 + ε(q_{k+1})) + 3, and by induction fromk = M,ε(q_k) ≤ Efor everyk ≥ 1withE = ((1 + ρ)σ̄ + ρ(ε_s + 4) + 3)/(1 − ρ),σ̄ = max σ_k;ε(Q) ≤ (1 + ρ)σ₀ + ρ(ε_s + 4 + E) + 3. ∎ - (C7) Truncation. A series cut after its
N-th term is charged the bound of its remainder, relative to the value, as one more term.
A product two_prod(a, b) with |a b| < 2⁻⁹⁶⁹ is not exact (Chapter
11.1, T2) and leaves an absolute error up to η; each proof says why
that does not matter where it can happen (an intermediate far below the
scale of the result, or a branch for tiny arguments that avoids it).
§Algorithm E (exp, exp2: Tang’s table-driven exponential)
Input x ∈ dd, finite, −745.2 ≤ x_h ≤ 709.79 (outside: +0, +∞,
NaN by the table of special cases). ℓ = ln 2/64; C₁, C₂, C₃ its three
parts of 53 bits (|ℓ − C₁ − C₂ − C₃| < 2⁻¹⁶⁶); T_j the table entry of
2^(j/64).
E1. [Index.] n ← round(x_h · RN(64/ln 2)), an integer with |n| ≤ 2¹⁷; k ← ⌊n/64⌋, j ← n − 64k ∈ [0, 64).
E2. [Reduce.] r ← ((x − n C₁) − n C₂) − n C₃ with each n Cᵢ an exact
product (from_product) and each subtraction A2; if n = 0, r ← x.
Then x = n ℓ + r up to the error δ_r below, and |r| ≤ ρ_E = 0.005 43 (ℓ/2 = 0.005 415 plus the rounding of n).
E3. [Polynomial.] p ← P(r), where P(r) = r + r²Q(r) and Q(r) = Σ_{m=2}^{11} r^(m−2)/m! by Horner (Lemma H); P(r) ← r when |r_h| < 2⁻⁴⁰⁰ (then |eʳ − 1 − r| ≤ r² < 2⁻⁴⁰⁰|r|).
E4. [Reconstruct.] z ← (T_j + T_j·p) · 2ᵏ (M2, A2, ldexp).
exp2 replaces E1–E2 by: n ← round(64 x_h), y ← (x_h − n/64) + x_ℓ
(exact: x_h − n/64 is a Sterbenz difference scaled by 2⁻⁶, and
from_sum adds x_ℓ exactly), r ← y · LN_2 (M2), |y| ≤ 1/128. For an
integer x, y = r = p = 0 and the result is 1 · 2ᵏ, exact for k ∈ [−1074, 1023].
Theorem E. For results in [2⁻⁹⁶⁸, Ω], ε(exp) ≤ 4.6 and
ε(exp2) ≤ 4.6; below, the bound plus η.
Proof. (i) Reduction. The exact r* = x − nℓ. The first difference
has the exact value r₁ = r* + n(C₂ + C₃) + nτ, |nC₂| ≤ 2¹⁷ · 2⁻⁶⁰
(C₂ ≤ ulp(C₁)/2), so |r₁| ≤ ρ_E + 2⁻⁴²; each of the three A2 errs by
at most 3u² times its result, so δ_r = |r − r*| ≤ 3u²(3ρ_E + 2⁻⁴¹) + 2¹⁷ · 2⁻¹⁶⁶ < 0.05u². As an absolute error of the argument of eʳ it is
a relative error of the result (C4): 0.05. For exp2, r = y LN_2
with ε ≤ 1 + 4 (table, M2), an absolute 5u² ρ_E < 0.03u².
(ii) Polynomial. In Lemma H, s = r is exact (we bound against
P(r) at the computed r), the coefficient ratio is |r|/(m + 1) ≤ ρ_E/3, so ρ = 0.0019, σ₀ = 0 (1/2 is exact) and σ = 1: E = (1.0019 + 0.0076 + 3)/0.9981 = 4.02, ε(Q) ≤ 0.0019 · 8.02 + 3 = 3.02.
ε(r²) = 3, ε(r²Q) ≤ 3 + 3.02 + 4 = 10.02. In r + r²Q the weights are
|r|/|P| ≤ 1/(1 − ρ_E/2) ≤ 1.0028 (exact term) and |r²Q|/|P| ≤ 0.0028:
ε ≤ 0.0028 · 10.02 + 3 = 3.03. The remainder Σ_{m≥12} |r|^m/m! < 1.01 ρ_E^11/12! · |r| < 2⁻¹¹¹|P| adds 0.02: ε(p) ≤ 3.05.
(iii) Reconstruction. ε(T_j p) ≤ 1 + 3.05 + 4 = 8.05; in T_j + T_j p the weights are 1/|1 + p| ≤ 1.0055 and |p|/|1 + p| ≤ 0.0055
(|p| ≤ e^ρ_E − 1 < 0.005 45): ε ≤ 1.0055 · 1 + 0.0055 · 8.05 + 3 = 4.05. With (i), 4.10 (exp) and 4.08 (exp2).
(iv) Scaling. ldexp is exact while both components stay normal.
When the result is at least 2⁻⁹⁶⁸ its leading component is normal and
only the trailing one can round, by at most η/2 = 2⁻¹⁰⁷⁵ ≤ u²|z|/2: + 0.5. Below 2⁻⁹⁶⁸ the scaling is done in two multiplications when k < −1000, and the trailing component may round twice; the two components
together err by at most η. Overflow of
ldexp returns +∞ (step E of Chapter 11.2), which happens only when
T_j(1 + p) 2ᵏ, within 4.6u² of eˣ, exceeds MAX_dd. ∎
Underflow inside: no product of E2–E4 leaves the range of two_prod
when |r| ≥ 2⁻⁴⁰⁰, and for smaller r the only product is T_j r,
whose absolute error (≤ η) is negligible against T_j ≥ 1.
§Algorithm M (exp_m1)
Input x ∈ dd, finite; x_h > 709.79 gives +∞ and x_h < −745.2
gives −1 (then 0 < eˣ < η/2). D_N is the table entry of e^(N/64) − 1, T_j and D′_j those of 2^(j/64) and 2^(j/64) − 1.
M1. [Small.] If |x_h| < 1/2: N ← trunc(64 x_h) ∈ [−31, 31], r ← (x_h − N/64) + x_ℓ — exact, as in exp2, and with the sign of x
(or |r| ≤ u|x|). p ← P(r) with the terms up to m = 13 (Q of 12
coefficients), |r| ≤ 1/64. If N = 0 return p; else return (D_N + D_N p) + p.
M2. [Large.] Else E1–E3 give k, j, r, p. If |k| > 53 return
T_j(1 + p)2ᵏ − 1 (E4, then A1 with −1).
M3. Else return (2ᵏD′_j + (2ᵏ − 1)) + 2ᵏ(T_j p) — 2ᵏ − 1 is an exact
f64 for |k| ≤ 53, the first sum is A1, the second A2.
Theorem M. ε(exp_m1) ≤ 7.2 for results in [2⁻⁹⁶⁸, Ω].
Proof. Small, N = 0: Lemma H with ρ = (1/64)/3 = 0.0053: E = (1.0053 + 0.0212 + 3)/0.9947 = 4.05, ε(Q) ≤ 0.0053 · 8.05 + 3 = 3.05,
ε(r²Q) ≤ 10.05; weights |r|/|P| ≤ 1/(1 − 1/128) = 1.008, |r²Q|/|P| ≤ 0.008; remainder < 2⁻¹¹⁴|P|: ε(p) ≤ 0.008 · 10.05 + 3 + 0.01 = 3.09. Small, N ≠ 0: ε(D p) ≤ 1 + 3.09 + 4 = 8.09; A = D + Dp = D(1 + p) has weights 1/|1 + p| ≤ 1.016 and |p|/|1 + p| ≤ 0.016, so
ε(A) ≤ 1.016 + 0.13 + 3 = 4.15. A and p have the sign of x (N
and r do; in the exceptional case |r| ≤ u|x| the weights exceed 1
by less than 2⁻⁴⁵), so in A + p the weights sum to 1 and ε ≤ max(4.15, 3.09) + 3 = 7.15. Large: count absolute errors in units of
u². S = 2ᵏD′_j + (2ᵏ − 1) errs by at most 2ᵏD′_j (table) + 2|S|
(A1); V = 2ᵏT_j p by at most 2ᵏT_j(0.0055 · 8.05 + 0.05) = 0.094 · 2ᵏT_j (Theorem E (i)–(iii)); the last A2 adds 3|z|. For k ≥ 1, |z| ≥ 0.4946 · 2ᵏT_j, so 2ᵏT_j/|z| ≤ 2.03, 2ᵏD′_j/|z| ≤ 0.68 (largest
at k = 1, T_j → 2) and |S|/|z| ≤ 1.011: ε ≤ 0.68 + 2.03 + 0.19 + 3 = 5.9. For k = 0 (x ∈ [1/2, 0.688), so j ≥ 46, |z| ≥ 0.648):
D′_j/|z| ≤ 1.02, T_j/|z| ≤ 2.6: ε ≤ 1.02 + 2.04 + 0.25 + 3 = 6.3.
For k ≤ −1 (|z| ≥ 1 − e^(−1/2) = 0.393): 2ᵏD′_j/|z| ≤ 0.5,
2ᵏT_j/|z| ≤ 1.55: ε ≤ 0.5 + 2.02 + 0.15 + 3 = 5.7. For k > 53, A1
on eˣ ≥ 2⁵³: ε ≤ 4.1(1 + 2⁻⁵²) + 2 = 6.1; for k < −53, eˣ/|z| ≤ 2⁻⁵²: ε ≤ 2.01. The maximum is 7.15. ∎
§Algorithm L (ln, and the parts of ln_1p, log2, log10)
Input x ∈ dd, 0 < x < +∞ (the rest by the table of special cases).
LNC_j, K⁺_j, K⁻_j are the table entries of ln(1 + j/64),
ln(2(1 + j/64)) and ln((1 + j/64)/2); A, B, C the parts of ln 2
(A of 42 bits).
L1. [Scale.] If x_h < 2⁻¹⁰²² (then x_ℓ = 0), x ← x · 2¹⁰⁶ and e ← −106, else e ← 0. Add to e the exponent of x_h, and y ← x · 2^−exponent ∈ [1, 2); if y_h ≥ RN(√2), y ← y/2, e ← e + 1. Now
x = 2ᵉ y exactly, y ∈ [0.707, 1.415) and |e| ≤ 1074.
L2. [Table index.] j ← trunc(64(y_h − 1)) ∈ [−18, 26] (y_h − 1 is a
Sterbenz difference), c ← 1 + j/64 — between 1 and y_h.
L3. [Reduce.] d ← (y_h − c) + y_ℓ (a Sterbenz difference, then
from_sum: exact), with the sign of y − 1 or |d| ≤ u; z ← d if
j = 0, else z ← d/c (D1). |z| ≤ ζ = 0.0218 (0.0157 if j = 0).
L4. [Series.] L ← z − z²Q(z), Q(z) = Σ_{m=2}^{20} (−z)^(m−2)/m
(Horner); L ← z if |z_h| < 2⁻⁴⁰⁰. This is ln(1 + z) = ln(y/c).
L5. [Combine.] If e = 1 and y_h < 1: K⁺_j + L. If e = −1 and
y_h ≥ 1: K⁻_j + L (these are the two cases in which e ln 2 and
ln y cancel). Otherwise ln y ← L (j = 0) or LNC_j + L, and the
result is ln y (e = 0) or e ln 2 + ln y (A2).
L6. [e ln 2.] a ← e·A (exact: 42 + 11 bits), (p, q) ← two_prod(e, B), (s, t) ← Fast2Sum(a, p), v ← t + (q + e·C),
result from_sum(s, v).
Lemma L6. ε(e ln 2) ≤ 1 + 2⁻⁴⁰. Proof. a + p + q = e(A + B)
exactly; |p| ≤ 2⁻⁴²|a|, so Fast2Sum applies and is exact; |t| ≤ u|s|, |q| ≤ u|p|, |e C| ≤ |e| 2⁻⁹⁸ < 2⁻⁹⁷|s|
(as |s| ≥ 0.69|e|). Two roundings remain:
q + eC, at most u · 2⁻⁹³|s|, and t + (…), at most u|v| ≤ u²|s|(1 + 2⁻⁴¹); the parts of ln 2 beyond C weigh 2¹¹ · 2⁻¹⁴⁸. ∎
Theorem L. ε(ln) ≤ 6.7 for all x ∈ dd, 0 < x < ∞, with
ln x ≠ 0 (ln 1 = +0 exactly).
Proof. (i) Series. In Lemma H the ratio of consecutive terms of Q
is at most ζ(1 + ζ) (alternating when z > 0, all positive when z < 0), so ρ = 0.0225 covers both signs (0.0161 when j = 0); σ₀ = 0
(1/2 is exact), σ = 1, ε_s = ε(z). For j = 0, ε(z) = 0: E = 4.15, ε(Q) ≤ 3.14, ε(z²Q) ≤ 3 + 3.14 + 4 = 10.14; the weights in z − z²Q are at most (1 − ζ/2)⁻¹ and ζ/2(1 − ζ/2)⁻¹ ≤ 0.008: ε(L) ≤ 3.09.
For j ≠ 0, ε(z) = 3 (D1): E = 4.28, ε(Q) ≤ 3.26, ε(z²) ≤ 9,
ε(z²Q) ≤ 16.3, weights 1.011 and 0.011: ε(L) ≤ 1.011 · 3 + 0.011 · 16.3 + 3 = 6.22. The remainder after m = 20 is below ζ²⁰/21 · |z| < 2⁻¹¹⁴|L| (at most 0.004, inside the 6.22: the sum before rounding up
is 6.212). (ii) ln y. LNC_j and L have the same sign (but for
|d| ≤ u, where the weights exceed 1 by 2⁻⁴⁵); the weight of L is
largest for j = ±1, 0.496 and 0.504: ε(ln y) ≤ 3 + 0.496 + 0.504 · 6.22 = 6.63. (iii) Cancelling cases. |ln x| = |ln(2y)| or |ln(y/2)| ≥ ln √2 = 0.3466 and |L| ≤ 0.022: weights 1.064 (table) and 0.064:
ε ≤ 3 + 1.064 + 0.064 · 6.22 = 4.46. (iv) Others. With e ln 2 and
ln y of the same sign the weight of ln y is at most 0.3466/1.0397
and ε ≤ 3 + 0.67 + 0.333 · 6.63 = 5.88; of opposite signs |e| ≥ 2,
weights 1.333 and 0.333: ε ≤ 3 + 1.333 + 2.21 = 6.54. The maximum
is 6.63. No product leaves the range of two_prod: |z| ≥ 2⁻⁴⁰⁰ in
L4, and all other operands are near 1. ∎
§Algorithm L′ (ln_1p)
L′1. If |x_h| < 1/64: z ← x and step L4 (ε ≤ 3.09).
L′2. If x_h ≤ −1/2: w ← (1 + x_h) + x_ℓ (Sterbenz, then from_sum:
exact) and ln w (ε ≤ 6.63).
L′3. Else w ← x + 1 (A1). If w_h ≥ 2⁵³, return ln w (the rounding of
w, 2u² relative, changes ln w by 2u²/ln w < 0.06u² of it).
Otherwise δ ← x − ((w_h − 1) + w_ℓ) (w_h − 1 exact for 1/2 ≤ w_h < 2⁵³; A2), κ ← RN(δ_h/w_h) and return ln w + κ (A1).
Theorem L′. ε(ln_1p) ≤ 7.7. Proof. 1 + x = w + δ* with |δ*| ≤ 2u²|w|(1 + 2⁻⁵⁰) (A1), and ln(1 + x) = ln w + δ*/w − θ, 0 ≤ θ ≤ (δ*/w)². The computed κ differs from δ*/w by at most 4u|δ*/w|
(A2 on exact operands, the dropped δ_ℓ and w_ℓ, one rounding).
|ln w| ≥ ln(65/64) > 0.0155 in L′3, so |κ| ≤ 130u²|ln w| < 2⁻¹⁰u|ln w| and Lemma S applies: the last A1 adds u²(1 + 2⁻⁹). With the
6.63 of ln w (weight 1 + 2⁻⁹⁵), ε ≤ 6.63 + 1.002 + 2⁻⁴⁰ < 7.64. ∎
log2 and log10. log10 x = ln x · LOG10_E (M2 and a table
constant: ε ≤ 6.63 + 5 = 11.63). log2 x is e exactly when x = 2ᵉ
(tested first); in the cancelling cases of L5 it is ln x · LOG2_E
(4.46 + 5); otherwise ln y · LOG2_E (ε ≤ 11.63) plus the exact e
by A1, with weight at most 0.5/1.5 on log₂ y when e ≠ 0: ε ≤ 2 + 0.333 · 11.63 = 5.88. So ε(log2), ε(log10) ≤ 11.7. Below 2⁻⁹⁶⁸
(only x = (1, δ), ln x = δ to δ/2 relative): in the final M2 the
leading product and its error term, both on the grid of η, lose at
most η/2 together, and the cross term δ · LOG_ℓ rounds by at most
η/2: the η of the bound.
§Algorithm P (powi: binary powering with a separate exponent)
Input x ∈ dd finite and nonzero, n ∉ {−1, 0, 1} (those and the
non-finite x by the table of special cases). N = |n|.
P1. [Split.] x = ±2^(e_x) y with y ∈ [1, 2) (exact; a subnormal x_h
is first scaled by 2¹⁰⁶). b ← y, e_b ← e_x, a ← 1, e_a ← 0
(exponents in i64).
P2. [Loop.] For each bit of N from the least significant: if it is set,
a ← a·b (M2), e_a ← e_a + e_b, and renormalize a into [1, 2)
by an exact power of two; then, if bits remain, b ← b² (M3), e_b ← 2e_b, and renormalize b.
P3. [Finish.] If n < 0, a ← 1/a (D2) and e_a ← −e_a. Return ±a · 2^(e_a) (ldexp; ±∞ or ±0 when e_a is out of every range), the
sign by the parity of n.
Theorem P. ε(powi) ≤ 3N + popcount(N) − 4 ≤ 4N − 4 for n > 0
and ≤ 4N + 11 for n < 0; powi(x, 2) is one M3 (3u²) and
powi(x, −1) one D2. Proof. After i squarings ε(b) ≤ 3(2ⁱ − 1)
(ε ← 2ε + 3, Chapter 11.2). The first factor enters a = 1 exactly
(M2 with the operand 1 is exact), each further one adds 4: ε(a) ≤ Σ_{i∈bits} 3(2ⁱ − 1) + 4(popcount − 1) = 3N + popcount − 4. Renormalizing
is exact and keeps every operand in [1, 4), so no product leaves the
range of two_prod and no intermediate over- or underflows, whatever
xⁿ is (in particular x⁻ⁿ with xⁿ > Ω is finite and accurate). D2
adds 15. The second-order terms are below (4N u²)² ≤ 2⁻¹⁴⁶, since N ≤ 2³¹. ∎
§powf (exp(y ln x))
For finite nonzero x, finite nonzero y ≠ 1 (the rest by the table of
special cases): P ← y · ln|x| (Algorithm L, then M2) and z ← exp(P)
(Algorithm E), with the sign − when x < 0 and y is an odd integer
(x < 0 with y not an integer is NaN). “y is an integer”: both
components are; “odd”: the trailing component is odd when nonzero (then
|y_h| ≥ 2⁵³ is even), else the leading one.
Theorem F. ε(powf) ≤ 4.6 + 10.7 G, G = |y ln x|. Proof. ε(P) ≤ 6.63 + 4 (Theorem L, M2), an absolute error at most 10.63u²G in the
argument of exp, which multiplies the result by e^(ΔP) = 1 + ΔP(1 + ΔP) (C4); Theorem E adds 4.6. Overflow of P (|y| huge) gives exp
of ±∞, the right limit. ∎
The contract proposed the growth coefficient 8; the proof gives
10.63, because the logarithm’s own bound, 6.63u², is multiplied by
G as well as the product’s 4u². The declared row therefore has 11
(ratified 2026-11-18, decision log D-0122).
§Algorithm R (argument reduction: Payne–Hanek in integers)
Input x ∈ dd, finite, x ≥ 0 (the callers use the parity of the
functions), x_h > RN(π/4). Output q ∈ {0, 1, 2, 3} and r ∈ dd,
|r| ≤ π/4 (1 + 2⁻³¹⁰), with x ≡ qπ/2 + r (mod 2π) up to the error of
Theorem R. b_i is bit i of 2/π = Σ_{i≥1} b_i 2⁻ⁱ; the table holds
i ≤ 1408.
R1. [Each component.] For c ∈ {x_h, x_ℓ} write |c| = m 2ᵉ with an
integer m < 2⁵³. Let I = e + 382; if I < 1, skip c (c · 2/π < 2⁻³²⁸). Else W ← ⌊2^I · 2/π⌋ mod 2³⁸⁴ — the bits b_{I−383}, …, b_I,
six 64-bit words — and A_c ← ⌊m W / 2⁶⁴⌋ mod 2³²⁰, negated modulo
2³²⁰ when c < 0 (x_ℓ may be negative).
R2. [Sum.] A ← (A_{x_h} + A_{x_ℓ}) mod 2³²⁰. A · 2⁻³¹⁸ is x · 2/π
modulo 4, as two integer bits and a 318-bit fraction F.
R3. [Quadrant.] If F < 2³¹⁷: q ← the integer bits, G ← 2F, sign
+. Else q ← the integer bits + 1 (mod 4), G ← 2(2³¹⁸ − F),
sign −. Then ĝ = G · 2⁻³¹⁸ ∈ [0, 1] and r = ±ĝ · π/4 (ĝ
approximates the exact g = |r*|/(π/4) of Theorem R).
R4. [Multiply.] R ← ⌊G · P / 2²⁵⁶⌋ with P = ⌊2³²⁰ π/4⌋ (five words),
so |r| ≈ R · 2⁻³⁸², R < 2³⁸³.
R5. [Convert.] With L the position of the leading bit of R, take the
53-bit chunks c₀, c₁, c₂ starting at bits L − 52, L − 105, L − 158 (each exactly an f64 vᵢ after scaling by a power of two);
(s, t) ← Fast2Sum(v₀, v₁), r ← ±from_sum(s, t + v₂).
Theorem R. |r − r*| ≤ (1 + 2⁻⁴⁹)u²|r*| + 2⁻³¹⁶, where r* = x − (4k + q)π/2 exactly, for some integer k.
Proof. R1: the bits of 2/π with i ≤ e − 2 contribute multiples of
4 to c · 2/π (m is an integer) and are dropped exactly; those with
i > I contribute less than m 2^(e−I) < 2^(53−382) = 2⁻³²⁹; and
A_c 2⁻³¹⁸ = m W 2^(e−I) − θ with 0 ≤ θ < 2⁻³¹⁸ (the dropped word), all
modulo 4 (2³²⁰ · 2⁻³¹⁸ = 4); negation keeps |θ| < 2⁻³¹⁸. The skipped
components weigh less than 2⁻³²⁸. So A 2⁻³¹⁸ ≡ x · 2/π − δ (mod 4)
with |δ| < 2⁻³¹⁶·⁹. R3:
the chosen integer is within 1/2 + δ of x · 2/π; |ĝ − g| ≤ 2δ.
R4: P errs by less than 2⁻³²⁰, and the floor drops less than
2⁻³⁸²: |R 2⁻³⁸² − g π/4| < (π/4) 2δ + 2⁻³²⁰ + 2⁻³⁸² < 2⁻³¹⁶. R5:
v₀ + v₁ + v₂ is R 2⁻³⁸² truncated after 159 bits (< 2⁻¹⁵⁸ of it);
Fast2Sum is exact (|v₁| < ulp(v₀)); |t| ≤ u|s|, |v₂| < 2⁻¹⁰⁵ · R 2⁻³⁸², so the one rounding, of t + v₂, is at most u²(1 + 2⁻⁵¹) of
the value; from_sum is exact. ∎ When R ≥ 1, |r| ≥ 2⁻³⁸² (the
chunks are exact multiples of 2⁻³⁸²); R = 0, possible only if |r*| < 2⁻³¹⁵, gives r = 0 — and Lemma D below shows that it never happens.
Lemma D (no double-double is near a multiple of π/2). For every
double-double x with x_h > RN(π/4) and every integer k, `|x − kπ/2|
2⁻¹⁴⁰
. So|r*| > 2⁻¹⁴⁰in Theorem R,R ≥ 1, and|r| > 2⁻¹⁴¹. The closest double-double found (below) has|r*| ≈ 2⁻¹²⁴`.
Notation. ‖y‖ is the distance from y to the nearest integer, so
min_k |x − kπ/2| = (π/2)‖x · 2/π‖ and it suffices that ‖x · 2/π‖ ≥ 2⁻¹⁴⁰ (π/2 > 1). x_h = M 2ᴱ with 2⁵² ≤ M < 2⁵³ and −53 ≤ E ≤ 971
(x_h > 0.78); x_ℓ = 0 or x_ℓ = m 2ᵉ with |m| < 2⁵³ and e = −1074
or 2⁵² ≤ |m|; normalization (|x_ℓ| ≤ 2^(E−1)) gives e ≤ E − 53.
α_j = 2ʲ · 2/π mod 1. The method is the classical one for f64
(Muller, Chapter 11): continued
fractions bound ‖qα‖ for all q below a bound at once. A
double-double is two such numbers at independent exponents, so where the
gap between them is wide a lattice replaces the continued fraction.
D1. [Continued fractions.] For a rational β with convergents p_i/q_i
and a bound Q, let q_n < Q ≤ q_(n+1); then ‖qβ‖ ≥ |q_n β − p_n|
for every 0 < q < Q (Lagrange: a convergent is a best
approximation of the second kind; Khinchin, Continued Fractions,
chapter II). If |α − β| ≤ ϑ, ‖qα‖ ≥ |q_n β − p_n| − Qϑ.
D2. [The leading component.] D1 with β = β_E, a rational within
2^(E−1700) of α_E, and Q = 2⁵³ gives d_E ≤ ‖Mα_E‖ for every
0 < M < 2⁵³. This settles x_ℓ = 0; the smallest is d_797 = 2⁻⁶¹·⁵⁴, at 6 381 956 970 095 103 · 2⁷⁹⁷, the f64 nearest a
multiple of π/2 (the worst case of f64 listed by Muller).
D3. [A small trailing component.] If 2^(e+53) · 2/π ≤ d_E/2: ‖x · 2/π‖ ≥ ‖x_h · 2/π‖ − |x_ℓ| 2/π ≥ d_E/2.
D4. [A narrow gap: one integer.] Else, if s = E − e ≤ 60: x = N 2ᵉ
with 0 < N = M 2ˢ + m < 2^(54+s), and ‖x · 2/π‖ = ‖Nα_e‖ is
bounded by D1 with β = β_e and Q = 2^(54+s).
D5. [A wide gap: a lattice.] Else ‖x · 2/π‖ = ‖Mα_E + mα_e‖, a linear
form in two integers below 2⁵³. With Z = 2ᶻ, A = ⌊Zβ_E⌋, B = ⌊Zβ_e⌋, the lattice Λ spanned by the rows (1, 0, A), (0, 1, B),
(0, 0, Z) holds v = (M, m, MA + mB − kZ), whose last coordinate is
ZL − θ with L = Mα_E + mα_e − k and |θ| ≤ 2⁵⁴ + 1. For any
basis of Λ with Gram–Schmidt vectors b_i*, a nonzero v has
‖v‖ ≥ μ = min_i ‖b_i*‖ (take the last i with a nonzero
coefficient), so Z|L| ≥ √(μ² − 2¹⁰⁷) − 2⁵⁴ − 1. The basis is reduced
by LLL and then checked exactly: its rows lie in Λ, its determinant
is ±Z, and ‖b_i*‖² = Δ_i/Δ_(i−1) with the integer Gram
determinants Δ_i. z is the first of 170, 185, 200, 230, 260
that gives 2⁻¹⁴⁰.
Proof. D1 is the classical theorem; D2–D5 cover every x (D3 every
e below a cut, D4 and D5 the rest up to E − 53). The program
tests/reduction_bound.rs carries the computation out in integers only
(dashu-int, no floating point): π by Machin’s formula with its
truncation bounded, ⌊2¹⁷⁰⁰ · 2/π⌋ certified, then D2–D5 for all 1 025
exponents E and every e that D3 does not settle — 527 301 cases (D4
for 8 178 of them, D5 for 519 123), each asserted ≥ 2⁻¹⁴⁰. The
smallest bound is 2⁻¹²⁹·⁵ (D5 at E = 671, e = 78), so in fact
|r*| > 2⁻¹²⁹. The full run is #[ignore]d in the default suite
(about 20 s with --release); a sample of 11 exponents runs by
default. ∎
The lemma is a computer-assisted proof: it rests on that program, on
D1 and on the bound of D5, not on sampling. An independent run with
fpylll for the reduction and Python integers for the checks gave the
same 2⁻¹²⁹·⁵, and so did the independent review of the lemma, with its
own continued fractions and Gram–Schmidt in exact rationals. The
arguments closest to kπ/2 known are 7 688 177 032 635 270 · 2⁸⁷⁵ − 8 875 559 650 591 347 · 2⁻⁷⁵ (|r*| = 2⁻¹²⁴·⁴⁶, odd k; found by that
review, enumerating small combinations of a reduced basis of the lattice
of D5) and, from a search over the convergents of every α_E,
14 461 176.670… + 1.70·10⁻¹⁸ (2⁻¹¹⁷·⁹⁹) and 6 381 956 970 095 103 · 2⁷⁹⁷ − 4.69 · 10⁻¹⁹ (2⁻¹¹⁷·⁴⁶); the tests check the sharper bound of
tan there. Neither search is exhaustive: about four bits separate the
closest argument known from the proven floor.
The contract planned Cody–Waite (π/2 in five parts) below 2⁵² and
Payne–Hanek above. Cody–Waite in double-double arithmetic subtracts with
A2, whose error is relative to its own result: x − kP₁ is about
kP₂ ≈ k 2⁻⁵³, so the reduction carries an absolute error up to 3u²k 2⁻⁵³ — 2⁻¹⁰⁵ at k ≈ 2⁵², and 2⁻¹⁵⁷ even at k = 1. That cannot be
proven below the floor 2⁻²⁰⁰ of the declared bound (the pilot’s good
measurements near kπ/2 presumably reflect A2 being exact there in
practice; that is not a theorem). The integer reduction has the proven
absolute error 2⁻³¹⁶ of Theorem R, whatever x, and is used for every
x_h > RN(π/4) (its own cost was not measured separately).
§Algorithm K (sin, cos, sin_cos, tan)
S1. [Reduce.] a ← |x|. If a_h ≤ RN(π/4), q ← 0, r ← a; else
Algorithm R.
S2. [Kernels.] sin r ← r − r³Q_s(r²), Q_s = Σ_{m=1}^{14} (−r²)^(m−1)/ (2m+1)! (Horner); cos r ← 1 − 2 sin²(r/2), with sin(r/2) by the
same series to m = 11 (|r/2| ≤ π/8); sin r ← r and cos r ← 1
when |r_h| < 2⁻⁴⁰⁰.
S3. [Quadrant.] sin x = ±(sin r, cos r, −sin r, −cos r)[q] with the
sign of x; cos x = (cos r, −sin r, −cos r, sin r)[q]; tan x = sin r/cos r (q even) or −cos r/sin r (q odd), with the sign of
x (D2).
S4. [Tangent at r = 0.] For tan only: if q is odd and Algorithm R
returned r = 0, take r ← 2⁻³⁸², the smallest nonzero magnitude
that R5 produces (sin, cos and sin_cos keep r = 0). By Lemma
D no argument reaches this step (r = 0 needs |r*| < 2⁻³¹⁵); it is
kept as a guard for release builds, so that tan stays finite
should the computation of Lemma D be wrong, and is tested through an
internal hook. A debug build asserts Lemma D (|r| > 2⁻¹⁴¹) in
Algorithm R, and so panics before reaching the guard.
Each function calls the same kernels on the same (q, r), so sin_cos
gives the bits of sin and of cos; the kernels are odd and even bit
for bit (M2, M3 and A2 commute with negation), and S1 works on |x|, so
sin, tan are odd and cos is even bit for bit.
Theorem K. For every finite x, with f the function: |z − f(x)| ≤ 6.9u²|f(x)| + 2⁻³¹⁵ for sin, cos (and the pair), and |z − tan x| ≤ 27.4u²|tan x| + 2⁻³¹⁵(1 + tan²x).
Proof. Sine kernel: Lemma H with s = r² (ε_s = 3), ratio ρ = (π/4)²/20 (1 + 0.04) = 0.032, σ = 1: ε(Q_s) ≤ (1.032 + 0.032 · 7 + 3)/0.968 = 4.40; ε(r³) = 7, ε(r³Q_s) ≤ 15.4; the weight of r³Q_s
is (r − sin r)/sin r ≤ 0.111: ε ≤ 0.111 · 15.4 + 3 = 4.71. The first
omitted term is below 2⁻¹²² of sin r. Cosine kernel: for h = r/2,
ρ = 0.0078, ε(Q) ≤ 4.10, weight 0.026: ε(sin h) ≤ 3.40 (with
the truncation of its 11 terms, 10⁻³); ε(sin²h) ≤ 9.80; in 1 − 2 sin²h (A1, exact 1) the weight of 2 sin²h is (1 − cos r)/cos r ≤ 0.415: ε ≤ 2 + 0.415 · 9.80 = 6.06. Range (C2): for 2⁻⁴⁰⁰ ≤ |r| < 2⁻³²³ the product r · r² falls below 2⁻⁹⁶⁹ and M2 errs by up to
η absolute, below 2⁻⁶⁷⁰ of sin r; in cos r the square sin²h
underflows likewise against the exact 1 (and below 2⁻⁴⁰⁰, cos r ← 1
leaves r²/2 < 2⁻⁸⁰⁰).
Reduction (C4): by Theorem R the kernels see r instead of r*;
|sin r − sin r*| ≤ |r − r*|, which is ≤ 1.111u²|sin r*| + 2⁻³¹⁶, and
|cos r − cos r*| ≤ sin|r*| |r − r*| ≤ 0.79u²|cos r*| + 2⁻³¹⁶. Totals
4.71 + 1.12 and 6.06 + 0.8: 6.9. For x_h ≤ RN(π/4), r = x
exactly (such an x may exceed π/4 by 2.6·10⁻¹⁷, which changes the
constants above by less than 10⁻¹⁵). Tangent: D2 adds 15 to
4.71 + 6.06. For an even q, or an odd q (where |r*| > 2⁻¹⁴⁰ ≥ 2⁻³⁰⁰ by Lemma D; for x_h ≤ RN(π/4), q = 0):
then |r − r*| ≤ 2⁻¹⁶|r*|, so every ξ between r and r* has 1 + cot²ξ ≤ (1 + 2⁻¹²)(1 + cot²r*) (likewise for tan), and |tan r − tan r*| ≤ (1 + tan²ξ)|r − r*| has the relative part r/(sin r cos r) u²(1 + 2⁻¹²) ≤ 1.58u² (the same for cot) and the absolute part
2⁻³¹⁵(1 + tan²x): 27.4. This covers every finite x. (Before Lemma
D, an odd q with |r*| < 2⁻³⁰⁰ was left with the declared bound only;
the case does not exist.) ∎
§Algorithm T (atan)
Input a ∈ dd, 0 ≤ a < ∞ (atan is odd: the sign is applied last;
atan(±∞) = ±π/2). θ_c is the table entry of atan c.
T1. [Tiny.] If a_h < 2⁻⁶: atan a ← a − a³Q_a(a²), Q_a = Σ_{m=1}^{9} (−a²)^(m−1)/(2m + 1) (Horner; a itself below
2⁻⁴⁰⁰).
T2. [Table.] If a_h < 8: with e the exponent of a_h (−6 ≤ e ≤ 2) and i the top four bits of its fraction, c ← 2ᵉ(1 + (2i + 1)/32) (an f64 of six bits, |a − c| ≤ 2ᵉ/32); t ← ((a_h − c) + a_ℓ)/(a·c + 1) (Sterbenz and from_sum: exact numerator; M1, A1,
D2); atan a ← θ_c + atan t with atan t by the series of T1
(|t| ≤ 2ᵉ/32/(1 + 2²ᵉ) ≤ 1/64).
T3. [Large.] Else atan a ← π/2 − atan(1/a) (D2, then T1 or T2).
Theorem T. ε(atan) ≤ 5.8. Proof. T1: Lemma H with s = a²
(ε_s = 3), ρ = 0.895 · 2⁻¹² (a ≤ 2⁻⁶, so that T2’s |t| ≤ 1/64
is covered): ε(Q_a) ≤ 4.003, so ε(a³Q_a) ≤ 15.01;
its weight is at most a²/3 < 10⁻⁴: ε ≤ 3.002; the omitted terms are
below 2⁻¹²⁰ of the value. T2: ε(a·c + 1) ≤ 2 + 2, so ε(t) ≤ 4 + 15 = 19 and ε(atan t) ≤ 3.002 + 19 (C4, the condition number of
atan near 0 is at most 1). |atan t|/atan a ≤ 1/(8π) < 0.04 (for a
at most 1, atan a ≥ aπ/4 ≥ 2ᵉπ/4; for a > 1, atan a ≥ π/4, |t| ≤ 1/64):
weights 1.04 and 0.04, ε ≤ 3 + 1.04 + 0.04 · 22.0 = 4.92. T3:
ε(1/a) ≤ 15, ε(atan(1/a)) ≤ 4.92 + 15; with atan(1/a) ≤ atan(1/8)
the weights of π/2 and of atan(1/a) are 1.086 and 0.086, so
ε ≤ 3 + 1.086 + 0.086 · 19.92 = 5.80. Range (C2): in T1 the
products a², a · a² are formed only for a ≥ 2⁻⁴⁰⁰, where a³ ≥ 2⁻¹²⁰⁰ may underflow: its absolute error η is below 2⁻⁸⁰⁰ of a.
In T2 the numerator can be minuscule (a next to a cell’s centre c);
then t and the series are tiny and their weight |atan t|/atan a
makes any η negligible. In T3, 1/a is subnormal for a > 2¹⁰²²,
inexact by η, with weight below 2⁻¹⁰²² against π/2. ∎
atan2(y, x). After the special cases (the table of f64), both
magnitudes are scaled by the same power of two 2⁻ˢ so that the larger
is in [1, 2) (exact for the larger; the smaller can round, its
trailing component by at most η/2, which is at most 0.5u² of a
quotient of at least 2⁻⁹⁶⁸ — with a widely spaced trailing component
that happens for quotients up to about 2⁻⁹¹⁵). If |y| ≤ |x|: z ← atan(|y|/|x|), and the result is z (x > 0) or π − z; else z ← atan(|x|/|y|) and the result is π/2 − z (x > 0) or π/2 + z; then
the sign of y. The quotient q = n/d (n the smaller scaled
magnitude, d ∈ [1, 2) the larger) is formed in one of three ways:
Q1. [Tiny.] If n_h < 2⁻⁹⁶⁸: with the unscaled smaller magnitude m = 2ᵉ μ, μ ∈ [1, 2) (exact, a subnormal m scaled up first), q ← (μ/d) · 2^(e−s) (D2 on operands in [1, 2), then one ldexp).
Q2. [Small.] Else, if n_h < 2⁻⁴⁰⁰: q ← ((n · 2⁶⁰⁰)/d) · 2⁻⁶⁰⁰, so that
D2 stays in its range.
Q3. Else q ← n/d (D2).
In Q1 and Q2, q < 2⁻⁴⁰⁰ is its own arctangent. Q1: q < 2⁻⁹⁶⁸ (n < 2⁻⁹⁶⁸, d ≥ 1); the scaling of m is exact, D2 errs by 15u²|q|, and
the final ldexp rounds each component at most once by at most η/2
(its first factor 2⁻¹⁰⁰⁰, when e − s < −1000, leaves the leading
component of μ/d ∈ [1/2, 2) normal; a trailing component that it
rounds ends below η/2 anyway and is lost with at most that): |q̂ − q| ≤ 15u²|q| + η, the bound with its η. Scaling n itself and then
unscaling the quotient would round twice — the scaled n, subnormal,
and the result — up to about 2η (found by the property tests on
x86_64: 1.04η at y = (1.5127926632651903·10⁻²⁹⁵, −7.815437673005· 10⁻³¹²), x = 23 118 976 389 754.613). Q2: ε ≤ 15 + 0.5 + 0.5 = 16
(D2, the rounding of n’s trailing component, the ldexp(−600)),
below the 19.92 of z; q ≥ 2⁻⁹⁶⁹ there, and below 2⁻⁹⁶⁸ the two
roundings are of trailing components only, η in all. Bound:
ε(q) ≤ 15, ε(z) ≤ 4.92 + 15κ with κ ≤ 1 the condition number of
atan on [0, 1]. z: 19.92. π − z, z ≤ π/4: weights 4/3,
1/3: 3 + 1.33 + 6.64 = 11.0. π/2 − z: weight ≤ 2 on π/2, ≤ 1
on z, and w_z κ = q/((1 + q²)(π/2 − atan q)) ≤ 2/π: 3 + 2 + 4.92 + 15 · 0.637 = 19.5. π/2 + z: ≤ 10.7. So ε(atan2) ≤ 20.
Lemma W (a square root below 2⁻⁹⁶⁸). Algorithm R of Chapter 11.2
has its bound 25/8 u² only for operands v ≥ 2⁻⁹⁶⁸ (LLMPR, Theorem
3.6): below, the residual v_h − s_h² of its Newton step is a
subnormal fma result that loses its low bits, and the relative error
of √v reaches u. Step W: for 0 < v_h < 2⁻⁹⁶⁸, √v ← √(v · 2⁶⁰⁰) · 2⁻³⁰⁰; otherwise R itself (so W changes nothing from 2⁻⁹⁶⁸ up). Then
ε(√v) ≤ α/2 + 25/8 + 2⁻⁴³⁰ for ε(v) ≤ α. Proof. The scaling up is
exact and puts v · 2⁶⁰⁰ in [2⁻⁴⁷⁴, 2⁻³⁶⁸), inside the safe range of
Chapter 11.2; R’s result has its leading component in [2⁻²³⁷, 2⁻¹⁸⁴),
which stays normal after the scaling down, while the trailing one moves
by at most η/2 < 2⁻⁵³⁷ √v (√v ≥ √η = 2⁻⁵³⁷) if it becomes subnormal;
fast_two_sum renormalizes exactly (Chapter 11.2, ldexp). ∎
asin, acos. With a = |x| ≤ 1 and w = √((1 − a)(1 + a)):
for a ≥ 1/2, 1 − a is exact (Sterbenz, from_sum), 1 + a is A1
and the product M2: ε(w) ≤ (2 + 4)/2 + 25/8 = 6.13; for a < 1/2, w = √(1 − a²) (M3, A1 with the weight 1/3 on a²): ε(w) ≤ 3/2 + 25/8 = 4.63. The square root is step W. Its operand is below 2⁻⁹⁶⁸ only if
a_h = 1 and a_ℓ = −δ with 0 < δ < 2⁻⁹⁶⁹ (for a_h < 1, 1 − a ≥ 2⁻⁵⁴). Then 1 − a = δ and 1 + a = (2, −δ) are exact, δ · 2 is an
exact two_prod, and the only rounding in M2 is that of the cross term
−δ²: at most δ² when it underflows (δ/2 < 2⁻⁹⁷⁰ of the product
2δ), else at most η/2 with δ > 2⁻⁵³⁸ (below 2⁻⁵³⁶ of it). So
ε(w) ≤ 25/8 + 2⁻⁴²⁹ there, and acos(1 − δ) = atan(w/a), essentially
w, keeps the bound; Algorithm R alone would give it a relative error
up to u (found by the tests of the subnormal regime). Then asin x = ±atan(a/w) (a ≤ w) or ±(π/2 − atan(w/a)), and
acos x is atan(w/a) (w ≤ a) or π/2 − atan(a/w) for x ≥ 0, and π − atan(w/a) or π/2 + atan(a/w) for x < 0. Bound: the quotient has
ε ≤ 15 + ε(w) ≤ 21.13; atan(q) then 4.92 + 21.13 = 26.05; π/2 − atan q gives 3 + 2 + 4.92 + 0.637 · 21.13 = 23.4; the others are
smaller (13.0, 12.7). So ε(asin), ε(acos) ≤ 26.1. asin(±1) = ±π/2, acos(1) = +0 and acos(−1) = π exactly (w = 0). Range
(C2): below 2⁻⁴⁰⁰ asin returns x, and acos is π/2 − atan(a/w) with a/w ≈ a of weight below 2⁻³⁹⁹ (its D2 may err by
η for a subnormal a); above it a² and a/w are at least 2⁻⁸⁰⁰.
Near ±1, w ≥ 2⁻⁵³⁷ (step W), so w/a and its D2 products stay
above 2⁻⁹⁶⁹, and atan(w/a) is w/a itself below 2⁻⁴⁰⁰.
§The hyperbolic functions and their inverses (composition)
With a = |x| (the odd functions apply the sign of x last; cosh is
even), each below is a short composition whose bound follows from (C1)–
(C4) and Theorems E, M, L, L′:
sinh a = (E + E/(E + 1))/2,E = exp_m1(a), fora_h ≤ 709;exp(a − 1) · e/2above (a − 1is exact there,e/2isE/2of the table, exact scaling). Bound:ε(E + 1) ≤ 2 + 7.15 E/(E + 1),ε(E/(E + 1)) ≤ 24.15 + 7.15 E/(E + 1), and the last A2 weighs them(E + 1)/(E + 2)and1/(E + 2): largest asE → 0,3 + (7.15 + 24.15)/2 = 18.7. Above 709:4.6 + 1 + 4 = 9.6(the neglectede⁻ᵃis2⁻²⁰⁴⁵relative). Below2⁻⁴⁰⁰the result isa.cosh a = (E + 1/E)/2,E = exp(a), fora_h ≤ 709;exp(a − 1) · e/2above. Bound:ε(1/E) ≤ 4.6 + 15; the weightsE²/(E² + 1)and1/(E² + 1), largest atE = 1:3 + (4.6 + 19.6)/2 = 15.1. Range: neara = 709,1/Eis near2⁻¹⁰²³and its D2 can err byη, with the weight1/(E² + 1) < 2⁻²⁰⁴⁴.tanh a = E₂/(E₂ + 2),E₂ = exp_m1(2a), fora < 5/16; else(1 − F)/(1 + F),F = exp(−2a). Bound: below5/16,E₂ ≤ 0.868,ε(E₂ + 2) ≤ 2 + 0.303 · 7.15,ε ≤ 7.15 + 4.17 + 15 = 26.4; above,F ≤ 0.536,ε(1 − F) ≤ 2 + 1.152 · 4.6,ε(1 + F) ≤ 2 + 0.349 · 4.6,ε ≤ 7.30 + 3.61 + 15 = 25.9. For largea,Funderflows (an absoluteηagainst 1) and D2 returns the pair(1, −2F)untilF < η/2, then exactly 1.asinh a = ln_1p(a + a²/(1 + √(1 + a²)))fora < 2,ln(a + √(a² + 1))for2 ≤ a < 2⁶⁰,ln a + ln 2above (asinh a − ln 2a < 2⁻¹²²of it). Bound: fora < 2,ε(√(1 + a²)) ≤ 2.2 + 25/8,ε(1 + √) ≤ 5.68,ε(a²/(1 + √)) ≤ 23.7, and in the argumentvofln_1pits weight is at most0.382:ε(v) ≤ 12.1; the condition number ofln_1pis at most 1:ε ≤ 7.64 + 12.1 = 19.7. For2 ≤ a < 2⁶⁰,ε(v) ≤ 3 + 0.528 · 5.63and the condition number oflnatv ≥ 4.23is1/ln v ≤ 0.693:ε ≤ 6.63 + 4.14 = 10.8. Above:3 + 6.63 = 9.63. Range (C2): below2⁻⁴⁰⁰the result isa; above,a² ≥ 2⁻⁸⁰⁰and the products of the quotienta²/(1 + √(1 + a²))are of that size, above2⁻⁹⁶⁹(outside the conservative safe range of Chapter 11.2, but everytwo_prodis exact), and the quotient weighsa/2inv.acosh x = ln_1p(d + √(d(d + 2))),d = x − 1(exact), forx < 2;ln(x + √(x² − 1))for2 ≤ x < 2⁶⁰;ln x + ln 2above. Bound:ε(√(d(d + 2))) ≤ 3 + 25/8,ε(v) ≤ 3 + 6.13,ε ≤ 7.64 + 9.13 = 16.8(the square root is step W:d(d + 2) < 2⁻⁹⁶⁸only whenx_h = 1andd = x_ℓ < 2⁻⁹⁶⁹, where M2 errs by less than2⁻⁵³⁶relative, as inacos, andacosh x ≈ √(2d)is the square root itself);ε(x² − 1) ≤ 2 + (4/3) · 3,ε(v) ≤ 3 + 6.13/2,ε ≤ 6.63 + 0.76 · 6.07 = 11.3; above,3 + 6.63 = 9.63.atanh a = ln_1p(2a/(1 − a))/2, with1 − aexact fora ≥ 1/2and A1 below. Bound:ε(2a/(1 − a)) ≤ 2 + 15, condition number ofln_1pat most 1:ε ≤ 7.64 + 17 = 24.7. If1 − ais subnormal (thena = (1, −δ),δ < 2⁻¹⁰²², and2a/(1 − a) ≈ 2/δexceedsΩonceδ < 2⁻¹⁰²³),atanh a = (ln(1 + a) − ln(1 − a))/2instead, with1 + a = (2, −δ)exact (A1) and1 − a = δ: Theorem L twice, and A2 on two positive terms (ln(2 − δ) > 0,−ln δ > 0):ε ≤ 6.63 + 3 = 9.7. For a normal1 − abelow2⁻⁴⁷⁹the quotient exceeds2⁴⁸⁰, outside the conservative safe range of Chapter 11.2, but the products of D2 are near2aand its divisor is normal, so its hypotheses (T2, no overflow) hold and so does15u². Below2⁻⁴⁰⁰the result isa.
Below 2⁻⁴⁰⁰ the odd functions return x (the cubic term is 2⁻⁸⁰⁰
relative).
§Invariants
(F1) Well formed. Every output satisfies (D1)/(D2) of Chapter 11.2,
for every input, non-finite and subnormal ones included (a property
test calls check_invariants on every result).
(F2) Determinism. Only + − × ÷ √ fma, round, trunc of f64 and
the operations of Chapter 11.2, in a fixed order with branches that
depend only on the bits of the arguments: the same bits on every
platform, in debug and release, with or without the features (a
golden test of 246 values and a digest of 21 000; clippy.toml
forbids the transcendental functions of f64 in the crate).
(F3) Symmetry. sin, tan, asin, atan, sinh, tanh, asinh,
atanh are odd and cos, cosh even, bit for bit; sin_cos(x) = (sin x, cos x) bit for bit.
(F4) Inputs. Each function debug_assert!s (D1) of its arguments; in
release a non-normalized argument gives an unspecified but well
formed result.
§Measured
Largest error observed against dashu-float, 10⁵ random arguments per
family (in u²; mixed bounds: the relative part); the survey is the
#[ignore]d test survey_of_observed_errors. exp 1.77, exp2 1.77,
exp_m1 2.53, ln 1.91, ln_1p 2.16, log2 3.16, log10 3.40, sin
2.37, cos 1.89, tan 5.57, atan 1.94, atan2 5.21, asin 5.87,
acos 4.41, sinh 3.40, cosh 2.86, tanh 6.23, asinh 2.70,
acosh 3.73, atanh 3.46; powi ≤ 2.07 max(1, |n|), powf ≤ 4.30 max(1, |y ln x|). At the double-doubles nearest to kπ/2, k ≤ 2·10⁶:
0.50 relative, 4·10⁻⁵⁹ absolute at most.
In the subnormal regime (the #[ignore]d test
survey_of_the_subnormal_regime, 10⁴ arguments per family: tiny
arguments, subnormal or below 2⁻⁹⁰⁰; ±(1 ± δ) with such a δ;
exp, exp_m1 on [−745.2, −670] and exp2 on [−1076, −967]),
every function of one argument stays within 2.91u² relative for
results of at least 2⁻⁹⁶⁸ (log10 of tiny arguments; most are below
1.5) and within 0.99η absolute below (log2, log10 at 1 ± δ;
exp, exp2 0.75η; the larger search below reaches 1.01η, the
relative term included). The directed and property tests of that regime
also cover sin_cos, powi, powf and atan2. They found four
defects, fixed before publication: acos(1 − δ) and acosh(1 + δ)
with δ < 2⁻⁹⁶⁹ (up to u relative; Lemma W), atanh(±(1 − δ)) with
δ < 2⁻¹⁰²³ (±∞; the second form of atanh), and atan2 with a
quotient below 2⁻⁹⁶⁸ rounded twice (up to 1.26η beyond the relative
term in a search of 3·10⁵, 37 violations; step Q1). The #[ignore]d
search_of_subnormal_results (10⁶ arguments per family, results or
arguments below 2⁻⁹⁶⁸, trailing components often subnormal) finds no
violation after the fixes; beyond the relative term the error is at
most 0.75η for atan2, exp, exp2, powi, powf, 0.998η for
log2 and log10 at 1 + δ, and 0 for the functions that return
their tiny argument.
§Cost
The numbers below were measured by a harness outside the tree; the
example elementary_bench has its rows and its method, and prints the
table with the backend, the target and the load average. Time per call (ns,
median of 21 runs over 1 024 independent arguments,
so a throughput; release, Apple M2 Pro on AC power, load average 3.0
from other sessions): exp 232, exp2 214, exp_m1 241, ln 430,
ln_1p 443, log2 439, log10 443, powi(x, 7) 53, powi(x, −100)
138, powf 753, sin 279 (|x| ≤ 1) to 344 (|x| ≤ 10) and 352
(|x| up to 2⁹⁶⁰), cos 340, tan 599, sin_cos 599, atan 190,
atan2 258, asin 266, acos 266, sinh 298, cosh 271, tanh 278,
asinh 538, acosh 508, atanh 487. For scale: dd · dd 1.9, dd + dd 2.8, dd / dd 3.4, f64::exp 2.5.
§The declared bounds
The column “proven” is the constant of the proof in this chapter,
rounded up; “declared” is the row of DoubleDouble::FUNCTION_BOUNDS.
Both are bounds on |z − f(x)|: the numbers are in units of u²|f|
(u²|f| times the growth term where there is one); the terms 2⁻²⁰⁰,
2⁻³¹⁵ (times 1 + tan² for tan) are absolute.
| function | declared | proven | how |
|---|---|---|---|
exp, exp2 | 8 | 4.6 | Algorithm E |
exp_m1 | 8 | 7.2 | Algorithm M |
ln | 8 | 6.7 | Algorithm L |
ln_1p | 8 | 7.7 | Algorithm L′ |
log2, log10 | 12 | 11.7 | Algorithm L, then a product |
powi | 15 + 4|n| | 11 + 4|n| | Algorithm P |
powf | 16 + 11|y ln x| | 4.6 + 10.7|y ln x| | exp(y ln x) (Theorem F) |
sin, cos, sin_cos | 8|f| + 2⁻²⁰⁰ | 6.9|f| + 2⁻³¹⁵ | Algorithms R and K |
tan | 32|tan| + 2⁻²⁰⁰(1 + tan²) | 27.4|tan| + 2⁻³¹⁵(1 + tan²) | Algorithms R and K, D2; Lemma D |
atan | 8 | 5.8 | Algorithm T |
atan2, asin, acos | 32 | 20, 26.1, 26.1 | Algorithm T, composition |
sinh, cosh, tanh | 32 | 18.7, 15.1, 26.4 | Algorithms E and M, composition |
asinh, acosh, atanh | 32 | 19.7, 16.8, 24.7 | Algorithms L and L′, composition |
§Tables
The constants of the algorithms are private tables of literals
(elementary/tables.rs): parts of ln 2/64 and ln 2, 2^(j/64),
2^(j/64) − 1, e^(N/64) − 1, 1/n!, 1/n, ln(1 + j/64) and its
two shifted forms, atan(c) at 144 points, and 1 408 bits of 2/π
and 320 of π/4. A unit test checks each entry, bit for bit, against
dashu-float and against the independent enclosures of the tests.
§References
Muller, Elementary Functions: Algorithms and Implementation, 3rd ed.
(2016): Cody–Waite and Payne–Hanek reduction, table-driven methods
(Tang) — cited from memory. Tang, “Table-driven implementation of the
exponential function in IEEE floating-point arithmetic”, ACM TOMS 15
(1989) — from memory. Payne & Hanek, “Radian reduction for
trigonometric functions”, SIGNUM Newsletter 18 (1983) — from memory.
For Lemma D: Muller, op. cit., Chapter 11 (the worst cases of f64
for the reduction, by continued fractions, among them
6 381 956 970 095 103 · 2⁷⁹⁷) — from memory; Khinchin, Continued
Fractions (1964), Theorems 16–17 (best approximations) — from memory;
Lenstra, Lenstra & Lovász, “Factoring polynomials with rational
coefficients”, Math. Ann. 261 (1982), and Cohen, A Course in
Computational Algebraic Number Theory (1993), Algorithm 2.6.7 (the
integral LLL) — from memory; the lower bound λ₁ ≥ min ‖b_i*‖ is
proven in D5.
Joldes, Muller & Popescu (2017) and the other sources of Chapter 11.2
for the bounds of the operations. C99 Annex F and IEEE 754-2019 §9.2 for
the special cases (as restated in the documentation of f64).
Modules§
- tables 🔒
- The literal tables of Chapter 11.11 (private). Every double-double entry
is the pair
(RN(c), RN(c − RN(c)))of the valuecnamed in the comment of its table, as the bits(hi, lo); everyf64is the value named, rounded to nearest. They were generated withdashu-floatat 2 400 bits and are checked entry by entry, bit for bit, by the unit testtables_are_the_nearest_double_doublesof the parent module against two independent oracles.
Structs§
- Function
Bound - The declared error bound of one elementary function of
DoubleDouble:|z − f(x)| ≤ (units_of_u2 + growth_units_of_u2 · G) u² |f(x)| + absolute, for results of magnitude in [2⁻⁹⁶⁸, Ω] (below:+ η).
Constants§
- ATAN2_
SCALE 🔒 2⁶⁰⁰: the scale of a tiny quotient inatan2.- ATAN2_
TINY 🔒 2⁻⁹⁶⁸: a smaller scaled magnitude below it takes step Q1 ofatan2.- ATAN_
DIRECT 🔒 |a_h| < ATAN_DIRECTtakes step T1.- ATAN_
RECIP 🔒 a_h ≥ ATAN_RECIPtakes step T3.- ATAN_
TERMS 🔒 - The last term
t^(2m+1)/(2m+1)of the series ofatan t(|t| ≤ 1/64). - EXPM1_
EXACT_ 🔒K |k| ≤ EXPM1_EXACT_Kmakes2ᵏ − 1anf64(step M3).- EXPM1_
SMALL 🔒 |x_h| < EXPM1_SMALLtakes step M1.- EXPM1_
TERMS 🔒 - The last term in step M1 (
|r| ≤ 1/64). - EXP_
OVERFLOW 🔒 x_h > EXP_OVERFLOWgiveseˣ = +∞(ln MAX_dd ≈ 709.7827; between the two the computation overflows by itself, Theorem E (iv)).- EXP_
TERMS 🔒 - The last term
r^m/m!ofeʳ − 1in Algorithm E (|r| ≤ 0.005 43). - EXP_
UNDERFLOW 🔒 x_h < EXP_UNDERFLOWgiveseˣ < η/2:expreturns+0,exp_m1returns−1.- E_HALF 🔒
e/2(the tableE, scaled exactly).- FRAC_
PI_ 🔒4_ HI RN(π/4):|x|_h ≤ FRAC_PI_4_HIneeds no reduction (step S1).- HYPER_
LARGE 🔒 sinh,coshabove it useexp(a − 1) · e/2.- LEMMA_
D_ 🔒FLOOR 2⁻¹⁴¹: every|r|of Algorithm R exceeds it (Lemma D; asserted in debug builds only, so that no result depends on it).- LN1P_
SMALL 🔒 |x_h| < LN1P_SMALLtakes step L′1.- LN_
TERMS 🔒 - The last term
z^m/mof the series ofln(1 + z)(step L4). - REDUCTION_
QUANTUM 🔒 2⁻³⁸²: the smallest nonzero|r|of Algorithm R (step S4).- SIN_
HALF_ 🔒TERMS - The last term of
sin h,|h| ≤ π/8, insidecos r(step S2). - SIN_
TERMS 🔒 - The last term
r^(2m+1)/(2m+1)!ofsin r,|r| ≤ π/4(step S2). - SQRT_
2_ 🔒HI RN(√2):y_h ≥ SQRT_2_HIhalvesyin step L1.- SQRT_
SAFE 🔒 2⁻⁹⁶⁸: below it Algorithm R loses its bound, and step W scales.- TANH_
SPLIT 🔒 tanhbelow it usesexp_m1(2a), above itexp(−2a).- TAN_
GROWTH 🔒 2⁻⁹⁴ = 2⁻²⁰⁰/u²: the growth coefficient oftan.- TINY 🔒
2⁻⁴⁰⁰: below it a series is its first term (to2⁻⁴⁰⁰relative), and above it no product of a series underflows.- TRIG_
FLOOR 🔒 2⁻²⁰⁰, the absolute floor of the circular functions.- TWO_53 🔒
2⁵³: from here on1 + xloses nothing that matters (step L′3).- TWO_60 🔒
2⁶⁰:asinh,acoshabove it areln x + ln 2.- WINDOW_
SHIFT 🔒 I = e + WINDOW_SHIFTin step R1: 318 fraction bits, 53 form, 11 guard bits.
Functions§
- atan_
positive 🔒 - Algorithm T for a finite
a ≥ 0. - atan_
series 🔒 atan tby the series of step T1,|t| ≤ 1/64.- beyond_
one 🔒 |x| > 1(NaN excluded).- chunk53 🔒
- Bits
[t, t + 53)of a little-endian number (zeros below bit 0). - circular 🔒
- component 🔒
- Step R1 for one component:
A_c(five little-endian words), negated modulo2³²⁰for a negativec(a trailing component may be). - cos_
from 🔒 cos xfrom(q, r)(step S3).- cos_
kernel 🔒 cos r = 1 − 2 sin²(r/2)for|r| ≤ π/4(step S2).- cosine_
of_ 🔒arcsine √((1 − a)(1 + a))for0 ≤ a ≤ 1(asin,acos).- e_ln2 🔒
- Step L6:
e ln 2,e ≠ 0,|e| < 2¹¹. - entry 🔒
- A table entry
(hi, lo)as a double-double. - exp_
reconstruct 🔒 - Steps E3–E4.
- exp_
reduce 🔒 - Steps E1–E2:
x = (64k + j) ln 2/64 + r. - expm1_
poly 🔒 P(r) = eʳ − 1byr + r² Q(r),Q = Σ_{m=2}^{terms} r^(m−2)/m!(step E3).- exponent 🔒
- The unbiased exponent of a positive normal
f64. - half_
exp_ 🔒large exp(a − 1) · e/2 = eᵃ/2fora ≥ 709(a − 1exact).- index 🔒
- A table index
j + offsetforj ∈ [−offset, …]. - integer_
significand 🔒 x = m 2ᵉfor a finitex ≥ 0,m < 2⁵³an integer.- is_
integer 🔒 y(finite) is an integer: both components are.- is_odd 🔒
- An integer double-double is odd (by the trailing component when it is
nonzero, since then
|y_h| ≥ 2⁵³is even). - is_
odd_ 🔒f64 - An integer
f64is odd. - ln1p_
series 🔒 ln(1 + z)by step L4.- ln_
cancelling 🔒 - The two cancelling cases of step L5.
- ln_
parts 🔒 - Steps L1–L4 for a finite
x > 0:(e, y_h, j, L). - ln_
positive 🔒 - Algorithm L for a finite
x > 0. - ln_
twice 🔒 ln x + ln 2forx ≥ 2⁶⁰.- ln_y 🔒
ln yof step L5.- magnitude_
component 🔒 - Step R1 for
c ≥ 0. - minus_
sixty_ 🔒fourths (x_h − n/64) + x_ℓforn = round(64 x_h)ortrunc(64 x_h): exact (andxitself, signed zero included, whenn = 0).- mul_
words 🔒 a · bfor little-endian words,out.len() = a.len() + b.len().- plain 🔒
- pow2 🔒
2ᵏfor|k| ≤ 1022.- quadrant 🔒
- Step S1 on
|x|:(q, r). - reduce 🔒
- Algorithm R for a finite
x > π/4:(q, r)withx ≡ qπ/2 + r. - renormalize 🔒
- Renormalizes
a > 0into[1, 2):(a 2^−k, k). - signed_
limit 🔒 ±∞(big) or±0, negative whenneg.- sin_
from 🔒 sin xfrom(q, r)and the sign ofx(step S3).- sin_
kernel 🔒 sin rfor|r| ≤ π/4by step S2, the series toterms.- split 🔒
x = 2^e y,y ∈ [1, 2), for a finitex > 0.- sqrt_w 🔒
√vforv ≥ 0by step W (Lemma W): Algorithm R, onv · 2⁶⁰⁰when0 < v_h < 2⁻⁹⁶⁸.- tan_
from 🔒 tan xfrom(q, r)and the sign ofx(steps S3, S4).- to_i32 🔒
- An integer-valued
f64of magnitude below2³¹, as ani32. - two_
over_ 🔒pi_ bits - The 64 bits of
N = ⌊2¹⁴⁰⁸ · 2/π⌋from bittup (bit 0 the least significant; zeros outside[0, 1408)).