Next: 3.2 Other Distributions
Up: 3.1 Equidistribution
Previous: 3.1.1 Linear Congruential Generators
3.1.2 Shift Register Generators
(Also ``Tausworthe'' or ``XOR'' generators)
Originally for the production of random bits, but one may always
generate 16, 32, etc. bits at a time and combine them to a computer word.
Let bits
be already given; then
with
, and
... ``exclusive or'' (XOR)
To find optimal indices : see the theory of
``primitive polynomials modulo 2''.
``Exhaustive'' property: Starting such a recursion with an arbitrary
combination of bits (except ),
all possible configurations of bits will be realized just
once before a new cycle begins.
EXAMPLE:
is one of the optimal combinations.
Starting with the sequence
and applying
etc.,
we find
the sequence, reading from left to right,
It is evident that indeed all possible 3-bit groups (except
) occur before the sequence repeats.
A very popular prescription is
the ``R250'' algorithm of Kirkpatrick-Stoll,
based on and :
For the first random integers, use a linear congruential generator.
Next: 3.2 Other Distributions
Up: 3.1 Equidistribution
Previous: 3.1.1 Linear Congruential Generators
Franz J. Vesely Oct 2005
See also: "Computational Physics - An Introduction," Kluwer-Plenum 2001