homediscover ncsapartnershipsoutreachsoftware_tech
next up previous
Next: Lagged-Fibonacci Generators Up: Methods for Random Number Previous: Prime Modulus

Shift-Register Generators


Shift Register Generators (SRGs) [21, 22] are of the form:
where the tex2html_wrap_inline1521's and the tex2html_wrap_inline1523's are either 0 or 1. The maximal period of tex2html_wrap_inline1525 and can be achieved using as few as two non-zero values of tex2html_wrap_inline1523. This leads to a very fast random number generator.

There are two ways to make pseudorandom integers out of the bits produced by Eq. (gif). The first, called the digital multi-step method, takes n successive bits from Eq. (gif) to form an integer of n-bits. Then n more bits are generated to create the next integer, and so on. The second method, called the generalized feedback shift-register, creates a new n-bit pseudorandom integer for every iteration of Eq. (gif). This is done by constructing the n-bit word from the last bit generated, tex2html_wrap_inline1539, and n-1 other bits from the k bits of SRG state. Thus a random number is generated for each new bit generated. While these two methods seem different, they are very related, and theoretical results for one always hold for the other. Serious correlations can result if k is small. Reader's interested in more general information on SRGs should consult the references: [23, 21, 22].

The shift register sequences can be parameterized through the choice of tex2html_wrap_inline1523. One can systematically assign the values of tex2html_wrap_inline1523 to the processors to produce distinct maximal period shift register sequences [24]. This scheme can be justified based on exponential sum bounds, as in the case of the prime modulus LCG. This similarity is no accident, and is based on the fact that both generators are maximal period linear recursions over a finite field [25].

The National Center for Supercomputing Applications

University of Illinois at Urbana-Champaign


Last modified: September 16, 1997