Skip to main content

Module elementary

Module elementary 

Source
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, where w_a = |a|/|a + b|, w_b = |b|/|a + b| are the weights (both at most 1 when a and b have the same sign; their sum is the cancellation factor otherwise). With an exact f64 b, A1 gives w_a α + 2.
  • (C2) Products and quotients. M2: α + β + 4; M1 (exact f64 factor): α + 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): every two_prod it forms at least 2⁻⁹⁶⁹ in magnitude or exact (T2), no overflow, and for R an operand v ≥ 2⁻⁹⁶⁸ (LLMPR). Outside, a product or a quotient leaves an absolute error up to η and R a relative one up to u. 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 below 2⁻⁴⁰⁰, or a result itself below 2⁻⁹⁶⁸, where η is allowed) or treats the case by a separate step (Lemma W, the second form of atanh).
  • (C3) Exact steps add nothing: negation, ldexp (in the normal range), DoubleDouble::from_sum, DoubleDouble::from_product in its range, Sterbenz subtractions a − b of f64 with b/2 ≤ a ≤ 2b, and the operations whose result the text shows to be exact.
  • (C4) Arguments. If f is evaluated at â instead of a by an algorithm with ε ≤ φ against f(â), then against f(a) the bound is φ + κ ε(â), where κ bounds the condition number |a f′(a)/f(a)| between a and â; 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 relative u) into f.
  • (C5) A tiny addend (Lemma S). If b ∈ F and |b| ≤ 2⁻¹⁰ u |a_h|, A1 returns a + b with absolute error at most u²|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 rounds v = a_ℓ + b, |v| ≤ (u + 2⁻¹⁰u)|a_h|, with error at most u|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 every k (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 from k = M, ε(q_k) ≤ E for every k ≥ 1 with E = ((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), for a_h ≤ 709; exp(a − 1) · e/2 above (a − 1 is exact there, e/2 is E/2 of 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) and 1/(E + 2): largest as E → 0, 3 + (7.15 + 24.15)/2 = 18.7. Above 709: 4.6 + 1 + 4 = 9.6 (the neglected e⁻ᵃ is 2⁻²⁰⁴⁵ relative). Below 2⁻⁴⁰⁰ the result is a.
  • cosh a = (E + 1/E)/2, E = exp(a), for a_h ≤ 709; exp(a − 1) · e/2 above. Bound: ε(1/E) ≤ 4.6 + 15; the weights E²/(E² + 1) and 1/(E² + 1), largest at E = 1: 3 + (4.6 + 19.6)/2 = 15.1. Range: near a = 709, 1/E is near 2⁻¹⁰²³ and its D2 can err by η, with the weight 1/(E² + 1) < 2⁻²⁰⁴⁴.
  • tanh a = E₂/(E₂ + 2), E₂ = exp_m1(2a), for a < 5/16; else (1 − F)/(1 + F), F = exp(−2a). Bound: below 5/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 large a, F underflows (an absolute η against 1) and D2 returns the pair (1, −2F) until F < η/2, then exactly 1.
  • asinh a = ln_1p(a + a²/(1 + √(1 + a²))) for a < 2, ln(a + √(a² + 1)) for 2 ≤ a < 2⁶⁰, ln a + ln 2 above (asinh a − ln 2a < 2⁻¹²² of it). Bound: for a < 2, ε(√(1 + a²)) ≤ 2.2 + 25/8, ε(1 + √) ≤ 5.68, ε(a²/(1 + √)) ≤ 23.7, and in the argument v of ln_1p its weight is at most 0.382: ε(v) ≤ 12.1; the condition number of ln_1p is at most 1: ε ≤ 7.64 + 12.1 = 19.7. For 2 ≤ a < 2⁶⁰, ε(v) ≤ 3 + 0.528 · 5.63 and the condition number of ln at v ≥ 4.23 is 1/ln v ≤ 0.693: ε ≤ 6.63 + 4.14 = 10.8. Above: 3 + 6.63 = 9.63. Range (C2): below 2⁻⁴⁰⁰ the result is a; above, a² ≥ 2⁻⁸⁰⁰ and the products of the quotient a²/(1 + √(1 + a²)) are of that size, above 2⁻⁹⁶⁹ (outside the conservative safe range of Chapter 11.2, but every two_prod is exact), and the quotient weighs a/2 in v.
  • acosh x = ln_1p(d + √(d(d + 2))), d = x − 1 (exact), for x < 2; ln(x + √(x² − 1)) for 2 ≤ x < 2⁶⁰; ln x + ln 2 above. 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 when x_h = 1 and d = x_ℓ < 2⁻⁹⁶⁹, where M2 errs by less than 2⁻⁵³⁶ relative, as in acos, and acosh 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, with 1 − a exact for a ≥ 1/2 and A1 below. Bound: ε(2a/(1 − a)) ≤ 2 + 15, condition number of ln_1p at most 1: ε ≤ 7.64 + 17 = 24.7. If 1 − a is subnormal (then a = (1, −δ), δ < 2⁻¹⁰²², and 2a/(1 − a) ≈ 2/δ exceeds Ω once δ < 2⁻¹⁰²³), atanh a = (ln(1 + a) − ln(1 − a))/2 instead, with 1 + a = (2, −δ) exact (A1) and 1 − a = δ: Theorem L twice, and A2 on two positive terms (ln(2 − δ) > 0, −ln δ > 0): ε ≤ 6.63 + 3 = 9.7. For a normal 1 − a below 2⁻⁴⁷⁹ the quotient exceeds 2⁴⁸⁰, outside the conservative safe range of Chapter 11.2, but the products of D2 are near 2a and its divisor is normal, so its hypotheses (T2, no overflow) hold and so does 15u². Below 2⁻⁴⁰⁰ the result is a.

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.

functiondeclaredprovenhow
exp, exp284.6Algorithm E
exp_m187.2Algorithm M
ln86.7Algorithm L
ln_1p87.7Algorithm L′
log2, log101211.7Algorithm L, then a product
powi15 + 4|n|11 + 4|n|Algorithm P
powf16 + 11|y ln x|4.6 + 10.7|y ln x|exp(y ln x) (Theorem F)
sin, cos, sin_cos8|f| + 2⁻²⁰⁰6.9|f| + 2⁻³¹⁵Algorithms R and K
tan32|tan| + 2⁻²⁰⁰(1 + tan²)27.4|tan| + 2⁻³¹⁵(1 + tan²)Algorithms R and K, D2; Lemma D
atan85.8Algorithm T
atan2, asin, acos3220, 26.1, 26.1Algorithm T, composition
sinh, cosh, tanh3218.7, 15.1, 26.4Algorithms E and M, composition
asinh, acosh, atanh3219.7, 16.8, 24.7Algorithms 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 value c named in the comment of its table, as the bits (hi, lo); every f64 is the value named, rounded to nearest. They were generated with dashu-float at 2 400 bits and are checked entry by entry, bit for bit, by the unit test tables_are_the_nearest_double_doubles of the parent module against two independent oracles.

Structs§

FunctionBound
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 in atan2.
ATAN2_TINY 🔒
2⁻⁹⁶⁸: a smaller scaled magnitude below it takes step Q1 of atan2.
ATAN_DIRECT 🔒
|a_h| < ATAN_DIRECT takes step T1.
ATAN_RECIP 🔒
a_h ≥ ATAN_RECIP takes step T3.
ATAN_TERMS 🔒
The last term t^(2m+1)/(2m+1) of the series of atan t (|t| ≤ 1/64).
EXPM1_EXACT_K 🔒
|k| ≤ EXPM1_EXACT_K makes 2ᵏ − 1 an f64 (step M3).
EXPM1_SMALL 🔒
|x_h| < EXPM1_SMALL takes step M1.
EXPM1_TERMS 🔒
The last term in step M1 (|r| ≤ 1/64).
EXP_OVERFLOW 🔒
x_h > EXP_OVERFLOW gives eˣ = +∞ (ln MAX_dd ≈ 709.7827; between the two the computation overflows by itself, Theorem E (iv)).
EXP_TERMS 🔒
The last term r^m/m! of eʳ − 1 in Algorithm E (|r| ≤ 0.005 43).
EXP_UNDERFLOW 🔒
x_h < EXP_UNDERFLOW gives eˣ < η/2: exp returns +0, exp_m1 returns −1.
E_HALF 🔒
e/2 (the table E, scaled exactly).
FRAC_PI_4_HI 🔒
RN(π/4): |x|_h ≤ FRAC_PI_4_HI needs no reduction (step S1).
HYPER_LARGE 🔒
sinh, cosh above it use exp(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_SMALL takes step L′1.
LN_TERMS 🔒
The last term z^m/m of the series of ln(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, inside cos r (step S2).
SIN_TERMS 🔒
The last term r^(2m+1)/(2m+1)! of sin r, |r| ≤ π/4 (step S2).
SQRT_2_HI 🔒
RN(√2): y_h ≥ SQRT_2_HI halves y in step L1.
SQRT_SAFE 🔒
2⁻⁹⁶⁸: below it Algorithm R loses its bound, and step W scales.
TANH_SPLIT 🔒
tanh below it uses exp_m1(2a), above it exp(−2a).
TAN_GROWTH 🔒
2⁻⁹⁴ = 2⁻²⁰⁰/u²: the growth coefficient of tan.
TINY 🔒
2⁻⁴⁰⁰: below it a series is its first term (to 2⁻⁴⁰⁰ 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 on 1 + x loses nothing that matters (step L′3).
TWO_60 🔒
2⁶⁰: asinh, acosh above it are ln x + ln 2.
WINDOW_SHIFT 🔒
I = e + WINDOW_SHIFT in step R1: 318 fraction bits, 53 for m, 11 guard bits.

Functions§

atan_positive 🔒
Algorithm T for a finite a ≥ 0.
atan_series 🔒
atan t by 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 modulo 2³²⁰ for a negative c (a trailing component may be).
cos_from 🔒
cos x from (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)) for 0 ≤ 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ʳ − 1 by r + 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ᵃ/2 for a ≥ 709 (a − 1 exact).
index 🔒
A table index j + offset for j ∈ [−offset, …].
integer_significand 🔒
x = m 2ᵉ for a finite x ≥ 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 f64 is 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 2 for x ≥ 2⁶⁰.
ln_y 🔒
ln y of step L5.
magnitude_component 🔒
Step R1 for c ≥ 0.
minus_sixty_fourths 🔒
(x_h − n/64) + x_ℓ for n = round(64 x_h) or trunc(64 x_h): exact (and x itself, signed zero included, when n = 0).
mul_words 🔒
a · b for 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) with x ≡ qπ/2 + r.
renormalize 🔒
Renormalizes a > 0 into [1, 2): (a 2^−k, k).
signed_limit 🔒
±∞ (big) or ±0, negative when neg.
sin_from 🔒
sin x from (q, r) and the sign of x (step S3).
sin_kernel 🔒
sin r for |r| ≤ π/4 by step S2, the series to terms.
split 🔒
x = 2^e y, y ∈ [1, 2), for a finite x > 0.
sqrt_w 🔒
√v for v ≥ 0 by step W (Lemma W): Algorithm R, on v · 2⁶⁰⁰ when 0 < v_h < 2⁻⁹⁶⁸.
tan_from 🔒
tan x from (q, r) and the sign of x (steps S3, S4).
to_i32 🔒
An integer-valued f64 of magnitude below 2³¹, as an i32.
two_over_pi_bits 🔒
The 64 bits of N = ⌊2¹⁴⁰⁸ · 2/π⌋ from bit t up (bit 0 the least significant; zeros outside [0, 1408)).