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}