On the distribution of $k$-dimensional vectors for simple and combined Tausworthe sequences
HTML articles powered by AMS MathViewer
- by Raymond Couture, Pierre L’Ecuyer and Shu Tezuka PDF
- Math. Comp. 60 (1993), 749-761 Request permission
Abstract:
The lattice structure of conventional linear congruential random number generators (LCGs), over integers, is well known. In this paper, we study LCGs in the field of formal Laurent series, with coefficients in the Galois field ${\mathbb {F}_2}$. The state of the generator (a Laurent series) evolves according to a linear recursion and can be mapped to a number between 0 and 1, producing what we call a LS2 sequence. In particular, the sequences produced by simple or combined Tausworthe generators are special cases of LS2 sequences. By analyzing the lattice structure of the LCG, we obtain a precise description of how all the k-dimensional vectors formed by successive values in the LS2 sequence are distributed in the unit hypercube. More specifically, for any partition of the k-dimensional hypercube into ${2^{kl}}$ identical subcubes, we can quickly compute a table giving the exact number of subcubes that contain exactly n points, for each integer n. We give numerical examples and discuss the practical implications of our results.References
- Debra A. André, Gary L. Mullen, and Harald Niederreiter, Figures of merit for digital multistep pseudorandom numbers, Math. Comp. 54 (1990), no. 190, 737–748. MR 1011436, DOI 10.1090/S0025-5718-1990-1011436-4
- 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 P. L’Ecuyer, Random numbers for simulation, Comm. ACM, 33, no. 10 (1990), 85-97.
- A. K. Lenstra, Factoring multivariate polynomials over finite fields, J. Comput. System Sci. 30 (1985), no. 2, 235–248. MR 801825, DOI 10.1016/0022-0000(85)90016-9
- Rudolf Lidl and Harald Niederreiter, Introduction to finite fields and their applications, Cambridge University Press, Cambridge, 1986. MR 860948
- Kurt Mahler, An analogue to Minkowski’s geometry of numbers in a field of series, Ann. of Math. (2) 42 (1941), 488–522. MR 4272, DOI 10.2307/1968914
- Kurt Mahler, On a theorem in the geometry of numbers in a space of Laurent series, J. Number Theory 17 (1983), no. 3, 403–416. MR 724538, DOI 10.1016/0022-314X(83)90057-4 G. Marsaglia et al., The McGill random number package super-duper, School of Computer Science, McGill University, Montreal, 1972.
- 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, Recent trends in random number and random vector generation, Ann. Oper. Res. 31 (1991), no. 1-4, 323–345. Stochastic programming, Part II (Ann Arbor, MI, 1989). MR 1118905, DOI 10.1007/BF02204856
- 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 S. Tezuka, Random number generation based on the polynomial arithmetic modulo two, Report no. RT-0017, IBM Research, Tokyo Research Laboratory, Oct. 1989. S. Tezuka and P. L’Ecuyer, Efficient and portable combined Tausworthe random number generators, ACM Trans. Model. Comput. Simulation 1 (1991) 99-112.
Additional Information
- © Copyright 1993 American Mathematical Society
- Journal: Math. Comp. 60 (1993), 749-761
- MSC: Primary 11K45
- DOI: https://doi.org/10.1090/S0025-5718-1993-1176708-4
- MathSciNet review: 1176708