The serial test for congruential pseudorandom numbers generated by inversions
Author:
Harald Niederreiter
Journal:
Math. Comp. 52 (1989), 135144
MSC:
Primary 65C10; Secondary 11K45
MathSciNet review:
971407
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: Two types of congruential pseudorandom number generators based on inversions were introduced recently. We analyze the statistical independence properties of these pseudorandom numbers by means of the serial test. The results show that these pseudorandom numbers perform satisfactorily under the serial test. The methods of proof rely heavily on bounds for character sums such as the WeilStepanov bound for character sums over finite fields.
 [1]
J. Eichenauer, H. Grothe & J. Lehn, "Marsaglia's lattice test and nonlinear congruential pseudo random number generators," Metrika, v. 35, 1988, pp. 241250.
 [2]
Jürgen
Eichenauer and Jürgen
Lehn, A nonlinear congruential pseudorandom number generator,
Statist. Hefte 27 (1986), no. 4, 315–326. MR 877295
(88i:65014)
 [3]
Jürgen
Eichenauer, Jürgen
Lehn, and Alev
Topuzoğlu, A nonlinear congruential pseudorandom
number generator with power of two modulus, Math. Comp. 51 (1988), no. 184, 757–759. MR 958641
(89i:65007), http://dx.doi.org/10.1090/S00255718198809586411
 [4]
Donald
E. Knuth, The art of computer programming. Vol. 2, 2nd ed.,
AddisonWesley Publishing Co., Reading, Mass., 1981. Seminumerical
algorithms; AddisonWesley Series in Computer Science and Information
Processing. MR
633878 (83i:68003)
 [5]
Rudolf
Lidl and Harald
Niederreiter, Finite fields, Encyclopedia of Mathematics and
its Applications, vol. 20, AddisonWesley Publishing Company Advanced
Book Program, Reading, MA, 1983. With a foreword by P. M. Cohn. MR 746963
(86c:11106)
 [6]
Harald
Niederreiter, Pseudorandom numbers and optimal coefficients,
Advances in Math. 26 (1977), no. 2, 99–181. MR 0476679
(57 #16238)
 [7]
Harald
Niederreiter, QuasiMonte Carlo methods and
pseudorandom numbers, Bull. Amer. Math.
Soc. 84 (1978), no. 6, 957–1041. MR 508447
(80d:65016), http://dx.doi.org/10.1090/S000299041978145327
 [8]
H. Niederreiter, "Numbertheoretic problems in pseudorandom number generation," in Proc. Sympos. on Applications of Number Theory to Numerical Analysis, Lecture Notes No. 537, Research Inst. of Math. Sciences, Kyoto, 1984, pp. 1828.
 [9]
Harald
Niederreiter, The serial test for pseudorandom numbers generated by
the linear congruential method, Numer. Math. 46
(1985), no. 1, 51–68. MR 777824
(86i:65010), http://dx.doi.org/10.1007/BF01400255
 [10]
Harald
Niederreiter, Statistical independence of nonlinear congruential
pseudorandom numbers, Monatsh. Math. 106 (1988),
no. 2, 149–159. MR 968332
(89j:11079), http://dx.doi.org/10.1007/BF01298835
 [11]
H.
Niederreiter, Remarks on nonlinear congruential pseudorandom
numbers, Metrika 35 (1988), no. 6,
321–328. MR
980847 (90e:11119), http://dx.doi.org/10.1007/BF02613320
 [12]
H. Salié, "Über die Kloostermanschen Summen ," Math. Z., v. 34, 1932, pp. 91109.
 [13]
S.
A. Stepanov, The estimation of rational trigonometric sums with
prime denominator, Trudy Mat. Inst. Steklov. 112
(1971), 346–371, 389. (errata insert) (Russian). Collection of
articles dedicated to Academician Ivan Matveevič Vinogradov on his
eightieth birthday. I. MR 0318158
(47 #6706)
 [14]
André
Weil, On some exponential sums, Proc. Nat. Acad. Sci. U. S. A.
34 (1948), 204–207. MR 0027006
(10,234e)
 [1]
 J. Eichenauer, H. Grothe & J. Lehn, "Marsaglia's lattice test and nonlinear congruential pseudo random number generators," Metrika, v. 35, 1988, pp. 241250.
 [2]
 J. Eichenauer & J. Lehn, "A nonlinear congruential pseudo random number generator," Statist. Papers, v. 27, 1986, pp. 315326. MR 877295 (88i:65014)
 [3]
 J. Eichenauer, J. Lehn & A. Topuzoglu, "A nonlinear congruential pseudorandom number generator with power of two modulus," Math. Comp., v. 51, 1988, pp. 757759. MR 958641 (89i:65007)
 [4]
 D. E. Knuth, The Art of Computer Programming, vol. 2: Seminumerical Algorithms, 2nd ed., AddisonWesley, Reading, Mass., 1981. MR 633878 (83i:68003)
 [5]
 R. Lidl & H. Niederreiter, Finite Fields, AddisonWesley, Reading, Mass., 1983. MR 746963 (86c:11106)
 [6]
 H. Niederreiter, "Pseudorandom numbers and optimal coefficients," Adv. in Math., v. 26, 1977, pp. 99181. MR 0476679 (57:16238)
 [7]
 H. Niederreiter, "QuasiMonte Carlo methods and pseudorandom numbers," Bull. Amer. Math. Soc., v. 84, 1978, pp. 9571041. MR 508447 (80d:65016)
 [8]
 H. Niederreiter, "Numbertheoretic problems in pseudorandom number generation," in Proc. Sympos. on Applications of Number Theory to Numerical Analysis, Lecture Notes No. 537, Research Inst. of Math. Sciences, Kyoto, 1984, pp. 1828.
 [9]
 H. Niederreiter, "The serial test for pseudorandom numbers generated by the linear congruential method," Numer. Math., v. 46, 1985, pp. 5168. MR 777824 (86i:65010)
 [10]
 H. Niederreiter, "Statistical independence of nonlinear congruential pseudorandom numbers," Monatsh. Math. (To appear.) MR 968332 (89j:11079)
 [11]
 H. Niederreiter, "Remarks on nonlinear congruential pseudorandom numbers," Metrika (To appear.) MR 980847 (90e:11119)
 [12]
 H. Salié, "Über die Kloostermanschen Summen ," Math. Z., v. 34, 1932, pp. 91109.
 [13]
 S. A. Stepanov, "On estimating rational trigonometric sums with prime denominator," Trudy Mat. Inst. Steklov., v. 112, 1971, pp. 346371. (Russian) MR 0318158 (47:6706)
 [14]
 A. Weil, "On some exponential sums," Proc. Nat. Acad. Sci. U.S.A., v. 34, 1948, pp. 204207. MR 0027006 (10:234e)
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC:
65C10,
11K45
Retrieve articles in all journals
with MSC:
65C10,
11K45
Additional Information
DOI:
http://dx.doi.org/10.1090/S00255718198909714072
PII:
S 00255718(1989)09714072
Article copyright:
© Copyright 1989 American Mathematical Society
