Mathematics of Computation

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

The serial test for a nonlinear pseudorandom number generator

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

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:

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.

	Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
\|