X-Git-Url: http://repo.macrolet.net/gitweb/?a=blobdiff_plain;f=doc%2Fmanual%2Fbeyond-ansi.texinfo;h=221ebc5e7f57f5dddbc4a049799aa0dcf83cdbe0;hb=746c4003dd76ea67647c87176e4c818f512d59b7;hp=0c72409f084a6518de059a719c2c24b00b91818f;hpb=8a33bf220856487a5cde4b183476b6ab5103983a;p=sbcl.git

diff --git a/doc/manual/beyond-ansi.texinfo b/doc/manual/beyond-ansi.texinfo
index 0c72409..221ebc5 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,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