Uniform random number generators: a review <s> LINEAR RECURRENCES <s> A necessary and suf- ficient condition is established for the generalized feedback shift regis- ter (GFSR) sequence introduced by Lewis and Payne to be k-distrib- uted. Based upon the theorem, a theoretical test for k-distributivity is proposed and performed in a rea- sonable amount of computer time, even for k = 16 and a high degree of resolution (for which stutistical tests are impossible because of the astronomical amount of computer time required). For the special class of GFSR generators considered by Arvillias and Maritsus based on the primitive trinomial D p + D ~ + 1 with q = an integral power of 2, it is shown that the sequence is k-dis- tributed if and only if the lengths of all subregisters are at least k. The theorem also leads to a simple and efficient method of initializing the GFSR generator so that the se- quence to be generated is ko dis~buted. <s> BIB001 </s> Uniform random number generators: a review <s> LINEAR RECURRENCES <s> Abstract An equivalence relation is shown to hold between two classes of pseudorandom sequences based on the linear recurrences modulo two. A fast initialization method for GFSR sequence is proposed. <s> BIB002 </s> Uniform random number generators: a review <s> LINEAR RECURRENCES <s> Preface 1. Monte Carlo methods and Quasi-Monte Carlo methods 2. Quasi-Monte Carlo methods for numerical integration 3. Low-discrepancy point sets and sequences 4. Nets and (t,s)-sequences 5. Lattice rules for numerical integration 6. Quasi- Monte Carlo methods for optimization 7. Random numbers and pseudorandom numbers 8. Nonlinear congruential pseudorandom numbers 9. Shift-Register pseudorandom numbers 10. Pseudorandom vector generation Appendix A. Finite fields and linear recurring sequences Appendix B. Continued fractions Bibliography Index. <s> BIB003 </s> Uniform random number generators: a review <s> LINEAR RECURRENCES <s> The twisted GFSR generators proposed in a previous article have a defect in k -distribution for k larger than the order of recurrence. In this follow up article, we introduce and analyze a new TGFSR variant having better k -distribution property. We provide an efficient algorithm to obtain the order of equidistribution, together with a tight upper bound on the order. We discuss a method to search for generators attaining this bound, and we list some of these such generators. The upper bound turns out to be (sometimes far) less than the maximum order of equidistribution for a generator of that period length, but far more than that for a GFSR with a working are of the same size. <s> BIB004 </s> Uniform random number generators: a review <s> LINEAR RECURRENCES <s> Introduction.- Estimating Volume and Count.- Generating Samples.- Increasing Efficiency.- Random Tours.- Designing and Analyzing Sample Paths.- Generating Pseudorandom Numbers. <s> BIB005 </s> Uniform random number generators: a review <s> LINEAR RECURRENCES <s> A new algorithm called Mersenne Twister (MT) is proposed for generating uniform pseudorandom numbers. For a particular choice of parameters, the algorithm provides a super astronomical period of 2 19937 −1 and 623-dimensional equidistribution up to 32-bit accuracy, while using a working area of only 624 words. This is a new variant of the previously proposed generators, TGFSR, modified so as to admit a Mersenne-prime period. The characteristic polynomial has many terms. The distribution up to v bits accuracy for 1 ≤ v ≤ 32 is also shown to be good. An algorithm is also given that checks the primitivity of the characteristic polynomial of MT with computational complexity O(p 2 ) where p is the degree of the polynomial. We implemented this generator in portable C-code. It passed several stringent statistical tests, including diehard. Its speed is comparable to other modern generators. Its merits are due to the efficient algorithms that are unique to polynomial calculations over the two-element field. <s> BIB006
A multiple recursive generator (MRG) is defined by the recurrence 2, = (u1xn--1+ * *. + akx,-k) mod m; (1) The modulus m and order k are positive integers, the coefficients ai belong to Z, = (0, 1, . . . , m -l}, and the state at step R. is s, = (xn-k+r, . . . , c,). For prime m and properly chosen ai's, the sequence has (maximal) period length p = mk -1. This can be achieved with only two non-zero ai's  ; L'Ecuyer 1997c), i.e., This slim version makes the implementation faster. The classical linear congruential generator (LCG) corresponds to the case k = 1. Taking m = 2e for e > 1 (a power-of-two modulus) also makes things easier from the implementation viewpoint, but leads to a much shorter period for k > 1 and to several important structural defects (L'Ecuyer 1990; L'Ecuyer 1997c). This should be avoided. One approach for using a power-of-two modulus while keeping a long period and the potential for good properties is the linear recurrence with a carry Uniform Random Number Generators: A Review 129 (Couture and L'Ecuyer 1995;  : where "div" is the integer division, b can be a power of two, and c,, is called the carry at step n. This socalled Multiply-with-Carry (MWC) generator turns out to be approximately equivalent (with a difference of less than l/b on the uLn's) to an LCG with modulus m = Cf==, uebL, where us = -1, and multiplier a equal to the inverse of b modulo m. These MWC generators can thus be analyzed much in the same way as LCGs from the structural viewpoint, and offer a promising avenue for constructing fast and robust generators.  give an indepth theoretical analysis of their properties. In (2), each number is a multiple of l/m. To reduce this discretization error, one may construct each output value from more than one term of the recurrence (1). For example, where s and L 5 k are positive integers. If (1) has period p and gcd(p, s) = 1, then (4) also has period p. The digital expansion (4) permits one to take smaller values of m. An important special case is m = 2. Then, u,, is constructed from L successive bits of the binary sequence (l), with spacings of s -L bits between the blocks. The resulting RNG is called a linearfeedback shift register (LFSR) or Tausworthe generator  BIB003 Tausworthe 1965) . Its implementation is discussed by  BIB005 ), L'Ecuyer (1996b ), and Tezuka (1995 . Another approach is to have L copies of the recurrence (1) running in parallel, with different initial values, and use one copy for each digit of the fractional expansion of u,, . If {xj,n} denotes the jth copy and if zj,n = z,+dj for all j and n, then (GFSR) generator BIB001 BIB002 . Denoting X,, = (Xl,n, . . ' , Xk,n), we have where @ denotes the bitwise exclusive-or, and this provides for an extremely fast implementation of the GFSR. A modification of the GFSR is the laggedAbonacci generator, where @ can be replaced by any arithmetic or logical operation, such as +, -, etc. For example, the additive generator  ): X, = (X,-, + &+k) mod m, (7) where m = 2L, is proposed on many systems, including UNIX. It is a special case of the MRG with a power-of-two modulus. Slight variations of it are the add-with-carry (AWC) and subtract-with-borrow (SWB), proposed by  , which are in fact special cases of the MWC generator with only two nonzero coefficients ej, both equal to fl. The modification permits to increase the period length from 2k+L-1 up to approximately 2kL. However, all these generators have gross structural defects. For example, for the additive one, all triples of the form (u,, u,+k-r, un+k), n 2 0, lie in only two planes in the three-dimensional unit cube, and for the AWC/SWB generators, the same happens with the triples (u,, u,+,, u,+k) (see L'Ecuyer 1997a). Other (better) types of modifications of (6), which maintain the speed but increase the period length from 2" -1 to ZkL -1, are the twisted GFSR proposed by BIB004 and BIB006 . The multiple recursive matrix method of Niederreiter (1995a) provides a general framework that encompasses many of these modifications and variants.