Efficient Xorshift skip ahead

Question

I need a fast random number generator that allows me to randomly access numbers at various positions of the random number sequence. I chose Xorshift, because it's fast and easy to implement.

To get a specific random number from the sequence, I implemented the following method (mPos saves the position of the next random number):

void XorshiftRandomGenerator::skipTo(unsigned int pos)
{
    // Reset if we passed the position
    if (mPos>pos)
        reset();

    // Generate random numbers until we're done
    while (mPos<pos)
        random();
}

A subsequent random() will return the desired number, but this method is very expensive. Is there a way to skip a large amount of random numbers with Xorshift, without calculating every random number in between?

As an alternative I could go with another random number generator. Could you suggest one that allows fast skipping ahead?

Answer 1

There is a 1994 Paper by Forest B. Brown called Random Number Generation with Arbitrary Strides which extensively deals with this topic.

As Nabb stated in the comments, a Linear Congruential Generator can be used for efficient skipping. Of course, the usual advantages and disadvantages of LNGs apply: the thing's simple and blazingly fast, but the pseudo-random numbers are not of very high quality. The formula is explained here in detail.

Answer 2

You can certainly jump in xorshift, and the process is described here, but I haven't read that for myself so I don't know how easy it is to follow.

Alternatively, you could look at PCG which offers a jump function by using an underlying LCG (the same as @Daerst's answer) but post-processes it to improve its statistical properties, or some of the splittable generators described here. The SplitMix generator, for example, has only an in-loop addition of a constant, so to jump an arbitrary distance you need only multiply the jump distance by the constant and add that (here's a SplitMix derivitive that apparently passes BigCrush).

Answer 3

You could use a hierarchy of random number generators. I.e. Every number you generate with generator A is used as a seed for generator B, which generates i.e. 100 numbers before it takes the next number from A to reinitialize itself and generates the next 100 numbers etc.. This way you could skip forward in steps by 100. You can of course cascade this into a tree of generators.