Leap-Frog Method - 5.2 English - 68552

AOCL API Guide (68552)
Document ID
68552
Release Date
2025-12-29
Version
5.2 English

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:

\[\begin{split}\begin{align} Subsequence 1& : x_1, x_{k+1}, x_{2k+1}, \dotsc \\ Subsequence 2& : x_2, x_{k+2}, x_{2k+2}, \dotsc \\ \ddots \\ Subsequence k& : x_k, x2k, x3k,\dotsc \end{align}\end{split}\]

each subsequence 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 LCG and MCG. The library provides leap-frogging for the NAG Basic generator, the Wichmann-Hill generators and MRG32K3A generator.

C Generate 3 * 100 values from the Uniform distribution
C Multiple streams generated using the Leap Frog method
    INTEGER LSTATE,N
    PARAMETER (LSTATE=16,N=100)
    INTEGER I,INFO
    INTEGER SEED(1),STATE1(LSTATE),STATE2(LSTATE),STATE3(LSTATE)
    DOUBLE PRECISION X1(N),X2(N),X3(N)
    DOUBLE PRECISION A,B

C Set the seed
    SEED(1) = 1234

C Set the distributional parameters
    A = 0.0D0
    B = 1.0D0

C Initialize the STATE1 vector
    CALL DRANDINITIALIZE(1,1,SEED,1,STATE1,LSTATE,INFO)

C Copy the STATE1 vector into other state vectors
    DO 20 I = 1,LSTATE
        STATE2(I) = STATE1(I)
        STATE3(I) = STATE1(I)
20  CONTINUE

C Update each stream so they generate every 3rd value
    CALL DRANDLEAPFROG(3,1,STATE1,INFO)
    CALL DRANDLEAPFROG(3,2,STATE2,INFO)
    CALL DRANDLEAPFROG(3,3,STATE3,INFO)

C Generate 3 sets of N variates from the Univariate distribution
    CALL DRANDUNIFORM(N,A,B,STATE1,X1,LDX,INFO)
    CALL DRANDUNIFORM(N,A,B,STATE2,X2,LDX,INFO)
    CALL DRANDUNIFORM(N,A,B,STATE3,X3,LDX,INFO)

C Print the results
    DO 40 I = 1,N
        WRITE(6,*) X1(I),X2(I),X3(I)
40  CONTINUE

Comparative Analysis

  • Different Seeds Method should be avoided in most of the cases.

  • Different Generators Method is only really of any practical use when using Wichmann-Hill Generator, and is then still limited to 273 streams.

  • Both Skipping-ahead and Leap-frogging work using the sequence from a single generator and both guarantee that the different sequences will not overlap and both can be scaled to an arbitrary number of streams.

  • Leap-frogging requires no a-priori knowledge about the number of variates being generated, whereas skip-ahead requires the user to know the maximum number (approximately) of variates required from each stream.

  • Skipping-ahead requires no a-priori information on the number of streams required. In contrast leap-frogging requires the user to know the maximum number of streams required, prior to generating the first value.

  • It is known that, dependent on the number of streams required, leap-frogging can lead to sequences with poor statistical properties, especially when applied to LCG.

  • For more complicated generators like MRG32K3A, leap-frogging can increase the time required to generate each variate compared to skipping-ahead. The additional time required by skipping-ahead occurs at the initialization stage, and not at the variate generation stage. Therefore in most instances skipping-ahead would be the preferred method for generating multiple sequences.

  • A LCG has the form \(x_{i+1}\ =\ a_1 x_i\ mod\ m1\). The recursive nature of a LCG means that

    \[\begin{split}\begin{align} x_{i+v}& = a_1 x_{i+v−1}\ mod\ m_1 \\ & = a_1(a_1 x_{i+v−2}\ mod\ m1)\ mod\ m_1 \\ & = a_2 x_{i+v−2}\ mod\ m_1 \\ & = a_1^v x_i\ mod\ m_1 \\ \end{align}\end{split}\]

    The sequence can be quickly advanced v places by multiplying the current state \((x_i)\) by \(a_1^v\ mod\ m_1\), hence allowing skipping-ahead. Leap-frogging is implemented by using \(a_k\), where k is the number of streams required, in place of \(a_1\) in the standard LCG recursive formula.

  • In a LCG the multiplier \(a_1\) 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 \(a_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 emphasized 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.