On the discrepancy of quadratic congruential pseudorandom numbers

摘要

One of the alternatives to linear congruential pseudorandom number generators with their undesirable lattice structure is the quadratic congruential method which is due to Knuth. In the present paper the statistical independence properties of pairs of consecutive pseudorandom numbers generated according to this method are analysed by means of the serial test. Upper bounds for the discrepancy of these pairs are established which are essentially best possible. The results show that the quadratic congruential method performs uniformly satisfactorily if a reasonable choice of one of the parameters is made. The method of proof relies heavily on the evaluation of certain exponential sums.