WELL Random number generator

lfsr04.pdf, F. Panneton, P. L'Ecuyer and M. Matsumoto, "Improved Long-Period Generators Based on Linear Recurrences Modulo 2", submitted to ACM TOMS.


Fast uniform random number generators with extremely long periods have been defined and implemented based on linear recurrences modulo 2. The twisted GFSR and the Mersenne twister are famous recent examples. Besides the period length, the statistical quality of these generators is usually assessed via their equidistribution properties. The huge-period generators proposed so far are not quite optimal in that respect. In this paper, we propose new generators, with better equidistribution and “bit-mixing” properties for equivalent period length and speed. Approximately half of the coefficients of the characteristic polynomial of these generators are nonzero. The state of our new generators evolves in a more chaotic way than for the Mersenne twister. We illustrate how this can reduce the impact of persistent dependencies among successive output values, which can be observed in certain parts of the period of gigantic generators such as the Mersenne twister.

Keywords: Random number generation, linear feedback shift register, GFSR linear recurrence modulo 2, Mersenne twister.

Code in C: