Skip to main content

xingo_extprec/
elementary.rs

1//! # Chapter 11.11 — Elementary functions of double-doubles
2//!
3//! ## Purpose
4//! The elementary functions of [`DoubleDouble`] (task L2.4; contract
5//! ratified as D-0121): the exponentials, logarithms and powers, the
6//! circular functions and their inverses, the hyperbolic functions and
7//! their inverses — the names and special cases of `f64` — and the 19
8//! constants of `core::f64::consts`. Each function has a declared error
9//! bound, a row of [`DoubleDouble::FUNCTION_BOUNDS`], and each bound is
10//! **proven** below: the four kernels (exponential, logarithm, sine and
11//! cosine, arctangent) directly, the other functions by composition. No
12//! bound was fitted to a measurement; the tests measure against two
13//! independent oracles and report the largest errors seen.
14//!
15//! ## Notation
16//! As in Chapters 11.1 and 11.2: `RN` is rounding to nearest even, `u =
17//! 2⁻⁵³`, `u² = 2⁻¹⁰⁶`, `η = 2⁻¹⁰⁷⁴`, `Ω` the largest finite `f64`.
18//! `MAX_dd = (Ω, ℓ)`, with `ℓ` the largest `f64` below `ulp(Ω)/2`, is the
19//! largest finite double-double. The operations A1 (`dd + f64`), A2 (`dd +
20//! dd`), M1 (`dd · f64`), M2 (`dd · dd`), M3 (`dd²`), D1 (`dd / f64`), D2
21//! (`dd / dd`) and R (`√dd`) are those of Chapter 11.2, with their proven
22//! relative bounds `2u²`, `3u²`, `2u²`, `4u²`, `3u²`, `3u²`, `15u²`,
23//! `25/8 u²` (first-order constants; the exact expressions are in that
24//! chapter). A *table entry* is the nearest double-double of its value,
25//! with relative error at most `u²(1 + u)`. "`x ∈ dd`" means a normalized
26//! double-double (invariant D1).
27//!
28//! ## How the bounds are stated
29//! A function `f` with declared constants `(c, c₂, G, A)` (one row of
30//! [`DoubleDouble::FUNCTION_BOUNDS`]) returns, for every finite argument
31//! whose result `f(x)` has magnitude in `[2⁻⁹⁶⁸, Ω]`, a value `z` with
32//!
33//! ```text
34//! |z − f(x)| ≤ (c + c₂·G) u² |f(x)| + A,
35//! ```
36//!
37//! and for results of smaller magnitude the same plus `η` (the trailing
38//! component loses bits to the subnormal range; Chapter 11.2, "safe
39//! range"). `G` is `|n|` in `powi`, `|y ln x|` in `powf`, `|tan x|` in
40//! `tan` (where `c₂ = 2⁻⁹⁴` turns `A(1 + tan²x)` into this form) and absent
41//! elsewhere; `A` is `2⁻²⁰⁰` for the circular functions and their pair
42//! and `0` elsewhere. Nothing is correctly rounded.
43//!
44//! ## How the bounds are proved (the error calculus)
45//! For a computed `ẑ` of an exact `z` write `ε(ẑ) ≤ c` for `|ẑ − z| ≤ c u²
46//! |z|`, and work to first order in `u²`: every product of two such
47//! errors is below `(64u²)² < 2⁻¹⁹⁹`, and a proof that sums at most a few
48//! hundred of them at a constant of at most a few hundred `u²` is changed by
49//! less than one part in `2⁸⁰`. Each proven constant `c*` is therefore
50//! honest up to the factor `1 + 2⁻⁸⁰`, and every declared constant exceeds
51//! its `c*` by more than that. The rules, all from Chapter 11.2:
52//!
53//! * **(C1) Sums.** If `ε(â) ≤ α`, `ε(b̂) ≤ β`, A2 returns `ŝ` with `ε(ŝ) ≤
54//!   w_a α + w_b β + 3`, where `w_a = |a|/|a + b|`, `w_b = |b|/|a + b|` are
55//!   the *weights* (both at most 1 when `a` and `b` have the same sign;
56//!   their sum is the cancellation factor otherwise). With an exact `f64`
57//!   `b`, A1 gives `w_a α + 2`.
58//! * **(C2) Products and quotients.** M2: `α + β + 4`; M1 (exact `f64`
59//!   factor): `α + 2`; M3: `2α + 3`; D2: `α + β + 15`; D1: `α + 3`;
60//!   R: `α/2 + 25/8`. *Range.* These constants are theorems only where
61//!   the operation's own hypotheses hold (Chapter 11.2): every `two_prod`
62//!   it forms at least `2⁻⁹⁶⁹` in magnitude or exact (T2), no overflow,
63//!   and for R an operand `v ≥ 2⁻⁹⁶⁸` (LLMPR). Outside, a product or a
64//!   quotient leaves an absolute error up to `η` and R a relative one up
65//!   to `u`. Every proof below therefore says, for each operation whose
66//!   operands or result can be that small or that large, why it does not
67//!   matter (a term whose weight in the result is below `2⁻⁴⁰⁰`, or a
68//!   result itself below `2⁻⁹⁶⁸`, where `η` is allowed) or treats the case
69//!   by a separate step (Lemma W, the second form of `atanh`).
70//! * **(C3) Exact steps** add nothing: negation, `ldexp` (in the normal
71//!   range), [`DoubleDouble::from_sum`], [`DoubleDouble::from_product`]
72//!   in its range, Sterbenz subtractions `a − b` of `f64` with `b/2 ≤ a ≤
73//!   2b`, and the operations whose result the text shows to be exact.
74//! * **(C4) Arguments.** If `f` is evaluated at `â` instead of `a` by an
75//!   algorithm with `ε ≤ φ` against `f(â)`, then against `f(a)` the bound is
76//!   `φ + κ ε(â)`, where `κ` bounds the condition number `|a f′(a)/f(a)|`
77//!   between `a` and `â`; or, in absolute terms, `|f(â) − f(a)| ≤ |â − a|
78//!   max|f′|`. The `ε(â)` is the one of (C2), so (C4) inherits its range
79//!   hypotheses: an `â` computed outside them carries the absolute error
80//!   `η` (or, after R, the relative `u`) into `f`.
81//! * **(C5) A tiny addend (Lemma S).** If `b ∈ F` and `|b| ≤ 2⁻¹⁰ u |a_h|`,
82//!   A1 returns `a + b` with absolute error at most `u²|a_h|(1 + 2⁻⁹)`.
83//!   *Proof.* `|b| < ulp(a_h)/2`, so step 1 of A1 is `(s_h, s_ℓ) = (a_h,
84//!   b)`, exactly; step 2 rounds `v = a_ℓ + b`, `|v| ≤ (u + 2⁻¹⁰u)|a_h|`,
85//!   with error at most `u|v|`; step 3 is exact (Chapter 11.1, T1). ∎
86//! * **(C6) Horner (Lemma H).** Let `Q = q₀`, `q_k = c_k + s q_{k+1}`
87//!   (`k = M − 1, …, 0`), `q_M = c_M`, be evaluated with A2 and M2 from
88//!   table coefficients (`ε ≤ σ_k`, `σ_k ∈ {0, 1}`) and a computed `ŝ`
89//!   with `ε(ŝ) ≤ ε_s`, and suppose `|s q_{k+1}| ≤ ρ |q_k|` and `|c_k| ≤
90//!   (1 + ρ)|q_k|` for every `k` (the terms of an alternating or decreasing
91//!   series with ratio at most `ρ`). Then `ε(q_k) ≤ (1 + ρ)σ_k + ρ(ε_s + 4 +
92//!   ε(q_{k+1})) + 3`, and by induction from `k = M`, `ε(q_k) ≤ E` for every
93//!   `k ≥ 1` with `E = ((1 + ρ)σ̄ + ρ(ε_s + 4) + 3)/(1 − ρ)`, `σ̄ = max σ_k`;
94//!   `ε(Q) ≤ (1 + ρ)σ₀ + ρ(ε_s + 4 + E) + 3`. ∎
95//! * **(C7) Truncation.** A series cut after its `N`-th term is charged the
96//!   bound of its remainder, relative to the value, as one more term.
97//!
98//! A product `two_prod(a, b)` with `|a b| < 2⁻⁹⁶⁹` is not exact (Chapter
99//! 11.1, T2) and leaves an absolute error up to `η`; each proof says why
100//! that does not matter where it can happen (an intermediate far below the
101//! scale of the result, or a branch for tiny arguments that avoids it).
102//!
103//! ## Algorithm E (`exp`, `exp2`: Tang's table-driven exponential)
104//! Input `x ∈ dd`, finite, `−745.2 ≤ x_h ≤ 709.79` (outside: `+0`, `+∞`,
105//! NaN by the table of special cases). `ℓ = ln 2/64`; `C₁, C₂, C₃` its three
106//! parts of 53 bits (`|ℓ − C₁ − C₂ − C₃| < 2⁻¹⁶⁶`); `T_j` the table entry of
107//! `2^(j/64)`.
108//!
109//! E1. [Index.] `n ← round(x_h · RN(64/ln 2))`, an integer with `|n| ≤
110//!     2¹⁷`; `k ← ⌊n/64⌋`, `j ← n − 64k ∈ [0, 64)`.
111//! E2. [Reduce.] `r ← ((x − n C₁) − n C₂) − n C₃` with each `n Cᵢ` an exact
112//!     product (`from_product`) and each subtraction A2; if `n = 0`, `r ← x`.
113//!     Then `x = n ℓ + r` up to the error `δ_r` below, and `|r| ≤ ρ_E =
114//!     0.005 43` (`ℓ/2 = 0.005 415` plus the rounding of `n`).
115//! E3. [Polynomial.] `p ← P(r)`, where `P(r) = r + r²Q(r)` and `Q(r) =
116//!     Σ_{m=2}^{11} r^(m−2)/m!` by Horner (Lemma H); `P(r) ← r` when `|r_h| <
117//!     2⁻⁴⁰⁰` (then `|eʳ − 1 − r| ≤ r² < 2⁻⁴⁰⁰|r|`).
118//! E4. [Reconstruct.] `z ← (T_j + T_j·p) · 2ᵏ` (M2, A2, `ldexp`).
119//!
120//! `exp2` replaces E1–E2 by: `n ← round(64 x_h)`, `y ← (x_h − n/64) + x_ℓ`
121//! (exact: `x_h − n/64` is a Sterbenz difference scaled by `2⁻⁶`, and
122//! `from_sum` adds `x_ℓ` exactly), `r ← y · LN_2` (M2), `|y| ≤ 1/128`. For an
123//! integer `x`, `y = r = p = 0` and the result is `1 · 2ᵏ`, exact for `k ∈
124//! [−1074, 1023]`.
125//!
126//! **Theorem E.** For results in `[2⁻⁹⁶⁸, Ω]`, `ε(exp) ≤ 4.6` and
127//! `ε(exp2) ≤ 4.6`; below, the bound plus `η`.
128//!
129//! *Proof.* (i) *Reduction.* The exact `r* = x − nℓ`. The first difference
130//! has the exact value `r₁ = r* + n(C₂ + C₃) + nτ`, `|nC₂| ≤ 2¹⁷ · 2⁻⁶⁰`
131//! (`C₂ ≤ ulp(C₁)/2`), so `|r₁| ≤ ρ_E + 2⁻⁴²`; each of the three A2 errs by
132//! at most `3u²` times its result, so `δ_r = |r − r*| ≤ 3u²(3ρ_E + 2⁻⁴¹) +
133//! 2¹⁷ · 2⁻¹⁶⁶ < 0.05u²`. As an absolute error of the argument of `eʳ` it is
134//! a relative error of the result (C4): `0.05`. For `exp2`, `r = y LN_2`
135//! with `ε ≤ 1 + 4` (table, M2), an absolute `5u² ρ_E < 0.03u²`.
136//! (ii) *Polynomial.* In Lemma H, `s = r` is exact (we bound against
137//! `P(r)` at the computed `r`), the coefficient ratio is `|r|/(m + 1) ≤
138//! ρ_E/3`, so `ρ = 0.0019`, `σ₀ = 0` (`1/2` is exact) and `σ = 1`: `E =
139//! (1.0019 + 0.0076 + 3)/0.9981 = 4.02`, `ε(Q) ≤ 0.0019 · 8.02 + 3 = 3.02`.
140//! `ε(r²) = 3`, `ε(r²Q) ≤ 3 + 3.02 + 4 = 10.02`. In `r + r²Q` the weights are
141//! `|r|/|P| ≤ 1/(1 − ρ_E/2) ≤ 1.0028` (exact term) and `|r²Q|/|P| ≤ 0.0028`:
142//! `ε ≤ 0.0028 · 10.02 + 3 = 3.03`. The remainder `Σ_{m≥12} |r|^m/m! <
143//! 1.01 ρ_E^11/12! · |r| < 2⁻¹¹¹|P|` adds `0.02`: `ε(p) ≤ 3.05`.
144//! (iii) *Reconstruction.* `ε(T_j p) ≤ 1 + 3.05 + 4 = 8.05`; in `T_j +
145//! T_j p` the weights are `1/|1 + p| ≤ 1.0055` and `|p|/|1 + p| ≤ 0.0055`
146//! (`|p| ≤ e^ρ_E − 1 < 0.005 45`): `ε ≤ 1.0055 · 1 + 0.0055 · 8.05 + 3 =
147//! 4.05`. With (i), `4.10` (`exp`) and `4.08` (`exp2`).
148//! (iv) *Scaling.* `ldexp` is exact while both components stay normal.
149//! When the result is at least `2⁻⁹⁶⁸` its leading component is normal and
150//! only the trailing one can round, by at most `η/2 = 2⁻¹⁰⁷⁵ ≤ u²|z|/2`: `+
151//! 0.5`. Below `2⁻⁹⁶⁸` the scaling is done in two multiplications when `k <
152//! −1000`, and the trailing component may round twice; the two components
153//! together err by at most `η`. Overflow of
154//! `ldexp` returns `+∞` (step E of Chapter 11.2), which happens only when
155//! `T_j(1 + p) 2ᵏ`, within `4.6u²` of `eˣ`, exceeds `MAX_dd`. ∎
156//!
157//! Underflow inside: no product of E2–E4 leaves the range of `two_prod`
158//! when `|r| ≥ 2⁻⁴⁰⁰`, and for smaller `r` the only product is `T_j r`,
159//! whose absolute error (`≤ η`) is negligible against `T_j ≥ 1`.
160//!
161//! ## Algorithm M (`exp_m1`)
162//! Input `x ∈ dd`, finite; `x_h > 709.79` gives `+∞` and `x_h < −745.2`
163//! gives `−1` (then `0 < eˣ < η/2`). `D_N` is the table entry of `e^(N/64) −
164//! 1`, `T_j` and `D′_j` those of `2^(j/64)` and `2^(j/64) − 1`.
165//!
166//! M1. [Small.] If `|x_h| < 1/2`: `N ← trunc(64 x_h) ∈ [−31, 31]`, `r ←
167//!     (x_h − N/64) + x_ℓ` — exact, as in `exp2`, and with the sign of `x`
168//!     (or `|r| ≤ u|x|`). `p ← P(r)` with the terms up to `m = 13` (Q of 12
169//!     coefficients), `|r| ≤ 1/64`. If `N = 0` return `p`; else return `(D_N +
170//!     D_N p) + p`.
171//! M2. [Large.] Else E1–E3 give `k`, `j`, `r`, `p`. If `|k| > 53` return
172//!     `T_j(1 + p)2ᵏ − 1` (E4, then A1 with `−1`).
173//! M3. Else return `(2ᵏD′_j + (2ᵏ − 1)) + 2ᵏ(T_j p)` — `2ᵏ − 1` is an exact
174//!     `f64` for `|k| ≤ 53`, the first sum is A1, the second A2.
175//!
176//! **Theorem M.** `ε(exp_m1) ≤ 7.2` for results in `[2⁻⁹⁶⁸, Ω]`.
177//!
178//! *Proof.* *Small, `N = 0`:* Lemma H with `ρ = (1/64)/3 = 0.0053`: `E =
179//! (1.0053 + 0.0212 + 3)/0.9947 = 4.05`, `ε(Q) ≤ 0.0053 · 8.05 + 3 = 3.05`,
180//! `ε(r²Q) ≤ 10.05`; weights `|r|/|P| ≤ 1/(1 − 1/128) = 1.008`, `|r²Q|/|P|
181//! ≤ 0.008`; remainder `< 2⁻¹¹⁴|P|`: `ε(p) ≤ 0.008 · 10.05 + 3 + 0.01 =
182//! 3.09`. *Small, `N ≠ 0`:* `ε(D p) ≤ 1 + 3.09 + 4 = 8.09`; `A = D + Dp =
183//! D(1 + p)` has weights `1/|1 + p| ≤ 1.016` and `|p|/|1 + p| ≤ 0.016`, so
184//! `ε(A) ≤ 1.016 + 0.13 + 3 = 4.15`. `A` and `p` have the sign of `x` (`N`
185//! and `r` do; in the exceptional case `|r| ≤ u|x|` the weights exceed 1
186//! by less than `2⁻⁴⁵`), so in `A + p` the weights sum to 1 and `ε ≤
187//! max(4.15, 3.09) + 3 = 7.15`. *Large:* count absolute errors in units of
188//! `u²`. `S = 2ᵏD′_j + (2ᵏ − 1)` errs by at most `2ᵏD′_j` (table) `+ 2|S|`
189//! (A1); `V = 2ᵏT_j p` by at most `2ᵏT_j(0.0055 · 8.05 + 0.05) = 0.094 ·
190//! 2ᵏT_j` (Theorem E (i)–(iii)); the last A2 adds `3|z|`. For `k ≥ 1`, `|z|
191//! ≥ 0.4946 · 2ᵏT_j`, so `2ᵏT_j/|z| ≤ 2.03`, `2ᵏD′_j/|z| ≤ 0.68` (largest
192//! at `k = 1`, `T_j → 2`) and `|S|/|z| ≤ 1.011`: `ε ≤ 0.68 + 2.03 + 0.19 + 3
193//! = 5.9`. For `k = 0` (`x ∈ [1/2, 0.688)`, so `j ≥ 46`, `|z| ≥ 0.648`):
194//! `D′_j/|z| ≤ 1.02`, `T_j/|z| ≤ 2.6`: `ε ≤ 1.02 + 2.04 + 0.25 + 3 = 6.3`.
195//! For `k ≤ −1` (`|z| ≥ 1 − e^(−1/2) = 0.393`): `2ᵏD′_j/|z| ≤ 0.5`,
196//! `2ᵏT_j/|z| ≤ 1.55`: `ε ≤ 0.5 + 2.02 + 0.15 + 3 = 5.7`. For `k > 53`, A1
197//! on `eˣ ≥ 2⁵³`: `ε ≤ 4.1(1 + 2⁻⁵²) + 2 = 6.1`; for `k < −53`, `eˣ/|z| ≤
198//! 2⁻⁵²`: `ε ≤ 2.01`. The maximum is `7.15`. ∎
199//!
200//! ## Algorithm L (`ln`, and the parts of `ln_1p`, `log2`, `log10`)
201//! Input `x ∈ dd`, `0 < x < +∞` (the rest by the table of special cases).
202//! `LNC_j`, `K⁺_j`, `K⁻_j` are the table entries of `ln(1 + j/64)`,
203//! `ln(2(1 + j/64))` and `ln((1 + j/64)/2)`; `A`, `B`, `C` the parts of `ln 2`
204//! (`A` of 42 bits).
205//!
206//! L1. [Scale.] If `x_h < 2⁻¹⁰²²` (then `x_ℓ = 0`), `x ← x · 2¹⁰⁶` and `e ←
207//!     −106`, else `e ← 0`. Add to `e` the exponent of `x_h`, and `y ← x ·
208//!     2^−exponent ∈ [1, 2)`; if `y_h ≥ RN(√2)`, `y ← y/2`, `e ← e + 1`. Now
209//!     `x = 2ᵉ y` exactly, `y ∈ [0.707, 1.415)` and `|e| ≤ 1074`.
210//! L2. [Table index.] `j ← trunc(64(y_h − 1)) ∈ [−18, 26]` (`y_h − 1` is a
211//!     Sterbenz difference), `c ← 1 + j/64` — between 1 and `y_h`.
212//! L3. [Reduce.] `d ← (y_h − c) + y_ℓ` (a Sterbenz difference, then
213//!     `from_sum`: exact), with the sign of `y − 1` or `|d| ≤ u`; `z ← d` if
214//!     `j = 0`, else `z ← d/c` (D1). `|z| ≤ ζ = 0.0218` (`0.0157` if `j =
215//!     0`).
216//! L4. [Series.] `L ← z − z²Q(z)`, `Q(z) = Σ_{m=2}^{20} (−z)^(m−2)/m`
217//!     (Horner); `L ← z` if `|z_h| < 2⁻⁴⁰⁰`. This is `ln(1 + z) = ln(y/c)`.
218//! L5. [Combine.] If `e = 1` and `y_h < 1`: `K⁺_j + L`. If `e = −1` and
219//!     `y_h ≥ 1`: `K⁻_j + L` (these are the two cases in which `e ln 2` and
220//!     `ln y` cancel). Otherwise `ln y ← L` (`j = 0`) or `LNC_j + L`, and the
221//!     result is `ln y` (`e = 0`) or `e ln 2 + ln y` (A2).
222//! L6. [`e ln 2`.] `a ← e·A` (exact: 42 + 11 bits), `(p, q) ←
223//!     two_prod(e, B)`, `(s, t) ← Fast2Sum(a, p)`, `v ← t + (q + e·C)`,
224//!     result `from_sum(s, v)`.
225//!
226//! **Lemma L6.** `ε(e ln 2) ≤ 1 + 2⁻⁴⁰`. *Proof.* `a + p + q = e(A + B)`
227//! exactly; `|p| ≤ 2⁻⁴²|a|`, so Fast2Sum applies and is exact; `|t| ≤
228//! u|s|`, `|q| ≤ u|p|`, `|e C| ≤ |e| 2⁻⁹⁸ < 2⁻⁹⁷|s|`
229//! (as `|s| ≥ 0.69|e|`). Two roundings remain:
230//! `q + eC`, at most `u · 2⁻⁹³|s|`, and `t + (…)`, at most `u|v| ≤ u²|s|(1 +
231//! 2⁻⁴¹)`; the parts of `ln 2` beyond `C` weigh `2¹¹ · 2⁻¹⁴⁸`. ∎
232//!
233//! **Theorem L.** `ε(ln) ≤ 6.7` for all `x ∈ dd`, `0 < x < ∞`, with
234//! `ln x ≠ 0` (`ln 1 = +0` exactly).
235//!
236//! *Proof.* (i) *Series.* In Lemma H the ratio of consecutive terms of `Q`
237//! is at most `ζ(1 + ζ)` (alternating when `z > 0`, all positive when `z <
238//! 0`), so `ρ = 0.0225` covers both signs (`0.0161` when `j = 0`); `σ₀ = 0`
239//! (`1/2` is exact), `σ = 1`, `ε_s = ε(z)`. For `j = 0`, `ε(z) = 0`: `E =
240//! 4.15`, `ε(Q) ≤ 3.14`, `ε(z²Q) ≤ 3 + 3.14 + 4 = 10.14`; the weights in `z
241//! − z²Q` are at most `(1 − ζ/2)⁻¹` and `ζ/2(1 − ζ/2)⁻¹ ≤ 0.008`: `ε(L) ≤ 3.09`.
242//! For `j ≠ 0`, `ε(z) = 3` (D1): `E = 4.28`, `ε(Q) ≤ 3.26`, `ε(z²) ≤ 9`,
243//! `ε(z²Q) ≤ 16.3`, weights `1.011` and `0.011`: `ε(L) ≤ 1.011 · 3 + 0.011 ·
244//! 16.3 + 3 = 6.22`. The remainder after `m = 20` is below `ζ²⁰/21 · |z| <
245//! 2⁻¹¹⁴|L|` (at most `0.004`, inside the `6.22`: the sum before rounding up
246//! is `6.212`). (ii) *`ln y`.* `LNC_j` and `L` have the same sign (but for
247//! `|d| ≤ u`, where the weights exceed 1 by `2⁻⁴⁵`); the weight of `L` is
248//! largest for `j = ±1`, `0.496` and `0.504`: `ε(ln y) ≤ 3 + 0.496 + 0.504 ·
249//! 6.22 = 6.63`. (iii) *Cancelling cases.* `|ln x| = |ln(2y)|` or `|ln(y/2)|
250//! ≥ ln √2 = 0.3466` and `|L| ≤ 0.022`: weights `1.064` (table) and `0.064`:
251//! `ε ≤ 3 + 1.064 + 0.064 · 6.22 = 4.46`. (iv) *Others.* With `e ln 2` and
252//! `ln y` of the same sign the weight of `ln y` is at most `0.3466/1.0397`
253//! and `ε ≤ 3 + 0.67 + 0.333 · 6.63 = 5.88`; of opposite signs `|e| ≥ 2`,
254//! weights `1.333` and `0.333`: `ε ≤ 3 + 1.333 + 2.21 = 6.54`. The maximum
255//! is `6.63`. No product leaves the range of `two_prod`: `|z| ≥ 2⁻⁴⁰⁰` in
256//! L4, and all other operands are near 1. ∎
257//!
258//! ## Algorithm L′ (`ln_1p`)
259//! L′1. If `|x_h| < 1/64`: `z ← x` and step L4 (`ε ≤ 3.09`).
260//! L′2. If `x_h ≤ −1/2`: `w ← (1 + x_h) + x_ℓ` (Sterbenz, then `from_sum`:
261//!      exact) and `ln w` (`ε ≤ 6.63`).
262//! L′3. Else `w ← x + 1` (A1). If `w_h ≥ 2⁵³`, return `ln w` (the rounding of
263//!      `w`, `2u²` relative, changes `ln w` by `2u²/ln w < 0.06u²` of it).
264//!      Otherwise `δ ← x − ((w_h − 1) + w_ℓ)` (`w_h − 1` exact for `1/2 ≤ w_h
265//!      < 2⁵³`; A2), `κ ← RN(δ_h/w_h)` and return `ln w + κ` (A1).
266//!
267//! **Theorem L′.** `ε(ln_1p) ≤ 7.7`. *Proof.* `1 + x = w + δ*` with `|δ*| ≤
268//! 2u²|w|(1 + 2⁻⁵⁰)` (A1), and `ln(1 + x) = ln w + δ*/w − θ`, `0 ≤ θ ≤
269//! (δ*/w)²`. The computed `κ` differs from `δ*/w` by at most `4u|δ*/w|`
270//! (A2 on exact operands, the dropped `δ_ℓ` and `w_ℓ`, one rounding).
271//! `|ln w| ≥ ln(65/64) > 0.0155` in L′3, so `|κ| ≤ 130u²|ln w| < 2⁻¹⁰u|ln
272//! w|` and Lemma S applies: the last A1 adds `u²(1 + 2⁻⁹)`. With the
273//! `6.63` of `ln w` (weight `1 + 2⁻⁹⁵`), `ε ≤ 6.63 + 1.002 + 2⁻⁴⁰ < 7.64`. ∎
274//!
275//! **`log2` and `log10`.** `log10 x = ln x · LOG10_E` (M2 and a table
276//! constant: `ε ≤ 6.63 + 5 = 11.63`). `log2 x` is `e` exactly when `x = 2ᵉ`
277//! (tested first); in the cancelling cases of L5 it is `ln x · LOG2_E`
278//! (`4.46 + 5`); otherwise `ln y · LOG2_E` (`ε ≤ 11.63`) plus the exact `e`
279//! by A1, with weight at most `0.5/1.5` on `log₂ y` when `e ≠ 0`: `ε ≤ 2 +
280//! 0.333 · 11.63 = 5.88`. So `ε(log2), ε(log10) ≤ 11.7`. *Below `2⁻⁹⁶⁸`*
281//! (only `x = (1, δ)`, `ln x = δ` to `δ/2` relative): in the final M2 the
282//! leading product and its error term, both on the grid of `η`, lose at
283//! most `η/2` together, and the cross term `δ · LOG_ℓ` rounds by at most
284//! `η/2`: the `η` of the bound.
285//!
286//! ## Algorithm P (`powi`: binary powering with a separate exponent)
287//! Input `x ∈ dd` finite and nonzero, `n ∉ {−1, 0, 1}` (those and the
288//! non-finite `x` by the table of special cases). `N = |n|`.
289//!
290//! P1. [Split.] `x = ±2^(e_x) y` with `y ∈ [1, 2)` (exact; a subnormal `x_h`
291//!     is first scaled by `2¹⁰⁶`). `b ← y`, `e_b ← e_x`, `a ← 1`, `e_a ← 0`
292//!     (exponents in `i64`).
293//! P2. [Loop.] For each bit of `N` from the least significant: if it is set,
294//!     `a ← a·b` (M2), `e_a ← e_a + e_b`, and renormalize `a` into `[1, 2)`
295//!     by an exact power of two; then, if bits remain, `b ← b²` (M3), `e_b ←
296//!     2e_b`, and renormalize `b`.
297//! P3. [Finish.] If `n < 0`, `a ← 1/a` (D2) and `e_a ← −e_a`. Return `±a ·
298//!     2^(e_a)` (`ldexp`; `±∞` or `±0` when `e_a` is out of every range), the
299//!     sign by the parity of `n`.
300//!
301//! **Theorem P.** `ε(powi) ≤ 3N + popcount(N) − 4 ≤ 4N − 4` for `n > 0`
302//! and `≤ 4N + 11` for `n < 0`; `powi(x, 2)` is one M3 (`3u²`) and
303//! `powi(x, −1)` one D2. *Proof.* After `i` squarings `ε(b) ≤ 3(2ⁱ − 1)`
304//! (`ε ← 2ε + 3`, Chapter 11.2). The first factor enters `a = 1` exactly
305//! (M2 with the operand 1 is exact), each further one adds `4`: `ε(a) ≤
306//! Σ_{i∈bits} 3(2ⁱ − 1) + 4(popcount − 1) = 3N + popcount − 4`. Renormalizing
307//! is exact and keeps every operand in `[1, 4)`, so no product leaves the
308//! range of `two_prod` and no intermediate over- or underflows, whatever
309//! `xⁿ` is (in particular `x⁻ⁿ` with `xⁿ > Ω` is finite and accurate). D2
310//! adds `15`. The second-order terms are below `(4N u²)² ≤ 2⁻¹⁴⁶`, since `N
311//! ≤ 2³¹`. ∎
312//!
313//! ## `powf` (`exp(y ln x)`)
314//! For finite nonzero `x`, finite nonzero `y ≠ 1` (the rest by the table of
315//! special cases): `P ← y · ln|x|` (Algorithm L, then M2) and `z ← exp(P)`
316//! (Algorithm E), with the sign `−` when `x < 0` and `y` is an odd integer
317//! (`x < 0` with `y` not an integer is NaN). "`y` is an integer": both
318//! components are; "odd": the trailing component is odd when nonzero (then
319//! `|y_h| ≥ 2⁵³` is even), else the leading one.
320//!
321//! **Theorem F.** `ε(powf) ≤ 4.6 + 10.7 G`, `G = |y ln x|`. *Proof.* `ε(P) ≤
322//! 6.63 + 4` (Theorem L, M2), an absolute error at most `10.63u²G` in the
323//! argument of `exp`, which multiplies the result by `e^(ΔP) = 1 + ΔP(1 +
324//! ΔP)` (C4); Theorem E adds `4.6`. Overflow of `P` (`|y|` huge) gives `exp`
325//! of `±∞`, the right limit. ∎
326//!
327//! The contract proposed the growth coefficient `8`; the proof gives
328//! `10.63`, because the logarithm's own bound, `6.63u²`, is multiplied by
329//! `G` as well as the product's `4u²`. The declared row therefore has `11`
330//! (ratified 2026-11-18, decision log D-0122).
331//!
332//! ## Algorithm R (argument reduction: Payne–Hanek in integers)
333//! Input `x ∈ dd`, finite, `x ≥ 0` (the callers use the parity of the
334//! functions), `x_h > RN(π/4)`. Output `q ∈ {0, 1, 2, 3}` and `r ∈ dd`,
335//! `|r| ≤ π/4 (1 + 2⁻³¹⁰)`, with `x ≡ qπ/2 + r (mod 2π)` up to the error of
336//! Theorem R. `b_i` is bit `i` of `2/π = Σ_{i≥1} b_i 2⁻ⁱ`; the table holds
337//! `i ≤ 1408`.
338//!
339//! R1. [Each component.] For `c ∈ {x_h, x_ℓ}` write `|c| = m 2ᵉ` with an
340//!     integer `m < 2⁵³`. Let `I = e + 382`; if `I < 1`, skip `c` (`c · 2/π <
341//!     2⁻³²⁸`). Else `W ← ⌊2^I · 2/π⌋ mod 2³⁸⁴` — the bits `b_{I−383}, …, b_I`,
342//!     six 64-bit words — and `A_c ← ⌊m W / 2⁶⁴⌋ mod 2³²⁰`, negated modulo
343//!     `2³²⁰` when `c < 0` (`x_ℓ` may be negative).
344//! R2. [Sum.] `A ← (A_{x_h} + A_{x_ℓ}) mod 2³²⁰`. `A · 2⁻³¹⁸` is `x · 2/π`
345//!     modulo 4, as two integer bits and a 318-bit fraction `F`.
346//! R3. [Quadrant.] If `F < 2³¹⁷`: `q ←` the integer bits, `G ← 2F`, sign
347//!     `+`. Else `q ←` the integer bits `+ 1 (mod 4)`, `G ← 2(2³¹⁸ − F)`,
348//!     sign `−`. Then `ĝ = G · 2⁻³¹⁸ ∈ [0, 1]` and `r = ±ĝ · π/4` (`ĝ`
349//!     approximates the exact `g = |r*|/(π/4)` of Theorem R).
350//! R4. [Multiply.] `R ← ⌊G · P / 2²⁵⁶⌋` with `P = ⌊2³²⁰ π/4⌋` (five words),
351//!     so `|r| ≈ R · 2⁻³⁸²`, `R < 2³⁸³`.
352//! R5. [Convert.] With `L` the position of the leading bit of `R`, take the
353//!     53-bit chunks `c₀, c₁, c₂` starting at bits `L − 52`, `L − 105`, `L −
354//!     158` (each exactly an `f64` `vᵢ` after scaling by a power of two);
355//!     `(s, t) ← Fast2Sum(v₀, v₁)`, `r ← ±from_sum(s, t + v₂)`.
356//!
357//! **Theorem R.** `|r − r*| ≤ (1 + 2⁻⁴⁹)u²|r*| + 2⁻³¹⁶`, where `r* = x −
358//! (4k + q)π/2` exactly, for some integer `k`.
359//!
360//! *Proof.* *R1:* the bits of `2/π` with `i ≤ e − 2` contribute multiples of
361//! 4 to `c · 2/π` (`m` is an integer) and are dropped exactly; those with
362//! `i > I` contribute less than `m 2^(e−I) < 2^(53−382) = 2⁻³²⁹`; and
363//! `A_c 2⁻³¹⁸ = m W 2^(e−I) − θ` with `0 ≤ θ < 2⁻³¹⁸` (the dropped word), all
364//! modulo 4 (`2³²⁰ · 2⁻³¹⁸ = 4`); negation keeps `|θ| < 2⁻³¹⁸`. The skipped
365//! components weigh less than `2⁻³²⁸`. So `A 2⁻³¹⁸ ≡ x · 2/π − δ (mod 4)`
366//! with `|δ| < 2⁻³¹⁶·⁹`. *R3:*
367//! the chosen integer is within `1/2 + δ` of `x · 2/π`; `|ĝ − g| ≤ 2δ`.
368//! *R4:* `P` errs by less than `2⁻³²⁰`, and the floor drops less than
369//! `2⁻³⁸²`: `|R 2⁻³⁸² − g π/4| < (π/4) 2δ + 2⁻³²⁰ + 2⁻³⁸² < 2⁻³¹⁶`. *R5:*
370//! `v₀ + v₁ + v₂` is `R 2⁻³⁸²` truncated after 159 bits (`< 2⁻¹⁵⁸` of it);
371//! Fast2Sum is exact (`|v₁| < ulp(v₀)`); `|t| ≤ u|s|`, `|v₂| < 2⁻¹⁰⁵ ·
372//! R 2⁻³⁸²`, so the one rounding, of `t + v₂`, is at most `u²(1 + 2⁻⁵¹)` of
373//! the value; `from_sum` is exact. ∎ When `R ≥ 1`, `|r| ≥ 2⁻³⁸²` (the
374//! chunks are exact multiples of `2⁻³⁸²`); `R = 0`, possible only if `|r*|
375//! < 2⁻³¹⁵`, gives `r = 0` — and Lemma D below shows that it never happens.
376//!
377//! **Lemma D (no double-double is near a multiple of `π/2`).** For every
378//! double-double `x` with `x_h > RN(π/4)` and every integer `k`, `|x − kπ/2|
379//! > 2⁻¹⁴⁰`. So `|r*| > 2⁻¹⁴⁰` in Theorem R, `R ≥ 1`, and `|r| > 2⁻¹⁴¹`.
380//! The closest double-double found (below) has `|r*| ≈ 2⁻¹²⁴`.
381//!
382//! *Notation.* `‖y‖` is the distance from `y` to the nearest integer, so
383//! `min_k |x − kπ/2| = (π/2)‖x · 2/π‖` and it suffices that `‖x · 2/π‖ ≥
384//! 2⁻¹⁴⁰` (`π/2 > 1`). `x_h = M 2ᴱ` with `2⁵² ≤ M < 2⁵³` and `−53 ≤ E ≤ 971`
385//! (`x_h > 0.78`); `x_ℓ = 0` or `x_ℓ = m 2ᵉ` with `|m| < 2⁵³` and `e = −1074`
386//! or `2⁵² ≤ |m|`; normalization (`|x_ℓ| ≤ 2^(E−1)`) gives `e ≤ E − 53`.
387//! `α_j = 2ʲ · 2/π mod 1`. The method is the classical one for `f64`
388//! (Muller, Chapter 11): continued
389//! fractions bound `‖qα‖` for all `q` below a bound at once. A
390//! double-double is two such numbers at independent exponents, so where the
391//! gap between them is wide a lattice replaces the continued fraction.
392//!
393//! D1. [Continued fractions.] For a rational `β` with convergents `p_i/q_i`
394//!     and a bound `Q`, let `q_n < Q ≤ q_(n+1)`; then `‖qβ‖ ≥ |q_n β − p_n|`
395//!     for every `0 < q < Q` (Lagrange: a convergent is a best
396//!     approximation of the second kind; Khinchin, *Continued Fractions*,
397//!     chapter II). If `|α − β| ≤ ϑ`, `‖qα‖ ≥ |q_n β − p_n| −
398//!     Qϑ`.
399//! D2. [The leading component.] D1 with `β = β_E`, a rational within
400//!     `2^(E−1700)` of `α_E`, and `Q = 2⁵³` gives `d_E ≤ ‖Mα_E‖` for every
401//!     `0 < M < 2⁵³`. This settles `x_ℓ = 0`; the smallest is `d_797 =
402//!     2⁻⁶¹·⁵⁴`, at `6 381 956 970 095 103 · 2⁷⁹⁷`, the `f64` nearest a
403//!     multiple of `π/2` (the worst case of `f64` listed by Muller).
404//! D3. [A small trailing component.] If `2^(e+53) · 2/π ≤ d_E/2`: `‖x ·
405//!     2/π‖ ≥ ‖x_h · 2/π‖ − |x_ℓ| 2/π ≥ d_E/2`.
406//! D4. [A narrow gap: one integer.] Else, if `s = E − e ≤ 60`: `x = N 2ᵉ`
407//!     with `0 < N = M 2ˢ + m < 2^(54+s)`, and `‖x · 2/π‖ = ‖Nα_e‖` is
408//!     bounded by D1 with `β = β_e` and `Q = 2^(54+s)`.
409//! D5. [A wide gap: a lattice.] Else `‖x · 2/π‖ = ‖Mα_E + mα_e‖`, a linear
410//!     form in two integers below `2⁵³`. With `Z = 2ᶻ`, `A = ⌊Zβ_E⌋`, `B =
411//!     ⌊Zβ_e⌋`, the lattice `Λ` spanned by the rows `(1, 0, A)`, `(0, 1, B)`,
412//!     `(0, 0, Z)` holds `v = (M, m, MA + mB − kZ)`, whose last coordinate is
413//!     `ZL − θ` with `L = Mα_E + mα_e − k` and `|θ| ≤ 2⁵⁴ + 1`. For *any*
414//!     basis of `Λ` with Gram–Schmidt vectors `b_i*`, a nonzero `v` has
415//!     `‖v‖ ≥ μ = min_i ‖b_i*‖` (take the last `i` with a nonzero
416//!     coefficient), so `Z|L| ≥ √(μ² − 2¹⁰⁷) − 2⁵⁴ − 1`. The basis is reduced
417//!     by LLL and then checked exactly: its rows lie in `Λ`, its determinant
418//!     is `±Z`, and `‖b_i*‖² = Δ_i/Δ_(i−1)` with the integer Gram
419//!     determinants `Δ_i`. `z` is the first of `170, 185, 200, 230, 260`
420//!     that gives `2⁻¹⁴⁰`.
421//!
422//! *Proof.* D1 is the classical theorem; D2–D5 cover every `x` (D3 every
423//! `e` below a cut, D4 and D5 the rest up to `E − 53`). The program
424//! `tests/reduction_bound.rs` carries the computation out in integers only
425//! (`dashu-int`, no floating point): `π` by Machin's formula with its
426//! truncation bounded, `⌊2¹⁷⁰⁰ · 2/π⌋` certified, then D2–D5 for all 1 025
427//! exponents `E` and every `e` that D3 does not settle — 527 301 cases (D4
428//! for 8 178 of them, D5 for 519 123), each asserted `≥ 2⁻¹⁴⁰`. The
429//! smallest bound is `2⁻¹²⁹·⁵` (D5 at `E = 671`, `e = 78`), so in fact
430//! `|r*| > 2⁻¹²⁹`. The full run is `#[ignore]`d in the default suite
431//! (about 20 s with `--release`); a sample of 11 exponents runs by
432//! default. ∎
433//!
434//! The lemma is a computer-assisted proof: it rests on that program, on
435//! D1 and on the bound of D5, not on sampling. An independent run with
436//! `fpylll` for the reduction and Python integers for the checks gave the
437//! same `2⁻¹²⁹·⁵`, and so did the independent review of the lemma, with its
438//! own continued fractions and Gram–Schmidt in exact rationals. The
439//! arguments closest to `kπ/2` known are `7 688 177 032 635 270 · 2⁸⁷⁵ −
440//! 8 875 559 650 591 347 · 2⁻⁷⁵` (`|r*| = 2⁻¹²⁴·⁴⁶`, odd `k`; found by that
441//! review, enumerating small combinations of a reduced basis of the lattice
442//! of D5) and, from a search over the convergents of every `α_E`,
443//! `14 461 176.670… + 1.70·10⁻¹⁸` (`2⁻¹¹⁷·⁹⁹`) and `6 381 956 970 095 103 ·
444//! 2⁷⁹⁷ − 4.69 · 10⁻¹⁹` (`2⁻¹¹⁷·⁴⁶`); the tests check the sharper bound of
445//! `tan` there. Neither search is exhaustive: about four bits separate the
446//! closest argument known from the proven floor.
447//!
448//! The contract planned Cody–Waite (`π/2` in five parts) below `2⁵²` and
449//! Payne–Hanek above. Cody–Waite in double-double arithmetic subtracts with
450//! A2, whose error is relative to *its own* result: `x − kP₁` is about
451//! `kP₂ ≈ k 2⁻⁵³`, so the reduction carries an absolute error up to `3u²k
452//! 2⁻⁵³` — `2⁻¹⁰⁵` at `k ≈ 2⁵²`, and `2⁻¹⁵⁷` even at `k = 1`. That cannot be
453//! proven below the floor `2⁻²⁰⁰` of the declared bound (the pilot's good
454//! measurements near `kπ/2` presumably reflect A2 being exact there in
455//! practice; that is not a theorem). The integer reduction has the proven
456//! absolute error `2⁻³¹⁶` of Theorem R, whatever `x`, and is used for every
457//! `x_h > RN(π/4)` (its own cost was not measured separately).
458//!
459//! ## Algorithm K (`sin`, `cos`, `sin_cos`, `tan`)
460//! S1. [Reduce.] `a ← |x|`. If `a_h ≤ RN(π/4)`, `q ← 0`, `r ← a`; else
461//!     Algorithm R.
462//! S2. [Kernels.] `sin r ← r − r³Q_s(r²)`, `Q_s = Σ_{m=1}^{14} (−r²)^(m−1)/
463//!     (2m+1)!` (Horner); `cos r ← 1 − 2 sin²(r/2)`, with `sin(r/2)` by the
464//!     same series to `m = 11` (`|r/2| ≤ π/8`); `sin r ← r` and `cos r ← 1`
465//!     when `|r_h| < 2⁻⁴⁰⁰`.
466//! S3. [Quadrant.] `sin x = ±(sin r, cos r, −sin r, −cos r)[q]` with the
467//!     sign of `x`; `cos x = (cos r, −sin r, −cos r, sin r)[q]`; `tan x =
468//!     sin r/cos r` (`q` even) or `−cos r/sin r` (`q` odd), with the sign of
469//!     `x` (D2).
470//! S4. [Tangent at `r = 0`.] For `tan` only: if `q` is odd and Algorithm R
471//!     returned `r = 0`, take `r ← 2⁻³⁸²`, the smallest nonzero magnitude
472//!     that R5 produces (`sin`, `cos` and `sin_cos` keep `r = 0`). By Lemma
473//!     D no argument reaches this step (`r = 0` needs `|r*| < 2⁻³¹⁵`); it is
474//!     kept as a guard for release builds, so that `tan` stays finite
475//!     should the computation of Lemma D be wrong, and is tested through an
476//!     internal hook. A debug build asserts Lemma D (`|r| > 2⁻¹⁴¹`) in
477//!     Algorithm R, and so panics before reaching the guard.
478//!
479//! Each function calls the same kernels on the same `(q, r)`, so `sin_cos`
480//! gives the bits of `sin` and of `cos`; the kernels are odd and even bit
481//! for bit (M2, M3 and A2 commute with negation), and S1 works on `|x|`, so
482//! `sin`, `tan` are odd and `cos` is even bit for bit.
483//!
484//! **Theorem K.** For every finite `x`, with `f` the function: `|z − f(x)|
485//! ≤ 6.9u²|f(x)| + 2⁻³¹⁵` for `sin`, `cos` (and the pair), and `|z −
486//! tan x| ≤ 27.4u²|tan x| + 2⁻³¹⁵(1 + tan²x)`.
487//!
488//! *Proof.* *Sine kernel:* Lemma H with `s = r²` (`ε_s = 3`), ratio `ρ =
489//! (π/4)²/20 (1 + 0.04) = 0.032`, `σ = 1`: `ε(Q_s) ≤ (1.032 + 0.032 · 7 +
490//! 3)/0.968 = 4.40`; `ε(r³) = 7`, `ε(r³Q_s) ≤ 15.4`; the weight of `r³Q_s`
491//! is `(r − sin r)/sin r ≤ 0.111`: `ε ≤ 0.111 · 15.4 + 3 = 4.71`. The first
492//! omitted term is below `2⁻¹²²` of `sin r`. *Cosine kernel:* for `h = r/2`,
493//! `ρ = 0.0078`, `ε(Q) ≤ 4.10`, weight `0.026`: `ε(sin h) ≤ 3.40` (with
494//! the truncation of its 11 terms, `10⁻³`); `ε(sin²h) ≤ 9.80`; in `1 − 2
495//! sin²h` (A1, exact 1) the weight of `2 sin²h` is `(1 − cos r)/cos r ≤
496//! 0.415`: `ε ≤ 2 + 0.415 · 9.80 = 6.06`. *Range (C2):* for `2⁻⁴⁰⁰ ≤ |r|
497//! < 2⁻³²³` the product `r · r²` falls below `2⁻⁹⁶⁹` and M2 errs by up to
498//! `η` absolute, below `2⁻⁶⁷⁰` of `sin r`; in `cos r` the square `sin²h`
499//! underflows likewise against the exact 1 (and below `2⁻⁴⁰⁰`, `cos r ← 1`
500//! leaves `r²/2 < 2⁻⁸⁰⁰`).
501//! *Reduction (C4):* by Theorem R the kernels see `r` instead of `r*`;
502//! `|sin r − sin r*| ≤ |r − r*|`, which is `≤ 1.111u²|sin r*| + 2⁻³¹⁶`, and
503//! `|cos r − cos r*| ≤ sin|r*| |r − r*| ≤ 0.79u²|cos r*| + 2⁻³¹⁶`. Totals
504//! `4.71 + 1.12` and `6.06 + 0.8`: `6.9`. For `x_h ≤ RN(π/4)`, `r = x`
505//! exactly (such an `x` may exceed `π/4` by `2.6·10⁻¹⁷`, which changes the
506//! constants above by less than `10⁻¹⁵`). *Tangent:* D2 adds `15` to
507//! `4.71 + 6.06`. For an even `q`, or an odd `q` (where `|r*| > 2⁻¹⁴⁰ ≥
508//! 2⁻³⁰⁰` by Lemma D; for `x_h ≤ RN(π/4)`, `q = 0`):
509//! then `|r − r*| ≤ 2⁻¹⁶|r*|`, so every `ξ` between `r` and `r*` has `1 +
510//! cot²ξ ≤ (1 + 2⁻¹²)(1 + cot²r*)` (likewise for `tan`), and `|tan r −
511//! tan r*| ≤ (1 + tan²ξ)|r − r*|` has the relative part `r/(sin r cos r)
512//! u²(1 + 2⁻¹²) ≤ 1.58u²` (the same for `cot`) and the absolute part
513//! `2⁻³¹⁵(1 + tan²x)`: `27.4`. This covers every finite `x`. (Before Lemma
514//! D, an odd `q` with `|r*| < 2⁻³⁰⁰` was left with the declared bound only;
515//! the case does not exist.) ∎
516//!
517//! ## Algorithm T (`atan`)
518//! Input `a ∈ dd`, `0 ≤ a < ∞` (`atan` is odd: the sign is applied last;
519//! `atan(±∞) = ±π/2`). `θ_c` is the table entry of `atan c`.
520//!
521//! T1. [Tiny.] If `a_h < 2⁻⁶`: `atan a ← a − a³Q_a(a²)`, `Q_a =
522//!     Σ_{m=1}^{9} (−a²)^(m−1)/(2m + 1)` (Horner; `a` itself below
523//!     `2⁻⁴⁰⁰`).
524//! T2. [Table.] If `a_h < 8`: with `e` the exponent of `a_h` (`−6 ≤ e ≤
525//!     2`) and `i` the top four bits of its fraction, `c ← 2ᵉ(1 + (2i +
526//!     1)/32)` (an `f64` of six bits, `|a − c| ≤ 2ᵉ/32`); `t ← ((a_h − c) +
527//!     a_ℓ)/(a·c + 1)` (Sterbenz and `from_sum`: exact numerator; M1, A1,
528//!     D2); `atan a ← θ_c + atan t` with `atan t` by the series of T1
529//!     (`|t| ≤ 2ᵉ/32/(1 + 2²ᵉ) ≤ 1/64`).
530//! T3. [Large.] Else `atan a ← π/2 − atan(1/a)` (D2, then T1 or T2).
531//!
532//! **Theorem T.** `ε(atan) ≤ 5.8`. *Proof.* *T1:* Lemma H with `s = a²`
533//! (`ε_s = 3`), `ρ = 0.895 · 2⁻¹²` (`a ≤ 2⁻⁶`, so that T2's `|t| ≤ 1/64`
534//! is covered): `ε(Q_a) ≤ 4.003`, so `ε(a³Q_a) ≤ 15.01`;
535//! its weight is at most `a²/3 < 10⁻⁴`: `ε ≤ 3.002`; the omitted terms are
536//! below `2⁻¹²⁰` of the value. *T2:* `ε(a·c + 1) ≤ 2 + 2`, so `ε(t) ≤ 4 +
537//! 15 = 19` and `ε(atan t) ≤ 3.002 + 19` (C4, the condition number of
538//! `atan` near 0 is at most 1). `|atan t|/atan a ≤ 1/(8π) < 0.04` (for `a`
539//! at most 1, `atan a ≥ aπ/4 ≥ 2ᵉπ/4`; for `a > 1`, `atan a ≥ π/4`, `|t| ≤ 1/64`):
540//! weights `1.04` and `0.04`, `ε ≤ 3 + 1.04 + 0.04 · 22.0 = 4.92`. *T3:*
541//! `ε(1/a) ≤ 15`, `ε(atan(1/a)) ≤ 4.92 + 15`; with `atan(1/a) ≤ atan(1/8)`
542//! the weights of `π/2` and of `atan(1/a)` are `1.086` and `0.086`, so
543//! `ε ≤ 3 + 1.086 + 0.086 · 19.92 = 5.80`. *Range (C2):* in T1 the
544//! products `a²`, `a · a²` are formed only for `a ≥ 2⁻⁴⁰⁰`, where `a³ ≥
545//! 2⁻¹²⁰⁰` may underflow: its absolute error `η` is below `2⁻⁸⁰⁰` of `a`.
546//! In T2 the numerator can be minuscule (`a` next to a cell's centre `c`);
547//! then `t` and the series are tiny and their weight `|atan t|/atan a`
548//! makes any `η` negligible. In T3, `1/a` is subnormal for `a > 2¹⁰²²`,
549//! inexact by `η`, with weight below `2⁻¹⁰²²` against `π/2`. ∎
550//!
551//! **`atan2(y, x)`.** After the special cases (the table of `f64`), both
552//! magnitudes are scaled by the same power of two `2⁻ˢ` so that the larger
553//! is in `[1, 2)` (exact for the larger; the smaller can round, its
554//! trailing component by at most `η/2`, which is at most `0.5u²` of a
555//! quotient of at least `2⁻⁹⁶⁸` — with a widely spaced trailing component
556//! that happens for quotients up to about `2⁻⁹¹⁵`). If `|y| ≤ |x|`: `z ←
557//! atan(|y|/|x|)`, and the result is `z` (`x > 0`) or `π − z`; else `z ←
558//! atan(|x|/|y|)` and the result is `π/2 − z` (`x > 0`) or `π/2 + z`; then
559//! the sign of `y`. The quotient `q = n/d` (`n` the smaller scaled
560//! magnitude, `d ∈ [1, 2)` the larger) is formed in one of three ways:
561//!
562//! Q1. [Tiny.] If `n_h < 2⁻⁹⁶⁸`: with the *unscaled* smaller magnitude `m =
563//!     2ᵉ μ`, `μ ∈ [1, 2)` (exact, a subnormal `m` scaled up first), `q ←
564//!     (μ/d) · 2^(e−s)` (D2 on operands in `[1, 2)`, then one `ldexp`).
565//! Q2. [Small.] Else, if `n_h < 2⁻⁴⁰⁰`: `q ← ((n · 2⁶⁰⁰)/d) · 2⁻⁶⁰⁰`, so that
566//!     D2 stays in its range.
567//! Q3. Else `q ← n/d` (D2).
568//!
569//! In Q1 and Q2, `q < 2⁻⁴⁰⁰` is its own arctangent. *Q1:* `q < 2⁻⁹⁶⁸` (`n <
570//! 2⁻⁹⁶⁸`, `d ≥ 1`); the scaling of `m` is exact, D2 errs by `15u²|q|`, and
571//! the final `ldexp` rounds each component at most once by at most `η/2`
572//! (its first factor `2⁻¹⁰⁰⁰`, when `e − s < −1000`, leaves the leading
573//! component of `μ/d ∈ [1/2, 2)` normal; a trailing component that it
574//! rounds ends below `η/2` anyway and is lost with at most that): `|q̂ − q|
575//! ≤ 15u²|q| + η`, the bound with its `η`. Scaling `n` itself and then
576//! unscaling the quotient would round twice — the scaled `n`, subnormal,
577//! and the result — up to about `2η` (found by the property tests on
578//! x86_64: `1.04η` at `y = (1.5127926632651903·10⁻²⁹⁵, −7.815437673005·
579//! 10⁻³¹²)`, `x = 23 118 976 389 754.613`). *Q2:* `ε ≤ 15 + 0.5 + 0.5 = 16`
580//! (D2, the rounding of `n`'s trailing component, the `ldexp(−600)`),
581//! below the `19.92` of `z`; `q ≥ 2⁻⁹⁶⁹` there, and below `2⁻⁹⁶⁸` the two
582//! roundings are of trailing components only, `η` in all. *Bound:*
583//! `ε(q) ≤ 15`, `ε(z) ≤ 4.92 + 15κ` with `κ ≤ 1` the condition number of
584//! `atan` on `[0, 1]`. `z`: `19.92`. `π − z`, `z ≤ π/4`: weights `4/3`,
585//! `1/3`: `3 + 1.33 + 6.64 = 11.0`. `π/2 − z`: weight `≤ 2` on `π/2`, `≤ 1`
586//! on `z`, and `w_z κ = q/((1 + q²)(π/2 − atan q)) ≤ 2/π`: `3 + 2 + 4.92 +
587//! 15 · 0.637 = 19.5`. `π/2 + z`: `≤ 10.7`. So `ε(atan2) ≤ 20`.
588//!
589//! **Lemma W (a square root below `2⁻⁹⁶⁸`).** Algorithm R of Chapter 11.2
590//! has its bound `25/8 u²` only for operands `v ≥ 2⁻⁹⁶⁸` (LLMPR, Theorem
591//! 3.6): below, the residual `v_h − s_h²` of its Newton step is a
592//! subnormal `fma` result that loses its low bits, and the relative error
593//! of `√v` reaches `u`. Step W: for `0 < v_h < 2⁻⁹⁶⁸`, `√v ← √(v · 2⁶⁰⁰) ·
594//! 2⁻³⁰⁰`; otherwise R itself (so W changes nothing from `2⁻⁹⁶⁸` up). Then
595//! `ε(√v) ≤ α/2 + 25/8 + 2⁻⁴³⁰` for `ε(v) ≤ α`. *Proof.* The scaling up is
596//! exact and puts `v · 2⁶⁰⁰` in `[2⁻⁴⁷⁴, 2⁻³⁶⁸)`, inside the safe range of
597//! Chapter 11.2; R's result has its leading component in `[2⁻²³⁷, 2⁻¹⁸⁴)`,
598//! which stays normal after the scaling down, while the trailing one moves
599//! by at most `η/2 < 2⁻⁵³⁷ √v` (`√v ≥ √η = 2⁻⁵³⁷`) if it becomes subnormal;
600//! `fast_two_sum` renormalizes exactly (Chapter 11.2, `ldexp`). ∎
601//!
602//! **`asin`, `acos`.** With `a = |x| ≤ 1` and `w = √((1 − a)(1 + a))`:
603//! for `a ≥ 1/2`, `1 − a` is exact (Sterbenz, `from_sum`), `1 + a` is A1
604//! and the product M2: `ε(w) ≤ (2 + 4)/2 + 25/8 = 6.13`; for `a < 1/2`, `w
605//! = √(1 − a²)` (M3, A1 with the weight `1/3` on `a²`): `ε(w) ≤ 3/2 + 25/8 =
606//! 4.63`. The square root is step W. Its operand is below `2⁻⁹⁶⁸` only if
607//! `a_h = 1` and `a_ℓ = −δ` with `0 < δ < 2⁻⁹⁶⁹` (for `a_h < 1`, `1 − a ≥
608//! 2⁻⁵⁴`). Then `1 − a = δ` and `1 + a = (2, −δ)` are exact, `δ · 2` is an
609//! exact `two_prod`, and the only rounding in M2 is that of the cross term
610//! `−δ²`: at most `δ²` when it underflows (`δ/2 < 2⁻⁹⁷⁰` of the product
611//! `2δ`), else at most `η/2` with `δ > 2⁻⁵³⁸` (below `2⁻⁵³⁶` of it). So
612//! `ε(w) ≤ 25/8 + 2⁻⁴²⁹` there, and `acos(1 − δ) = atan(w/a)`, essentially
613//! `w`, keeps the bound; Algorithm R alone would give it a relative error
614//! up to `u` (found by the tests of the subnormal regime). Then `asin x =
615//! ±atan(a/w)` (`a ≤ w`) or `±(π/2 − atan(w/a))`, and
616//! `acos x` is `atan(w/a)` (`w ≤ a`) or `π/2 − atan(a/w)` for `x ≥ 0`, and `π
617//! − atan(w/a)` or `π/2 + atan(a/w)` for `x < 0`. *Bound:* the quotient has
618//! `ε ≤ 15 + ε(w) ≤ 21.13`; `atan(q)` then `4.92 + 21.13 = 26.05`; `π/2 −
619//! atan q` gives `3 + 2 + 4.92 + 0.637 · 21.13 = 23.4`; the others are
620//! smaller (`13.0`, `12.7`). So `ε(asin), ε(acos) ≤ 26.1`. `asin(±1) =
621//! ±π/2`, `acos(1) = +0` and `acos(−1) = π` exactly (`w = 0`). *Range
622//! (C2):* below `2⁻⁴⁰⁰` `asin` returns `x`, and `acos` is `π/2 −
623//! atan(a/w)` with `a/w ≈ a` of weight below `2⁻³⁹⁹` (its D2 may err by
624//! `η` for a subnormal `a`); above it `a²` and `a/w` are at least `2⁻⁸⁰⁰`.
625//! Near `±1`, `w ≥ 2⁻⁵³⁷` (step W), so `w/a` and its D2 products stay
626//! above `2⁻⁹⁶⁹`, and `atan(w/a)` is `w/a` itself below `2⁻⁴⁰⁰`.
627//!
628//! ## The hyperbolic functions and their inverses (composition)
629//! With `a = |x|` (the odd functions apply the sign of `x` last; `cosh` is
630//! even), each below is a short composition whose bound follows from (C1)–
631//! (C4) and Theorems E, M, L, L′:
632//!
633//! * `sinh a = (E + E/(E + 1))/2`, `E = exp_m1(a)`, for `a_h ≤ 709`;
634//!   `exp(a − 1) · e/2` above (`a − 1` is exact there, `e/2` is `E/2` of the
635//!   table, exact scaling). *Bound:* `ε(E + 1) ≤ 2 + 7.15 E/(E + 1)`,
636//!   `ε(E/(E + 1)) ≤ 24.15 + 7.15 E/(E + 1)`, and the last A2 weighs them
637//!   `(E + 1)/(E + 2)` and `1/(E + 2)`: largest as `E → 0`, `3 + (7.15 +
638//!   24.15)/2 = 18.7`. Above 709: `4.6 + 1 + 4 = 9.6` (the neglected `e⁻ᵃ` is
639//!   `2⁻²⁰⁴⁵` relative). Below `2⁻⁴⁰⁰` the result is `a`.
640//! * `cosh a = (E + 1/E)/2`, `E = exp(a)`, for `a_h ≤ 709`; `exp(a − 1) · e/2`
641//!   above. *Bound:* `ε(1/E) ≤ 4.6 + 15`; the weights `E²/(E² + 1)` and
642//!   `1/(E² + 1)`, largest at `E = 1`: `3 + (4.6 + 19.6)/2 = 15.1`. *Range:*
643//!   near `a = 709`, `1/E` is near `2⁻¹⁰²³` and its D2 can err by `η`, with
644//!   the weight `1/(E² + 1) < 2⁻²⁰⁴⁴`.
645//! * `tanh a = E₂/(E₂ + 2)`, `E₂ = exp_m1(2a)`, for `a < 5/16`; else `(1 −
646//!   F)/(1 + F)`, `F = exp(−2a)`. *Bound:* below `5/16`, `E₂ ≤ 0.868`,
647//!   `ε(E₂ + 2) ≤ 2 + 0.303 · 7.15`, `ε ≤ 7.15 + 4.17 + 15 = 26.4`; above,
648//!   `F ≤ 0.536`, `ε(1 − F) ≤ 2 + 1.152 · 4.6`, `ε(1 + F) ≤ 2 + 0.349 · 4.6`,
649//!   `ε ≤ 7.30 + 3.61 + 15 = 25.9`. For large `a`, `F` underflows (an
650//!   absolute `η` against 1) and D2 returns the pair `(1, −2F)` until `F <
651//!   η/2`, then exactly 1.
652//! * `asinh a = ln_1p(a + a²/(1 + √(1 + a²)))` for `a < 2`, `ln(a + √(a² +
653//!   1))` for `2 ≤ a < 2⁶⁰`, `ln a + ln 2` above (`asinh a − ln 2a < 2⁻¹²²` of
654//!   it). *Bound:* for `a < 2`, `ε(√(1 + a²)) ≤ 2.2 + 25/8`, `ε(1 + √) ≤
655//!   5.68`, `ε(a²/(1 + √)) ≤ 23.7`, and in the argument `v` of `ln_1p` its
656//!   weight is at most `0.382`: `ε(v) ≤ 12.1`; the condition number of
657//!   `ln_1p` is at most 1: `ε ≤ 7.64 + 12.1 = 19.7`. For `2 ≤ a < 2⁶⁰`, `ε(v)
658//!   ≤ 3 + 0.528 · 5.63` and the condition number of `ln` at `v ≥ 4.23` is
659//!   `1/ln v ≤ 0.693`: `ε ≤ 6.63 + 4.14 = 10.8`. Above: `3 + 6.63 = 9.63`.
660//!   *Range (C2):* below `2⁻⁴⁰⁰` the result is `a`; above, `a² ≥ 2⁻⁸⁰⁰` and
661//!   the products of the quotient `a²/(1 + √(1 + a²))` are of that size,
662//!   above `2⁻⁹⁶⁹` (outside the conservative safe range of Chapter 11.2,
663//!   but every `two_prod` is exact), and the quotient weighs `a/2` in `v`.
664//! * `acosh x = ln_1p(d + √(d(d + 2)))`, `d = x − 1` (exact), for `x < 2`;
665//!   `ln(x + √(x² − 1))` for `2 ≤ x < 2⁶⁰`; `ln x + ln 2` above. *Bound:*
666//!   `ε(√(d(d + 2))) ≤ 3 + 25/8`, `ε(v) ≤ 3 + 6.13`, `ε ≤ 7.64 + 9.13 =
667//!   16.8` (the square root is step W: `d(d + 2) < 2⁻⁹⁶⁸` only when `x_h =
668//!   1` and `d = x_ℓ < 2⁻⁹⁶⁹`, where M2 errs by less than `2⁻⁵³⁶` relative,
669//!   as in `acos`, and `acosh x ≈ √(2d)` is the square root itself);
670//!   `ε(x² − 1) ≤ 2 + (4/3) · 3`, `ε(v) ≤ 3 + 6.13/2`, `ε ≤ 6.63 + 0.76 ·
671//!   6.07 = 11.3`; above, `3 + 6.63 = 9.63`.
672//! * `atanh a = ln_1p(2a/(1 − a))/2`, with `1 − a` exact for `a ≥ 1/2` and A1
673//!   below. *Bound:* `ε(2a/(1 − a)) ≤ 2 + 15`, condition number of `ln_1p` at
674//!   most 1: `ε ≤ 7.64 + 17 = 24.7`. If `1 − a` is subnormal (then `a = (1,
675//!   −δ)`, `δ < 2⁻¹⁰²²`, and `2a/(1 − a) ≈ 2/δ` exceeds `Ω` once `δ <
676//!   2⁻¹⁰²³`), `atanh a = (ln(1 + a) − ln(1 − a))/2` instead, with `1 + a =
677//!   (2, −δ)` exact (A1) and `1 − a = δ`: Theorem L twice, and A2 on two
678//!   positive terms (`ln(2 − δ) > 0`, `−ln δ > 0`): `ε ≤ 6.63 + 3 = 9.7`.
679//!   For a normal `1 − a` below `2⁻⁴⁷⁹` the quotient exceeds `2⁴⁸⁰`, outside
680//!   the conservative safe range of Chapter 11.2, but the products of D2
681//!   are near `2a` and its divisor is normal, so its hypotheses (T2, no
682//!   overflow) hold and so does `15u²`. Below `2⁻⁴⁰⁰` the result is `a`.
683//!
684//! Below `2⁻⁴⁰⁰` the odd functions return `x` (the cubic term is `2⁻⁸⁰⁰`
685//! relative).
686//!
687//! ## Invariants
688//! (F1) *Well formed.* Every output satisfies (D1)/(D2) of Chapter 11.2,
689//!      for every input, non-finite and subnormal ones included (a property
690//!      test calls `check_invariants` on every result).
691//! (F2) *Determinism.* Only `+ − × ÷ √ fma`, `round`, `trunc` of `f64` and
692//!      the operations of Chapter 11.2, in a fixed order with branches that
693//!      depend only on the bits of the arguments: the same bits on every
694//!      platform, in debug and release, with or without the features (a
695//!      golden test of 246 values and a digest of 21 000; `clippy.toml`
696//!      forbids the transcendental functions of `f64` in the crate).
697//! (F3) *Symmetry.* `sin`, `tan`, `asin`, `atan`, `sinh`, `tanh`, `asinh`,
698//!      `atanh` are odd and `cos`, `cosh` even, bit for bit; `sin_cos(x) =
699//!      (sin x, cos x)` bit for bit.
700//! (F4) *Inputs.* Each function `debug_assert!`s (D1) of its arguments; in
701//!      release a non-normalized argument gives an unspecified but well
702//!      formed result.
703//!
704//! ## Measured
705//! Largest error observed against `dashu-float`, `10⁵` random arguments per
706//! family (in `u²`; mixed bounds: the relative part); the survey is the
707//! `#[ignore]`d test `survey_of_observed_errors`. `exp` 1.77, `exp2` 1.77,
708//! `exp_m1` 2.53, `ln` 1.91, `ln_1p` 2.16, `log2` 3.16, `log10` 3.40, `sin`
709//! 2.37, `cos` 1.89, `tan` 5.57, `atan` 1.94, `atan2` 5.21, `asin` 5.87,
710//! `acos` 4.41, `sinh` 3.40, `cosh` 2.86, `tanh` 6.23, `asinh` 2.70,
711//! `acosh` 3.73, `atanh` 3.46; `powi` `≤ 2.07 max(1, |n|)`, `powf` `≤ 4.30
712//! max(1, |y ln x|)`. At the double-doubles nearest to `kπ/2`, `k ≤ 2·10⁶`:
713//! `0.50` relative, `4·10⁻⁵⁹` absolute at most.
714//!
715//! In the subnormal regime (the `#[ignore]`d test
716//! `survey_of_the_subnormal_regime`, `10⁴` arguments per family: tiny
717//! arguments, subnormal or below `2⁻⁹⁰⁰`; `±(1 ± δ)` with such a `δ`;
718//! `exp`, `exp_m1` on `[−745.2, −670]` and `exp2` on `[−1076, −967]`),
719//! every function of one argument stays within `2.91u²` relative for
720//! results of at least `2⁻⁹⁶⁸` (`log10` of tiny arguments; most are below
721//! `1.5`) and within `0.99η` absolute below (`log2`, `log10` at `1 ± δ`;
722//! `exp`, `exp2` `0.75η`; the larger search below reaches `1.01η`, the
723//! relative term included). The directed and property tests of that regime
724//! also cover `sin_cos`, `powi`, `powf` and `atan2`. They found four
725//! defects, fixed before publication: `acos(1 − δ)` and `acosh(1 + δ)`
726//! with `δ < 2⁻⁹⁶⁹` (up to `u` relative; Lemma W), `atanh(±(1 − δ))` with
727//! `δ < 2⁻¹⁰²³` (`±∞`; the second form of `atanh`), and `atan2` with a
728//! quotient below `2⁻⁹⁶⁸` rounded twice (up to `1.26η` beyond the relative
729//! term in a search of `3·10⁵`, `37` violations; step Q1). The `#[ignore]`d
730//! `search_of_subnormal_results` (`10⁶` arguments per family, results or
731//! arguments below `2⁻⁹⁶⁸`, trailing components often subnormal) finds no
732//! violation after the fixes; beyond the relative term the error is at
733//! most `0.75η` for `atan2`, `exp`, `exp2`, `powi`, `powf`, `0.998η` for
734//! `log2` and `log10` at `1 + δ`, and `0` for the functions that return
735//! their tiny argument.
736//!
737//! ## Cost
738//! The numbers below were measured by a harness outside the tree; the
739//! example `elementary_bench` has its rows and its method, and prints the
740//! table with the backend, the target and the load average. Time per call (ns,
741//! median of 21 runs over 1 024 independent arguments,
742//! so a throughput; release, Apple M2 Pro on AC power, load average 3.0
743//! from other sessions): `exp` 232, `exp2` 214, `exp_m1` 241, `ln` 430,
744//! `ln_1p` 443, `log2` 439, `log10` 443, `powi(x, 7)` 53, `powi(x, −100)`
745//! 138, `powf` 753, `sin` 279 (`|x| ≤ 1`) to 344 (`|x| ≤ 10`) and 352
746//! (`|x|` up to `2⁹⁶⁰`), `cos` 340, `tan` 599, `sin_cos` 599, `atan` 190,
747//! `atan2` 258, `asin` 266, `acos` 266, `sinh` 298, `cosh` 271, `tanh` 278,
748//! `asinh` 538, `acosh` 508, `atanh` 487. For scale: `dd · dd` 1.9, `dd +
749//! dd` 2.8, `dd / dd` 3.4, `f64::exp` 2.5.
750//!
751//! ## The declared bounds
752//! The column "proven" is the constant of the proof in this chapter,
753//! rounded up; "declared" is the row of [`DoubleDouble::FUNCTION_BOUNDS`].
754//! Both are bounds on `|z − f(x)|`: the numbers are in units of `u²|f|`
755//! (`u²|f|` times the growth term where there is one); the terms `2⁻²⁰⁰`,
756//! `2⁻³¹⁵` (times `1 + tan²` for `tan`) are absolute.
757//!
758//! | function | declared | proven | how |
759//! |---|---|---|---|
760//! | `exp`, `exp2` | `8` | `4.6` | Algorithm E |
761//! | `exp_m1` | `8` | `7.2` | Algorithm M |
762//! | `ln` | `8` | `6.7` | Algorithm L |
763//! | `ln_1p` | `8` | `7.7` | Algorithm L′ |
764//! | `log2`, `log10` | `12` | `11.7` | Algorithm L, then a product |
765//! | `powi` | `15 + 4\|n\|` | `11 + 4\|n\|` | Algorithm P |
766//! | `powf` | `16 + 11\|y ln x\|` | `4.6 + 10.7\|y ln x\|` | `exp(y ln x)` (Theorem F) |
767//! | `sin`, `cos`, `sin_cos` | `8\|f\| + 2⁻²⁰⁰` | `6.9\|f\| + 2⁻³¹⁵` | Algorithms R and K |
768//! | `tan` | `32\|tan\| + 2⁻²⁰⁰(1 + tan²)` | `27.4\|tan\| + 2⁻³¹⁵(1 + tan²)` | Algorithms R and K, D2; Lemma D |
769//! | `atan` | `8` | `5.8` | Algorithm T |
770//! | `atan2`, `asin`, `acos` | `32` | `20`, `26.1`, `26.1` | Algorithm T, composition |
771//! | `sinh`, `cosh`, `tanh` | `32` | `18.7`, `15.1`, `26.4` | Algorithms E and M, composition |
772//! | `asinh`, `acosh`, `atanh` | `32` | `19.7`, `16.8`, `24.7` | Algorithms L and L′, composition |
773//!
774//! ## Tables
775//! The constants of the algorithms are private tables of literals
776//! (`elementary/tables.rs`): parts of `ln 2/64` and `ln 2`, `2^(j/64)`,
777//! `2^(j/64) − 1`, `e^(N/64) − 1`, `1/n!`, `1/n`, `ln(1 + j/64)` and its
778//! two shifted forms, `atan(c)` at 144 points, and 1 408 bits of `2/π`
779//! and 320 of `π/4`. A unit test checks each entry, bit for bit, against
780//! `dashu-float` and against the independent enclosures of the tests.
781//!
782//! ## References
783//! Muller, *Elementary Functions: Algorithms and Implementation*, 3rd ed.
784//! (2016): Cody–Waite and Payne–Hanek reduction, table-driven methods
785//! (Tang) — cited from memory. Tang, "Table-driven implementation of the
786//! exponential function in IEEE floating-point arithmetic", ACM TOMS 15
787//! (1989) — from memory. Payne & Hanek, "Radian reduction for
788//! trigonometric functions", SIGNUM Newsletter 18 (1983) — from memory.
789//! For Lemma D: Muller, *op. cit.*, Chapter 11 (the worst cases of `f64`
790//! for the reduction, by continued fractions, among them
791//! `6 381 956 970 095 103 · 2⁷⁹⁷`) — from memory; Khinchin, *Continued
792//! Fractions* (1964), Theorems 16–17 (best approximations) — from memory;
793//! Lenstra, Lenstra & Lovász, "Factoring polynomials with rational
794//! coefficients", Math. Ann. 261 (1982), and Cohen, *A Course in
795//! Computational Algebraic Number Theory* (1993), Algorithm 2.6.7 (the
796//! integral LLL) — from memory; the lower bound `λ₁ ≥ min ‖b_i*‖` is
797//! proven in D5.
798//! Joldes, Muller & Popescu (2017) and the other sources of Chapter 11.2
799//! for the bounds of the operations. C99 Annex F and IEEE 754-2019 §9.2 for
800//! the special cases (as restated in the documentation of `f64`).
801
802#![allow(clippy::float_cmp)] // exact comparisons, as in Chapter 11.2
803
804use crate::dd::DoubleDouble;
805
806mod tables;
807
808use crate::eft::{fast_two_sum, two_prod};
809use tables::{
810    ATAN_C, EXP2_64, EXP2_64_M1, EXPM1_64, FRAC_3PI_4, INV_FACT, INV_INT, INV_LN2_64, LN_2C, LN_C,
811    LN_C_2, LN2_64, LN2_SPLIT, PI_OVER_4, TWO_OVER_PI,
812};
813
814/// The declared error bound of one elementary function of [`DoubleDouble`]:
815/// `|z − f(x)| ≤ (units_of_u2 + growth_units_of_u2 · G) u² |f(x)| + absolute`,
816/// for results of magnitude in [2⁻⁹⁶⁸, Ω] (below: `+ η`).
817#[derive(Clone, Copy, Debug, PartialEq)]
818#[non_exhaustive]
819pub struct FunctionBound {
820    /// The function, as named in Rust (`"exp"`, `"powi"`, …).
821    pub function: &'static str,
822    /// The constant term, in units of `u² = 2⁻¹⁰⁶`.
823    pub units_of_u2: f64,
824    /// The coefficient of the growth term `G`, in units of `u²` (0 if none).
825    pub growth_units_of_u2: f64,
826    /// What `G` is: `""`, `"|n|"` (powi), `"|y ln x|"` (powf) or
827    /// `"|tan x|"` (tan).
828    pub growth: &'static str,
829    /// The absolute floor (`2⁻²⁰⁰` for the circular functions, else 0).
830    pub absolute: f64,
831}
832
833/// `2⁻²⁰⁰`, the absolute floor of the circular functions.
834const TRIG_FLOOR: f64 = f64::from_bits((1023 - 200) << 52);
835/// `2⁻⁹⁴ = 2⁻²⁰⁰/u²`: the growth coefficient of `tan`.
836const TAN_GROWTH: f64 = f64::from_bits((1023 - 94) << 52);
837
838const fn plain(function: &'static str, units_of_u2: f64) -> FunctionBound {
839    FunctionBound {
840        function,
841        units_of_u2,
842        growth_units_of_u2: 0.0,
843        growth: "",
844        absolute: 0.0,
845    }
846}
847
848const fn circular(function: &'static str, units_of_u2: f64) -> FunctionBound {
849    FunctionBound {
850        function,
851        units_of_u2,
852        growth_units_of_u2: 0.0,
853        growth: "",
854        absolute: TRIG_FLOOR,
855    }
856}
857
858impl DoubleDouble {
859    /// The declared error bounds of the elementary functions (Chapter
860    /// 11.11), one row per function, each proven in the chapter. The tests
861    /// read them.
862    pub const FUNCTION_BOUNDS: &'static [FunctionBound] = &[
863        plain("exp", 8.0),
864        plain("exp2", 8.0),
865        plain("exp_m1", 8.0),
866        plain("ln", 8.0),
867        plain("ln_1p", 8.0),
868        plain("log2", 12.0),
869        plain("log10", 12.0),
870        FunctionBound {
871            function: "powi",
872            units_of_u2: 15.0,
873            growth_units_of_u2: 4.0,
874            growth: "|n|",
875            absolute: 0.0,
876        },
877        FunctionBound {
878            function: "powf",
879            units_of_u2: 16.0,
880            // The contract's 8 does not cover the proof (Theorem F).
881            growth_units_of_u2: 11.0,
882            growth: "|y ln x|",
883            absolute: 0.0,
884        },
885        circular("sin", 8.0),
886        circular("cos", 8.0),
887        FunctionBound {
888            function: "tan",
889            units_of_u2: 32.0,
890            growth_units_of_u2: TAN_GROWTH,
891            growth: "|tan x|",
892            absolute: TRIG_FLOOR,
893        },
894        circular("sin_cos", 8.0),
895        plain("asin", 32.0),
896        plain("acos", 32.0),
897        plain("atan", 8.0),
898        plain("atan2", 32.0),
899        plain("sinh", 32.0),
900        plain("cosh", 32.0),
901        plain("tanh", 32.0),
902        plain("asinh", 32.0),
903        plain("acosh", 32.0),
904        plain("atanh", 32.0),
905    ];
906}
907
908/// A table entry `(hi, lo)` as a double-double.
909const fn entry(p: (u64, u64)) -> DoubleDouble {
910    DoubleDouble::from_raw(f64::from_bits(p.0), f64::from_bits(p.1))
911}
912
913/// `x_h > EXP_OVERFLOW` gives `eˣ = +∞` (`ln MAX_dd ≈ 709.7827`; between
914/// the two the computation overflows by itself, Theorem E (iv)).
915const EXP_OVERFLOW: f64 = 709.79;
916/// `x_h < EXP_UNDERFLOW` gives `eˣ < η/2`: `exp` returns `+0`, `exp_m1`
917/// returns `−1`.
918const EXP_UNDERFLOW: f64 = -745.2;
919/// `2⁻⁴⁰⁰`: below it a series is its first term (to `2⁻⁴⁰⁰` relative), and
920/// above it no product of a series underflows.
921const TINY: f64 = f64::from_bits((1023 - 400) << 52);
922/// The last term `r^m/m!` of `eʳ − 1` in Algorithm E (`|r| ≤ 0.005 43`).
923const EXP_TERMS: usize = 11;
924/// The last term in step M1 (`|r| ≤ 1/64`).
925const EXPM1_TERMS: usize = 13;
926/// `|x_h| < EXPM1_SMALL` takes step M1.
927const EXPM1_SMALL: f64 = 0.5;
928/// `|k| ≤ EXPM1_EXACT_K` makes `2ᵏ − 1` an `f64` (step M3).
929const EXPM1_EXACT_K: i32 = 53;
930
931/// `2ᵏ` for `|k| ≤ 1022`.
932fn pow2(k: i32) -> f64 {
933    f64::from_bits(u64::try_from(k + 1023).expect("|k| ≤ 1022") << 52)
934}
935
936/// An integer-valued `f64` of magnitude below `2³¹`, as an `i32`.
937#[allow(clippy::cast_possible_truncation)] // the value is an integer below 2³¹
938fn to_i32(n: f64) -> i32 {
939    debug_assert!(n == n.trunc() && n.abs() < 2_147_483_648.0);
940    n as i32
941}
942
943/// `P(r) = eʳ − 1` by `r + r² Q(r)`, `Q = Σ_{m=2}^{terms} r^(m−2)/m!` (step E3).
944fn expm1_poly(r: DoubleDouble, terms: usize) -> DoubleDouble {
945    if r.hi().abs() < TINY {
946        return r;
947    }
948    let mut q = entry(INV_FACT[terms]);
949    for m in (2..terms).rev() {
950        q = q * r + entry(INV_FACT[m]);
951    }
952    r + r.square() * q
953}
954
955/// Steps E1–E2: `x = (64k + j) ln 2/64 + r`.
956fn exp_reduce(x: DoubleDouble) -> (i32, usize, DoubleDouble) {
957    let n = (x.hi() * INV_LN2_64).round();
958    let r = if n == 0.0 {
959        x
960    } else {
961        let mut r = x;
962        for c in LN2_64 {
963            r -= DoubleDouble::from_product(n, c);
964        }
965        r
966    };
967    let n = to_i32(n);
968    (n >> 6, usize::try_from(n & 63).expect("in [0, 64)"), r)
969}
970
971/// Steps E3–E4.
972fn exp_reconstruct(k: i32, j: usize, r: DoubleDouble) -> DoubleDouble {
973    let t = entry(EXP2_64[j]);
974    (t + t * expm1_poly(r, EXP_TERMS)).ldexp(k)
975}
976
977/// `(x_h − n/64) + x_ℓ` for `n = round(64 x_h)` or `trunc(64 x_h)`: exact
978/// (and `x` itself, signed zero included, when `n = 0`).
979fn minus_sixty_fourths(x: DoubleDouble, n: f64) -> DoubleDouble {
980    if n == 0.0 {
981        x
982    } else {
983        DoubleDouble::from_sum(x.hi() - n * (1.0 / 64.0), x.lo())
984    }
985}
986
987impl DoubleDouble {
988    /// `eˣ` (Algorithm E). Relative error at most `8u²` for results in
989    /// `[2⁻⁹⁶⁸, Ω]` (proven: `4.6u²`), plus `η` below. `exp(±0) = 1`,
990    /// `exp(+∞) = +∞`, `exp(−∞) = +0`; `+∞` on overflow, `+0` for `x <
991    /// −745.2`.
992    #[must_use]
993    pub fn exp(self) -> Self {
994        debug_assert!(self.check_invariants().is_ok());
995        let h = self.hi();
996        if h.is_nan() {
997            return Self::NAN;
998        }
999        if h > EXP_OVERFLOW {
1000            return Self::INFINITY;
1001        }
1002        if h < EXP_UNDERFLOW {
1003            return Self::ZERO;
1004        }
1005        let (k, j, r) = exp_reduce(self);
1006        exp_reconstruct(k, j, r)
1007    }
1008
1009    /// `2ˣ` (Algorithm E); exact for integer `x` whose power is
1010    /// representable. Bound as [`DoubleDouble::exp`].
1011    #[must_use]
1012    pub fn exp2(self) -> Self {
1013        debug_assert!(self.check_invariants().is_ok());
1014        let h = self.hi();
1015        if h.is_nan() {
1016            return Self::NAN;
1017        }
1018        if h > 1024.0 {
1019            return Self::INFINITY;
1020        }
1021        if h < -1076.0 {
1022            return Self::ZERO;
1023        }
1024        let n = (h * 64.0).round();
1025        let r = minus_sixty_fourths(self, n) * Self::LN_2;
1026        let n = to_i32(n);
1027        exp_reconstruct(n >> 6, usize::try_from(n & 63).expect("in [0, 64)"), r)
1028    }
1029
1030    /// `eˣ − 1`, with relative accuracy near zero (Algorithm M): relative
1031    /// error at most `8u²` for results in `[2⁻⁹⁶⁸, Ω]` (proven: `7.2u²`).
1032    /// `exp_m1(±0) = ±0`, `exp_m1(+∞) = +∞`, `exp_m1(−∞) = −1`; for very
1033    /// negative `x` the pair `(−1, eˣ)`, exactly `−1` once `eˣ < η/2`.
1034    #[must_use]
1035    pub fn exp_m1(self) -> Self {
1036        debug_assert!(self.check_invariants().is_ok());
1037        let h = self.hi();
1038        if h.is_nan() {
1039            return Self::NAN;
1040        }
1041        if h > EXP_OVERFLOW {
1042            return Self::INFINITY;
1043        }
1044        if h < EXP_UNDERFLOW {
1045            return -Self::ONE;
1046        }
1047        if h.abs() < EXPM1_SMALL {
1048            // Step M1.
1049            let n = (h * 64.0).trunc();
1050            let p = expm1_poly(minus_sixty_fourths(self, n), EXPM1_TERMS);
1051            if n == 0.0 {
1052                return p;
1053            }
1054            let d = entry(EXPM1_64[usize::try_from(to_i32(n) + 31).expect("|N| ≤ 31")]);
1055            return (d + d * p) + p;
1056        }
1057        let (k, j, r) = exp_reduce(self);
1058        if k.abs() > EXPM1_EXACT_K {
1059            // Step M2.
1060            return exp_reconstruct(k, j, r) - 1.0;
1061        }
1062        // Step M3.
1063        let t = entry(EXP2_64[j]);
1064        let s = entry(EXP2_64_M1[j]).ldexp(k) + (pow2(k) - 1.0);
1065        s + (t * expm1_poly(r, EXP_TERMS)).ldexp(k)
1066    }
1067}
1068
1069/// `RN(√2)`: `y_h ≥ SQRT_2_HI` halves `y` in step L1.
1070const SQRT_2_HI: f64 = core::f64::consts::SQRT_2;
1071/// The last term `z^m/m` of the series of `ln(1 + z)` (step L4).
1072const LN_TERMS: usize = 20;
1073/// `|x_h| < LN1P_SMALL` takes step L′1.
1074const LN1P_SMALL: f64 = 1.0 / 64.0;
1075/// `2⁵³`: from here on `1 + x` loses nothing that matters (step L′3).
1076const TWO_53: f64 = 9_007_199_254_740_992.0;
1077
1078/// The unbiased exponent of a positive normal `f64`.
1079fn exponent(h: f64) -> i32 {
1080    i32::try_from((h.to_bits() >> 52) & 0x7ff).expect("11 bits") - 1023
1081}
1082
1083/// A table index `j + offset` for `j ∈ [−offset, …]`.
1084fn index(j: i32, offset: i32) -> usize {
1085    usize::try_from(j + offset).expect("an index of the table")
1086}
1087
1088/// `ln(1 + z)` by step L4.
1089fn ln1p_series(z: DoubleDouble) -> DoubleDouble {
1090    if z.hi().abs() < TINY {
1091        return z;
1092    }
1093    let coefficient = |m: usize| {
1094        let c = entry(INV_INT[m]);
1095        if m % 2 == 1 { -c } else { c }
1096    };
1097    let mut q = coefficient(LN_TERMS);
1098    for m in (2..LN_TERMS).rev() {
1099        q = q * z + coefficient(m);
1100    }
1101    z - z.square() * q
1102}
1103
1104/// Steps L1–L4 for a finite `x > 0`: `(e, y_h, j, L)`.
1105fn ln_parts(x: DoubleDouble) -> (i32, f64, i32, DoubleDouble) {
1106    let (x, mut e) = if x.hi() < f64::MIN_POSITIVE {
1107        (x.ldexp(106), -106)
1108    } else {
1109        (x, 0)
1110    };
1111    let ex = exponent(x.hi());
1112    e += ex;
1113    let mut y = x.ldexp(-ex);
1114    if y.hi() >= SQRT_2_HI {
1115        y = y.ldexp(-1);
1116        e += 1;
1117    }
1118    let j = to_i32((64.0 * (y.hi() - 1.0)).trunc());
1119    let c = 1.0 + f64::from(j) / 64.0;
1120    let d = DoubleDouble::from_sum(y.hi() - c, y.lo());
1121    let z = if j == 0 { d } else { d / c };
1122    (e, y.hi(), j, ln1p_series(z))
1123}
1124
1125/// The two cancelling cases of step L5.
1126fn ln_cancelling(e: i32, y_hi: f64, j: i32, l: DoubleDouble) -> Option<DoubleDouble> {
1127    if e == 1 && y_hi < 1.0 {
1128        Some(entry(LN_2C[index(j, 18)]) + l)
1129    } else if e == -1 && y_hi >= 1.0 {
1130        Some(entry(LN_C_2[index(j, 0)]) + l)
1131    } else {
1132        None
1133    }
1134}
1135
1136/// `ln y` of step L5.
1137fn ln_y(j: i32, l: DoubleDouble) -> DoubleDouble {
1138    if j == 0 {
1139        l
1140    } else {
1141        entry(LN_C[index(j, 18)]) + l
1142    }
1143}
1144
1145/// Step L6: `e ln 2`, `e ≠ 0`, `|e| < 2¹¹`.
1146fn e_ln2(e: i32) -> DoubleDouble {
1147    let e = f64::from(e);
1148    let a = e * LN2_SPLIT[0];
1149    let (p, q) = two_prod(e, LN2_SPLIT[1]);
1150    let (s, t) = fast_two_sum(a, p);
1151    DoubleDouble::from_sum(s, t + (q + e * LN2_SPLIT[2]))
1152}
1153
1154/// Algorithm L for a finite `x > 0`.
1155fn ln_positive(x: DoubleDouble) -> DoubleDouble {
1156    let (e, y_hi, j, l) = ln_parts(x);
1157    if let Some(z) = ln_cancelling(e, y_hi, j, l) {
1158        return z;
1159    }
1160    let ly = ln_y(j, l);
1161    if e == 0 { ly } else { e_ln2(e) + ly }
1162}
1163
1164impl DoubleDouble {
1165    /// Natural logarithm (Algorithm L): relative error at most `8u²`
1166    /// (proven: `6.7u²`); `ln(1) = +0`. NaN for `x < 0`, `−∞` for `±0`,
1167    /// `+∞` for `+∞`.
1168    #[must_use]
1169    pub fn ln(self) -> Self {
1170        debug_assert!(self.check_invariants().is_ok());
1171        let h = self.hi();
1172        if h.is_nan() || h < 0.0 {
1173            return Self::NAN;
1174        }
1175        if h == 0.0 {
1176            return -Self::INFINITY;
1177        }
1178        if h == f64::INFINITY {
1179            return Self::INFINITY;
1180        }
1181        ln_positive(self)
1182    }
1183
1184    /// `ln(1 + x)`, with relative accuracy near zero (Algorithm L′):
1185    /// relative error at most `8u²` (proven: `7.7u²`). `±0` for `±0`, `−∞`
1186    /// for `−1`, NaN for `x < −1`.
1187    #[must_use]
1188    pub fn ln_1p(self) -> Self {
1189        debug_assert!(self.check_invariants().is_ok());
1190        let h = self.hi();
1191        if h.is_nan() || h < -1.0 || (h == -1.0 && self.lo() < 0.0) {
1192            return Self::NAN;
1193        }
1194        if h == -1.0 && self.lo() == 0.0 {
1195            return -Self::INFINITY;
1196        }
1197        if h == f64::INFINITY {
1198            return Self::INFINITY;
1199        }
1200        if h.abs() < LN1P_SMALL {
1201            // Step L′1.
1202            return ln1p_series(self);
1203        }
1204        if h <= -0.5 {
1205            // Step L′2.
1206            return ln_positive(Self::from_sum(1.0 + h, self.lo()));
1207        }
1208        // Step L′3.
1209        let w = self + 1.0;
1210        if w.hi() >= TWO_53 {
1211            return ln_positive(w);
1212        }
1213        let delta = self - Self::from_sum(w.hi() - 1.0, w.lo());
1214        ln_positive(w) + delta.hi() / w.hi()
1215    }
1216
1217    /// Base-2 logarithm; exact for powers of two. Relative error at most
1218    /// `12u²` (proven: `11.7u²`). Special cases as [`DoubleDouble::ln`].
1219    #[must_use]
1220    pub fn log2(self) -> Self {
1221        debug_assert!(self.check_invariants().is_ok());
1222        let h = self.hi();
1223        if h.is_nan() || h < 0.0 {
1224            return Self::NAN;
1225        }
1226        if h == 0.0 {
1227            return -Self::INFINITY;
1228        }
1229        if h == f64::INFINITY {
1230            return Self::INFINITY;
1231        }
1232        if self.lo() == 0.0 {
1233            // A power of two: one bit in the significand (normal or not).
1234            let bits = h.to_bits();
1235            let frac = bits & ((1 << 52) - 1);
1236            if bits >> 52 != 0 && frac == 0 {
1237                return Self::from_f64(f64::from(exponent(h)));
1238            }
1239            if bits >> 52 == 0 && frac.is_power_of_two() {
1240                let k = i32::try_from(frac.trailing_zeros()).expect("< 52");
1241                return Self::from_f64(f64::from(k - 1074));
1242            }
1243        }
1244        let (e, y_hi, j, l) = ln_parts(self);
1245        if let Some(z) = ln_cancelling(e, y_hi, j, l) {
1246            return z * Self::LOG2_E;
1247        }
1248        let t = ln_y(j, l) * Self::LOG2_E;
1249        if e == 0 { t } else { t + f64::from(e) }
1250    }
1251
1252    /// Base-10 logarithm, `ln x · LOG10_E`: relative error at most `12u²`
1253    /// (proven: `11.7u²`). Special cases as [`DoubleDouble::ln`].
1254    #[must_use]
1255    pub fn log10(self) -> Self {
1256        self.ln() * Self::LOG10_E
1257    }
1258}
1259
1260/// Renormalizes `a > 0` into `[1, 2)`: `(a 2^−k, k)`.
1261fn renormalize(a: DoubleDouble) -> (DoubleDouble, i64) {
1262    let k = exponent(a.hi());
1263    (a.ldexp(-k), i64::from(k))
1264}
1265
1266/// `x = 2^e y`, `y ∈ [1, 2)`, for a finite `x > 0`.
1267fn split(x: DoubleDouble) -> (DoubleDouble, i64) {
1268    if x.hi() < f64::MIN_POSITIVE {
1269        let (y, e) = renormalize(x.ldexp(106));
1270        (y, e - 106)
1271    } else {
1272        renormalize(x)
1273    }
1274}
1275
1276/// `y` (finite) is an integer: both components are.
1277fn is_integer(y: DoubleDouble) -> bool {
1278    y.hi().trunc() == y.hi() && y.lo().trunc() == y.lo()
1279}
1280
1281/// An integer `f64` is odd.
1282fn is_odd_f64(v: f64) -> bool {
1283    v.abs() < TWO_53 && (v * 0.5).trunc() != v * 0.5
1284}
1285
1286/// An integer double-double is odd (by the trailing component when it is
1287/// nonzero, since then `|y_h| ≥ 2⁵³` is even).
1288fn is_odd(y: DoubleDouble) -> bool {
1289    if y.lo() == 0.0 {
1290        is_odd_f64(y.hi())
1291    } else {
1292        is_odd_f64(y.lo())
1293    }
1294}
1295
1296/// `±∞` (`big`) or `±0`, negative when `neg`.
1297fn signed_limit(big: bool, neg: bool) -> DoubleDouble {
1298    let z = if big {
1299        DoubleDouble::INFINITY
1300    } else {
1301        DoubleDouble::ZERO
1302    };
1303    if neg { -z } else { z }
1304}
1305
1306impl DoubleDouble {
1307    /// `xⁿ` by binary powering with a separate exponent (Algorithm P): no
1308    /// spurious overflow or underflow. Relative error at most `(15 +
1309    /// 4|n|)u²` (proven: `(11 + 4|n|)u²`); exact for `n ∈ {0, 1}`, one
1310    /// square (`3u²`) for `n = 2`, [`DoubleDouble::recip`] for `n = −1`.
1311    /// The special cases of IEEE 754 `pown`: `powi(x, 0) = 1` for every `x`,
1312    /// NaN included; `±0` and `±∞` by the sign and parity of `n`.
1313    #[must_use]
1314    pub fn powi(self, n: i32) -> Self {
1315        debug_assert!(self.check_invariants().is_ok());
1316        if n == 0 {
1317            return Self::ONE;
1318        }
1319        if n == 1 {
1320            return self;
1321        }
1322        let h = self.hi();
1323        if h.is_nan() {
1324            return Self::NAN;
1325        }
1326        let neg = h.is_sign_negative() && n & 1 == 1;
1327        if h == 0.0 {
1328            return signed_limit(n < 0, neg);
1329        }
1330        if h.is_infinite() {
1331            return signed_limit(n > 0, neg);
1332        }
1333        if n == -1 {
1334            return self.recip();
1335        }
1336        // Steps P1–P2.
1337        let (mut b, mut eb) = split(self.abs());
1338        let (mut a, mut ea) = (Self::ONE, 0_i64);
1339        let mut m = n.unsigned_abs();
1340        loop {
1341            if m & 1 == 1 {
1342                let (r, k) = renormalize(a * b);
1343                a = r;
1344                ea += eb + k;
1345            }
1346            m >>= 1;
1347            if m == 0 {
1348                break;
1349            }
1350            let (r, k) = renormalize(b.square());
1351            b = r;
1352            eb = 2 * eb + k;
1353        }
1354        // Step P3.
1355        if n < 0 {
1356            a = a.recip();
1357            ea = -ea;
1358        }
1359        let z = match i32::try_from(ea) {
1360            Ok(e) => a.ldexp(e),
1361            Err(_) => signed_limit(ea > 0, false),
1362        };
1363        if neg { -z } else { z }
1364    }
1365
1366    /// `xʸ` as `exp(y ln x)` (Theorem F): relative error at most `(16 +
1367    /// 11|y ln x|)u²` (proven: `(4.6 + 10.7|y ln x|)u²`); `x` itself for `y =
1368    /// 1`. The special cases of IEEE 754 `pow` (C99 Annex F), as `f64`:
1369    /// `pow(x, ±0) = 1` and `pow(1, y) = 1` even for NaN; NaN for `x < 0`
1370    /// and `y` not an integer; `±0`, `±∞` and `±1` by the usual limits.
1371    #[must_use]
1372    pub fn powf(self, y: Self) -> Self {
1373        debug_assert!(self.check_invariants().is_ok() && y.check_invariants().is_ok());
1374        let (xh, yh) = (self.hi(), y.hi());
1375        if yh == 0.0 || (xh == 1.0 && self.lo() == 0.0) {
1376            return Self::ONE;
1377        }
1378        if xh.is_nan() || yh.is_nan() {
1379            return Self::NAN;
1380        }
1381        if yh == 1.0 && y.lo() == 0.0 {
1382            return self;
1383        }
1384        let y_odd = yh.is_finite() && is_integer(y) && is_odd(y);
1385        if xh == 0.0 {
1386            return signed_limit(yh < 0.0, xh.is_sign_negative() && y_odd);
1387        }
1388        if yh.is_infinite() {
1389            if xh == -1.0 && self.lo() == 0.0 {
1390                return Self::ONE;
1391            }
1392            return signed_limit((yh > 0.0) == (self.abs() > Self::ONE), false);
1393        }
1394        if xh.is_infinite() {
1395            return signed_limit(yh > 0.0, xh < 0.0 && y_odd);
1396        }
1397        if xh < 0.0 && !is_integer(y) {
1398            return Self::NAN;
1399        }
1400        let z = (y * ln_positive(self.abs())).exp();
1401        if xh < 0.0 && y_odd { -z } else { z }
1402    }
1403}
1404
1405/// `RN(π/4)`: `|x|_h ≤ FRAC_PI_4_HI` needs no reduction (step S1).
1406const FRAC_PI_4_HI: f64 = core::f64::consts::FRAC_PI_4;
1407/// The last term `r^(2m+1)/(2m+1)!` of `sin r`, `|r| ≤ π/4` (step S2).
1408const SIN_TERMS: usize = 14;
1409/// The last term of `sin h`, `|h| ≤ π/8`, inside `cos r` (step S2).
1410const SIN_HALF_TERMS: usize = 11;
1411/// `I = e + WINDOW_SHIFT` in step R1: 318 fraction bits, 53 for `m`, 11
1412/// guard bits.
1413const WINDOW_SHIFT: i32 = 382;
1414
1415/// The 64 bits of `N = ⌊2¹⁴⁰⁸ · 2/π⌋` from bit `t` up (bit 0 the least
1416/// significant; zeros outside `[0, 1408)`).
1417fn two_over_pi_bits(t: i32) -> u64 {
1418    // Little-endian word k of N is the big-endian word 21 − k.
1419    let word = |k: i32| -> u64 {
1420        if (0..22).contains(&k) {
1421            TWO_OVER_PI[usize::try_from(21 - k).expect("in range")]
1422        } else {
1423            0
1424        }
1425    };
1426    let k = t.div_euclid(64);
1427    let off = t.rem_euclid(64);
1428    if off == 0 {
1429        word(k)
1430    } else {
1431        (word(k) >> off) | (word(k + 1) << (64 - off))
1432    }
1433}
1434
1435/// `x = m 2ᵉ` for a finite `x ≥ 0`, `m < 2⁵³` an integer.
1436fn integer_significand(x: f64) -> (u64, i32) {
1437    let bits = x.to_bits();
1438    let be = i32::try_from(bits >> 52).expect("x ≥ 0");
1439    let frac = bits & ((1 << 52) - 1);
1440    if be == 0 {
1441        (frac, -1074)
1442    } else {
1443        (frac | (1 << 52), be - 1075)
1444    }
1445}
1446
1447/// `a · b` for little-endian words, `out.len() = a.len() + b.len()`.
1448fn mul_words(a: &[u64], b: &[u64], out: &mut [u64]) {
1449    out.fill(0);
1450    for (i, &ai) in a.iter().enumerate() {
1451        let mut carry = 0_u128;
1452        for (j, &bj) in b.iter().enumerate() {
1453            let t = u128::from(ai) * u128::from(bj) + u128::from(out[i + j]) + carry;
1454            out[i + j] = u64::try_from(t & u128::from(u64::MAX)).expect("the low word");
1455            carry = t >> 64;
1456        }
1457        out[i + b.len()] = u64::try_from(carry).expect("a word");
1458    }
1459}
1460
1461/// Step R1 for one component: `A_c` (five little-endian words), negated
1462/// modulo `2³²⁰` for a negative `c` (a trailing component may be).
1463fn component(c: f64) -> [u64; 5] {
1464    let a = magnitude_component(c.abs());
1465    if c >= 0.0 {
1466        return a;
1467    }
1468    let mut n = [0_u64; 5];
1469    let mut borrow = false;
1470    for k in 0..5 {
1471        let (s1, b1) = 0_u64.overflowing_sub(a[k]);
1472        let (s2, b2) = s1.overflowing_sub(u64::from(borrow));
1473        n[k] = s2;
1474        borrow = b1 || b2;
1475    }
1476    n
1477}
1478
1479/// Step R1 for `c ≥ 0`.
1480fn magnitude_component(c: f64) -> [u64; 5] {
1481    let (m, e) = integer_significand(c);
1482    let i = e + WINDOW_SHIFT;
1483    if i < 1 || m == 0 {
1484        return [0; 5];
1485    }
1486    // W = ⌊2^I 2/π⌋ mod 2³⁸⁴ = bits [1408 − I, 1408 − I + 384) of N.
1487    let base = 1408 - i;
1488    let w: [u64; 6] =
1489        core::array::from_fn(|k| two_over_pi_bits(base + 64 * i32::try_from(k).expect("k < 6")));
1490    let mut p = [0_u64; 7];
1491    mul_words(&[m], &w, &mut p);
1492    [p[1], p[2], p[3], p[4], p[5]]
1493}
1494
1495/// Bits `[t, t + 53)` of a little-endian number (zeros below bit 0).
1496fn chunk53(r: &[u64; 6], t: i32) -> u64 {
1497    let get = |b: i32| -> u64 {
1498        if (0..384).contains(&b) {
1499            let b = usize::try_from(b).expect("b ≥ 0");
1500            (r[b / 64] >> (b % 64)) & 1
1501        } else {
1502            0
1503        }
1504    };
1505    // 53 bits, assembled from two shifted words when t ≥ 0.
1506    if t >= 0 {
1507        let k = usize::try_from(t / 64).expect("t ≥ 0");
1508        let off = t % 64;
1509        let lo = r[k] >> off;
1510        let hi = if off == 0 || k + 1 >= 6 {
1511            0
1512        } else {
1513            r[k + 1] << (64 - off)
1514        };
1515        (lo | hi) & ((1 << 53) - 1)
1516    } else {
1517        (0..53).fold(0, |acc, b| acc | (get(t + b) << b))
1518    }
1519}
1520
1521/// `2⁻¹⁴¹`: every `|r|` of Algorithm R exceeds it (Lemma D; asserted in
1522/// debug builds only, so that no result depends on it).
1523const LEMMA_D_FLOOR: f64 = f64::from_bits((1023 - 141) << 52);
1524
1525/// Algorithm R for a finite `x > π/4`: `(q, r)` with `x ≡ qπ/2 + r`.
1526fn reduce(x: DoubleDouble) -> (u32, DoubleDouble) {
1527    // Steps R1–R2.
1528    let (a, b) = (component(x.hi()), component(x.lo()));
1529    let mut acc = [0_u64; 5];
1530    let mut carry = false;
1531    for k in 0..5 {
1532        let (s1, c1) = a[k].overflowing_add(b[k]);
1533        let (s2, c2) = s1.overflowing_add(u64::from(carry));
1534        acc[k] = s2;
1535        carry = c1 || c2;
1536    }
1537    // Step R3: two integer bits (62, 63 of word 4) and a 318-bit fraction.
1538    let int = u32::try_from(acc[4] >> 62).expect("two bits");
1539    let half = (acc[4] >> 61) & 1 == 1;
1540    let mut f = acc;
1541    f[4] &= (1 << 62) - 1;
1542    let (q, negative, g) = if half {
1543        // G = 2(2³¹⁸ − F).
1544        let mut d = [0_u64; 5];
1545        let mut borrow = false;
1546        for k in 0..5 {
1547            let top: u64 = if k == 4 { 1 << 62 } else { 0 };
1548            let (s1, b1) = top.overflowing_sub(f[k]);
1549            let (s2, b2) = s1.overflowing_sub(u64::from(borrow));
1550            d[k] = s2;
1551            borrow = b1 || b2;
1552        }
1553        ((int + 1) % 4, true, d)
1554    } else {
1555        (int, false, f)
1556    };
1557    // G = 2g', as an integer of 319 bits: one shift.
1558    let mut gg = [0_u64; 5];
1559    for k in (0..5).rev() {
1560        gg[k] = (g[k] << 1) | if k == 0 { 0 } else { g[k - 1] >> 63 };
1561    }
1562    // Step R4: R = ⌊G P / 2²⁵⁶⌋.
1563    let p: [u64; 5] = core::array::from_fn(|k| PI_OVER_4[4 - k]);
1564    let mut prod = [0_u64; 10];
1565    mul_words(&gg, &p, &mut prod);
1566    let rw: [u64; 6] = core::array::from_fn(|k| prod[k + 4]);
1567    // Step R5. R = 0 needs |r*| < 2⁻³¹⁵, which Lemma D excludes.
1568    debug_assert!(rw.iter().any(|&w| w != 0), "Lemma D: R = 0 at {x:?}");
1569    let Some(top) = (0..6).rev().find(|&k| rw[k] != 0) else {
1570        return (q, DoubleDouble::ZERO);
1571    };
1572    let l = 64 * i32::try_from(top).expect("k < 6") + 63
1573        - i32::try_from(rw[top].leading_zeros()).expect("< 64");
1574    let v = |t: i32| {
1575        // The chunk at bit t, as the exact value c · 2^(t − 382).
1576        #[allow(clippy::cast_precision_loss)] // 53 bits: exact
1577        let c = chunk53(&rw, t) as f64;
1578        DoubleDouble::from_f64(c).ldexp(t - 382).hi()
1579    };
1580    let (s, t) = fast_two_sum(v(l - 52), v(l - 105));
1581    let r = DoubleDouble::from_sum(s, t + v(l - 158));
1582    debug_assert!(r.hi() > LEMMA_D_FLOOR, "Lemma D: |r| = {r:?} at {x:?}");
1583    (q, if negative { -r } else { r })
1584}
1585
1586/// `sin r` for `|r| ≤ π/4` by step S2, the series to `terms`.
1587fn sin_kernel(r: DoubleDouble, terms: usize) -> DoubleDouble {
1588    if r.hi().abs() < TINY {
1589        return r;
1590    }
1591    let r2 = r.square();
1592    let coefficient = |m: usize| {
1593        let c = entry(INV_FACT[2 * m + 1]);
1594        if m.is_multiple_of(2) { -c } else { c }
1595    };
1596    let mut q = coefficient(terms);
1597    for m in (1..terms).rev() {
1598        q = q * r2 + coefficient(m);
1599    }
1600    r - (r * r2) * q
1601}
1602
1603/// `cos r = 1 − 2 sin²(r/2)` for `|r| ≤ π/4` (step S2).
1604fn cos_kernel(r: DoubleDouble) -> DoubleDouble {
1605    let s = sin_kernel(r.ldexp(-1), SIN_HALF_TERMS);
1606    -s.square().ldexp(1) + 1.0
1607}
1608
1609/// Step S1 on `|x|`: `(q, r)`.
1610fn quadrant(a: DoubleDouble) -> (u32, DoubleDouble) {
1611    if a.hi() <= FRAC_PI_4_HI {
1612        (0, a)
1613    } else {
1614        reduce(a)
1615    }
1616}
1617
1618/// `sin x` from `(q, r)` and the sign of `x` (step S3).
1619fn sin_from(q: u32, r: DoubleDouble, negative: bool) -> DoubleDouble {
1620    let z = match q {
1621        0 => sin_kernel(r, SIN_TERMS),
1622        1 => cos_kernel(r),
1623        2 => -sin_kernel(r, SIN_TERMS),
1624        _ => -cos_kernel(r),
1625    };
1626    if negative { -z } else { z }
1627}
1628
1629/// `2⁻³⁸²`: the smallest nonzero `|r|` of Algorithm R (step S4).
1630const REDUCTION_QUANTUM: f64 = f64::from_bits((1023 - 382) << 52);
1631
1632/// `tan x` from `(q, r)` and the sign of `x` (steps S3, S4).
1633fn tan_from(q: u32, r: DoubleDouble, negative: bool) -> DoubleDouble {
1634    let r = if q % 2 == 1 && r.hi() == 0.0 {
1635        // Step S4 (unreachable by Lemma D: |r*| < 2⁻³¹⁵; a guard).
1636        DoubleDouble::from_f64(REDUCTION_QUANTUM)
1637    } else {
1638        r
1639    };
1640    let (s, c) = (sin_kernel(r, SIN_TERMS), cos_kernel(r));
1641    let z = if q.is_multiple_of(2) { s / c } else { -(c / s) };
1642    if negative { -z } else { z }
1643}
1644
1645/// `cos x` from `(q, r)` (step S3).
1646fn cos_from(q: u32, r: DoubleDouble) -> DoubleDouble {
1647    match q {
1648        0 => cos_kernel(r),
1649        1 => -sin_kernel(r, SIN_TERMS),
1650        2 => -cos_kernel(r),
1651        _ => sin_kernel(r, SIN_TERMS),
1652    }
1653}
1654
1655impl DoubleDouble {
1656    /// Sine (Algorithms R and K): error at most `8u²|sin x| + 2⁻²⁰⁰` for
1657    /// every finite `x` (proven: `6.9u²|sin x| + 2⁻³¹⁵`), so relative when
1658    /// `|sin x| ≥ 2⁻⁹⁴`. `sin(±0) = ±0`; NaN for `±∞`; odd bit for bit.
1659    #[must_use]
1660    pub fn sin(self) -> Self {
1661        debug_assert!(self.check_invariants().is_ok());
1662        if !self.is_finite() {
1663            return Self::NAN;
1664        }
1665        let (q, r) = quadrant(self.abs());
1666        sin_from(q, r, self.hi().is_sign_negative())
1667    }
1668
1669    /// Cosine; bound as [`DoubleDouble::sin`]. `cos(±0) = 1`; NaN for `±∞`;
1670    /// even bit for bit.
1671    #[must_use]
1672    pub fn cos(self) -> Self {
1673        debug_assert!(self.check_invariants().is_ok());
1674        if !self.is_finite() {
1675            return Self::NAN;
1676        }
1677        let (q, r) = quadrant(self.abs());
1678        cos_from(q, r)
1679    }
1680
1681    /// Tangent (Algorithms R and K, then D2): error at most `32u²|tan x| +
1682    /// 2⁻²⁰⁰(1 + tan²x)` (proven: `27.4u²|tan x| + 2⁻³¹⁵(1 + tan²x)`).
1683    /// `tan(±0) = ±0`; NaN for `±∞`; odd bit for bit.
1684    #[must_use]
1685    pub fn tan(self) -> Self {
1686        debug_assert!(self.check_invariants().is_ok());
1687        if !self.is_finite() {
1688            return Self::NAN;
1689        }
1690        let (q, r) = quadrant(self.abs());
1691        tan_from(q, r, self.hi().is_sign_negative())
1692    }
1693
1694    /// `(sin x, cos x)` from one argument reduction; the same bits as
1695    /// [`DoubleDouble::sin`] and [`DoubleDouble::cos`].
1696    #[must_use]
1697    pub fn sin_cos(self) -> (Self, Self) {
1698        debug_assert!(self.check_invariants().is_ok());
1699        if !self.is_finite() {
1700            return (Self::NAN, Self::NAN);
1701        }
1702        let (q, r) = quadrant(self.abs());
1703        (sin_from(q, r, self.hi().is_sign_negative()), cos_from(q, r))
1704    }
1705}
1706
1707/// `|a_h| < ATAN_DIRECT` takes step T1.
1708const ATAN_DIRECT: f64 = 1.0 / 64.0;
1709/// `a_h ≥ ATAN_RECIP` takes step T3.
1710const ATAN_RECIP: f64 = 8.0;
1711/// The last term `t^(2m+1)/(2m+1)` of the series of `atan t` (`|t| ≤ 1/64`).
1712const ATAN_TERMS: usize = 9;
1713/// `2⁻⁹⁶⁸`: a smaller scaled magnitude below it takes step Q1 of `atan2`.
1714const ATAN2_TINY: f64 = f64::from_bits((1023 - 968) << 52);
1715/// `2⁶⁰⁰`: the scale of a tiny quotient in `atan2`.
1716const ATAN2_SCALE: i32 = 600;
1717
1718/// `atan t` by the series of step T1, `|t| ≤ 1/64`.
1719fn atan_series(t: DoubleDouble) -> DoubleDouble {
1720    if t.hi().abs() < TINY {
1721        return t;
1722    }
1723    let t2 = t.square();
1724    let coefficient = |m: usize| {
1725        let c = entry(INV_INT[2 * m + 1]);
1726        if m.is_multiple_of(2) { -c } else { c }
1727    };
1728    let mut q = coefficient(ATAN_TERMS);
1729    for m in (1..ATAN_TERMS).rev() {
1730        q = q * t2 + coefficient(m);
1731    }
1732    t - (t * t2) * q
1733}
1734
1735/// Algorithm T for a finite `a ≥ 0`.
1736fn atan_positive(a: DoubleDouble) -> DoubleDouble {
1737    let h = a.hi();
1738    if h < ATAN_DIRECT {
1739        return atan_series(a);
1740    }
1741    if h >= ATAN_RECIP {
1742        return DoubleDouble::FRAC_PI_2 - atan_positive(a.recip());
1743    }
1744    let e = exponent(h);
1745    let i = i32::try_from((h.to_bits() >> 48) & 15).expect("four bits");
1746    let c = f64::from(33 + 2 * i) * pow2(e - 5);
1747    let theta = entry(ATAN_C[index(16 * (e + 6) + i, 0)]);
1748    let t = DoubleDouble::from_sum(h - c, a.lo()) / (a * c + 1.0);
1749    theta + atan_series(t)
1750}
1751
1752/// `2⁻⁹⁶⁸`: below it Algorithm R loses its bound, and step W scales.
1753const SQRT_SAFE: f64 = f64::from_bits((1023 - 968) << 52);
1754
1755/// `√v` for `v ≥ 0` by step W (Lemma W): Algorithm R, on `v · 2⁶⁰⁰` when
1756/// `0 < v_h < 2⁻⁹⁶⁸`.
1757fn sqrt_w(v: DoubleDouble) -> DoubleDouble {
1758    if 0.0 < v.hi() && v.hi() < SQRT_SAFE {
1759        v.ldexp(600).sqrt().ldexp(-300)
1760    } else {
1761        v.sqrt()
1762    }
1763}
1764
1765/// `√((1 − a)(1 + a))` for `0 ≤ a ≤ 1` (`asin`, `acos`).
1766fn cosine_of_arcsine(a: DoubleDouble) -> DoubleDouble {
1767    if a.hi() >= 0.5 {
1768        sqrt_w(DoubleDouble::from_sum(1.0 - a.hi(), -a.lo()) * (a + 1.0))
1769    } else {
1770        sqrt_w(-a.square() + 1.0)
1771    }
1772}
1773
1774/// `|x| > 1` (NaN excluded).
1775fn beyond_one(a: DoubleDouble) -> bool {
1776    a.hi() > 1.0 || (a.hi() == 1.0 && a.lo() > 0.0)
1777}
1778
1779impl DoubleDouble {
1780    /// Arctangent in `[−π/2, π/2]` (Algorithm T): relative error at most
1781    /// `8u²` (proven: `5.8u²`). `atan(±0) = ±0`, `atan(±∞) = ±π/2`; odd bit
1782    /// for bit.
1783    #[must_use]
1784    pub fn atan(self) -> Self {
1785        debug_assert!(self.check_invariants().is_ok());
1786        let h = self.hi();
1787        if h.is_nan() {
1788            return Self::NAN;
1789        }
1790        let z = if h.is_infinite() {
1791            Self::FRAC_PI_2
1792        } else {
1793            atan_positive(self.abs())
1794        };
1795        if h.is_sign_negative() { -z } else { z }
1796    }
1797
1798    /// Four-quadrant arctangent of `self / other` (`self` is `y`), in `[−π,
1799    /// π]`: relative error at most `32u²` (proven: `20u²`). The special
1800    /// cases of `f64::atan2`: `(±0, −0) → ±π`, `(±0, +0) → ±0`, `(±0, x < 0)
1801    /// → ±π`, `(±0, x > 0) → ±0`, `(y ≠ 0, ±0) → ±π/2` by the sign of `y`,
1802    /// `(±y, −∞) → ±π` and `(±y, +∞) → ±0` for finite `y`, `(±∞, x finite) →
1803    /// ±π/2`, `(±∞, −∞) → ±3π/4`, `(±∞, +∞) → ±π/4`; NaN in either → NaN.
1804    #[must_use]
1805    pub fn atan2(self, other: Self) -> Self {
1806        debug_assert!(self.check_invariants().is_ok() && other.check_invariants().is_ok());
1807        let (y, x) = (self, other);
1808        let (yh, xh) = (y.hi(), x.hi());
1809        if yh.is_nan() || xh.is_nan() {
1810            return Self::NAN;
1811        }
1812        let negative = yh.is_sign_negative();
1813        let sign = |z: Self| if negative { -z } else { z };
1814        let x_left = xh.is_sign_negative();
1815        if yh == 0.0 {
1816            return sign(if x_left { Self::PI } else { Self::ZERO });
1817        }
1818        if xh == 0.0 {
1819            return sign(Self::FRAC_PI_2);
1820        }
1821        if yh.is_infinite() {
1822            return sign(if xh.is_infinite() {
1823                if x_left {
1824                    entry(FRAC_3PI_4)
1825                } else {
1826                    Self::FRAC_PI_4
1827                }
1828            } else {
1829                Self::FRAC_PI_2
1830            });
1831        }
1832        if xh.is_infinite() {
1833            return sign(if x_left { Self::PI } else { Self::ZERO });
1834        }
1835        let (ay, ax) = (y.abs(), x.abs());
1836        let s = exponent(ay.hi().max(ax.hi()).max(f64::MIN_POSITIVE));
1837        let (ay, ax) = (ay.ldexp(-s), ax.ldexp(-s));
1838        // Steps Q1–Q3; `m` is the unscaled `n`.
1839        let quotient = |m: Self, n: Self, d: Self| {
1840            if n.hi() < ATAN2_TINY {
1841                let (mu, e) = split(m);
1842                let k = i32::try_from(e - i64::from(s)).expect("|e − s| < 2¹¹");
1843                (mu / d).ldexp(k)
1844            } else if n.hi() < TINY {
1845                (n.ldexp(ATAN2_SCALE) / d).ldexp(-ATAN2_SCALE)
1846            } else {
1847                n / d
1848            }
1849        };
1850        let (my, mx) = (y.abs(), x.abs());
1851        let z = if ay <= ax {
1852            let z = atan_positive(quotient(my, ay, ax));
1853            if x_left { Self::PI - z } else { z }
1854        } else {
1855            let z = atan_positive(quotient(mx, ax, ay));
1856            if x_left {
1857                Self::FRAC_PI_2 + z
1858            } else {
1859                Self::FRAC_PI_2 - z
1860            }
1861        };
1862        sign(z)
1863    }
1864
1865    /// Arcsine in `[−π/2, π/2]`: relative error at most `32u²` (proven:
1866    /// `26.1u²`). NaN outside `[−1, 1]`; `asin(±1) = ±π/2`, `asin(±0) = ±0`;
1867    /// odd bit for bit.
1868    #[must_use]
1869    pub fn asin(self) -> Self {
1870        debug_assert!(self.check_invariants().is_ok());
1871        let a = self.abs();
1872        if self.is_nan() || beyond_one(a) {
1873            return Self::NAN;
1874        }
1875        if a.hi() < TINY {
1876            return self;
1877        }
1878        let w = cosine_of_arcsine(a);
1879        let z = if a <= w {
1880            atan_positive(a / w)
1881        } else {
1882            Self::FRAC_PI_2 - atan_positive(w / a)
1883        };
1884        if self.hi().is_sign_negative() { -z } else { z }
1885    }
1886
1887    /// Arccosine in `[0, π]`: relative error at most `32u²` (proven:
1888    /// `26.1u²`). NaN outside `[−1, 1]`; `acos(1) = +0`, `acos(−1) = π`,
1889    /// `acos(±0) = π/2`.
1890    #[must_use]
1891    pub fn acos(self) -> Self {
1892        debug_assert!(self.check_invariants().is_ok());
1893        let a = self.abs();
1894        if self.is_nan() || beyond_one(a) {
1895            return Self::NAN;
1896        }
1897        let w = cosine_of_arcsine(a);
1898        let left = self.hi() < 0.0;
1899        if w <= a {
1900            let z = atan_positive(w / a);
1901            if left { Self::PI - z } else { z }
1902        } else {
1903            let z = atan_positive(a / w);
1904            if left {
1905                Self::FRAC_PI_2 + z
1906            } else {
1907                Self::FRAC_PI_2 - z
1908            }
1909        }
1910    }
1911}
1912
1913/// `sinh`, `cosh` above it use `exp(a − 1) · e/2`.
1914const HYPER_LARGE: f64 = 709.0;
1915/// `tanh` below it uses `exp_m1(2a)`, above it `exp(−2a)`.
1916const TANH_SPLIT: f64 = 0.3125;
1917/// `2⁶⁰`: `asinh`, `acosh` above it are `ln x + ln 2`.
1918const TWO_60: f64 = 1_152_921_504_606_846_976.0;
1919/// `e/2` (the table `E`, scaled exactly).
1920const E_HALF: DoubleDouble =
1921    DoubleDouble::from_raw(DoubleDouble::E.hi() * 0.5, DoubleDouble::E.lo() * 0.5);
1922
1923/// `exp(a − 1) · e/2 = eᵃ/2` for `a ≥ 709` (`a − 1` exact).
1924fn half_exp_large(a: DoubleDouble) -> DoubleDouble {
1925    DoubleDouble::from_sum(a.hi() - 1.0, a.lo()).exp() * E_HALF
1926}
1927
1928/// `ln x + ln 2` for `x ≥ 2⁶⁰`.
1929fn ln_twice(x: DoubleDouble) -> DoubleDouble {
1930    ln_positive(x) + DoubleDouble::LN_2
1931}
1932
1933impl DoubleDouble {
1934    /// Hyperbolic sine: relative error at most `32u²` (proven: `18.7u²`).
1935    /// `±0`, `±∞` for `±0`, `±∞`; `±∞` on overflow; odd bit for bit.
1936    #[must_use]
1937    pub fn sinh(self) -> Self {
1938        debug_assert!(self.check_invariants().is_ok());
1939        let a = self.abs();
1940        if self.is_nan() {
1941            return Self::NAN;
1942        }
1943        if a.hi() < TINY {
1944            return self;
1945        }
1946        let z = if a.hi() > HYPER_LARGE {
1947            half_exp_large(a)
1948        } else {
1949            let e = a.exp_m1();
1950            (e + e / (e + 1.0)).ldexp(-1)
1951        };
1952        if self.hi().is_sign_negative() { -z } else { z }
1953    }
1954
1955    /// Hyperbolic cosine: relative error at most `32u²` (proven: `15.1u²`).
1956    /// `cosh(±0) = 1`, `+∞` for `±∞` and on overflow; even bit for bit.
1957    #[must_use]
1958    pub fn cosh(self) -> Self {
1959        debug_assert!(self.check_invariants().is_ok());
1960        let a = self.abs();
1961        if self.is_nan() {
1962            return Self::NAN;
1963        }
1964        if a.hi() > HYPER_LARGE {
1965            return half_exp_large(a);
1966        }
1967        let e = a.exp();
1968        (e + e.recip()).ldexp(-1)
1969    }
1970
1971    /// Hyperbolic tangent: relative error at most `32u²` (proven:
1972    /// `26.4u²`). `±0` for `±0`, `±1` for `±∞`; for large `|x|` the pair
1973    /// `(±1, ∓2e^(−2|x|))`, exactly `±1` once that is below `η/2`; odd bit
1974    /// for bit.
1975    #[must_use]
1976    pub fn tanh(self) -> Self {
1977        debug_assert!(self.check_invariants().is_ok());
1978        let a = self.abs();
1979        if self.is_nan() {
1980            return Self::NAN;
1981        }
1982        if a.hi() < TINY {
1983            return self;
1984        }
1985        let z = if a.hi() < TANH_SPLIT {
1986            let e = a.ldexp(1).exp_m1();
1987            e / (e + 2.0)
1988        } else {
1989            let f = (-a.ldexp(1)).exp();
1990            (-f + 1.0) / (f + 1.0)
1991        };
1992        if self.hi().is_sign_negative() { -z } else { z }
1993    }
1994
1995    /// Inverse hyperbolic sine: relative error at most `32u²` (proven:
1996    /// `19.7u²`). `±0`, `±∞` for `±0`, `±∞`; odd bit for bit.
1997    #[must_use]
1998    pub fn asinh(self) -> Self {
1999        debug_assert!(self.check_invariants().is_ok());
2000        let a = self.abs();
2001        if self.is_nan() {
2002            return Self::NAN;
2003        }
2004        if a.hi() < TINY || a.hi().is_infinite() {
2005            return self;
2006        }
2007        let z = if a.hi() >= TWO_60 {
2008            ln_twice(a)
2009        } else if a.hi() >= 2.0 {
2010            ln_positive(a + (a.square() + 1.0).sqrt())
2011        } else {
2012            let a2 = a.square();
2013            (a + a2 / ((a2 + 1.0).sqrt() + 1.0)).ln_1p()
2014        };
2015        if self.hi().is_sign_negative() { -z } else { z }
2016    }
2017
2018    /// Inverse hyperbolic cosine: relative error at most `32u²` (proven:
2019    /// `16.8u²`). NaN for `x < 1`, `acosh(1) = +0`, `+∞` for `+∞`.
2020    #[must_use]
2021    pub fn acosh(self) -> Self {
2022        debug_assert!(self.check_invariants().is_ok());
2023        let h = self.hi();
2024        if h.is_nan() || h < 1.0 || (h == 1.0 && self.lo() < 0.0) {
2025            return Self::NAN;
2026        }
2027        if h == f64::INFINITY {
2028            return Self::INFINITY;
2029        }
2030        if h >= TWO_60 {
2031            ln_twice(self)
2032        } else if h >= 2.0 {
2033            ln_positive(self + (self.square() - 1.0).sqrt())
2034        } else {
2035            let d = Self::from_sum(h - 1.0, self.lo());
2036            (d + sqrt_w(d * (d + 2.0))).ln_1p()
2037        }
2038    }
2039
2040    /// Inverse hyperbolic tangent: relative error at most `32u²` (proven:
2041    /// `24.7u²`). NaN outside `[−1, 1]`, `±∞` at `±1`, `±0` for `±0`; odd bit
2042    /// for bit.
2043    #[must_use]
2044    pub fn atanh(self) -> Self {
2045        debug_assert!(self.check_invariants().is_ok());
2046        let a = self.abs();
2047        if self.is_nan() || beyond_one(a) {
2048            return Self::NAN;
2049        }
2050        let negative = self.hi().is_sign_negative();
2051        if a == Self::ONE {
2052            return if negative {
2053                -Self::INFINITY
2054            } else {
2055                Self::INFINITY
2056            };
2057        }
2058        if a.hi() < TINY {
2059            return self;
2060        }
2061        let den = if a.hi() >= 0.5 {
2062            Self::from_sum(1.0 - a.hi(), -a.lo())
2063        } else {
2064            -a + 1.0
2065        };
2066        let z = if den.hi() < f64::MIN_POSITIVE {
2067            // 1 − a subnormal: 2a/(1 − a) may exceed Ω.
2068            (ln_positive(a + 1.0) - ln_positive(den)).ldexp(-1)
2069        } else {
2070            (a.ldexp(1) / den).ln_1p().ldexp(-1)
2071        };
2072        if negative { -z } else { z }
2073    }
2074}
2075
2076#[cfg(test)]
2077#[path = "../tests/support/mod.rs"]
2078mod oracle;
2079
2080#[cfg(test)]
2081#[allow(
2082    clippy::disallowed_methods,
2083    clippy::cast_possible_wrap,
2084    clippy::cast_possible_truncation,
2085    clippy::cast_sign_loss,
2086    clippy::cast_precision_loss,
2087    clippy::too_many_lines,
2088    clippy::needless_range_loop,
2089    clippy::assign_op_pattern
2090)]
2091mod tests {
2092    use super::oracle::{self, Dy, Iv};
2093    use super::*;
2094
2095    /// The first oracle's value of an enclosure: `dashu-float` at 2 400
2096    /// bits gives `c`; the nearest double-double of `c` and of the
2097    /// enclosure must agree with the table entry.
2098    fn check_entry(name: &str, i: usize, e: (u64, u64), f: &oracle::F, iv: &Iv) {
2099        let want = oracle::nearest_dd(&oracle::dy(f));
2100        let got = (f64::from_bits(e.0), f64::from_bits(e.1));
2101        assert_eq!(
2102            (got.0.to_bits(), got.1.to_bits()),
2103            (want.0.to_bits(), want.1.to_bits()),
2104            "{name}[{i}] against dashu-float"
2105        );
2106        let second = iv.nearest_dd().expect("a narrow enclosure");
2107        assert_eq!(
2108            (got.0.to_bits(), got.1.to_bits()),
2109            (second.0.to_bits(), second.1.to_bits()),
2110            "{name}[{i}] against the enclosure"
2111        );
2112    }
2113
2114    fn fz(n: i64, d: i64) -> oracle::F {
2115        oracle::F::from(n).with_precision(2400).value() / oracle::F::from(d)
2116    }
2117
2118    fn q(n: i64, d: i64) -> Iv {
2119        Iv::int(n).div(&Iv::int(d))
2120    }
2121
2122    /// Step S4, which no argument reaches (Lemma D): an odd quadrant with
2123    /// `r = 0` gives `∓2³⁸²`, within the declared bound of `tan` for every
2124    /// `|r*| < 2⁻³¹⁵` consistent with `r = 0`; an even one gives `±0`.
2125    #[test]
2126    fn tangent_at_a_zero_reduction() {
2127        for (q, neg) in [(1, false), (3, false), (1, true), (3, true)] {
2128            let z = tan_from(q, DoubleDouble::ZERO, neg);
2129            let want = if neg {
2130                oracle::pow2f(382)
2131            } else {
2132                -oracle::pow2f(382)
2133            };
2134            // −cos r / sin r at r = 2⁻³⁸²: 2³⁸²(1 − 2⁻⁷⁶⁵/…), finite.
2135            assert!(
2136                z.hi() == want && z.lo().abs() < 1e-100 * want.abs(),
2137                "q = {q}: {z:?}"
2138            );
2139            // tan x = −cot r* ≈ −1/r*: |z − tan x| ≤ 2⁻²⁰⁰(1 + tan²x), in
2140            // log₂ terms, for |r*| from 2⁻³¹⁵ down.
2141            for k in 315..=1000 {
2142                let cot = oracle::pow2f(k);
2143                let err = oracle::pow2f(382) + cot;
2144                let floor = oracle::pow2f(-200) * (1.0 + cot * cot);
2145                assert!(err <= floor || !floor.is_finite(), "k = {k}");
2146            }
2147        }
2148        for q in [0, 2] {
2149            let z = tan_from(q, DoubleDouble::ZERO, false);
2150            assert_eq!(z.hi(), 0.0);
2151        }
2152        // r ≠ 0: the same bits as before step S4 existed.
2153        let r = DoubleDouble::from_f64(0.25);
2154        let (s, c) = (sin_kernel(r, SIN_TERMS), cos_kernel(r));
2155        let z = tan_from(1, r, false);
2156        let old = -(c / s);
2157        assert_eq!(
2158            (z.hi().to_bits(), z.lo().to_bits()),
2159            (old.hi().to_bits(), old.lo().to_bits())
2160        );
2161    }
2162
2163    #[test]
2164    fn function_bounds_cover_every_function() {
2165        let names = [
2166            "exp", "exp2", "exp_m1", "ln", "ln_1p", "log2", "log10", "powi", "powf", "sin", "cos",
2167            "tan", "sin_cos", "asin", "acos", "atan", "atan2", "sinh", "cosh", "tanh", "asinh",
2168            "acosh", "atanh",
2169        ];
2170        assert_eq!(DoubleDouble::FUNCTION_BOUNDS.len(), names.len());
2171        for (b, n) in DoubleDouble::FUNCTION_BOUNDS.iter().zip(names) {
2172            assert_eq!(b.function, n);
2173            assert!(b.units_of_u2 >= 8.0 && b.growth_units_of_u2 >= 0.0);
2174        }
2175        assert_eq!(TRIG_FLOOR, oracle::pow2f(-200));
2176        assert_eq!(TAN_GROWTH, oracle::pow2f(-94));
2177    }
2178
2179    #[test]
2180    fn tables_are_the_nearest_double_doubles() {
2181        let p = 2400;
2182        let one = oracle::F::from(1).with_precision(p).value();
2183        let ln2f = oracle::F::from(2).with_precision(p).value().ln();
2184        let pif = oracle::F::pi(p);
2185        let ln2 = oracle::ln2();
2186        // 2^(j/64) and 2^(j/64) − 1.
2187        for j in 0..64 {
2188            let f = (ln2f.clone() * fz(j, 64)).exp();
2189            let iv = oracle::exp_iv(&ln2.mul(&q(j, 64)));
2190            check_entry("EXP2_64", j as usize, EXP2_64[j as usize], &f, &iv);
2191            check_entry(
2192                "EXP2_64_M1",
2193                j as usize,
2194                EXP2_64_M1[j as usize],
2195                &(f - one.clone()),
2196                &iv.sub(&Iv::int(1)),
2197            );
2198        }
2199        for n in -31..=31_i64 {
2200            let i = (n + 31) as usize;
2201            let f = fz(n, 64).exp() - one.clone();
2202            let iv = oracle::exp(&Dy::int(n).scale(-6)).sub(&Iv::int(1));
2203            check_entry("EXPM1_64", i, EXPM1_64[i], &f, &iv);
2204        }
2205        let mut factf = one.clone();
2206        for n in 0..34_usize {
2207            if n > 0 {
2208                factf = factf * oracle::F::from(n as i64);
2209            }
2210            let f = one.clone() / factf.clone();
2211            let iv = Iv::int(1).div(&Iv::exact(oracle::dy(&factf)));
2212            check_entry("INV_FACT", n, INV_FACT[n], &f, &iv);
2213        }
2214        for n in 1..42_i64 {
2215            check_entry(
2216                "INV_INT",
2217                n as usize,
2218                INV_INT[n as usize],
2219                &fz(1, n),
2220                &q(1, n),
2221            );
2222        }
2223        for j in -18..=26_i64 {
2224            let i = (j + 18) as usize;
2225            let c = Dy::int(64 + j).scale(-6);
2226            check_entry("LN_C", i, LN_C[i], &fz(64 + j, 64).ln(), &oracle::ln(&c));
2227        }
2228        for j in -18..=0_i64 {
2229            let i = (j + 18) as usize;
2230            let c = Dy::int(64 + j).scale(-5);
2231            check_entry("LN_2C", i, LN_2C[i], &fz(64 + j, 32).ln(), &oracle::ln(&c));
2232        }
2233        for j in 0..=26_i64 {
2234            let c = Dy::int(64 + j).scale(-7);
2235            check_entry(
2236                "LN_C_2",
2237                j as usize,
2238                LN_C_2[j as usize],
2239                &fz(64 + j, 128).ln(),
2240                &oracle::ln(&c),
2241            );
2242        }
2243        for e in -6..=2_i64 {
2244            for i in 0..16_i64 {
2245                let k = (16 * (e + 6) + i) as usize;
2246                // c = 2^e (1 + (2i + 1)/32) = (33 + 2i) 2^(e − 5)
2247                let c = Dy::int(33 + 2 * i).scale((e - 5) as isize);
2248                let f = oracle::fdd(
2249                    oracle::pow2f((e - 5) as isize) * (33 + 2 * i) as f64,
2250                    0.0,
2251                    p,
2252                )
2253                .atan();
2254                check_entry("ATAN_C", k, ATAN_C[k], &f, &oracle::atan(&c));
2255            }
2256        }
2257        let three = pif.clone() * oracle::F::from(3) / oracle::F::from(4);
2258        check_entry(
2259            "FRAC_3PI_4",
2260            0,
2261            FRAC_3PI_4,
2262            &three,
2263            &oracle::pi().mul(&q(3, 4)),
2264        );
2265        // The f64 parts.
2266        let parts = |v: &oracle::F, n: usize| -> Vec<f64> {
2267            let mut r = oracle::dy(v);
2268            (0..n)
2269                .map(|_| {
2270                    let h = r.rn();
2271                    r = r.sub(&Dy::f(h));
2272                    h
2273                })
2274                .collect()
2275        };
2276        let l64 = ln2f.clone() / oracle::F::from(64);
2277        assert_eq!(
2278            parts(&l64, 3),
2279            LN2_64.to_vec(),
2280            "LN2_64 against dashu-float"
2281        );
2282        let iv = ln2.scale(-6);
2283        let mut lo = iv.lo.clone();
2284        let mut hi = iv.hi.clone();
2285        for (k, &p) in LN2_64.iter().enumerate() {
2286            assert_eq!(
2287                (lo.rn(), hi.rn()),
2288                (p, p),
2289                "LN2_64[{k}] against the enclosure"
2290            );
2291            lo = lo.sub(&Dy::f(p));
2292            hi = hi.sub(&Dy::f(p));
2293        }
2294        let inv = oracle::F::from(64).with_precision(p).value() / ln2f.clone();
2295        assert_eq!(oracle::dy(&inv).rn(), INV_LN2_64);
2296        let inv = Iv::int(64).div(ln2);
2297        assert_eq!((inv.lo.rn(), inv.hi.rn()), (INV_LN2_64, INV_LN2_64));
2298        // LN2_SPLIT: A = ln 2 rounded to 42 bits.
2299        let a = oracle::dy(&ln2f).round(42, false);
2300        let a_up = oracle::dy(&ln2f).round(42, true);
2301        let ln2d = oracle::dy(&ln2f);
2302        let a = if ln2d.sub(&a).abs().le(&a_up.sub(&ln2d).abs()) {
2303            a
2304        } else {
2305            a_up
2306        };
2307        assert_eq!(a.rn(), LN2_SPLIT[0]);
2308        let rest = ln2d.sub(&a);
2309        assert_eq!(rest.rn(), LN2_SPLIT[1]);
2310        assert_eq!(rest.sub(&Dy::f(LN2_SPLIT[1])).rn(), LN2_SPLIT[2]);
2311        for (k, end) in [&ln2.lo, &ln2.hi].into_iter().enumerate() {
2312            let r = end.sub(&Dy::f(LN2_SPLIT[0]));
2313            assert_eq!(r.rn(), LN2_SPLIT[1], "LN2_SPLIT[1], end {k}");
2314            assert_eq!(
2315                r.sub(&Dy::f(LN2_SPLIT[1])).rn(),
2316                LN2_SPLIT[2],
2317                "LN2_SPLIT[2], end {k}"
2318            );
2319        }
2320        // The bits of 2/π and π/4.
2321        let two_pi = oracle::F::from(2).with_precision(p).value() / pif.clone();
2322        let words = |v: &oracle::F, n: usize| -> Vec<u64> {
2323            Iv::exact(oracle::dy(v)).fixed_words(n).expect("exact")
2324        };
2325        assert_eq!(
2326            words(&two_pi, 22),
2327            TWO_OVER_PI.to_vec(),
2328            "2/π against dashu-float"
2329        );
2330        let pi = oracle::pi();
2331        assert_eq!(
2332            Iv::int(2).div(pi).fixed_words(22).expect("narrow"),
2333            TWO_OVER_PI.to_vec(),
2334            "2/π against the enclosure"
2335        );
2336        assert_eq!(words(&(pif / oracle::F::from(4)), 5), PI_OVER_4.to_vec());
2337        assert_eq!(
2338            pi.scale(-2).fixed_words(5).expect("narrow"),
2339            PI_OVER_4.to_vec()
2340        );
2341    }
2342}