PRNG 2: Generalized Feedback Shift Register

Purpose

Among many kinds of algorithms, linear congruential generator (LCG) is the most common one due to its speed. However, as mentioned in the post about LCG, it is not suitable for Monte-Carlo or any other serious studies using random numbers. Therefore, researchers need to learn other kinds of algorithms.

Generalized feedback shift register (GFSR) has long been a powerful alternative to LCG for its long period and statistical robustness.

 

Concept

Express a positive integer in binary form. Then it will be a string of 1 and 0. Each digit is called bit. (And this is the definition of computer jargon “bit”) Most computing systems are 32-bits as of today, so this post considers it.

Consider an automatic bit-switch; it generates each bit, automatically determining 0 or 1 by referring to earlier bits. And then each positive integer (in decimal form) comes out from this algorithm by joining each 32 bits.

If there is any rules to generate all possible combinations of 32 bits once (in one period), then it will result in positive integers from 0 to once in one period.

GFSR is an algorithm to do this job. Although there is a lot of parameter sets, this post will explain GFSR with the most common parameters sets. List of appropriate parameters is followed.

 

Algorithm

Consider a 32-bits GFSR. First, prepare 17 random integers as inputs (from onwards, let them “seeds”) by any other algorithms. LCG is usually used for seeds generation. These seeds have 32 * 17 = 544 bits.

Now, let’s following bits automatically. Let each bit a, then bit generator is defined as below;

where % is modulus operation.

Now, generate 521 integers in decimal. As we are handling binary bits, we need to generate 32 * 521 = 16672 bits. These 521 integers are our final seeds to generate new random numbers onwards. Let each integer in decimal X, then our final GFSR is defined as below;

where is XOR (exclusively OR) operation, which is one of bit operations prepared in most programming environments, and defined as below;

In other words, when 2 bits have 0 and 1 relatively, then XOR yields 1, otherwise (i.e. if 2 bits are same) 0.

This algorithm has the period of

In this algorithm, 521 is period determinant and 32 is called tap.

 

Advantages and disadvantages

Since most programming environments have bit operations such as XOR as default, GFSR is very fast. Also, it is very simple algorithm; it can be easily built using only Excel worksheet functions. Above all, pseudo-random numbers generated by GFSR satisfy many statistical requirements (which will be explained some other posts). And also, compared to LCG, GFSR generates PRNs of long period. For most social science studies, there is only few demand of more PRNs than 1 period of GFSR.

The only disadvantage of GFSR is, for meteorology, physics, or some other pure sciences, there may be demand for longer period.

 

Note: Brief list of parameters for M-sequence

Choice of appropriate period determinant and taps are very important in GFSR. If these parameters are bad, then the period will become extremely short, and the result PRNs will sometimes fail statistical tests.

Results of GFSR with good parameters are called M-sequence, which stands for “maximum length random sequence”, because M-sequence has the longest possible period under given determinant n.

As mentioned earlier, here is a list of period determinant (denoted as “n”) and taps. (Note number of taps can be more than one) My deep appreciation to the authors of the original technical paper. This list is partial extraction of their wonderful paper.

List of appropriate tap for given period determinant (Source: R. W. Ward and T.C.A. Molteno, “Table of Multiple Feedback Shift Register”, Electronics Technical Report No.2009-1, Otago University, New Zealand)

Note: My apology in advance for any misinterpretation.