A remark on the discrepancy of quadratic congruential pseudorandom numbers

AbstractThe linear congruential method for generating uniform pseudorandom numbers has several known deficiencies which can render the generated sequences useless for certain simulation purposes. One of the alternatives is Knuth's quadratic congruential method. Recently, it was proved that pairs of quadratic congruential pseudorandom numbers have uniformly excellent statistical independence properties. In the present paper it is shown that unfortunately a similar result cannot be obtained for k-tuples with k⩾3. It is proved that for a positive percentage of the possible generators the discrepancy of these k-tuples is too large. The method of proof relies on the evaluation of certain exponential sums. In view of the present result it becomes doubtful whether the quadratic congruential method is absolutely suitable for generating uniform pseudorandom numbers