Previous Table of Contents Next


26.4 EXTENDED FIBONACCI GENERATORS

A Fibonacci sequence {xn} is generated by the following relationship:

xn = xn-1 + xn-2

The generation of random numbers can be attempted by using the following modification to the Fibonnaci sequence:

xn = xn-1 + xn-2 mod m

However, this sequence does not have good randomness properties. In particular, it has a high serial correlation. An extension of this approach would be to combine, for instance, the fifth and seventeenth most recent values:

xn = xn-5 + xn-17 mod 2k

Marsaglia (1983) points out that this generator passes most statistical tests and recommends its implementation as follows using 17 storage locations L[1]...., L[17]. During initialization, fill these locations with 17 integers, not all even, and set two pointers i and j to 17 and 5, respectively. On each successive call, the following procedure is executed, which returns the next random number and updates the pointers:

x:= L[i] + L[j];
L[i]:= x;
i:= i-1; IF i = 0 THEN i:= 17;
j:= j - 1; IF j = 0 THEN j:= 17
Return x;

The add operation in the first line of this generator is automatically mod 2k in k-bit machines with 2’s complement arithmetic. The period of the generator is 2k(217 - 1). For k, = 8 16, 32, this period is 1.6 x 107, 4.3 x 109, and 2.8 x 1014, respectively. This is considerably longer than that possible with LCGs.

26.5 COMBINED GENERATORS

It is possible to combine two or more random generators to produce a “better” generator. Three such techniques are described next:

1.  Adding random numbers obtained by two or more generators. If xn and yn are two random-number sequences in the range 0 and m - 1, they can be combined to produce wn = (xn + yn). If the two sequences have different periods and are obtained by different algorithms, this may considerably increase the period and randomness. For example, L’Ecuyer (1988) recommends combining the following two generators:

xn = 40014xn-1 mod 2,147,483,563

yn = 40692yn-1 mod 2,147,483,399


This would produce

wn = (xn - yn) mod 2,147,483,562

This generator has a period of 2.3 × 1018. Also, it does not have the problem of all points in the k-dimension falling on a small number of hyperplanes. For 16-bit computers, L’Ecuyer suggests combining the following three generators:

wn = 157wn-1 mod 32,363

xn = 146xn-1 mod 31,727

yn = 142yn-1 mod 31,657

This would produce

vn = (wn - xn + yn) mod 32,363


This generator has a period of 8.1 × 1012. Portable implementations of these combined generators can be found in L’Ecuyer (1988).
2.  Exclusive-or random numbers obtained by two or more generators. This technique is similar to the previous one except that the arithmetic addition is replaced by bit-wise exclusive-or operation. Santha and Vazirani (1984) showed that the exclusive-or of several slightly random generators, each producing n-bit numbers, can be used to generate a more random sequence.
3.  Shuffle. This technique, known as shuffling, uses one sequence as an index to decide which of several numbers generated by a second sequence should be returned. Many different shuffling procedures have been suggested in the literature. One popular technique, which is credited to Marsaglia and Bray (1964), is known as algorithm M. Here, an array of size 100, for instance, is filled with random numbers from a random sequence xn. To generate a random number, generate a new Yn (between 0 and m -1) and scale it to obtain an index i = 1 + 100yn/m. The value in the ith element of the array is returned as the next random number. A new value of xn is generated and stored in the it hlocation. This generator is claimed to have better k-distributivity properties than the generators based on LFSRs.
One problem with shuffling is that it is not easy to skip a long subsequence as is usually required in multiple-stream simulations.

26.6 A SURVEY OF RANDOM-NUMBER GENERATORS

In this section, we describe a number of generators that have either been proposed in published literature or have been used in various simulation packages. In some cases, known problems and properties are also discussed. The list follows:

  A currently popular multiplicative LCG is

xn = 75 xn-1 mod(231 - 1)

  This generator is used in the SIMPL/I system (IBM 1972), the APL system from IBM (Katzan 1971), the PRIMOS operating system from Prime Computer (1984), and the scientific library from IMSL (1987). Since 231 - 1 is a prime number and 75 is a primitive root of it, this generator has the full period of 231 - 2. This generator has been extensively analyzed and shown to be good. Its low-order bits are uniformly distributed. It has reasonable randomness properties. This generator was highly recommended by Park and Miller (1988), and they called it the minimal standard. Pascal programs to implement this generator were presented earlier in Figures 26.2 and 26.3.
  Fishman and Moore (1986) conducted an exhaustive search of all full-period, multiplicative LCGs with modulus m = 231 - 1 and compared them on the basis of implementation efficiency and randomness. Their conclusion was that the following two generators were the best:

xn = 48,271xn-1 mod(231 - 1)

xn = 69,621xn-1 mod(231 - 1)

  The following generator is used in SIMSCRIPT II.5 and in DEC-20 FORTRAN:

xn = 630,360,016xn-1 mod(231 - 1)

  The following multiplicative LCG, known as “RANDU” (IBM 1968), was very popular in the 1960s:

xn = (216 + 3)xn-1 mod 231

  The modulus and the multiplier were selected primarily to facilitate easy computation. Multiplication by 216 + 3 = 65,539 can be easily accomplished by a few shift and add instructions. This generator does not have a full period and has been shown to be flawed in many respects. Also, it does not have good randomness properties (Knuth, 1981). When the triplets of successive numbers generated by RANDU are plotted as points in a three-dimensional space, all the points lie on a total of 15 planes in the space. In other words, it has unsatisfactory three-distributivity (see Section 27.5 for k-distributivity). Also, like all LCGs with m = 2k, the lower order bits of this generator have a small period, which is discussed later in Section 26.8. RANDU is no longer used.
  The following analog of RANDU is sometimes recommended for 16-bit microprocessors:

xn = (28 + 3)xn-1 mod(215)


Previous Table of Contents Next

Copyright © John Wiley & Sons, Inc.