Explicit inversive congruential pseudorandom numbers: The compound approach
Let \(p_ 1,p_ 2,\dots,p_ r\geq 5\) be distinct primes. For \(1\leq i\leq r\) let \(a_ i\in \mathbb{Z}_{p_ i}\backslash \{0\}\), and \(b_ i\in\mathbb{Z}_{p_ i}\). Define the corresponding explicit inversive congruential sequence \((y^{(i)}_ n)_{n\geq 0}\) in \(\mathbb{Z}_{p_ i}\) by \(y^{(i)}_ n\equiv \overline{a_ i n+b_ i}(\text{mod } p_ i)\), \(n\geq 0\), where \(\bar z\) denotes the inverse of \(z\) modulo \(p_ i\). Let \(m=p_ 1\cdots p_ r\) and \(m_ i= m/p_ i\) for \(1\leq i\leq r\). Then define the compound explicit inversive congruential sequence \((y_ n)_{n\geq 0}\) in \(\mathbb{Z}_ m\) by \(y_ n\equiv m_ 1 y^{(1)}_ n+\cdots+ m_ r y^{(r)}_ n(\text{mod } m)\),\(n\geq 0\). Let \(x_ n= y_ n/m\), \(n\geq 0\). Finally, define the \(s\)-tuples \(\vec x_ n= (x_{n+n_ 1},\dots,x_{n+n_ s})\in [0,1)^ s\), \(n\geq 0\), where \(2\leq s\leq \min(p_ 1,\dots,p_ r)\), and \(n_ 1,\dots,n_ s\) are arbitrary integers such that \(0= n_ 1<n_ 2<\cdots <n_ s<\min(p_ 1,\dots,p_ r)\). The author proves that the discrepancy \(D^{(s)}_ m\) of the sequence \(\{\vec x_ 0,\dots,\vec x_{m-1}\}\) satisfies \[ D^{(s)}_ m< m^{- 1/2}\left({2\over \pi}\log m+{7\over 5}\right)^ s\prod^ r_{i=1} (2s- 2+(s+2)p^{-1/2}_ i)+ sm^{-1}, \] and shows that this upper bound for \(D^{(s)}_ m\) is best possible up to the logarithmic factor.
explicit inversive congruential sequence
scientific article; zbMATH DE number 482261
scientific article