Add a section about random number generation to the manual.

Document initial random state consistency, how to achieve or avoid
repeatability of random numbers, extensions with respect to seeding,
generation of random floats, and the currently used PRNG algorithm.

Move the docstring of SEED-RANDOM-STATE over from the "Miscellaneous
Extensions" section.

diff --git a/NEWS b/NEWS
index 58436b2..ba46d35 100644 (file)
--- a/NEWS
+++ b/NEWS
@@ -1,4 +1,8 @@
 ;;;; -*- coding: utf-8; fill-column: 78 -*-
+changes relative to sbcl-1.0.58:
+  * documentation: a section on random number generation has been added to the
+    manual. (lp#656839)
+
 changes in sbcl-1.0.58 relative to sbcl-1.0.57:
   * enhancement: implicit generic function warnings now specify the package
     in which the new generic function is being created.

diff --git a/doc/manual/beyond-ansi.texinfo b/doc/manual/beyond-ansi.texinfo
index 0c72409..221ebc5 100644 (file)
--- 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,81 @@ 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
+
+Some notes on random floats: The standard doesn't prescribe a specific
+method of generating random floats. The following paragraph describes
+SBCL's current implementation and should be taken purely informational,
+that is, user code should not depend on any of its specific properties.
+The method used has been chosen because it is common, conceptually
+simple and fast.
+
+To generate random floats, SBCL evaluates code that has an equivalent
+effect as
+@lisp
+(* limit
+   (float (/ (random (expt 2 23)) (expt 2 23)) 1.0f0))
+@end lisp
+(for single-floats) and correspondingly (with @code{52} and
+@code{1.0d0} instead of @code{23} and @code{1.0f0}) for double-floats.
+Note especially that this means that zero is a possible return value
+occurring with probability @code{(expt 2 -23)} respectively
+@code{(expt 2 -52)}. Also note that there exist twice as many
+equidistant floats between 0 and 1 as are generated. For example, the
+largest number that @code{(random 1.0f0)} ever returns is
+@code{(float (/ (1- (expt 2 23)) (expt 2 23)) 1.0f0)} while
+@code{(float (/ (1- (expt 2 24)) (expt 2 24)) 1.0f0)} is the
+largest single-float less than 1. This is a side effect of the fact
+that the implementation uses the fastest possible conversion from bits
+to floats.
+
+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 +524,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