Uniform random number generation

In typical stochastic simulations, randomness is produced by generating a sequence of independent uniform variates (usually real-valued between 0 and 1, or integer-valued in some interval) and transforming them in an appropriate way. This paper examines practical ways of generating (deterministic approximations to) such uniform variates on a computer. It compares them in terms of ease of implementation, efficiency, theoretical support, and statistical robustness. The paper looks in particular at several classes of generators, such as linear congruential, multiple recursive, digital multistep, Tausworthe, lagged-Fibonacci, generalized feedback shift register, matrix, linear congruential over fields of formal series, and combined generators, and shows how all of them can be analyzed in terms of their lattice structure. It also mentions other classes of generators, like non-linear generators, discusses other kinds of theoretical and empirical statistical tests, and gives a bibliographic survey of recent papers on the subject.