RANDOM210 signature
The RANDOM210 signature is an interface for a seeded
(deterministic) pseudorandom number generator which is usable in a parallel
context, since seeds may be split to be used in conjunction with
functions from
PRIMITIVES.
It is important to note that every seed must only be “used”
once. We say that a seed which has already been used to generate random
data is no longer “fresh”. We can generate a new fresh seed
from an old one through calls to next or one of the splitting
functions.
type rand
val fromInt : int → rand
val next : rand → rand
val split : rand → rand * (rand * rand)
val split3 : rand → rand * (rand * rand * rand)
val splitTab : rand * int → rand * (int → rand)
val bool : rand → bool
val biasedBool : (int * int) → rand → bool
val int : rand → int
val boundedInt : (int * int) → rand → int
val real : rand → real
val boundedReal : (real * real) → rand → real
val char : rand → char
val boundedChar : (char * char) → rand → chartype randval fromInt :
int → randval next :
rand → randval split :
rand → rand * (rand * rand)(split r) evalutes to $(r', (r_1, r_2))$ where all three of
$r'$, $r_1$, and $r_2$ are fresh seeds. This function should be used in
conjunction with
par, where
$r_1$ and $r_2$ are passed to the two parallel subcomputations, and $r'$
is used in the continuation of the current thread. Failure to use the
seeds in this manner will reduce the quality of the resulting randomness.
val split3 :
rand → rand * (rand * rand * rand)(split3 r) evalutes to $(r', (r_1, r_2, r_3))$ where all four
of $r'$, $r_1$, $r_2$, and $r_3$ are fresh seeds. This function should be
used in conjunction with
par3, where
$r_1$, $r_2$, and $r_3$ are passed to the three parallel subcomputations,
and $r'$ is used in the continuation of the current thread. Failure to use
the seeds in this manner will reduce the quality of the resulting
randomness.
val splitTab :
rand * int → rand * (int → rand)(splitTab (r, n)) evaluates to $(r', f)$, where $r'$ is a
fresh seed, as is $f(i)$ for every $0 \leq i < n$. This function should
be used in conjuction with
parTab,
where $r'$ is used in the continuation of the current thread, and the $n$
seeds yielded by $f$ should be passed to the $n$ parallel subcomputations.
Failure to use the seeds in this manner will reduce the quality of the
resulting randomness.
val bool :
rand → boolval biasedBool :
(int * int) → rand → bool(biasedBool (h, t) r) is a biased random boolean with
probability of true being $\frac h {h + t}$. For example,
(biasedBool (1, 1) r) produces true with
probability $1/2$ and (biasedBool (3, 5) r) produces
true with probability $3/8$.
val int :
rand → intval boundedInt :
(int * int) → rand → int(boundedInt (a, b) r) is a uniformly random integer $x$
bounded by $a \leq x < b$.
val real :
rand → realval boundedReal :
(real * real) → rand → realval char :
rand → charval boundedChar :
(char * char) → rand → char