Nonoverlapping pairs of explicit inversive congruential pseudorandom numbers (Q1345715)

Consider an odd integer-valued sequence \(y_n = (an + b)^{-1} \bmod m\) \((m = 2^l\), \(l \geq 7)\). Then \((x_n \equiv (y_n/m))_{n \geq 0} \subset [0,1)\) serves as a pseudorandom sequence approximating the independently sampled realizations of a random variable with the uniform distribution on \([0,1)\). A statistical discrepancy of \(N\) nonoverlapping pairs \({\mathbf x}_0, {\mathbf x}_1, \dots, {\mathbf x}_{N-1} \in [0,1)^2\) is defined as follows: \[ D^{(2)}_N = \sup_J \left |{\#({\mathbf x}_i \in J)\over N} - \text{Area} (J) \right |, \] where \(J\) is a rectangle \(\subset [0,1)^2\) and \({\mathbf x}_n = (x_{2n}, x_{2n + 1})\). The main result can be summarized as follows: \(Bm^{-{1\over 2}} \leq D^{(2)}_{m/4} \leq Cm^{-{1\over 2}} (\log m)^2\), where \(B\), \(C\) are some universal constants. These estimates are obtained by a highly sophisticated analysis of complex exponential sum over the integer lattice. A comparison with the discrepancy of the truly random sequence, known to be of order \(m^{-{1\over 2}} (\log \log m)^{1\over 2}\), shows that this nonlinear generator may actually be better than most linear congruential generators available on mainframe computers. For practical use, however, it would be of interest to know whether a computer implementation of this nonlinear algorithm would be capable of generating tens of millions of random numbers relatively fast, despite its complexity due to evaluating the multiplicative inverse of an integer.