Random Numbers
Before carrying on with the discussion of testing random number generators we like to introduce another type of generator used very frequently in simulations. The lagged Fibonacci generator, symbolically denoted by LF(p,q,Ä ) with p>q, is based on a Fibonacci sequence of numbers with respect to an operation which we have given the generic symbol Ä . Let S be the model set for the operation Ä , for example the positive real numbers, the positive integers, or the set S = {0,1}. The binary operation Ä computes a new number from previously generated numbers with a lag p

To start the generator we need p numbers. These can be generated using for example a modulo generator. The advantage of the lagged Fibonacci generator, apart from removing some of the deficiencies that are build into the modulo type generators, is that one can operate on the level of numbers or on the level of bits. For example, we can construct a generalized shift-register generator GFSR(p,q,Ä ), where the operation Ä is interpreted as the exclusive or, which acts on every of the 32 bits in a computer word. This generator is also known under the name of R250. The generator R250 is the generator used in many of the simulation programs accompanying this book.

A further advantage over the modulo generator is that the period can be made quite large even though the machine precision may be low.

 

Program Fibonacci Generator

We show here only the innermost loop generating, assuming real numbers in the interval [0,1] stored in the array mf, new numbers using the operation +. This + operation is closed on the real interval (0,1). The result is put into the array x. After computing a new random number the indices p and q are cyclically incremented.

for(i=0; i< max_sweeps; i++) {

   mf[p] = mf[p] + mf[q];

   if ( mf[p] > 1 ) mf[p] -= 1;

   x[i] = mf[p];

   if ( ++p == lagP-1 ) p = 0;

   if ( ++q == lagP-1 ) q = 0;

}

 

In the following we have listed some lagged Fibonacci generators that the reader may try to program or use the program supplied with this text and modify it at the appropriate places.

 

Some Recursion Relation and their Periods

Recusion Relation

Period

xi = xi-17 - xi-5 mod 2n

(217 - 1)2(n-1)

xi = xi-31 - xi-13 mod 2n

(217 - 1)2(n-1)

xi = xi-55 - xi-24 mod 2n

224(297 - 1) with a 24-Bit Mantissa
previous page next page