Further ``Linear'' Methods and a Unified Framework

Recently L'Ecuyer studied different combinations of MRGs [135]. The paper analyzes the period and lattice of these PRNGs and contains specific generators and portable implementations. It turns out that combined MRGs are equivalent (or approximately equivalent), to an MRG with large modulus. As a similar result, the add-with-carry (AWC) and subtract with borrow (SWB) pseudorandom number generator proposed by Marsaglia and Zaman [167] is equivalent to a LCG with large prime modulus [224]. The latter paper also illustrates the fact that AWC and SWB generators have extremely bad lattice structure in high dimensions (see also [32,222]). Bad lattice structures for vectors of non-successive values produced by several linear methods (LCG, MRG, lagged-Fibonacci, AWC/SWB) have been studied by L'Ecuyer [136,148]. Example 5 in [136] considers the widely available combined generator RANMAR (see [107] [25, V113]). The bad lattice structure is examined by a MRG which closely approximates RANMAR [34]. A generalization of the family of AWC generators is given by the multiply-with-carry (MWC) family proposed by Marsaglia (see [33]). The $s$-dimensional uniformity of MWC generators is studied in [35]. The paper also contains a method for finding good parameters in terms of the spectral test.

An efficient algorithm of the spectral test which facilitates the analysis of lattices generated by vectors of successive or non-successive values produced by linear congruential generators with moduli of essentially unlimited sizes was derived by [148].

The analog to the multiplicative LCG for pseudorandom vector generation is the matrix method. For references and an overview of this method see [186, Sect. 5.1]. Niederreiter introduced a unified framework for ``linear'' methods, the multiple-recursive matrix method, see [186, Sect. 4.1 and 5.2] and Section for some details.