B3 Nonuniform random number generators 609where the numbersciare all equal to 0 or 1. We see that the shift-register generator is
a generalisation of the modulo generator. The maximum cycle length is 2n−1. This
maximum length is obtained for special combinations of the numbersci. Of course,
the algorithm presented can also be used to generate rows of random bits [10].
A simple form of this generator is the one for which only twociare nonzero:
xi(k)=(
xi(−k)q+xi(−k)p)
mod 2. (B.5)The sum combined with the mod 2 condition is precisely theXORoperation which
can be executed very fast in a computer. ‘Magical’(p,q)pairs yielding an optimal
cycle length are:(98, 27),(521, 32)and finally(250, 103), which is frequently used.
Before the generator (B.4) can be started, the firstnrandom numbers have to
be known already. These can be generated with a modulo generator. Since only a
limited number of starting values is needed, correlations between these are not yet
noticeable[11].
B3 Nonuniform random number generators
Random numbers with a nonuniform distribution are usually constructed starting
from a uniform generator. In this section, we show how this can be done. As a first
example we consider a generator with a Gaussian distribution:
P(x)=e−(x−x^0 )(^2) / 2 σ 2
. (B.6)
From the central limit theorem, which states that the sum of many uncorrelated
random numbers is distributed according to a Gaussian with a width proportional
to 1/
√
N, it follows directly that we can obtain a Gaussian distribution just by
addingnuniform random numbers; the highernthe more accurate this distribution
will match the Gaussian form. If we want to have a Gaussian with a widthσand a
centrex ̄, we transform the sumSofnuniform random numbers according to
x= ̄x− 2 σ(S/n− 1 / 2 )√
3 (B.7)
This method for achieving a Gaussian distribution of the random numbers is very
inefficient as we have to generatenuniform random numbers to obtain a single
Gaussian one. We discuss more efficient methods below.
More generally, one can make a nonuniform random number generator using a
real functionf, and for each numberxgenerated by a uniform generator, taking
f(x)as the new nonuniform random number, wherefis a function designed such as
to arrive at the prescribed distributionP. As the number of random numbers lying
betweenxandx+dxis proportional to dxand the same number of nonuniform
random numbersy=f(x)will lie betweenyandy+dywith dy/dx=f′(x), the