[RNG-97] JumpableUniformRandomProvider

• Type: New Feature
• Status: Closed
• Priority: Major
• Resolution: Implemented
• Affects Version/s: 1.3
• Fix Version/s: 1.3
• Component/s: client-api, core
• Assignee: Alex Herbert
• Reporter: Alex Herbert
• Created: 27/Apr/19 12:35
• Updated: 11/Nov/19 14:25
• Resolved: 10/Jun/19 20:10

Description

A feature of random number generators is their internal state is updated for every generation of a new random number. This is a single step. Some generators have the ability to compute the update to the state that is required to advance n steps. This is a jump. This can be supported using a new interface:

/**
 * Applies to generators that can be advanced a large number of 
 * steps of the output sequence in a single operation.
 */
public interface JumpableUniformRandomProvider
    extends UniformRandomProvider {
    /**
     * Creates a copy of the UniformRandomProvider and advances the
     * state of the copy. The state of the current instance is not altered. 
     * The state of the copy will be advanced an equivalent of {@code n}
     * sequential calls to a method that updates the state of the provider.
     *
     * @return the copy with an advanced state
     */
    JumpableUniformRandomProvider jump();
}

A suggestion for how to document an implementation is:

public class JumpableRNG implements JumpableUniformRandomProvider {
    /**
     * {@inheritDoc}
     *
     * <p>The jump size {@code n} is the equivalent of <pre>2<sup>32</sup></pre>
     * calls to {@link UniformRandomProvider#nextLong() nextLong()}.</p>
     */
    @Override
    public JumpableUniformRandomProvider jump() {
        return ...;
    }

    // etc.
}

Notes on the interface:

• A copy is returned
• The original is not altered and so multiple calls to jump will return the same generator with an advanced state

The intended use case is to create multiple copies of a RNG that will not overlap in sequence for use in parallel computations. A helper method can be added to RandomSource to facilitate this:

/**
 * Create a series of {@code n} generators by jumping from the source generator
 * {@code n} times. The resulting set of generators can be used in parallel
 * computations with a guarantee of no sequence overlap for at least the
 * length of the jump distance.
 *
 * <p>Note: The source generator state is not affected. Reuse of this
 * generator may overlap with output from the jump series.</p>
 *
 * @param source The source generator.
 * @param n The size of the series.
 */
public static UniformRandomProvider[] createJumpSeries(
        JumpableUniformRandomProvider source, int n) {
    if (n <= 0) {
        throw new IllegalArgumentException("Size must be strictly positive");
    }
    final UniformRandomProvider[] rngs = new UniformRandomProvider[n];
    for (int i = 0; i < n; i++) {
        source = source.jump();
        // Option to wrap the JumpableUniformRandomProvider to
        // restrict to the functionality of UniformRandomProvider
        rngs[i] = source;
    }
    return rngs;
}

Note: There is the possibility to wrap the jumped RNGs to restrict their functionality to UniformRandomProvider (or RestorableUniformRandomProvider). This prevents any of the series from being jumped again.

Issue Links

• links to: GitHub Pull Request #48