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?
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.
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).
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With