## Figures of merit for digital multistep pseudorandom numbers

HTML articles powered by AMS MathViewer

- by Debra A. André, Gary L. Mullen and Harald Niederreiter PDF
- Math. Comp.
**54**(1990), 737-748 Request permission

## 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

- John Brillhart, D. H. Lehmer, J. L. Selfridge, Bryant Tuckerman, and S. S. Wagstaff Jr.,
*Factorizations of $b^n \pm 1$*, 2nd ed., Contemporary Mathematics, vol. 22, American Mathematical Society, Providence, RI, 1988. $b=2,3,5,6,7,10,11,12$ up to high powers. MR**996414**, DOI 10.1090/conm/022 - Donald E. Knuth,
*The art of computer programming. Vol. 2*, 2nd ed., Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass., 1981. Seminumerical algorithms. MR**633878** - Rudolf Lidl and Harald Niederreiter,
*Introduction to finite fields and their applications*, Cambridge University Press, Cambridge, 1986. MR**860948** - G. L. Mullen and H. Niederreiter,
*Optimal characteristic polynomials for digital multistep pseudorandom numbers*, Computing**39**(1987), no. 2, 155–163 (English, with German summary). MR**919665**, DOI 10.1007/BF02310104 - Harald Niederreiter,
*Quasi-Monte Carlo methods and pseudo-random numbers*, Bull. Amer. Math. Soc.**84**(1978), no. 6, 957–1041. MR**508447**, DOI 10.1090/S0002-9904-1978-14532-7 - Harald Niederreiter,
*The performance of $k$-step pseudorandom number generators under the uniformity test*, SIAM J. Sci. Statist. Comput.**5**(1984), no. 4, 798–810. MR**765207**, DOI 10.1137/0905057 - Harald Niederreiter,
*Pseudozufallszahlen und die Theorie der Gleichverteilung*, Österreich. Akad. Wiss. Math.-Natur. Kl. Sitzungsber. II**195**(1986), no. 1-3, 109–138 (German). MR**881335** - Harald Niederreiter,
*Rational functions with partial quotients of small degree in their continued fraction expansion*, Monatsh. Math.**103**(1987), no. 4, 269–288. MR**897953**, DOI 10.1007/BF01318069 - Harald Niederreiter,
*Point sets and sequences with small discrepancy*, Monatsh. Math.**104**(1987), no. 4, 273–337. MR**918037**, DOI 10.1007/BF01294651 - Harald Niederreiter,
*The serial test for digital $k$-step pseudorandom numbers*, Math. J. Okayama Univ.**30**(1988), 93–119. MR**976736** - W. Wesley Peterson and E. J. Weldon Jr.,
*Error-correcting codes*, 2nd ed., The M.I.T. Press, Cambridge, Mass.-London, 1972. MR**0347444** - Robert C. Tausworthe,
*Random numbers generated by linear recurrence modulo two*, Math. Comp.**19**(1965), 201–209. MR**184406**, DOI 10.1090/S0025-5718-1965-0184406-1
A. van Wijngaarden,

*Mathematics and computing*, in Proc. Sympos. on Automatic Digital Computation (London, 1954), H. M. Stationery Office, London, 1954, pp. 125-129.

## Additional Information

- © Copyright 1990 American Mathematical Society
- Journal: Math. Comp.
**54**(1990), 737-748 - MSC: Primary 65C10
- DOI: https://doi.org/10.1090/S0025-5718-1990-1011436-4
- MathSciNet review: 1011436