Some long-period random number generators using shifts and xors

Abstract

Marsaglia recently introduced a class of `xorshift' random number generators with periods \(2^n-1\) for \(n = 32, 64,\ldots\). Here Marsaglia's xorshift generators are generalised to obtain fast and high quality random number generators with extremely long periods. Whereas random number generators based on primitive trinomials may be unsatisfactory, because a trinomial has very small weight, these new generators can be chosen so that their minimal polynomials have a large number of non-zero terms and, hence, a large weight. A computer search using Magma found good random number generators for\(~n\) a power of two up to 4096. These random number generators are implemented in a free software package \texttt{xorgens}.