The Random structure

The Random structure implements a random number generator using a subtract-with-borrow (SWB) generator as described in Marsaglia and Zaman, "https://doi.org/10.1214/aoap/1177005878[A New Class of Random Number Generators]," Annuals of Applied Probability 1(3), 1991, pp. 462-480.

The SWB generator is a 31-bit generator with lags 48 and 8. It has period (21487 - 2247) / 105 or about 10445. In general, these generators are excellent. They act locally like a lagged Fibonacci generator. however, and thus have troubles with the birthday test. Thus, we combine this SWB generator with the linear congruential generator (48271 \* a) mod (231 - 1).

Although the interface is fairly abstract, the implementation uses 31-bit ML words. At some point, it might be good to use 32-bit words.

Synopsis

structure Random

Interface

type rand

val rand : (int * int) -> rand

val toString : rand -> string
val fromString : string -> rand

val randInt : rand -> int

val randNat : rand -> int

val randReal : rand -> real

val randRange : (int * int) -> rand -> int

Description

type rand

Represents the internal state of a random number generator.

val rand : (int * int) -> rand

rand (n1, n2) creates a random number generator from the initial seed specified by the pair (n1, n2).

val toString : rand -> string

toString rand returns a string representing the random-number-generator state rand. This string is not meant to be human readable and will likely contain non-printable characters.

val fromString : string -> rand

fromString s returns the random-number-generator encoded as the string s (presumably generated by toString). This expression will raise Fail exception if the string s does not have the proper form.

val randInt : rand -> int

randInt rand generates a random integer with a uniform distribution in the range [minInt .. maxInt].

Warning
The range of values is for 32-bit machines.
val randNat : rand -> int

randInt rand generates a random integer with a uniform distribution in the range [0 .. maxInt].

Warning
The range of values is for 32-bit machines.
val randReal : rand -> real

randReal rand generates a random real number in the range [0..1).

val randRange : (int * int) -> rand -> int

randRange (lo, hi) rand generates a random number in the [lo..hi]. This function will raise the Fail exception if hi < lo.

Bugs

The toString/fromString functions should be replaced with functions that encode the state as a Word8Vector.vector.

This implementation needs to be updated for 64-bit systems.