public class XorShiftStarRandom extends Random
Random's
(and its cycle length is 264 − 1, more than enough for 99.9% applications).
On an Intel i7 at 2.6 GHz, all methods of this class except for nextInt() are faster than
those of ThreadLocalRandom.
Timings are orders of magnitude faster than Random's, but Random is slowed down by the
fact of being thread safe, so the comparison is not fair. The following table reports timings
in nanoseconds for some type of calls:
ThreadLocalRandom
| XorShiftStarRandom
| ||
|---|---|---|---|
| nextInt() | 1.52 | 2.00 | |
| nextLong() | 3.16 | 1.99 | |
| nextDouble() | 3.27 | 2.27 | |
| nextInt(1000000) | 3.54 | 2.91 | |
| nextInt(2^29+2^28) | 7.29 | 2.94 | |
| nextInt(2^30) | 3.29 | 2.15 | |
| nextInt(2^30+1) | 14.03 | 3.32 | |
| nextInt(2^30+2^29-1) | 7.28 | 2.87 | |
| nextInt(2^30+2^29) | 7.25 | 2.93 | |
| nextLong(1000000000000) | 81.30 | 3.80 | |
| nextLong(2^62+1) | 251.89 | 14.69 |
The quality of this generator is high: for instance, it performs significantly better than WELL1024a (itself an
improvement over the Mersenne Twister) in suites like
TestU01 and
Dieharder (more precisely, over 100 runs of the BigCrush test suite
starting from equispaced points of the state space, this generator and its reverse fail 368 tests, whereas WELL1024a and its reverse
fail 882 tests; in both cases the only test that is failed at all points is MatrixRank; Random and its reverse fail 13564 tests of all kind).
Moreover, the memory usage is the smallest possible: a single long.
This class extends Random, overriding (as usual) the Random.next(int) method. Nonetheless,
since the generator is inherently 64-bit also Random.nextInt(), Random.nextInt(int),
Random.nextLong() and Random.nextDouble() have been overridden for speed (preserving, of course, Random's semantics).
See in particular the comments in the documentation of nextInt(int), which is tailored for speed at the price of an essentially undetectable bias.
If you do not need an instance of Random, or if you need a RandomGenerator to use
with Commons Math, you might be wanting
XorShiftStarRandomGenerator instead of this class.
There are five parameters to choose in a pseudorandom number generator of this kind: the three shift values, the type of shift, and the multiplier. Numerical Recipes (third edition, Cambridge University Press, 2007) suggests a choice of parameters which gives a generator of lower quality than that implemented by this class (in the same settings as above, it fails 463 tests including BirthdaySpacing at all points). We have experimented with different multipliers proposed by Pierre L'Ecuyer (“Tables of linear congruential generators of different sizes and good lattice structure”, Math. Comput., 68(225):249−260, 1999), and set the other parameters by extensive experimentation on the 2200 possible choices using TestU01 and Dieharder. More details will appear in a forthcoming paper.
Warning: this class is still experimental, and different parameters might be used in the future.
The lower bits of this generator are of slightly better quality than the higher bits. Thus, masking the lower bits is a safe and effective way to obtain small random numbers. The code in this class usually extracts lower bits, rather than upper bits, whenever a subset of bits is necessary (when extracting 63 bits we use a right shift for performance reasons, though).
| Constructor and Description |
|---|
XorShiftStarRandom()
Creates a new generator seeded using
Util.randomSeed(). |
XorShiftStarRandom(long seed)
Creates a new generator using a given seed.
|
| Modifier and Type | Method and Description |
|---|---|
protected int |
next(int bits) |
boolean |
nextBoolean() |
void |
nextBytes(byte[] bytes) |
double |
nextDouble() |
float |
nextFloat() |
int |
nextInt() |
int |
nextInt(int n)
Returns a pseudorandom, approximately uniformly distributed
int value
between 0 (inclusive) and the specified value (exclusive), drawn from
this random number generator's sequence. |
long |
nextLong() |
long |
nextLong(long n)
Returns a pseudorandom uniformly distributed
long value
between 0 (inclusive) and the specified value (exclusive), drawn from
this random number generator's sequence. |
void |
setSeed(long seed) |
nextGaussianpublic XorShiftStarRandom()
Util.randomSeed().public XorShiftStarRandom(long seed)
seed - a nonzero seed for the generator (if zero, the generator will be seeded with -1).public int nextInt(int n)
int value
between 0 (inclusive) and the specified value (exclusive), drawn from
this random number generator's sequence.
The hedge “approximately” is due to the fact that to be always
faster than ThreadLocalRandom
we return
the upper 63 bits of nextLong() modulo n instead of using
Random's fancy algorithm (which nextLong(long) uses though).
This choice introduces a bias: the numbers from 0 to 263 mod n
are slightly more likely than the other ones. In the worst case, “more likely”
means 1.00000000023 times more likely, which is in practice undetectable (actually,
due to the abysmally low quality of Random's generator, the result is statistically
better in any case than Random.nextInt(int)'s) .
If for some reason you need truly uniform generation, just use nextLong(long).
public long nextLong(long n)
long value
between 0 (inclusive) and the specified value (exclusive), drawn from
this random number generator's sequence. The algorithm used to generate
the value guarantees that the result is uniform, provided that the
sequence of 64-bit values produced by this generator is.n - the positive bound on the random number to be returned.long value between 0 (inclusive) and n (exclusive).public double nextDouble()
nextDouble in class Randompublic boolean nextBoolean()
nextBoolean in class Random