Improved long-period generators based on linear recurrences modulo 2

2006/03/01 by François Panneton, Pierre L'Ecuyer, Pierre L’Ecuyer +1 · 5 citations
Computer Science · #Chaos-based Image/Signal Encryption #Algorithms and Data Compression #Cellular Automata and Applications

paper · doi:10.1145/1132973.1132974

Abstract

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 this respect. In this article, we propose new generators of that form with better equidistribution and “bit-mixing” properties for equivalent period length and speed. 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.

Cited by

• A Search for Good Pseudo-random Number Generators : Survey and Empirical Studies
• First derivatives at the optimum analysis (fdao): An approach to estimate the uncertainty in nonlinear regression involving stochastically independent variables
• Fine with "1234"? An Analysis of SMS One-Time Password Randomness in Android Apps
• It is high time we let go of the Mersenne Twister
• TestU01

Related

• An experimental exploration of Marsaglia's xorshift generators, scrambled
• VMT19937: A SIMD-Friendly Pseudo Random Number Generator based on Mersenne Twister 19937
• Combining the Mersenne Twister and the Xorgens Designs
• Period of the d-Sequence Based Random Number Generator
• Long Period Sequences Generated by the Logistic Map over Finite Fields with Control Parameter Four