Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

The serial test for a nonlinear pseudorandom number generator


Authors: Takashi Kato, Li-Ming Wu and Niro Yanagihara
Journal: Math. Comp. 65 (1996), 761-769
MSC (1991): Primary 65C10; Secondary 11K45
DOI: https://doi.org/10.1090/S0025-5718-96-00712-0
MathSciNet review: 1333317
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Let $M = 2^{w},$ and $G_{M} = \{1,3,...,M-1 \}.$ A sequence $ \{y_{n} \}, y_{n} \in G_{M},$ is obtained by the formula $y_{n+1} \equiv a{\overline{y}_{n}} + b + cy_{n} \; \mathrm{mod} \; M.$ The sequence $ \{x_{n} \}, x_{n}=y_{n}/M,$ is a sequence of pseudorandom numbers of the maximal period length $M/2$ if and only if $a+c \equiv 1$ (mod 4), $b \equiv 2$ (mod 4). In this note, the uniformity is investigated by the 2-dimensional serial test for the sequence. We follow closely the method of papers by Eichenauer-Herrmann and Niederreiter.


References [Enhancements On Off] (What's this?)

  • 1. J. Eichenauer-Herrmann, Inversive congruential pseudorandom numbers avoid the planes, Math. Comp. 56 (1991), 297--301. MR 91k:65021
  • 2. J. Eichenauer-Herrmann, Statistical independence of a new class of inversive congruential pseudorandom numbers, Math. Comp. 60 (1993), 375--384. MR 93d:65011
  • 3. J. Eichenauer-Herrmann, On generalized inversive congruential pseudorandom numbers, Math. Comp. 63 (1994), 293--299. MR 94k:11088
  • 4. J. Eichenauer-Herrmann, H. Grothe, H. Niederreiter, and A. Topuzoglu, On the lattice structure of a nonlinear generator with modulus $2^{\alpha }$, J. Comp. Appl. Math. 31 (1990), 81--85. MR 91j:65012
  • 5. J. Eichenauer, J. Lehn, and A. Topuzoglu, A nonlinear congruential pseudorandom number generator with power of two modulus, Math. Comp. 51 (1988), 757--759. MR 89i:65007
  • 6. J. Eichenauer-Herrmann and H. Niederreiter, Lower bounds for the discrepancy of inversive congruential pseudorandom numbers with power of two modulus, Math. Comp. 58 (1992), 775--779. MR 92i:65018
  • 7. T. Kato, L.-M. Wu, and N. Yanagihara, On a nonlinear congruential pseudorandom number generator, Math. Comp. 65 (1996) (to appear).
  • 8. D. E. Knuth, The Art of Computer Programming, Vol.2: Seminumerical Algorithms, 2nd Ed., Addison-Wesley, Reading, Mass., 1981. MR 83i:68003
  • 9. H. Niederreiter, The serial test for congruential pseudorandom numbers generated by inversions, Math. Comp. 52 (1989), 135--144. MR 90e:65008
  • 10. H. Niederreiter, Recent trends in random number and random vector generation, Ann. Oper. Res. 31 (1991), 323--345. MR 92h:65010
  • 11. H. Niederreiter, Random number generation and quasi-Monte Carlo methods, SIAM, Philadelphia, PA, 1992. MR 93h:65008
  • 12. H. Salié, Über die Kloostermanschen Summen S(u,v;q), Math. Z. 34 (1932), 91--109.

Similar Articles

Retrieve articles in Mathematics of Computation of the American Mathematical Society with MSC (1991): 65C10, 11K45

Retrieve articles in all journals with MSC (1991): 65C10, 11K45


Additional Information

Takashi Kato
Affiliation: Department of Mathematics, Faculty of Education, Chiba University, 1-33 Yayoi-cho, Chiba City, 263 Japan

Li-Ming Wu
Affiliation: Department of Mathematics, Faculty of Science, Chiba University, 1-33 Yayoi-cho, Chiba City, 263 Japan

Niro Yanagihara
Affiliation: Department of Mathematics, Faculty of Science, Chiba University, 1-33 Yayoi-cho, Chiba City, 263 Japan
Email: yanagi@math.s.chiba-u.ac.jp

DOI: https://doi.org/10.1090/S0025-5718-96-00712-0
Keywords: Pseudorandom number generator, the inversive congruential method, power of two modulus, discrepancy, $k$-dimensional serial test, Kloostermann sum
Received by editor(s): October 25, 1994
Article copyright: © Copyright 1996 American Mathematical Society

American Mathematical Society