Supplement to On the Distribution of k-Dimensional Vectors for Simple and Combined Tausworthe Sequences
Supplement to On the Distribution of k-Dimensional Vectors for Simple and Combined Tausworthe Sequences
复制标题
简单和组合 Tausworthe 序列的 k 维向量分布的补充
DOI：
10.2307/2153149
复制
发表时间：
1991
影响因子：
2
通讯作者：
S. Tezuka
中科院分区：
文献类型：
--
作者：
Raymond Couture;P. L'Ecuyer;S. Tezuka
传统线性同余随机数发生器（LCGs）的晶格结构是众所周知的。本文研究了形式洛朗级数域中的LCGs，其系数在伽罗瓦场F2中。生成器的状态（一个洛朗级数）根据线性递归发展，可以映射到0到1之间的一个数字，产生我们所说的LS2序列。特别地，由简单的或组合的Tausworthe生成器产生的序列是LS2序列的特殊情况。通过分析LCG的晶格结构，我们得到了由LS2序列中连续值构成的所有k维向量在单位超立方体中的分布的精确描述。更具体地说，对于k维超立方体的任何划分为2kl个相同的子立方体，我们可以快速计算出一个表，给出包含恰好n个点的子立方体的确切数量，对于每个整数n。我们给出了数值示例并讨论了我们结果的实际含义。
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 F2. 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 2kl 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.