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.
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()
| 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.
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.
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.
Pending: bench/practrand.zsh runs RNG_test stdin64 to 2^32 bytes on every generator.
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.
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 |
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.