Previous: Skip Ahead, Up: Multiple Streams

6.2.4 Leap Frogging

Independent sequences of variates can be generated from a single base generator through the use of leap-frogging. This method involves splitting the sequence from a single generator into k disjoint subsequences. For example: Subsequence 1: x(1),x(k + 1),x(2 * k + 1), ..., Subsequence 2: x(2),x(k + 3),x(2 * k + 3), ..., Subsequence k: x(k),x(2 * k),x(3 * k), ... each subsequence is then provides an independent stream.

The leap-frog algorithm therefore requires the generation of every kth variate of a sequence. Due to their form this can be done efficiently for linear congruential generators and multiple congruential generators. The ACML provides leap-frogging for the NAG Basic generator, the Wichmann-Hill generators and L'Ecuyer's Combined Recursive generator.

As an illustrative example, a brief description of the algebra behind the implementation of the leap-frog algorithm (and block-splitting algorithm) for a linear congruential generator (LCG) will be given. A linear congruential generator has the form x(i+1) = a1 * x(i) mod m1. The recursive nature of a LCG means that x(i + v) = a1 * x(i + v - 1) mod m1 = a1 * [a1 * x(i + v - 2) mod m1] mod m1 = a1^2 * x(i + v - 2) mod m1 = a1^v * x(i) mod m1. The sequence can be quickly advanced v places by multiplying the current state (x(i)), by a1^v mod m1, hence allowing block-splitting. Leap-frogging is implemented by using a1^k where k is the number of streams required, in place of a1 in the standard LCG recursive formula. In a linear congruential generator the multiplier a1 is constructed so that the generator has good statistical properties in, for example, the spectral test. When using leap-frogging to construct multiple streams this multiplier is replaced with a1^k and there is no guarantee that this new multiplier will have suitable properties especially as the value of k depends on the number of streams required and so is likely to change depending on the application. This problem can be emphasised by the lattice structure of LCGs.

Note that, due to rounding, a sequence generated using leap-frogging and a sequence constructed by taking every kth value from a set of variates generated without leap-frogging may differ slightly. These differences should only affect the least significant digit.