next up previous
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 $b_{1}, b_{2}, .. b_{n}$ be already given; then

$\displaystyle b_{n+1}$ $\textstyle =$ $\displaystyle b_{k}\,\oplus\,b_{m}\,\oplus\, \dots \, \oplus\,b_{n} \, ,$  

with $k < m < .. < n$, and $\oplus$ ... ``exclusive or'' (XOR)

To find optimal indices $(k,m,\dots,n)$: see the theory of ``primitive polynomials modulo 2''.

``Exhaustive'' property: Starting such a recursion with an arbitrary combination of $n$ bits (except $0 \dots 0$), all possible configurations of $n$ bits will be realized just once before a new cycle begins.



EXAMPLE: $(1,3)$ is one of the optimal combinations. Starting with the sequence $\{b_{1},b_{2},b_{3}\}$ $=\{101\}$ and applying $b_{4}=b_{3}\,\oplus\,b_{1}$ etc., we find the sequence, reading from left to right,

\begin{displaymath}
101 \, 001 \, 110 \, 100 \, 111 \, 010 \, 011 \, 101 \, \dots
\end{displaymath}

It is evident that indeed all possible 3-bit groups (except $000$) occur before the sequence repeats.


A very popular prescription is the ``R250'' algorithm of Kirkpatrick-Stoll, based on $m=103$ and $n=250$:
    $\displaystyle \fbox{$
I_{s}=I_{s-103}\,\oplus\,I_{s-250}
$}$  



\begin{figure}\includegraphics[width=240pt]{figures/F3kst_neu_klein.ps}
\end{figure}

For the first $250$ random integers, use a linear congruential generator.


next up previous
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