Mathematics of Computation

Author(s): Takashi Kato; Li-Ming Wu; Niro Yanagihara.
Journal: Math. Comp. 65 (1996), 761-769.
MSC (1991): Primary 65C10; Secondary 11K45
Retrieve article in: PDF DVI PostScript
This article is available free of charge

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.

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.

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: 10.1090/S0025-5718-96-00712-0
PII: S 0025-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
Copyright of article: Copyright 1996, American Mathematical Society

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-6842(e) ISSN 0025-5718(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2008, American Mathematical Society Privacy Statement		Search the AMS