Figures of merit for digital multistep pseudorandom numbers

André, Debra A.; Mullen, Gary L.; Niederreiter, Harald

doi:10.1090/S0025-5718-1990-1011436-4

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

Mathematics and computing