A statistical analysis of generalized feedback shift register pseudorandom number generators. (English) Zbl 0634.65003

The author considers sequences of pseudorandom numbers, equidistributed in [0,1], of the form \(x_ n=\sum^{m}_{j=1}y_{n+k}p^{-j}\) \(n=0,1,2,..\). where the p-adic digits \(y_ r\) are obtained by the recurrence \(y_ r=a_{k-1}y_{r-1}+...+a_ 0y_{r-k}\) mod p and the numbers \(k_ j\) are distinct nonnegative arbitrary integers. The distribution of the sequence of s-dimensional vectors \(X_ n=(x_ n,x_{n+1},...,x_{n+s-1})\in [0,1]\quad s\) is examined by considering the discrepancy \(D_ N^{(s)}=\sup | E_ N(J)-V(J)|\) for \(N\geq 1\) where \(E_ N(J)\) is \(N^{-1}\) times the number of terms \(X_ 0,X_ 1,...,X_{N-1}\) falling into the s-dimensional interval \(J=\prod^{s}_{i=1}[0,t_ i]\), \(V(J)=\prod^{s}_{i=1}t_ i\), and the supremum is extended over all the intervals for which \(0\leq t_ i\leq 1.\)
It is assumed that \(f(x)=x\) \(k-a_{k-1}x^{k-1}...-a_ 0\) is an irreducible polynomial over the field \(F_ p\) of the residue classes mod p. Let \(\tau\) be the least period of the sequence: the maximal value of \(\tau\) is p k-1, and is achieved when f(x) is a primitive polynomial over \(F_ p\). In the paper some interesting formulae giving upper and lower bounds for \(D_ N^{(s)}\) are proved, both in the case \(N=\tau\) and in the case \(0\leq N<\tau\). Particular results for \(p=2\) are deduced. The troublesome evaluation of the term that measures the dependence of \(D_ N^{(s)}\) on f(x) and the constants \(k_ j\) is avoided in every case by the introduction of another quantity (called figure of merit) which is easier to handle.
Reviewer: M.Cugiani


65C10 Random number generation in numerical analysis
Full Text: DOI