Skip to main content

Module random

Module random 

Source
Expand description

§Chapter 12.1 — Reproducible randomness: Algorithm G and the logarithm

§Purpose

crate::rsvd() draws a test matrix Ω, crate::svds() a starting vector and the replacement vectors after a breakdown. Decision S4 of D-0127: the same seed gives the same bits on every platform, and the sequence for a seed is part of the semver contract. Hence no rand (its algorithms may change between versions) and no libm ln (its last bit differs between platforms): an own xoshiro256++ seeded by SplitMix64, Marsaglia’s polar method, and an own logarithm written with + − · / only, all of which IEEE 754 rounds identically everywhere (Rust never contracts a·b + c into a fused multiply-add on its own).

§Notation

u = ε_T/2 the unit roundoff of the scalar; fl(·) a rounded operation, fl(a ∘ b) = (a ∘ b)(1 + δ), |δ| ≤ u (the IEEE model for f64). ln 2 = A + B + C with three f64 constants (those of xingo-extprec, Chapter 11.2): A has 42 significant bits (so e·A is exact for |e| < 2¹¹), |B| < 2⁻⁴², |C| < 2⁻⁹⁷, |ln 2 − (A + B + C)| < 2⁻¹⁵⁰.

§Algorithm G (Gaussian deviates, bit-reproducible)

G1. [Seed.] The state s₀ … s₃ of xoshiro256++ (Blackman & Vigna) is four consecutive outputs of SplitMix64 started at the user’s seed (x ← x + 0x9e3779b97f4a7c15; z ← (z ⊕ z≫30)·0xbf58476d1ce4e5b9; z ← (z ⊕ z≫27)·0x94d049bb133111eb; output z ⊕ z≫31). SplitMix64 is a bijection of its counter, so at most one of the four words is zero: every seed, 0 included, gives a valid (nonzero) state. G2. [Uniform.] U = (next() ≫ 11)·2⁻⁵³ ∈ [0, 1), with next() the xoshiro256++ step: output rotl(s₀ + s₃, 23) + s₀; then t ← s₁ ≪ 17, s₂ ⊕= s₀, s₃ ⊕= s₁, s₁ ⊕= s₂, s₀ ⊕= s₃, s₂ ⊕= t, s₃ ← rotl(s₃, 45). G3. [Polar.] u ← 2U − 1, v ← 2U′ − 1 (two uniforms, in that order; both exact); s ← u² + v²; start again unless 0 < s < 1 (Marsaglia & Bray). The smallest nonzero s is 2⁻¹⁰⁴: normal. G4. [Transform.] g ← u · √(fl(−2·ln(s)) / s) with this chapter’s ln (Algorithm L) in f64. Only u’s deviate is used; v’s is discarded (one rule, no hidden state between calls). G5. [Fill.] A test matrix is filled column by column, entry by entry, from one stream: Ω_ij is the (i + j·n)-th deviate. The deviates are f64 and converted exactly (Real::from_f64), so the sketch is the same in every scalar.

Sketch::Rademacher draws ±1 from the top bit of one next() per entry (bit set: −1).

§Algorithm L (natural logarithm of a positive normal x, T: Real)

L1. [Exponent.] h ← x.to_f64() (for the double-double, its high part); if h is subnormal, x ← x·2⁵⁴ first and remember −54. e ← the unbiased exponent of h, read off its bits. L2. [Reduce.] m ← x·2⁻ᵉ (by at most two exact power-of-two products), so m ∈ [1, 2) (for the double-double m ≥ 1 − 2⁻⁵³). If m > √2 (the f64 nearest to it): m ← m/2, e ← e + 1. Now m ∈ [√½, √2] up to the rounding of the constant. L3. [Atanh argument.] z ← (m − 1)/(m + 1), w ← z²; |z| ≤ (√2 − 1)/(√2 + 1) = 0.1716, w ≤ w̄ = 0.02944. L4. [Series.] P ← c_N; for i = N − 1, …, 0: P ← P·w + c_i, with c_i = fl(1/(2i + 1)) (Horner on ln m = 2 atanh z = 2z Σ w^i/(2i + 1)). N is the least integer with w̄^{N+1}/((2N + 3)(1 − w̄)) ≤ ε_T/8, a function of ε_T only: N = 9 (ten terms) for f64, N = 19 for the double-double. L ← 2·z·P. L5. [Combine.] If e = 0, return L. Otherwise return e·A + (L + (e·B + e·C)), evaluated in that order.

Lemma L (accuracy in f64). For every positive normal x, the result of Algorithm L in f64 has relative error at most 6.4u (to first order in u), and ln 1 = 0 exactly.

Proof. L1–L2 are exact (power-of-two scalings of a normal number). L3: m − 1 is exact (Sterbenz: m ∈ [½, 2]), so z̃ = z(1 + θ), |θ| ≤ 2u (the rounding of m + 1 and of the quotient), and w̃ = w(1 + θ′), |θ′| ≤ 5u. L4: every term is positive and w P₁ ≤ w̄/(3(1 − w̄)) < 0.0102 where P = 1 + w P₁; the last step fl(1 + fl(w̃ P̃₁)) errs by at most u·P plus 0.0102·(5u + u + 2u) from w̃, the product and P̃₁ (whose own relative error is ≤ 2u by the same argument one level down), plus the truncation ≤ u/4 and the rounded c_i (inside the 8u): P̃ = P(1 + θ_P), |θ_P| ≤ 1.35u. So L̃ = L(1 + θ_L), |θ_L| ≤ 2u + 1.35u + u = 4.35u (the factor 2 is exact). L5, e ≠ 0: e·A is exact; t = fl(e·B + e·C) and the missing tail of ln 2 weigh ≤ |e|· 2⁻⁹⁴, negligible; the two remaining additions err by u|L + t| and u|r|. Since |L| ≤ ln √2 and |ln x| ≥ ln 2 − ln √2 = ln √2 when e ≠ 0, |L| ≤ |ln x|, hence |r − ln x| ≤ (4.35 + 1 + 1)u|ln x| + O(u²). For x = 1: z = 0, L = 0, e = 0. ∎

For the double-double the same derivation holds with the operation bounds of Chapter 11 in place of (1 + δ) (each a small multiple of u = 2⁻¹⁰⁵); the bound is measured there, not proved (tests below and l33-tables.md). Measured in f64 on 1.8·10⁵ arguments (all binades, the polar range (0, 1), and 1 ± 2⁻ᵏ): at most 3.5u against DoubleDouble::ln (proved to 8u², an exact oracle at this level); in the double-double, on 4.5·10⁴ full-precision arguments, at most 2.7u against the same oracle (whose own error, ≤ 8·2⁻¹⁰⁶, is of the same order: the measurement bounds the sum). The tests assert 6.4u and 16u.

§Invariants

(R1) Frozen sequence. For seed 0 the first 64 Gaussian deviates, the first raw words and the first Rademacher signs are pinned bit for bit by a test; changing them is a breaking change. (R2) Platform independence. Only integer operations, IEEE + − · / and sqrt are used (Algorithm L avoids libm). (R3) ln is exact at 1 and monotone enough for the polar method (not needed for correctness: any fixed function gives a fixed stream).

§References

Blackman & Vigna, “Scrambled linear pseudorandom number generators”, ACM TOMS 47 (2021), and the reference xoshiro256plusplus.c (whose first ten outputs from the state (1, 2, 3, 4), as reproduced in the tests of rand 0.9.4, are pinned below); Steele, Lea & Flood, “Fast splittable pseudorandom number generators”, OOPSLA 2014 (SplitMix64); Marsaglia & Bray, “A convenient method for generating normal variables”, SIAM Review 6 (1964); Muller, Elementary Functions (2016), ch. 6 (argument reduction; the atanh series); Higham, Accuracy and Stability of Numerical Algorithms (2002), ch. 2–3. Cited from memory, except the reference outputs.

Structs§

Rng 🔒
The generator of Algorithm G: xoshiro256++ seeded by SplitMix64.

Enums§

Sketch
Distribution of the test matrix Ω of crate::rsvd() and crate::range_finder (Algorithm G).

Constants§

EXPONENT_MASK 🔒
The exponent field of an f64.
LN2_A 🔒
ln 2 = A + B + C (the split of xingo-extprec, Chapter 11.2; A has 42 significant bits).
LN2_B 🔒
LN2_C 🔒
SPLITMIX_GAMMA 🔒
SplitMix64 increment (the golden ratio, ⌊2⁶⁴/φ⌋ odd).
SPLITMIX_M1 🔒
The two SplitMix64 multipliers.
SPLITMIX_M2 🔒
TWO_54 🔒
2⁵⁴, the pre-scaling of a subnormal high part (step L1).
W_BAR 🔒
w̄ = ((√2 − 1)/(√2 + 1))² = 17 − 12√2 rounded up (checked at 200 bits): the bound on w in step L3.

Functions§

ln 🔒
Algorithm L: ln x for a positive normal finite x (the callers guarantee it; anything else returns an unspecified value, never a panic).
pow2 🔒
2ᵏ for −1022 ≤ k ≤ 1023 (a normal f64, built from its bits).
series_degree 🔒
The number N of step L4 for the scalar T.