Some linear and nonlinear methods for pseudorandom number generation

ABSTRACT

Two principal classes of methods for the generation of uniform pseudorandom numbers can nowadays be distinguished, namely linear and nonlinear methods, and contributions to both types of methods are presented. A very general linear method, the multiple-recursive matrix method, was recently introduced and analyzed by the author. This method includes as special cases several classical methods, and also the twisted GFSR method. New theoretical results on the multiple-recursive matrix method are discussed. Among nonlinear methods, the digital inversive method recently introduced by Eichenauer-Herrmann and the author is highlighted. This method combines real and finite-field arithmetic and, in contrast to other inversive methods, allows a very fast implementation, while still retaining the advantages of inversive methods.

REFERENCES

• 1: Jürgen Eichenauer-Herrmann , Harald Niederreiter, Digital inversive pseudorandom numbers, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.4 n.4, p.339-349, Oct. 1994 [doi>10.1145/200883.200896]
• 2: Toshiya Itoh , Shigeo Tsujii, A fast algorithm for computing multiplicative inverses in GF(2m) using normal bases, Information and Computation, v.78 n.3, p.171-177, Sept. 1988 [doi>10.1016/0890-5401(88)90024-7]
• 3: L'Ecuyer, P. 1994. Uniform random number generation. Annals of Operations Research 53: 77-120.
• 4: Makoto Matsumoto , Yoshiharu Kurita, Twisted GFSR generators, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.2 n.3, p.179-194, July 1992 [doi>10.1145/146382.146383]
• 5: Harald Niederreiter, Random number generation and quasi-Monte Carlo methods, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1992
• 6: Niederreiter, H. 1993. Factorization of polynomials and some linear-algebra problems over finite fields. Linear Algebra and Its Applications 192: 301-328.
• 7: Niederreiter, H. 1995a. The multiple-recursive matrix method for pseudorandom number generation. Finite Fields and Their Applications 1: 3-30.
• 8: Harald Niederreiter, Pseudorandom vector generation by the multiple-recursive matrix method, Mathematics of Computation, v.64 n.209, p.279-294, Jan. 1995 [doi>10.2307/2153334]
• 9: Niederreiter, H. 1995c. New developments in uniform pseudorandom number and vector generation, in Monte Carlo and quasi-Monte Carlo methods in scientific computing, ed. H. Niederreiter and P.J.- S. Shiue. Berlin: Springer-Verlag, to appear.
• 10: Tezuka, S. 1995. Uniform random numbers: theory and practice. Norwell, MA: Kluwer Academic Publishers.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
  G.3 PROBABILITY AND STATISTICS
      Subjects: Statistical computing; Random number generation

General Terms:
Design, Theory