Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

 

 

On the distribution of $ k$-dimensional vectors for simple and combined Tausworthe sequences


Authors: Raymond Couture, Pierre L’Ecuyer and Shu Tezuka
Journal: Math. Comp. 60 (1993), 749-761, S11
MSC: Primary 11K45
DOI: https://doi.org/10.1090/S0025-5718-1993-1176708-4
MathSciNet review: 1176708
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 11K45

Retrieve articles in all journals with MSC: 11K45


Additional Information

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