×

zbMATH — the first resource for mathematics

A multiple recursive nonlinear congruential pseudo random number generator. (English) Zbl 0609.65005
A nonlinear multiple recursive congruential pseudo-random number generator with prime modulus p is introduced. Let \(x_ n\), \(n\geq 0\), be the sequence generated by a usual linear \((r+1)\)-step recursive congruential generator with prime modulus p and denote by N(n), \(n\geq 0\), the sequence of non-negative integers with \(x_{N(n)}\not\equiv 0\) (mod p). The nonlinear generator is defined by \(z_ n\equiv x_{N(n+1)}\cdot x^{-1}_{N(n)}\quad (mod p),\) \(n\geq 0\), where \(x^{-1}_{N(n)}\) denotes the inverse element of \(x_{N(n)}\) in the Galois field \(GF(p).\) A condition is given which ensures that the generated sequence is purely periodic with period length \(p^ r\) and all \((p-1)^ r\) r-tuples \((y_ 1,...,y_ r)\) with \(1\leq y_ 1,...,y_ r<p\) are generated once per period when r-tuples of consecutive numbers of the generated sequence are formed. For \(r=1\) this generator coincides with a nonlinear generator introduced by the first and the third author in an earlier paper.

MSC:
65C10 Random number generation in numerical analysis
PDF BibTeX XML Cite
Full Text: DOI EuDML
References:
[1] Beyer, W.A.; Roof, R.B. and Williamson, D.: The lattice structure of multiplicative pseudo-random vectors. Math. Comp. 25, 345–363 (1971) · Zbl 0269.65003
[2] Eichenauer, J. and Lehn J.: A non-linear congruential pseudo random number generator. Statistical Papers (to appear 1986) · Zbl 0607.65001
[3] Kowalsky, H.-J.: Lineare Algebra, 9th ed., de Gruyter, Berlin-New York (1979) · Zbl 0189.32801
[4] Knuth, D.E.: The art of computer programming, vol. 2, 2nd ed., Addison-Wesley, Reading (1981) · Zbl 0477.65002
[5] Marsaglia, G.: Random numbers fall mainly in the planes. Proc. Nat. Acad. Sci. 61, 25–28 (1968) · Zbl 0172.21002
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.