Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

 
 

 

Figures of merit for digital multistep pseudorandom numbers


Authors: Debra A. André, Gary L. Mullen and Harald Niederreiter
Journal: Math. Comp. 54 (1990), 737-748
MSC: Primary 65C10
DOI: https://doi.org/10.1090/S0025-5718-1990-1011436-4
MathSciNet review: 1011436
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: The statistical independence properties of s successive digital multistep pseudorandom numbers are governed by the figure of merit $ {\rho ^{(s)}}(f)$ which depends on s and the characteristic polynomial f of the recursion used in the generation procedure. We extend previous work for s = 2 and describe how to obtain large figures of merit for $ s > 2$, thus arriving at digital multistep pseudorandom numbers with attractive statistical independence properties. Tables of figures of merit for $ s = 3,4,5$ and degrees $ \leq 32$ are included.


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

  • [1] J. Brillhart, D. H. Lehmer, J. L. Selfridge, B. Tuckerman, and S. S. Wagstaff, Jr., Factorizations of $ {b^n} \pm 1$, $ b = 2,3,5,6,7,10,11,12$ up to high powers, 2nd ed., Contemporary Math., Vol. 22, Amer. Math. Soc., Providence, R.I., 1988. MR 996414 (90d:11009)
  • [2] D. E. Knuth, The art of computer programming, Vol. 2: Seminumerical algorithms, 2nd ed., Addison-Wesley, Reading, Mass., 1981. MR 633878 (83i:68003)
  • [3] R. Lidl and H. Niederreiter, Introduction to finite fields and their applications, Cambridge Univ. Press, Cambridge, 1986. MR 860948 (88c:11073)
  • [4] G. L. Mullen and H. Niederreiter, Optimal characteristic polynomials for digital multistep pseudorandom numbers, Computing 39 (1987), 155-163. MR 919665 (88m:65011)
  • [5] H. Niederreiter, Quasi-Monte Carlo methods and pseudo-random numbers, Bull. Amer. Math. Soc. 84 (1978), 957-1041. MR 508447 (80d:65016)
  • [6] -, The performance of k-step pseudorandom number generators under the uniformity test, SIAM J. Sci. Statist. Comput. 5 (1984), 798-810. MR 765207 (86f:65029)
  • [7] -, Pseudozufallszahlen und die Theorie der Gleichverteilung, Sitzungsber. Österr. Akad. Wiss. Math.-Natur. Kl. Abt. II 195 (1986), 109-138. MR 881335 (88g:11045)
  • [8] -, Rational functions with partial quotients of small degree in their continued fraction expansion, Monatsh. Math. 103 (1987), 269-288. MR 897953 (88h:12002)
  • [9] -, Point sets and sequences with small discrepancy, Monatsh. Math. 104 (1987), 273-337. MR 918037 (89c:11120)
  • [10] -, The serial test for digital k-step pseudorandom numbers, Math. J. Okayama Univ. 30 (1988), 93-119. MR 976736 (90g:65011)
  • [11] W. W. Peterson and E. J. Weldon, Jr., Error-correcting codes, 2nd ed., M.I.T. Press, Cambridge, Mass., 1972. MR 0347444 (49:12164)
  • [12] R. C. Tausworthe, Random numbers generated by linear recurrence modulo two, Math. Comp. 19 (1965), 201-209. MR 0184406 (32:1878)
  • [13] A. van Wijngaarden, Mathematics and computing, in Proc. Sympos. on Automatic Digital Computation (London, 1954), H. M. Stationery Office, London, 1954, pp. 125-129.

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 65C10

Retrieve articles in all journals with MSC: 65C10


Additional Information

DOI: https://doi.org/10.1090/S0025-5718-1990-1011436-4
Article copyright: © Copyright 1990 American Mathematical Society

American Mathematical Society