zbMATH — the first resource for mathematics

Marsaglia’s lattice test and non-linear congruential pseudo-random number generators. (English) Zbl 0653.65006
A recursive congruential non-additive generator of the form \((1)\quad x_{n+1}\equiv f(x_ n)(mod p),\) \(x_{n+1}\in {\mathbb{Z}}_ p\), \(n\geq 0\), is considered, where p is a large prime number, \({\mathbb{Z}}_ p=\{0,1,...,p-1\}\), \(x_ 0\in {\mathbb{Z}}_ p\), and f: \({\mathbb{Z}}_ p\to {\mathbb{Z}}_ p\) is a function such that (1) has maximal period length. The sequences of integers \(\{x_ i:\) \(i\geq 0\}\) generated by (1) are divided into vectors of \(d\geq 2\) consecutive numbers: \(v^ d_ i=(x_ i,...,x_{i+d-1})^ T\in {\mathbb{Z}}^ d_ p\) and let \(w^ d_ i\equiv v_ i^ d-v^ d_ 0(mod p),\) \(i\geq 0\). For \(d\leq 3\), it is shown that \(V^ d={\mathbb{Z}}^ d_ p,\) where \(V^ d=\{v\in {\mathbb{Z}}^ d_ p| \quad v\equiv \sum^{p-1}_{i=1}z_ iw^ d_ i(mod p);\quad z_ 1,...,z_{p-1}\in {\mathbb{Z}}_ p\}.\) In other words, (1) passes G. Marsaglia’s lattice test [Applications of number theory to numerical analysis, 249-285 (1972; Zbl 0266.65007)]. For \(d\geq 4\) there are generators (1) which fail this test. It is also shown that the generators of a class of nonlinear generators introduced by the first and the third author [Stat. Hefte 27, 315-326 (1986; Zbl 0607.65001)] pass Marsaglia’s lattice test for \(d\leq (p-1)/2\).
Reviewer: R.Theodorescu

65C10 Random number generation in numerical analysis
PDF BibTeX Cite
Full Text: DOI EuDML
[1] Beyer WA, Roof RB, Williamson D (1971) The lattice structure of multiplicative pseudo-random vectors. Math Comp 25:345–363 · Zbl 0269.65003
[2] Eichenauer J, Lehn J (1986) A non-linear congruential pseudo random number generator. Statistical Papers 27:315–326 · Zbl 0607.65001
[3] Marsaglia G (1972) The structure of linear congruential sequences. In: Zaremba SK (ed) Applications of number theory to numerical analysis, pp 249–285 · Zbl 0266.65007
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.