Skip to main content

xingo_statla/
random.rs

1//! # Chapter 12.1 — Reproducible randomness: Algorithm G and the logarithm
2//!
3//! ## Purpose
4//! [`crate::rsvd()`] draws a test matrix `Ω`, [`crate::svds()`] a starting
5//! vector and the replacement vectors after a breakdown. Decision S4 of
6//! D-0127: the same seed gives **the same bits on every platform**, and the
7//! sequence for a seed is part of the semver contract. Hence no `rand`
8//! (its algorithms may change between versions) and no `libm` `ln` (its
9//! last bit differs between platforms): an own xoshiro256++ seeded by
10//! SplitMix64, Marsaglia's polar method, and an own logarithm written with
11//! `+ − · /` only, all of which IEEE 754 rounds identically everywhere
12//! (Rust never contracts `a·b + c` into a fused multiply-add on its own).
13//!
14//! ## Notation
15//! `u = ε_T/2` the unit roundoff of the scalar; `fl(·)` a rounded
16//! operation, `fl(a ∘ b) = (a ∘ b)(1 + δ)`, `|δ| ≤ u` (the IEEE model for
17//! `f64`). `ln 2 = A + B + C` with three `f64` constants (those of
18//! `xingo-extprec`, Chapter 11.2): `A` has 42 significant bits (so `e·A` is
19//! exact for `|e| < 2¹¹`), `|B| < 2⁻⁴²`, `|C| < 2⁻⁹⁷`, `|ln 2 − (A + B + C)| <
20//! 2⁻¹⁵⁰`.
21//!
22//! ## Algorithm G (Gaussian deviates, bit-reproducible)
23//! G1. \[Seed.\] The state `s₀ … s₃` of xoshiro256++ (Blackman & Vigna) is
24//!     four consecutive outputs of SplitMix64 started at the user's `seed`
25//!     (`x ← x + 0x9e3779b97f4a7c15`; `z ← (z ⊕ z≫30)·0xbf58476d1ce4e5b9`;
26//!     `z ← (z ⊕ z≫27)·0x94d049bb133111eb`; output `z ⊕ z≫31`). SplitMix64
27//!     is a bijection of its counter, so at most one of the four words is
28//!     zero: every seed, `0` included, gives a valid (nonzero) state.
29//! G2. \[Uniform.\] `U = (next() ≫ 11)·2⁻⁵³ ∈ [0, 1)`, with `next()` the
30//!     xoshiro256++ step: output `rotl(s₀ + s₃, 23) + s₀`; then `t ← s₁ ≪
31//!     17`, `s₂ ⊕= s₀`, `s₃ ⊕= s₁`, `s₁ ⊕= s₂`, `s₀ ⊕= s₃`, `s₂ ⊕= t`, `s₃ ←
32//!     rotl(s₃, 45)`.
33//! G3. \[Polar.\] `u ← 2U − 1`, `v ← 2U′ − 1` (two uniforms, in that order;
34//!     both exact); `s ← u² + v²`; start again unless `0 < s < 1`
35//!     (Marsaglia & Bray). The smallest nonzero `s` is `2⁻¹⁰⁴`: normal.
36//! G4. \[Transform.\] `g ← u · √(fl(−2·ln(s)) / s)` with this chapter's `ln`
37//!     (Algorithm L) in `f64`. Only `u`'s deviate is used; `v`'s is
38//!     discarded (one rule, no hidden state between calls).
39//! G5. \[Fill.\] A test matrix is filled column by column, entry by entry,
40//!     from one stream: `Ω_ij` is the `(i + j·n)`-th deviate. The deviates
41//!     are `f64` and converted exactly (`Real::from_f64`), so the sketch is
42//!     the same in every scalar.
43//!
44//! [`Sketch::Rademacher`] draws `±1` from the
45//! top bit of one `next()` per entry (bit set: `−1`).
46//!
47//! ## Algorithm L (natural logarithm of a positive normal `x`, `T: Real`)
48//! L1. \[Exponent.\] `h ← x.to_f64()` (for the double-double, its high
49//!     part); if `h` is subnormal, `x ← x·2⁵⁴` first and remember `−54`.
50//!     `e ←` the unbiased exponent of `h`, read off its bits.
51//! L2. \[Reduce.\] `m ← x·2⁻ᵉ` (by at most two exact power-of-two products),
52//!     so `m ∈ [1, 2)` (for the double-double `m ≥ 1 − 2⁻⁵³`). If `m > √2`
53//!     (the `f64` nearest to it): `m ← m/2`, `e ← e + 1`. Now `m ∈ [√½,
54//!     √2]` up to the rounding of the constant.
55//! L3. \[Atanh argument.\] `z ← (m − 1)/(m + 1)`, `w ← z²`; `|z| ≤ (√2 −
56//!     1)/(√2 + 1) = 0.1716`, `w ≤ w̄ = 0.02944`.
57//! L4. \[Series.\] `P ← c_N`; for `i = N − 1, …, 0`: `P ← P·w + c_i`, with `c_i
58//!     = fl(1/(2i + 1))` (Horner on `ln m = 2 atanh z = 2z Σ w^i/(2i + 1)`).
59//!     `N` is the least integer with `w̄^{N+1}/((2N + 3)(1 − w̄)) ≤ ε_T/8`,
60//!     a function of `ε_T` only: `N = 9` (ten terms) for `f64`, `N = 19`
61//!     for the double-double. `L ← 2·z·P`.
62//! L5. \[Combine.\] If `e = 0`, return `L`. Otherwise return
63//!     `e·A + (L + (e·B + e·C))`, evaluated in that order.
64//!
65//! **Lemma L (accuracy in `f64`).** For every positive normal `x`, the
66//! result of Algorithm L in `f64` has relative error at most `6.4u` (to
67//! first order in `u`), and `ln 1 = 0` exactly.
68//!
69//! *Proof.* L1–L2 are exact (power-of-two scalings of a normal number).
70//! L3: `m − 1` is exact (Sterbenz: `m ∈ [½, 2]`), so `z̃ = z(1 + θ)`, `|θ| ≤
71//! 2u` (the rounding of `m + 1` and of the quotient), and `w̃ = w(1 + θ′)`,
72//! `|θ′| ≤ 5u`. L4: every term is positive and `w P₁ ≤ w̄/(3(1 − w̄)) <
73//! 0.0102` where `P = 1 + w P₁`; the last step `fl(1 + fl(w̃ P̃₁))` errs by
74//! at most `u·P` plus `0.0102·(5u + u + 2u)` from `w̃`, the product and
75//! `P̃₁` (whose own relative error is `≤ 2u` by the same argument one level
76//! down), plus the truncation `≤ u/4` and the rounded `c_i` (inside the
77//! `8u`): `P̃ = P(1 + θ_P)`, `|θ_P| ≤ 1.35u`. So `L̃ = L(1 + θ_L)`, `|θ_L| ≤
78//! 2u + 1.35u + u = 4.35u` (the factor 2 is exact). L5, `e ≠ 0`: `e·A` is
79//! exact; `t = fl(e·B + e·C)` and the missing tail of `ln 2` weigh `≤ |e|·
80//! 2⁻⁹⁴`, negligible; the two remaining additions err by `u|L + t|` and
81//! `u|r|`. Since `|L| ≤ ln √2` and `|ln x| ≥ ln 2 − ln √2 = ln √2` when `e ≠
82//! 0`, `|L| ≤ |ln x|`, hence `|r − ln x| ≤ (4.35 + 1 + 1)u|ln x| + O(u²)`.
83//! For `x = 1`: `z = 0`, `L = 0`, `e = 0`. ∎
84//!
85//! For the double-double the same derivation holds with the operation
86//! bounds of Chapter 11 in place of `(1 + δ)` (each a small multiple of
87//! `u = 2⁻¹⁰⁵`); the bound is *measured* there, not proved (tests below and
88//! `l33-tables.md`). Measured in `f64` on 1.8·10⁵ arguments (all binades,
89//! the polar range `(0, 1)`, and `1 ± 2⁻ᵏ`): at most `3.5u` against
90//! `DoubleDouble::ln` (proved to `8u²`, an exact oracle at this level); in
91//! the double-double, on 4.5·10⁴ full-precision arguments, at most `2.7u`
92//! against the same oracle (whose own error, `≤ 8·2⁻¹⁰⁶`, is of the same
93//! order: the measurement bounds the sum). The tests assert `6.4u` and
94//! `16u`.
95//!
96//! ## Invariants
97//! (R1) *Frozen sequence.* For seed 0 the first 64 Gaussian deviates, the
98//!      first raw words and the first Rademacher signs are pinned bit for
99//!      bit by a test; changing them is a breaking change.
100//! (R2) *Platform independence.* Only integer operations, IEEE `+ − · /`
101//!      and `sqrt` are used (Algorithm L avoids `libm`).
102//! (R3) `ln` is exact at `1` and monotone enough for the polar method (not
103//!      needed for correctness: any fixed function gives a fixed stream).
104//!
105//! ## References
106//! Blackman & Vigna, "Scrambled linear pseudorandom number generators",
107//! ACM TOMS 47 (2021), and the reference `xoshiro256plusplus.c` (whose
108//! first ten outputs from the state `(1, 2, 3, 4)`, as reproduced in the
109//! tests of `rand` 0.9.4, are pinned below); Steele, Lea & Flood,
110//! "Fast splittable pseudorandom number generators", OOPSLA 2014
111//! (SplitMix64); Marsaglia & Bray, "A convenient method for generating
112//! normal variables", SIAM Review 6 (1964); Muller, *Elementary Functions*
113//! (2016), ch. 6 (argument reduction; the atanh series); Higham, *Accuracy
114//! and Stability of Numerical Algorithms* (2002), ch. 2–3. Cited from
115//! memory, except the reference outputs.
116
117use xingo_sparse::Real;
118
119use crate::real::{le_exact, lt};
120
121/// Distribution of the test matrix `Ω` of [`crate::rsvd()`] and
122/// [`crate::range_finder`] (Algorithm G).
123///
124/// The sequence for a given seed is part of the semver contract (a
125/// frozen-sequence test pins the first 64 deviates): changing it is a
126/// breaking change.
127#[derive(Clone, Copy, Debug, PartialEq, Eq, Default)]
128#[non_exhaustive]
129pub enum Sketch {
130    /// Standard Gaussian entries (Algorithm G) — the distribution of the
131    /// HMT bounds. Default.
132    #[default]
133    Gaussian,
134    /// `±1` with probability ½ each (one bit of `next()` per entry). No
135    /// transcendental function; HMT's expectation bound is *not* proven
136    /// for it, though the pilot found it inside the bound on three
137    /// spectra.
138    Rademacher,
139}
140
141/// SplitMix64 increment (the golden ratio, `⌊2⁶⁴/φ⌋` odd).
142const SPLITMIX_GAMMA: u64 = 0x9e37_79b9_7f4a_7c15;
143/// The two SplitMix64 multipliers.
144const SPLITMIX_M1: u64 = 0xbf58_476d_1ce4_e5b9;
145const SPLITMIX_M2: u64 = 0x94d0_49bb_1331_11eb;
146
147/// `ln 2 = A + B + C` (the split of `xingo-extprec`, Chapter 11.2; `A` has
148/// 42 significant bits).
149const LN2_A: f64 = f64::from_bits(0x3fe6_2e42_fefa_3800);
150const LN2_B: f64 = f64::from_bits(0x3d2e_f357_93c7_6730);
151const LN2_C: f64 = f64::from_bits(0x398f_97b5_7a07_9a19);
152/// `w̄ = ((√2 − 1)/(√2 + 1))² = 17 − 12√2` rounded up (checked at 200
153/// bits): the bound on `w` in step L3.
154const W_BAR: f64 = 0.029_437_251_522_859_417;
155/// The exponent field of an `f64`.
156const EXPONENT_MASK: u64 = 0x7ff0_0000_0000_0000;
157/// `2⁵⁴`, the pre-scaling of a subnormal high part (step L1).
158const TWO_54: f64 = 18_014_398_509_481_984.0;
159
160/// The generator of Algorithm G: xoshiro256++ seeded by SplitMix64.
161#[derive(Clone, Debug)]
162pub(crate) struct Rng {
163    s: [u64; 4],
164}
165
166impl Rng {
167    /// G1.
168    pub(crate) fn new(seed: u64) -> Self {
169        let mut x = seed;
170        let mut s = [0; 4];
171        for w in &mut s {
172            x = x.wrapping_add(SPLITMIX_GAMMA);
173            let mut z = x;
174            z = (z ^ (z >> 30)).wrapping_mul(SPLITMIX_M1);
175            z = (z ^ (z >> 27)).wrapping_mul(SPLITMIX_M2);
176            *w = z ^ (z >> 31);
177        }
178        debug_assert_ne!(s, [0; 4], "(G1) SplitMix64 never gives four zeros");
179        Self { s }
180    }
181
182    /// The xoshiro256++ step (G2).
183    pub(crate) fn next_u64(&mut self) -> u64 {
184        let s = &mut self.s;
185        let out = s[0].wrapping_add(s[3]).rotate_left(23).wrapping_add(s[0]);
186        let t = s[1] << 17;
187        s[2] ^= s[0];
188        s[3] ^= s[1];
189        s[1] ^= s[2];
190        s[0] ^= s[3];
191        s[2] ^= t;
192        s[3] = s[3].rotate_left(45);
193        out
194    }
195
196    /// G2: `U ∈ [0, 1)`, a multiple of `2⁻⁵³`.
197    #[allow(clippy::cast_precision_loss)] // 53-bit integers are exact in f64
198    pub(crate) fn uniform(&mut self) -> f64 {
199        const TWO_M53: f64 = 1.0 / 9_007_199_254_740_992.0;
200        (self.next_u64() >> 11) as f64 * TWO_M53
201    }
202
203    /// G3–G4: one standard Gaussian deviate.
204    pub(crate) fn gaussian(&mut self) -> f64 {
205        loop {
206            // G3.
207            let u = 2.0 * self.uniform() - 1.0;
208            let v = 2.0 * self.uniform() - 1.0;
209            let s = u * u + v * v;
210            if lt(0.0, s) && lt(s, 1.0) {
211                // G4.
212                return u * ((-2.0 * ln(s)) / s).sqrt();
213            }
214        }
215    }
216
217    /// `±1` from the top bit of one word.
218    pub(crate) fn rademacher(&mut self) -> f64 {
219        if self.next_u64() >> 63 == 1 {
220            -1.0
221        } else {
222            1.0
223        }
224    }
225
226    /// One deviate of the distribution `sketch`.
227    pub(crate) fn deviate(&mut self, sketch: Sketch) -> f64 {
228        match sketch {
229            Sketch::Rademacher => self.rademacher(),
230            Sketch::Gaussian => self.gaussian(),
231        }
232    }
233
234    /// G5: fill `data` (column-major) entry by entry from the stream.
235    pub(crate) fn fill<T: Real>(&mut self, sketch: Sketch, data: &mut [T]) {
236        for v in data {
237            *v = T::from_f64(self.deviate(sketch));
238        }
239    }
240}
241
242/// `2ᵏ` for `−1022 ≤ k ≤ 1023` (a normal `f64`, built from its bits).
243#[allow(clippy::cast_sign_loss)] // k + 1023 ∈ [1, 2046]
244fn pow2(k: i32) -> f64 {
245    debug_assert!((-1022..=1023).contains(&k));
246    f64::from_bits(((k + 1023) as u64) << 52)
247}
248
249/// The number `N` of step L4 for the scalar `T`.
250fn series_degree<T: Real>() -> usize {
251    let target = T::EPSILON.to_f64() / 8.0;
252    let mut wp = W_BAR; // w̄^{N+1}
253    let mut n = 0usize;
254    loop {
255        #[allow(clippy::cast_precision_loss)]
256        let den = (2 * n + 3) as f64 * (1.0 - W_BAR);
257        if le_exact(wp / den, target) {
258            return n;
259        }
260        wp *= W_BAR;
261        n += 1;
262    }
263}
264
265/// Algorithm L: `ln x` for a positive normal finite `x` (the callers
266/// guarantee it; anything else returns an unspecified value, never a
267/// panic).
268pub(crate) fn ln<T: Real>(x: T) -> T {
269    debug_assert!(x.is_finite() && lt(T::ZERO, x), "Algorithm L needs x > 0");
270    // L1.
271    let mut x = x;
272    let mut e_adj = 0i32;
273    let mut bits = x.to_f64().to_bits();
274    if bits & EXPONENT_MASK == 0 {
275        x *= T::from_f64(TWO_54);
276        e_adj = -54;
277        bits = x.to_f64().to_bits();
278    }
279    #[allow(clippy::cast_possible_truncation, clippy::cast_possible_wrap)]
280    let mut e = ((bits & EXPONENT_MASK) >> 52) as i32 - 1023;
281    // L2. Two exact scalings keep every factor normal.
282    let half = -e / 2;
283    let mut m = x * T::from_f64(pow2(half)) * T::from_f64(pow2(-e - half));
284    if lt(T::from_f64(core::f64::consts::SQRT_2), m) {
285        m *= T::from_f64(0.5);
286        e += 1;
287    }
288    e += e_adj;
289    // L3.
290    let z = (m - T::ONE) / (m + T::ONE);
291    let w = z * z;
292    // L4.
293    let n = series_degree::<T>();
294    let coef = |i: usize| {
295        #[allow(clippy::cast_precision_loss)]
296        let d = (2 * i + 1) as f64;
297        T::ONE / T::from_f64(d)
298    };
299    let mut p = coef(n);
300    for i in (0..n).rev() {
301        p = p * w + coef(i);
302    }
303    let l = T::from_f64(2.0) * z * p;
304    // L5.
305    if e == 0 {
306        return l;
307    }
308    let ef = T::from_f64(f64::from(e));
309    let t = ef * T::from_f64(LN2_B) + ef * T::from_f64(LN2_C);
310    ef * T::from_f64(LN2_A) + (l + t)
311}
312
313#[cfg(test)]
314#[allow(
315    clippy::float_cmp,
316    clippy::cast_precision_loss,
317    clippy::unreadable_literal // frozen bit patterns
318)]
319mod tests {
320    use super::*;
321    use xingo_extprec::DoubleDouble as Dd;
322
323    #[test]
324    fn xoshiro_matches_the_reference_outputs() {
325        // State (1, 2, 3, 4); outputs of the reference C implementation as
326        // reproduced in the tests of `rand` 0.9.4.
327        let mut r = Rng { s: [1, 2, 3, 4] };
328        let expected: [u64; 10] = [
329            41_943_041,
330            58_720_359,
331            3_588_806_011_781_223,
332            3_591_011_842_654_386,
333            9_228_616_714_210_784_205,
334            9_973_669_472_204_895_162,
335            14_011_001_112_246_962_877,
336            12_406_186_145_184_390_807,
337            15_849_039_046_786_891_736,
338            10_450_023_813_501_588_000,
339        ];
340        for e in expected {
341            assert_eq!(r.next_u64(), e);
342        }
343    }
344
345    /// (R1): the frozen sequence of seed 0 (and the seeding of seed 1).
346    #[test]
347    fn sequence_of_seed_zero_is_frozen() {
348        let mut r = Rng::new(0);
349        assert_eq!(r.s, FROZEN_STATE_0);
350        let mut r1 = Rng::new(1);
351        let raw: Vec<u64> = (0..4).map(|_| r1.next_u64()).collect();
352        assert_eq!(raw, FROZEN_RAW_1);
353        let g: Vec<u64> = (0..64).map(|_| r.gaussian().to_bits()).collect();
354        assert_eq!(g, FROZEN_GAUSS_0);
355        let mut rr = Rng::new(0);
356        let signs: Vec<f64> = (0..16).map(|_| rr.rademacher()).collect();
357        assert_eq!(signs, FROZEN_RADEMACHER_0);
358    }
359
360    const FROZEN_STATE_0: [u64; 4] = [
361        16294208416658607535,
362        7960286522194355700,
363        487617019471545679,
364        17909611376780542444,
365    ];
366    const FROZEN_RAW_1: [u64; 4] = [
367        14971601782005023387,
368        13781649495232077965,
369        1847458086238483744,
370        13765271635752736470,
371    ];
372    /// Bits of the first 64 Gaussian deviates of seed 0 (the first is
373    /// `-1.5411826072230725`).
374    const FROZEN_GAUSS_0: [u64; 64] = [
375        0xbff8a8af17f2fe67,
376        0xbf708d7cb6a3955d,
377        0x3fbc958a80b0b8e6,
378        0xbfca60c5aa96ee22,
379        0xbfc8321083be657e,
380        0xbfe53100de8d3b86,
381        0x3fd233ab345f0647,
382        0xbffada9d88a0b370,
383        0xbfd9624e017442d8,
384        0xbff12f999b7f0784,
385        0xbfed1aaaa24ca640,
386        0xbff6a4ba59fafe1d,
387        0xbfd81899a654bd69,
388        0x3fd5e96343423eec,
389        0x3fa70d7e06e38361,
390        0x3fe258602afb1018,
391        0x3fe1c8af537e33dd,
392        0xbfc534af346ec048,
393        0xbfdde34fc2b742fa,
394        0xbff88db52ac5488e,
395        0x40046727b91817bf,
396        0x3fd57ba2329c55b9,
397        0x3ffc30ea6e625005,
398        0xbff651eca0888b18,
399        0x3fe399d771a6dede,
400        0xbfc8ae207ae66069,
401        0xbfe511bbf0d3868f,
402        0x3fd1e2d26a847ade,
403        0x3fe67e6ce7ea2ca3,
404        0x3ff3fd13aa3ae25f,
405        0x3ff9b1584aa24b3e,
406        0x3fe83534195628a4,
407        0x3fefa20547b88b13,
408        0x3ffdb0421ff79616,
409        0x3fdc9c2a580e3862,
410        0x3fdaa737134ed9c0,
411        0xbfe7774cdecdb232,
412        0x3fbcb2cf25eb1719,
413        0xbff3ae5d8e9d3e80,
414        0xbf59230c30a61bfa,
415        0x3ff1a35b827f0a06,
416        0x3fe33bceec22e0af,
417        0xbff62602652954ec,
418        0x3fee65bff8eaacf1,
419        0xbff1604ce70bb525,
420        0xbff2a3b0ab926856,
421        0xbfce454bf4ff4b01,
422        0x3fec727727057ace,
423        0x3ff08305cdbc9f80,
424        0x3ff501fe9e282575,
425        0x3fc786802bf04146,
426        0xbff77ee7a0537b14,
427        0x3fe1ae9378cd2d2a,
428        0xbfeec1282ba1af9d,
429        0x3ff34afa4b3870ba,
430        0x3ff205d8dc9f3a5f,
431        0xbff08d8b20cb5b2e,
432        0xbfede4e70a407787,
433        0xbfe7399116c7218a,
434        0x3fe6b38b58b12210,
435        0x3fe39f58ac2a7984,
436        0x3fe10b5b38bf6349,
437        0x3ffa0c12c6765728,
438        0x3ff5b042b55ceec0,
439    ];
440    const FROZEN_RADEMACHER_0: [f64; 16] = [
441        1.0, 1.0, 1.0, 1.0, 1.0, 1.0, -1.0, -1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0,
442    ];
443
444    #[test]
445    fn deviates_have_the_moments_of_a_standard_gaussian() {
446        let mut r = Rng::new(42);
447        let n = 200_000;
448        let (mut s1, mut s2, mut s4) = (0.0, 0.0, 0.0);
449        for _ in 0..n {
450            let g = r.gaussian();
451            s1 += g;
452            s2 += g * g;
453            s4 += g * g * g * g;
454        }
455        let n = f64::from(n);
456        assert!((s1 / n).abs() < 0.01, "mean {}", s1 / n);
457        assert!((s2 / n - 1.0).abs() < 0.015, "variance {}", s2 / n);
458        assert!((s4 / n - 3.0).abs() < 0.08, "fourth moment {}", s4 / n);
459        let mut rr = Rng::new(42);
460        let plus = (0..10_000).filter(|_| rr.rademacher() > 0.0).count();
461        assert!((4800..5200).contains(&plus));
462        let u: f64 = (0..10_000).map(|_| rr.uniform()).sum::<f64>() / 10_000.0;
463        assert!((u - 0.5).abs() < 0.01);
464    }
465
466    /// The arguments of the `ln` tests: every binade, the polar range, and
467    /// `1 ± 2⁻ᵏ`.
468    fn ln_arguments() -> Vec<f64> {
469        let mut r = Rng::new(7);
470        let mut xs = vec![1.0, 2.0, 0.5, core::f64::consts::SQRT_2, f64::MIN_POSITIVE];
471        xs.push(f64::MAX);
472        for k in 1..53 {
473            let d = pow2(-k);
474            xs.extend([1.0 + d, 1.0 - d / 2.0]);
475        }
476        for e in -1022..1024 {
477            for _ in 0..40 {
478                xs.push((1.0 + r.uniform()) * pow2(e.min(1023)));
479            }
480        }
481        for _ in 0..100_000 {
482            let s = r.uniform();
483            if s > 0.0 {
484                xs.push(s);
485            }
486        }
487        xs
488    }
489
490    /// `|ln(x) − oracle| / |oracle|` in units of `u`.
491    fn rel_err_u(own: Dd, oracle: Dd, u: f64) -> f64 {
492        if oracle == Dd::ZERO {
493            return if own == Dd::ZERO { 0.0 } else { f64::INFINITY };
494        }
495        ((own - oracle) / oracle).abs().to_f64() / u
496    }
497
498    /// Lemma L, measured: `f64` within `6.4u` of `DoubleDouble::ln`.
499    #[test]
500    fn ln_in_f64_is_within_the_proven_bound() {
501        let u = f64::EPSILON / 2.0;
502        let mut worst = 0.0f64;
503        for x in ln_arguments() {
504            let e = rel_err_u(Dd::from_f64(ln(x)), Dd::from_f64(x).ln(), u);
505            assert!(e <= 6.4, "ln({x:e}): {e} u");
506            worst = worst.max(e);
507        }
508        assert_eq!(ln(1.0), 0.0);
509        assert_eq!(series_degree::<f64>(), 9);
510        eprintln!("ln f64: max relative error {worst:.3} u");
511    }
512
513    /// Algorithm L in the double-double, against `DoubleDouble::ln`.
514    #[test]
515    fn ln_in_double_double_is_within_a_few_units() {
516        let u = Dd::EPSILON.to_f64() / 2.0;
517        let mut worst = 0.0f64;
518        let mut r = Rng::new(9);
519        for x in ln_arguments().into_iter().step_by(4) {
520            // A full-precision argument: x (1 + small) with a nonzero low part.
521            let xd = Dd::from_f64(x) * (Dd::ONE + Dd::from_f64(r.uniform() * f64::EPSILON));
522            if !(xd.to_f64() > 0.0 && xd.is_finite()) {
523                continue;
524            }
525            let e = rel_err_u(ln(xd), xd.ln(), u);
526            assert!(e <= 16.0, "ln({x:e}) in dd: {e} u");
527            worst = worst.max(e);
528        }
529        assert_eq!(series_degree::<Dd>(), 19);
530        eprintln!("ln dd: max relative error {worst:.3} u (oracle error included)");
531    }
532
533    #[test]
534    fn ln2_split_and_subnormal_reduction() {
535        let ln2 = Dd::from_f64(2.0).ln();
536        let split = Dd::from_f64(LN2_A) + Dd::from_f64(LN2_B) + Dd::from_f64(LN2_C);
537        assert!(((split - ln2) / ln2).abs().to_f64() < 1e-31);
538        assert_eq!(LN2_A.to_bits() & 0x7ff, 0, "A has 42 significant bits");
539        let w = ((2f64.sqrt() - 1.0) / (2f64.sqrt() + 1.0)).powi(2);
540        // `W_BAR ≥ w̄` exactly was checked at 200 bits (mpmath, task L3.3);
541        // here only that the constant is the right one.
542        assert!((W_BAR - w).abs() < 1e-16);
543        // Subnormal arguments go through the pre-scaling of L1.
544        for x in [f64::MIN_POSITIVE / 3.0, 5e-324, 1e-310] {
545            let e = rel_err_u(
546                Dd::from_f64(ln(x)),
547                Dd::from_f64(x).ln(),
548                f64::EPSILON / 2.0,
549            );
550            assert!(e <= 6.4, "{x:e}: {e}");
551        }
552    }
553}