Combined LCGs: cLCG

Combining different streams
, , of pseudorandom numbers into a new stream
,
yields an easy way to achieve
long periods while keeping the computational costs of generating the
numbers low by choosing suitable parameters for each underlying generator.
For references and an overview of this technique and its difficulties see
[134, Sect. 9] and [186, Sect. 4.2].
Different combination methods (combined generators,
composite congruential generators, compound generators, )
are given in [30,51,73,107,131,149,199,210,211].
**Quote**[134]: *Theoretical results in
[20,164] *(see also [85, p. 70])* appear to support
the view (at first glance) that combined generators should have better
statistical behavior in general than their individual components.
However, as explained in [132], applying those theoretical results to
``deterministic'' generators is a somewhat shaky reasoning.
Combination can conceivably worsen things. Nevertheless, empirical
results strongly support combinations [133,164].*

However, the more theoretical properties of a combined generator are known, the less undesired side-effects are possible.

In contrast to hybrid combinations, the combination of (multiplicative) LCGs only yields the advantage that the underlying structure of -dimensional overlapping tuples is known. This is due to the fact that cLCGs are equivalent to single LCGs with large moduli [85,149,235].

Combined LCGs provide an easy way to partition their output sequences into disjoint parallel streams by varying the seeds [84,85]. From the equivalence to LCGs, it follows that splitting a cLCG needs certain precautions as well [43]. Using a modified spectral test, MacLaren [161] has suggested a method to test the independence of parallel streams for cLCGs (and LCGs). The latter paper is the basis for the combined LCGs implemented in the Nag PVM Library.

A combination of multiplicative LCGs was first suggested by Wichmann and Hill [235].

Wichmann and Hill cLCG

Wichmann and Hill [235] combined three multiplicative LCGs:

LCG | 3 | 4 | 5 | 6 | 7 | 7 | |

0.9147 | 0.183 | 0.4082 | 0.6605 | 0.8212 | 0.4813 | 0.5507 | |

0.9195 | 0.6228 | 0.7039 | 0.7854 | 0.785 | 0.7014 | 0.584 | |

0.9085 | 0.6821 | 0.4639 | 0.7507 | 0.6049 | 0.7415 | 0.584 |

Zeisl (1986) [235] completed that this generator is equivalent to

For implementations see the StatLib server and [199, RAN7]. Empirical studies and further remarks on this generator are contained in [214].

L'Ecuyer cLCGs

In order to implement combined LCGs, the following ``good-lattice'' LCGs are suggested in [131]. The zoom above stems from which is equivalent to the combined generators using LCG 9, 12 and 13 (observe the ``weak'' lattice in dimension 2).

no. | 2 | 3 | 4 | 5 | 6 | 7 | 8 | ||

1 | 39373 | 0.791 | 0.755 | 0.787 | 0.758 | 0.754 | 0.779 | 0.560 | |

2 | 2147483563 | 40014 | 0.803 | 0.836 | 0.788 | 0.828 | 0.808 | 0.474 | 0.663 |

3 | 2147483399 | 40692 | 0.817 | 0.818 | 0.805 | 0.891 | 0.819 | 0.474 | 0.663 |

4 | 2147482811 | 41546 | 0.834 | 0.787 | 0.811 | 0.808 | 0.821 | 0.709 | 0.692 |

5 | 2147482801 | 42024 | 0.844 | 0.811 | 0.857 | 0.783 | 0.810 | 0.558 | 0.740 |

6 | 2147482739 | 45742 | 0.919 | 0.851 | 0.783 | 0.820 | 0.799 | 0.322 | 0.449 |

7 | 32749 | 162 | 0.833 | 0.796 | 0.710 | 0.658 | 0.763 | 0.505 | 0.578 |

8 | 32749 | 219 | 0.930 | 0.793 | 0.726 | 0.718 | 0.763 | 0.733 | 0.721 |

9 | 32363 | 157 | 0.812 | 0.851 | 0.827 | 0.782 | 0.788 | 0.584 | 0.669 |

10 | 32143 | 160 | 0.830 | 0.754 | 0.807 | 0.728 | 0.777 | 0.675 | 0.611 |

11 | 32119 | 172 | 0.893 | 0.719 | 0.735 | 0.776 | 0.740 | 0.653 | 0.511 |

12 | 31727 | 146 | 0.763 | 0.722 | 0.727 | 0.758 | 0.729 | 0.676 | 0.547 |

13 | 31657 | 142 | 0.743 | 0.762 | 0.824 | 0.785 | 0.779 | 0.655 | 0.698 |

An implementation using a combination of four LCGs (the parameters are given in the table below) which provides improved structural properties is given in [142].

no. | 2 | 3 | 4 | 5 | 6 | 7 | 8 | ||

14 | 2147483647 | 45991 | 0.924 | 0.819 | 0.790 | 0.719 | 0.716 | 0.761 | 0.698 |

15 | 2147483543 | 207707 | 0.208 | 0.831 | 0.615 | 0.499 | 0.690 | 0.646 | 0.670 |

16 | 2147483423 | 138556 | 0.321 | 0.913 | 0.770 | 0.652 | 0.580 | 0.729 | 0.610 |

17 | 2147483323 | 49689 | 0.994 | 0.777 | 0.508 | 0.776 | 0.613 | 0.676 | 0.638 |

NAG PVM Library (G05AAFP) - cLCGs

The NAG PVM (parallel virtual machine) Library Chapter G05 contains parameters for 273 combined multiplicative LCGs, four LCGs combined respectively (for example the first combination consists of , , and ). The different generators are used to produce ``independent'' parallel PRNGs. This approach is based on the paper of MacLaren [161]. The ``independence'' is tested with a modified spectral test.