random state

1.0.1

Portable random number generation.

About random-state

This is a collection of pseudo random number generators (PRNGs) and quasi-random number generators (QRNGs). While Common Lisp does provide a RANDOM function, it does not allow the user to pass an explicit seed, nor to portably exchange the random state between implementations. This can be a headache in cases like games, where a controlled seeding process is very useful.

How To

For both curiosity and convenience, this library offers multiple algorithms to generate random numbers, as well as a bunch of generally useful methods to produce desired ranges.

(loop with generator = (random-state:make-generator :mersenne-twister-32 123)
      repeat 10
      collect (random-state:random-int generator 0 10))
; => (8 10 9 5 3 10 9 2 9 2)

Several methods to compute random numbers in certain ranges are provided in advance: random-byte, random-bytes, random-sequence, random-unit, random-float, and random-int. Each of those can also be used with just the name of the generator you'd like to use as the first argument, in which case a global instance will be used.

For generators that are hash-based, such as squirrel, additional noise functions are provided: random-1d, random-2d, and random-3d, and some functions to manipulate the stepping of the generator: index, and rewind.

Implementations

The following algorithms are currently implemented:

Adler
Cityhash
Generic QRNG
Hammersley
KISS
Linear Congruence
Mersenne Twister
Middle Square
Murmurhash
PCG
RC4
Sobol
Squirrelhash
TT800
XKCD
Xorshift / Yorshift RNGs

The protocol also implements a fallback to the implementation's own random-state.

System Information

Version: 1.0.1

Dependencies:

documentation-utils

Author: Yukari Hafner

License: zlib

Homepage: https://Shinmera.github.io/random-state/

Bug Tracker: https://github.com/Shinmera/random-state/issues

Sources: https://github.com/Shinmera/random-state.git

Definition Index

RANDOM-STATE

ORG.SHIRAKUMO.RANDOM-STATE

No documentation provided.

EXTERNAL SPECIAL-VARIABLE

GENERATOR

The default random number generator used by RANDOM.

See RANDOM

EXTERNAL STRUCTURE

ADLER32

An RNG based on the Adler32 hash.

See https://en.wikipedia.org/wiki/Adler-32

EXTERNAL STRUCTURE

CITYHASH-64

An RNG based on the 64-bit CityHash.

See https://github.com/google/cityhash

EXTERNAL STRUCTURE

GENERATOR

General class for any random number generator.

See LIST-GENERATOR-TYPES
See SEED
See RESEED
See NEXT-BYTE
See BITS-PER-BYTE
See COPY
See MULTIVARIATE-P
See MAKE-GENERATOR
See STATEFUL-GENERATOR
See HASH-GENERATOR

EXTERNAL STRUCTURE

HAMMERSLEY

The Hammersley quasi-random number sequence.

This is a multivariate generator with default dimensionality of 3.
To change the dimensionality, pass a :LEAP initarg that is an array of
the desired dimensionality. Each element in the LEAP array should be
an integer greater or equal to 1, and can be used to advance the
sequence more quickly for each dimension.

See https://en.wikipedia.org/wiki/Low-discrepancy_sequence

EXTERNAL STRUCTURE

HASH-GENERATOR

Superclass for all generators that rely on a hashing function to generate numbers.

These generators are special in that numbers for any index can be
generated, so they can be rewound or arbitrarily stepped in their
sequence.

See GENERATOR
See INDEX
See REWIND

EXTERNAL STRUCTURE

KISS11

An implementation of the Kiss11 RNG.

See https://eprint.iacr.org/2011/007.pdf

EXTERNAL STRUCTURE

LINEAR-CONGRUENCE

A very simple random number generator based on linear congruence.

See https://en.wikipedia.org/wiki/Linear_congruential_generator

EXTERNAL STRUCTURE

MERSENNE-TWISTER-32

The de-facto standard random number generator algorithm.

See https://en.wikipedia.org/wiki/Mersenne_Twister
See http://www.acclab.helsinki.fi/~knordlun/mc/mt19937.c

EXTERNAL STRUCTURE

MERSENNE-TWISTER-64

A 64 bit variant of the Mersenne Twister algorithm.

See MERSENNE-TWISTER-32
See http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/VERSIONS/C-LANG/mt19937-64.c

EXTERNAL STRUCTURE

MIDDLE-SQUARE

An incredibly primitive, and basically in practise useless, random number algorithm.

See https://en.wikipedia.org/wiki/Middle-square_method

EXTERNAL STRUCTURE

MURMURHASH3

A hash-based RNG using the Murmurhash3 method.

See https://en.wikipedia.org/wiki/MurmurHash

EXTERNAL STRUCTURE

PCG

An adaptation of the PCG rng.

See http://www.pcg-random.org

EXTERNAL STRUCTURE

QUASI

A quasi-random number generator based on a uniform RNG.

When constructing the generator you may pass the :SOURCE initarg,
which should be a GENERATOR instance to use as a source of
randomness. By default the current value of *GENERATOR* is used.

See https://en.wikipedia.org/wiki/Low-discrepancy_sequence

EXTERNAL STRUCTURE

RC4

The RC4 cryptographic random number generator.

See https://en.wikipedia.org/wiki/RC4

EXTERNAL STRUCTURE

SOBOL

The Sobol quasi-random number sequence.

This is a multivariate generator with default dimensionality of 3.
You can pass the :DIM initarg to specify the dimensionality of the
result. :DIM must be in [ 1, 1111 [

See https://en.wikipedia.org/wiki/Low-discrepancy_sequence

EXTERNAL STRUCTURE

SQUIRREL

An adaptation of the "squirrel hash v3".

See https://www.youtube.com/watch?v=LWFzPP8ZbdU

EXTERNAL STRUCTURE

STATEFUL-GENERATOR

Superclass for all generators that rely on state to produce random numbers.

See GENERATOR

EXTERNAL STRUCTURE

TT800

The predecessor to the Mersenne Twister algorithm.

See http://random.mat.sbg.ac.at/publics/ftp/pub/data/tt800.c

EXTERNAL STRUCTURE

XKCD

XKCD-221 random number generator

See https://xkcd.com/221/

EXTERNAL STRUCTURE

XORSHIFT-1024*

Sixteen 64-bit word state variation of XORSHIFT-64*.

See XORSHIFT-64*

EXTERNAL STRUCTURE

XORSHIFT-128

The four times 32-bit word state variant of the Xorshift algorithm.

See XORSHIFT-32

EXTERNAL STRUCTURE

XORSHIFT-128+

Non-linear double 64-bit state variant of XORSHIFT-64 that's currently the standard on modern browsers' JavaScript engines.

See XORSHIFT-64
See https://en.wikipedia.org/wiki/Xorshift#xorshift+
See https://v8.dev/blog/math-random

EXTERNAL STRUCTURE

XORSHIFT-32

Linear 32-bit word state shift-register generator.

See https://en.wikipedia.org/wiki/Xorshift
See https://www.jstatsoft.org/article/view/v008i14

EXTERNAL STRUCTURE

XORSHIFT-64

The 64-bit variant of the Xorshift algorithm..

See XORSHIFT-32

EXTERNAL STRUCTURE

XORSHIFT-64*

Non-linear variation of XORSHIFT-64 by adding a modulo multiplier.

See XORSHIFT-64
See https://en.wikipedia.org/wiki/Xorshift#xorshift*

EXTERNAL STRUCTURE

XORWOW

Non-linear five times 32-bit word state shift-register generator.

See XORSHIFT-128
See https://en.wikipedia.org/wiki/Xorshift#xorwow

EXTERNAL STRUCTURE

XOSHIRO-128**

32-bit variant of XOSHIRO-256**.

See XOSHIRO-256**
See https://prng.di.unimi.it/xoshiro128starstar.c

EXTERNAL STRUCTURE

XOSHIRO-128+

32-bit variant of XOSHIRO-256+.

See XOSHIRO-256+
See https://prng.di.unimi.it/xoshiro128plus.c

EXTERNAL STRUCTURE

XOSHIRO-256**

Non-linear rotating general-purpose 64-bit number algorithm.

See https://prng.di.unimi.it/
See https://prng.di.unimi.it/xoshiro256starstar.c
See https://en.wikipedia.org/wiki/Xorshift#xoshiro

EXTERNAL STRUCTURE

XOSHIRO-256+

Slightly faster variant of XOSHIRO-256++ meant solely for generating 64-bit floating-point numbers by extracting the upper 53-bits due to the linearity of the lower bits.

See XOSHIRO-256++
See https://prng.di.unimi.it/xoshiro256plus.c

EXTERNAL FUNCTION

BENCHMARK

RNG
&KEY
SAMPLES
STREAM

Draw a number of samples from an NRG and determine how quickly it operates.

Prints the duration, # samples, samples/s, and s/sample to STREAM.
Returns samples/s.

See BENCHMARK-ALL

EXTERNAL FUNCTION

BENCHMARK-ALL

&KEY
SAMPLES
STREAM

Run a benchmark for all known generator types.

When completed, orders the the results from fastest to slowest and
prints them to STREAM. If a generator fails to be benchmarked, its
result is shown as -1.

See BENCHMARK

EXTERNAL FUNCTION

DRAW

N
&OPTIONAL
GENERATOR

Returns a vector with N random samples in [0,1[.

See ENSURE-GENERATOR
See RANDOM-UNIT

EXTERNAL FUNCTION

ENSURE-GENERATOR

GENERATOR-ISH

Ensures the argument is an object usable for random number generation.

See GLOBAL-GENERATOR
See GENERATOR

EXTERNAL FUNCTION

GLOBAL-GENERATOR

NAME

Returns a global instance of a generator.

You may also SETF this place to name specific generators of your own.

See MAKE-GENERATOR

EXTERNAL FUNCTION
(SETF GLOBAL-GENERATOR)
- VALUE
- NAME
Source
No documentation provided.

EXTERNAL FUNCTION

HISTOGRAM

RNG
BINS
&KEY
SAMPLES
WIDTH
STREAM

Compute a histogram from the given sample vector.

This will collect the samples into N bins, where the value of the bin
is the contribution of the samples in the bin towards all samples.

See PRINT-HISTOGRAM
See DRAW

EXTERNAL FUNCTION

HOPEFULLY-SUFFICIENTLY-RANDOM-SEED

Attempts to find a sufficiently random seed.

On Unix, this reads 64 bits from /dev/urandom
On Windows+SBCL, this reads 64 bits from SB-WIN32:CRYPT-GEN-RANDOM
Otherwise it uses an XOR of GET-INTERNAL-REAL-TIME and GET-UNIVERSAL-TIME.

EXTERNAL FUNCTION

INDEX

INSTANCE

Accesses the index of the hash-generator.

The index must be an (unsigned-byte 64).
The index is advanced for each call to NEXT-BYTE.

See HASH-GENERATOR

EXTERNAL FUNCTION
(SETF INDEX)
- VALUE
- INSTANCE
Source
No documentation provided.

EXTERNAL FUNCTION

LIST-GENERATOR-TYPES

Lists the types of generators supported by the library.

You may use any of these types to call MAKE-GENERATOR with.

See MAKE-GENERATOR

EXTERNAL FUNCTION

MAKE-GENERATOR

TYPE
&OPTIONAL
SEED
&REST
INITARGS

Creates a new generator of the given type.

You may pass an optional seed to initialise the generator with. If no
seed is specified, each constructed generator of the same type will
return the same sequence of numbers.

See RESEED
See GENERATOR

EXTERNAL FUNCTION

MULTIVARIATE-P

GENERATOR

Returns true if the generator is multivariate and returns an array of bytes on NEXT-BYTE.

See NEXT-BYTE
See GENERATOR

EXTERNAL FUNCTION

PRINT-HISTOGRAM

HISTOGRAM
&KEY
STREAM
WIDTH

Display the histogram vector in a user-friendly manner.

Prints a visual representation of the deviation of each bin from the
ideal uniform distribution as well as the cumulative deviation of all
bins.

See HISTOGRAM

EXTERNAL FUNCTION

RANDOM

MAX
&OPTIONAL
GENERATOR

Returns a number in [0, MAX[.

This is a drop-in replacement for CL:RANDOM.
The returned type is the same as MAX, where MAX must be an INTEGER or
a FLOAT greater than zero. The returned number must be smaller than MAX.

GENERATOR may be anything accepted by ENSURE-GENERATOR.

See RANDOM-INT
See RANDOM-FLOAT
See ENSURE-GENERATOR

EXTERNAL FUNCTION

RANDOM-1D

GENERATOR
INDEX
&OPTIONAL
SEED

Returns a byte for the given index and seed.

This is only usable with HASH-GENERATOR types.
Does *NOT* advance the generator's index.

See HASH-GENERATOR
See NEXT-BYTE

EXTERNAL FUNCTION

RANDOM-2D

GENERATOR
X
Y
&OPTIONAL
SEED

Returns a byte for the given location and seed.

This is only usable with HASH-GENERATOR types.
Does *NOT* advance the generator's index.

See HASH-GENERATOR
See NEXT-BYTE

EXTERNAL FUNCTION

RANDOM-3D

GENERATOR
X
Y
Z
&OPTIONAL
SEED

Returns a byte for the given location and seed.

This is only usable with HASH-GENERATOR types.
Does *NOT* advance the generator's index.

See HASH-GENERATOR
See NEXT-BYTE

EXTERNAL FUNCTION

RANDOM-BYTE

GENERATOR

Alias for NEXT-BYTE.

See GENERATOR
See NEXT-BYTE

EXTERNAL FUNCTION

RANDOM-BYTES

GENERATOR
BITS

Returns an (UNSIGNED-BYTE BITS) sized random number.

May advance the generator more than once.

See GENERATOR
See NEXT-BYTE

EXTERNAL FUNCTION

RANDOM-FLOAT

GENERATOR
FROM
TO

Returns a random float in [FROM, TO].

The returned float is of the same type as whatever type is larger
between FROM and TO.

See GENERATOR
See RANDOM-UNIT

EXTERNAL FUNCTION

RANDOM-INT

GENERATOR
FROM
TO

Returns a random integer in [FROM, TO].

See GENERATOR
See RANDOM-BYTES

EXTERNAL FUNCTION

RANDOM-SEQUENCE

GENERATOR
SEQUENCE
&KEY
START
END

Fills SEQUENCE between START and END with random numbers.

Note: it is up to you to ensure that SEQUENCE is capable of holding
numbers returned by the generator's NEXT-BYTE, and that doing so makes
sense. As in, do not fill a vector with element-type (unsigned-byte 8)
with a generator whose BITS-PER-BYTE is 32 or vice-versa.

Equivalent to:

  (map-into sequence (lambda () (next-byte generator)))

See GENERATOR
See NEXT-BYTE

EXTERNAL FUNCTION

RANDOM-UNIT

GENERATOR
&OPTIONAL
TYPE

Returns a random float in [0, 1].

The returned float is of the type specified in TYPE.

See GENERATOR
See RANDOM-BYTES

EXTERNAL GENERIC-FUNCTION

BITS-PER-BYTE

GENERATOR

Returns the number of bits of randomness returned by the generator for each NEXT-BYTE call.

This may either be an integer, describing the bits of randomness returned,
the symbol SINGLE-FLOAT or DOUBLE-FLOAT in which case NEXT-BYTE returns a unit float,
or a list composed of the aforementioned, in which case NEXT-BYTE returns an array
of such bytes.

See NEXT-BYTE
See GENERATOR

EXTERNAL GENERIC-FUNCTION

COPY

GENERATOR

Creates a fresh copy of the given generator.

This copy will return an identical sequence of bytes as the
original. Meaning, the following invariant holds true:

  (loop with copy = (copy generator) always (= (next-byte generator) (next-byte copy)))

See GENERATOR

EXTERNAL GENERIC-FUNCTION

NEXT-BYTE

GENERATOR

Returns the next byte (not octet) of random state.

The value returned is in accordance to the spec of BITS-PER-BYTE.
If the spec is an integer, the returned integer must be in the range
of

  [ 0, 1 << BITS-PER-BYTE GENERATOR [

If the spec is SINGLE-FLOAT or DOUBLE-FLOAT, the returned float must
be in the range of

  [ 0, 1 [

If the spec is a list, the returned value is an array with each of its
elements according to the above description.

See RANDOM-INT
See RANDOM-BYTES
See GENERATOR

EXTERNAL GENERIC-FUNCTION

RESEED

GENERATOR
NEW-SEED

Reset the RNG and seed it with the given seed number.

If T is passed for the new seed, a random seed as determined by
HOPEFULLY-SUFFICIENTLY-RANDOM-SEED is used.

See HOPEFULLY-SUFFICIENTLY-RANDOM-SEED
See GENERATOR

EXTERNAL GENERIC-FUNCTION

REWIND

HASH-GENERATOR
&OPTIONAL
BY

Rewind the hash-generator by BY numbers.

The following invariant holds for any N:

  (= (next-byte generator) (progn (rewind generator N) (loop repeat (1- N) (next-byte generator)) (next-byte generator)))

See HASH-GENERATOR

EXTERNAL GENERIC-FUNCTION

SEED

GENERATOR

Returns the seed that was used to initialise the generator.

See GENERATOR

EXTERNAL MACRO

DEFINE-GENERATOR

NAME
BITS-PER-BYTE
SUPER
SLOTS
&BODY
BODIES

Define a new random number generator type.

BITS-PER-BYTE is a form that should evaluate to the byte spec for the
generator.

SUPER should be a list of the following structure:

  SUPER     ::= (type SLOT*)
  SLOT      ::= (slot-name initform)
  type      --- The structure-type name to use as supertype
  slot-name --- The name of a slot in the supertype
  initform  --- The initial value for the slot

SLOTS should be a list of additional structure slot specs to hold the
generator's state.

BODIES should be any number of body expressions, each of which is a
list composed of a body type and any number of body forms, each of
which are evaluated in an environment where every specified slot in
SLOTS as well as every specified supertype slot in SUPER is
symbol-macrolet-bound to their respective name. The following body
types are permitted:

  :COPY   --- Provides the body forms for the COPY function. The
              generator instance is bound to GENERATOR. If this body
              expression is not provided, a copy function based on the
              SLOTS is automatically provided for you.
              This must be provided for HASH-GENERATORs.
  :RESEED --- Provides the body forms for the RESEED function. The
              generator instance is bound to GENERATOR and the seed to
              SEED.
              This must be provided for STATEFUL-GENERATORs.
  :NEXT   --- Provides the body forms for the NEXT-BYTE function. The
              generator instance is bound to GENERATOR. Must return a
              suitable byte for the generator.
              This must be provided for STATEFUL-GENERATORs.
  :HASH   --- Provides the stateless hashing function. The generator
              instance is notably NOT bound. However, the 64-bit index
              to hash is bound to INDEX. This will also automatically
              provide the NEXT-BYTE function for you.
              This must be provided for HASH-GENERATORs.

Each of the additional bindings in the body expressions is bound to a
symbol from the current package.

See BITS-PER-BYTE
See RESEED
See NEXT-BYTE
See HASH
See COPY
See HASH-GENERATOR
See STATEFUL-GENERATOR
See GENERATOR

EXTERNAL SOURCE-TRANSFORM
INDEX
No documentation provided.
EXTERNAL SOURCE-TRANSFORM
(SETF INDEX)
No documentation provided.