Skip to content
sysl-langPublic

About

Random number generation for sysl: SplitMix64, xoshiro, PCG64, ChaCha, Philox, Mersenne Twister, and the distributions over them

Resources

Security policy

Stars

0 stars

Watchers

0 watching

Forks

Latest commit

 

History

2 Commits

Folders and files

Repository files navigation

random

Random number generation for sysl: generators you can name and check, and the distributions that are easy to get wrong, written once over all of them.

sh/sysl/random/
    rng.sysl                 the Rng trait: next_u64, and every distribution as a default over it
    splitmix.sysl            SplitMix64
    xoshiro.sysl             xoshiro256++ and xoshiro256**, with jump, long_jump and split
    pcg64.sysl               PCG64 DXSM, NumPy's seeding, advance in O(log n)
    chacha.sysl              ChaCha8/12/20: RFC 8439's block function and cipher, and the generator
    philox.sysl              Philox4x32-7 and -10, counter-based
    mt.sysl                  MT19937 and MT19937-64, for compatibility
    ziggurat.sysl            the 256-layer ziggurat normal and exponential
    ziggurat_tables.sysl     its tables, generated by tools/ziggurat_tables.c
    tests.sysl               every generator against its authors' own output
    distribution_tests.sysl  what the distributions and the stream splitting claim
bench/                       C references and a sysl twin, timed side by side; PractRand driver
findings/                    the compiler findings this package turned up, one reduction each

The module is sh.sysl.random. It depends on nothing outside the standard library, allocates nothing (@no_alloc on every file) and reads no clock or device, so it builds for a freestanding target. Seeding is the caller's.

Using it

dependencies {
  random { git = "github.com/sysl-lang/random", version = "0.1.0" }
}
import sh.sysl.random.{Rng, Xoshiro256pp, ChaCha20}

var g = Xoshiro256pp.seeded(42)

val die = g.below(6) + 1
val x = g.normal()
val wait = g.exponential() * 3.5

var worker = g.split()

The generators

generator state what it is for checked against
SplitMix64 8 B seeding other generators from one word Vigna's splitmix64.c
Xoshiro256pp, Xoshiro256ss 32 B the default: fast, 2^256 − 1 period, jump/long_jump streams xoshiro256plusplus.c, xoshiro256starstar.c, incl. both jumps
Pcg64Dxsm 32 B the other default; 2^127 streams, advance(n) NumPy 2.5 PCG64DXSM: raw state, SeedSequence(42), advance
ChaCha8, ChaCha12, ChaCha20 136 B the cryptographically secure one RFC 8439 §2.3.2 and §2.4.2; Bernstein's chacha-ref.c at 8, 12, 20 rounds
Philox4x32 (Philox[R]) 40 B counter-based: output n is a pure function of (key, n) Random123's kat_vectors, 7 and 10 rounds
Mt19937, Mt19937_64 2.5 KB reproducing streams drawn elsewhere mt19937ar.out, mt19937-64.out.txt, C++ [rand.predef]

Only ChaCha is a source of unpredictability. Every other generator is determined by a state a few outputs reveal. Key ChaCha from an entropy source to draw keys, tokens or nonces.

The Mersenne Twister is here for compatibility and reproducibility with other languages, not as a recommended default. A stream published with its seed, or a fixture made with C++'s std::mt19937, Python's random or NumPy's MT19937, needs this exact generator. Anything new should use xoshiro256++ or PCG64 DXSM. The Twister's 2.5 KB state is a linear recurrence over GF(2), so it fails the linear-complexity and matrix-rank tests (TestU01's LinearComp and MatrixRank) that its successors pass, and it recovers slowly from a state that is mostly zeros.

The distributions

Every generator implements one member, next_u64; everything else is a default of Rng:

member what it gives how
below(n) uniform in [0, n), no modulo bias Lemire's nearly-divisionless method: one 64×64→128 multiply, and a division only on the rare draw that needs it
range(lo, hi) uniform in [lo, hi) over the whole i64 span below on the span at 128 bits
unit(), unit_f32() uniform in [0, 1) the top 53 (24) bits, scaled: every multiple of 2^-53 equally likely
unit_open_low() uniform in (0, 1] for a logarithm
normal(), exponential() standard normal, standard exponential 256-layer ziggurat (Marsaglia–Tsang, in Doornik's form): layer and position from one draw
shuffle(xs), fill(bytes) Fisher–Yates; raw bytes

Streams for threads. Xoshiro256.split() hands out the current stream and jumps by 2^128; Pcg64Dxsm.split(stream) seeds a child on its own increment from two draws; ChaCha.split(stream) and Philox.split(key) change the stream word or the key; Philox.seek(block) jumps anywhere. The tests run four sysl.threads workers on split streams and check each against the same stream drawn on one thread.

How it is tested

sysl test . runs 43 tests. Every generator is pinned to output its authors' code produced, and the vectors were mutated to prove they can fail: in a first pass of 27 single-constant or single-operator mutants, 21 turned a test red, 2 survivors are equivalent (a mask bit a shift has already cleared; % (n | 1) on a value already below n), and 3 exposed gaps the tests then closed (ChaCha's high stream word, the ziggurat's exact bit layout, the sign of the normal tail). The distribution tests use fixed seeds and bands of about five standard errors, so they cannot flake and a real bias lands far outside them. See STATUS.md for what is still to run.

PractRand

Pending: bench/practrand.zsh runs RNG_test stdin64 to 2^32 bytes on every generator.

Speed

bench/run.zsh builds a C reference for every generator and sampler — the authors' own C where it exists (splitmix64.c, xoshiro256*.c, NumPy's pcg64.h, mt19937ar.c, mt19937-64.c, and C++'s std::mt19937/std::mt19937_64 with libc++), Bernstein's chacha-ref.c core and Random123's Philox round otherwise — at clang -O3 -march=native, and times each against the sysl twin built --release -O3 --cpu native, with the same harness on both sides (2^27 outputs, best of 7, the checksums printed so both are seen to compute the same numbers). Run it as one exclusive marshal job.

The timings are deferred: the run is held until sysl 0.13.0 ships, so the machine's queue is not stalled by an exclusive job during the release.

Findings

What writing this package found in sysl 0.12.1. Each has a reduction in findings/.

finding class the shortest input what it cost here
Construction through an alias of a fully applied generic is refused: type G3 = G[3]; G3(5) → cannot infer the type argument 'N'. types.md § Type aliases says a struct is constructed through its alias. bug (0.13.1) findings/alias_construct.sysl the tests construct Xoshiro256[PlusPlus]([..]) instead of Xoshiro256pp([..])
if const M == A over an enum value parameter is refused as not known while compiling. generics.md admits enum variants as value parameters and a value parameter in an if const. bug (0.13.1) findings/if_const_enum.sysl xoshiro's scrambler is a plain if (both arms type-check, and it folds)
Self(...) is a conversion, never a constructor, so a generic struct's members spell their own type with its parameters (ChaCha[ROUNDS](...)). gap (0.14.0) findings/self_construct.sysl longer constructor calls in three types
A const function cannot call real.exp()/ln() (the C library's), so the ziggurat's tables cannot be built while compiling. gap (0.14.0) findings/const_exp.sysl tools/ziggurat_tables.c generates the table file

What is not here, yet

Hardware entropy (RNDR/RDRAND) — this machine's cores (Apple M-series) do not implement FEAT_RNG, and sysl has no sysl.cpu feature query to gate it on — and SFMT, the SIMD-oriented Twister. The distribution families of C++'s <random> beyond the normal and exponential (gamma, Poisson, binomial and the rest) are a later piece of work.

About

Random number generation for sysl: SplitMix64, xoshiro, PCG64, ChaCha, Philox, Mersenne Twister, and the distributions over them

Resources

Security policy

Stars

0 stars

Watchers

0 watching

Forks

Releases

Packages

Contributors

Languages