B2 Random number generators 607
different random numbers ism−1. It turns out that there exist special combinations
ofaandmallowing form−1 different random numbers to be generated. If the first
number of the sequence reappears, the sequence will repeat itself and the random
character is obviously lost.
To show that the choice ofaandmis indeed a subtle one, considera=12 and
m=143. In that case:
xi+ 1 = 12 ximod 143
xi+ 2 = 122 ximod 143
= 144 ximod 143=xi (B.3)
so the sequence has a length of only 2! It is not too difficult to see that the following
conditions are necessary and sufficient for obtaining a maximum length of the
random number sequence:
- x 0 is relatively prime tom, that is,x 0 andmhave no common factors;
- ais a primitive element modulom, that is, it is the integer with the largestorder
modulo mpossible. The order modulom, denoted byλ, for a numberais the
smallest integer numberλfor which it holds thataλ modm=1.
The maximum length of the random number sequence isλfor the primitive element
a.Ifmis prime, this length is equal tom−1. Form= 2 r, the maximum length
is 2r−^1.
If we userbits to represent the random numbers of our generator, there are in
principle 2rdifferent numbers possible. The choicem= 2 ris a convenient one
since calculations involving computer words are carried out modulo 2rafter cutting
off beyond therleast significant bits. In particular, for 32-bit integers with the first
bit acting as a sign-bit,rcan be chosen as 31. Primitive elements for this value of
mare all integersawitha mod 8=3 or 5. A random generator which has been
used frequently is IBM’sranduwhich usedm= 231 anda=65 539. This turns
out to have poor statistical properties (see below), and moreover it is not really
portable as it depends on the computer’s word length and on a specific handling of
the overflow in integer multiplication. A better choice ism= 231 −1, which is a
prime, leading to a maximal sequence length of 2^31 − 2 ≈ 2 × 109. A primitive
element for thismisa=16 807 [4]. Schrage has given a method for calculating
xi·amodmwithout causing overflow, even ifxi·ais larger than the computer
word size [5, 6]; see also Problem B.1. In fact, 16 807 is not the only primitive
element modulo 2^31 −1: there are more than half a million of them! Extensive
research has been carried out to find the ‘best’ ones among them and those to which
Schrage’s method is applicable [7]. It turns out that 16 807 is not the very best, but
it is not bad at all. Moreover, people feel safe using it, because it has been tested
more extensively than any other multiplier and has not exhibited really dangerous
