Analysis of Additive Random Number Generators.

摘要

This thesis presents an analysis of the distribution of residues generated by the kth power-order linear homogeneous recurrence y(n+k)=a(k-1)y(n+k-1)+ ... + a(0)y(n) mod p to the power alpha when x to the kth power - a(k-1) x to the (k-1) power - ... - a(0) is a primitive polynomial in z(p)(x). It is shown that for t < or = k the tuples of t consecutive residues are equidistributed in t dimensions in the limit as alpha goes to infinity, subject only to a much weaker condition on the distribution of the residues. When specialized to the absolute value of a(j) < or = 1, the recurrence is the basis, for a computer random number generator which can be efficiently implemented directly in floating-point arithmetic with no multiplication and little machine dependence. The results of empirical tests comparing generators of this type with standard linear congruential generators are also presented. (Author)