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
Ωofcrate::rsvd()andcrate::range_finder(Algorithm G).
Constants§
- EXPONENT_
MASK 🔒 - The exponent field of an
f64. - LN2_A 🔒
ln 2 = A + B + C(the split ofxingo-extprec, Chapter 11.2;Ahas 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√2rounded up (checked at 200 bits): the bound onwin step L3.
Functions§
- ln 🔒
- Algorithm L:
ln xfor a positive normal finitex(the callers guarantee it; anything else returns an unspecified value, never a panic). - pow2 🔒
2ᵏfor−1022 ≤ k ≤ 1023(a normalf64, built from its bits).- series_
degree 🔒 - The number
Nof step L4 for the scalarT.