GFSR pseudorandom number generation using APL

摘要

This paper demonstrates the effectiveness of APL for implementing the generalized feedback shift register (GFSR) approach to producing a random number stream. Various approaches to generating streams of pseudorandom numbers computationally have been devised, dating at least as far back as Norbert Wiener. These are normally discussed in the context of a course in modeling and simulation, since there may be practical implications to consider when building simulation models in APL or any other high level language. This is particularly the case for those circumstances when a (pseudo) random number sequence needs to be repeated, or when multiple streams are needed. In such cases a pseudorandom number generator other than that supplied in the programming language command set needs to be implemented. The linear congruential method for pseudorandom number generation is still commonly used, and is easily implemented in APL or any other high level language; however, it is known to have undesirable n-space uniformity characteristics. Moreover, the period length of its random number stream is limited by the underlying machine's word size. This is a serious issue, since at present day computer speeds, a simulation run could exhaust such a random number stream in a few hours. Very long period (VLP) pseudorandom number generators remedy this deficiency.One class of these, generalized feedback shift register (GFSR) pseudorandom number generators, is based on algebraic manipulation of irreducible trinomials of high order. The manner in which this is accomplished particularly lends itself to elegant APL implementation.