5.1 Pseudo-random variable generators, cont.

Pseudo-random variable generators, cont.

A shift-register generator

An alternative class of pseudo-numbers generators are shift-register or Tausworthe generators , which have their origins in the work of Golomb (1967) . These algorithms operate on n -bit, pseudo-random binary vectors, just as congruential generators operate on pseudo-random integers. To return a uniform $\left(\mathrm{0,1}\right)$ variate, the binary vector must be converted to an integer and divided by one plus the largest possible number, $2^n$ .

Fibonacci generators

The final major class of generators to be considered are the lagged Fibonacci generators , which take their name from the famous Fibonacci sequence $U_i=U_{i-1}+U_{i-2}$ . This recursion is reminiscent of the congruential generators, which the added feature that the current value depends on the two previous values.

The integer generator based directly on the Fibonacci formula

As examples:

• The $U_i=0$ are real and dot represents either mod 1 addition or subtraction.
• The $U_i=0$ are $\left(n-1\right)$ –bit integers and dot represents either mod $2^n$ addition, subtraction or multiplication.
• The $U_i=0$ are binary vectors and dot represents any of binary addition, binary subtraction, exclusive-or addition, or multiplication.

Other generators that generalize even further on the Fibonacci idea by using a linear combination of previous random integers to generate the current random integer are discussed in Knuth (1981, Chap 3.2.2) .

Combinations of generators (shuffling)

Intuitively, it is tempting to believe that “combining” two sequences of pseudo-random variables will produce one sequence with better uniformity and randomness properties than either of the two originals. In fact, even though good congruential , Tausworthe , and Fibonacci generators exist, combination generators may be better for a number of reasons. The individual generators with short cycle length can be combined intone with a very long cycle. This can be a great advantage, especially on computers with limited mathematical precision. These potential advantages have led to the development of a number of successful combination generators and research into many others.

One of such generator, is a combination of three congruential generators, developed and tested by Wichmann and Hill (1982) .

Another generator, Super-Duper , developed by G.Marsaglia, combines the binary form of the output form the multiplicative congruenatial generator with a multiplier a =69.069 and modulus $m=2^{32}$ with the output of the 32-bit Tausworthe generator using a left-shift of 17 and a right shift of 15. This generator performs well, though not perfectly, and suffers from some practical drawbacks.

A third general variation, a shuffled generator , randomizes the order in which a generator’s variates are output. Specifically, we consider one pseudo-random variate generator that produces the sequence $\left(U_1,U_2\mathrm{,...}\right)$ of uniform (0,1) variates, and a second generator that outputs random integers , say between 1 and 16.

The algorithm for the combined, shuffled generator is as follows:

• Set up a “table” in memory of locations 1 through 16 and store the values $U_1,U_2\mathrm{,...,}{U}_{16}$ sequentially in the table.
• Generate one value, V , between 1 and 16 from the second generator.
• Return the U variate from location V in the table as the desired output pseudo-random variate.
• Generate a new U variate and store it in the location V that was just accessed.
• If more random variates are desired, return to Step 2.

This method of shuffling by randomly accessing and filling a table is due to MacLaren and Marsaglia (1965) . Another scheme, attributed to M.Gentlemanin Andrews et al. (1972) , is to permute the table of 128 random numbers before returning them for use. The use of this type of combination of generators has also been described in the contexts of simulation problems in physics by Binder and Stauffer (1984) .