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}