From 82c75574e65a1b84b6ad5d67d62bfa9e2690f9b4 Mon Sep 17 00:00:00 2001 From: Lutz Euler Date: Fri, 29 Jun 2012 17:37:45 +0200 Subject: [PATCH] Add a manual section about random number generation. Document initial random state consistency, how to achieve or avoid repeatability of random numbers, extensions with respect to seeding, and the currently used PRNG algorithm. Move the docstring of SEED-RANDOM-STATE over from the "Miscellaneous Extensions" section. --- doc/manual/beyond-ansi.texinfo | 51 +++++++++++++++++++++++++++++++++++++++- 1 files changed, 50 insertions(+), 1 deletions(-) diff --git a/doc/manual/beyond-ansi.texinfo b/doc/manual/beyond-ansi.texinfo index 0c72409..134075f 100644 --- a/doc/manual/beyond-ansi.texinfo +++ b/doc/manual/beyond-ansi.texinfo @@ -15,6 +15,7 @@ it still has quite a few. @xref{Contributed Modules}. * Tools To Help Developers:: * Resolution of Name Conflicts:: * Hash Table Extensions:: +* Random Number Generation:: * Miscellaneous Extensions:: * Stale Extensions:: * Efficiency Hacks:: @@ -441,6 +442,55 @@ arguments to @code{make-hash-table}. @include fun-sb-ext-hash-table-weakness.texinfo +@node Random Number Generation +@comment node-name, next, previous, up +@section Random Number Generation +@cindex Random Number Generation + +The initial value of @code{*random-state*} is the same each time SBCL +is started. This makes it possible for user code to obtain repeatable +pseudo random numbers using only standard-provided functionality. See +@code{seed-random-state} below for an SBCL extension that allows to +seed the random number generator from given data for an additional +possibility to achieve this. Non-repeatable random numbers can always +be obtained using @code{(make-random-state t)}. + +The sequence of numbers produced by repeated calls to @code{random} +starting with the same random state and using the same sequence of +@code{limit} arguments is guaranteed to be reproducible only in the +same version of SBCL on the same platform, using the same code under +the same evaluator mode and compiler optimization qualities. Just two +examples of differences that may occur otherwise: calls to +@code{random} can be compiled differently depending on how much is +known about the @code{limit} argument at compile time, yielding +different results even if called with the same argument at run time, +and the results can differ depending on the machine's word size, for +example for limits that are fixnums under 64-bit word size but bignums +under 32-bit word size. + +@include fun-sb-ext-seed-random-state.texinfo + +SBCL currently uses the Mersenne Twister as its random number +generator, specifically the 32-bit version under both 32- and 64-bit +word size. The seeding algorithm has been improved several times by +the authors of the Mersenne Twister; SBCL uses the third version +(from 2002) which is still the most recent as of June 2012. The +implementation has been tested to provide output identical to the +recommended C implementation. + +While the Mersenne Twister generates random numbers of much better +statistical quality than other widely used generators, it uses only +linear operations modulo 2 and thus fails some statistical +tests@footnote{See chapter 7 "Testing widely used RNGs" in +@cite{TestU01: A C Library for Empirical Testing of Random Number +Generators} by Pierre L'Ecuyer and Richard Simard, ACM Transactions on +Mathematical Software, Vol. 33, article 22, 2007.}. +For example, the distribution of ranks of (sufficiently large) random +binary matrices is much distorted compared to the theoretically +expected one when the matrices are generated by the Mersenne Twister. +Thus, applications that are sensitive to this aspect should use a +different type of generator. + @node Miscellaneous Extensions @comment node-name, next, previous, up @section Miscellaneous Extensions @@ -448,7 +498,6 @@ arguments to @code{make-hash-table}. @include fun-sb-ext-array-storage-vector.texinfo @include fun-sb-ext-delete-directory.texinfo @include fun-sb-ext-get-time-of-day.texinfo -@include fun-sb-ext-seed-random-state.texinfo @include macro-sb-ext-wait-for.texinfo @node Stale Extensions -- 1.7.4.1