Fast Random Nunber Generators Based on Linear Recurrences Modulo 2: Overview and Comparison

wsc05rng.pdf, P. L'Ecuyer and F. Panneton, "Fast Random Nunber Generators Based on Linear Recurrences Modulo 2: Overview and Comparison'', 2005 Winter Simulation Conference, to appear.

Abstract:

Random number generators based on linear recurrences modulo 2 are among the fastest long-period generators currently available. The uniformity and independence of the points they produce, over their entire period length, can be measured by theoretical figures of merit that are easy to compute, and those having good values for these figures of merit are statistically reliable in general. Some of these generators can also provide disjoint streams and substreams efficiently. In this paper, we review the most interesting construction methods for these generators, examine their theoretical and empirical properties, and make comparisons.

Keywords: Random number generator, linear feedback shift register (LFSR), GFSR, linear recurrence modulo 2, Twisted GFSR, , Mersenne twister, Xorshift generator, WELL generator.