|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectjava.util.Random
it.unimi.dsi.util.XorShiftStarRandom
public class XorShiftStarRandom
A fast, high-quality 64-bit pseudorandom number generator that combines George Marsaglia's Xorshift
generators (described in “Xorshift RNGs”,
Journal of Statistical Software, 8:1−6, 2003) with a multiplication.
Note that this is not a cryptographic-strength
pseudorandom number generator, but its quality is preposterously higher than Random
's
(and its cycle length is 264 − 1).
On an Intel i5, calls to nextLong(long)
range from 20% faster to fifty times
faster than ThreadLocalRandom
's, and
calls to nextInt(int)
range from 20% slower to two times faster, depending on the argument.
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.
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).
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 from which we take only the multiplier (actually, proposed by Pierre L'Ecuyer in “Tables of linear congruential generators of different sizes and good lattice structure”, Math. Comput., 68(225):249−260, 1999). The remaining parameters have been set following 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 higher quality than the upper bits. Thus, masking the lower bits is a safe and effective way to obtain small random numbers. The code in this class methodically extracts lower bits, rather than upper bits, whenever a subset of bits is necessary.
Constructor Summary | |
---|---|
XorShiftStarRandom()
|
|
XorShiftStarRandom(long seed)
Creates a new generator using a given seed. |
Method Summary | |
---|---|
protected int |
next(int bits)
|
boolean |
nextBoolean()
|
void |
nextBytes(byte[] bytes)
|
double |
nextDouble()
|
float |
nextFloat()
|
int |
nextInt()
|
int |
nextInt(int n)
|
long |
nextLong()
|
long |
nextLong(long n)
|
void |
setSeed(long seed)
|
Methods inherited from class java.util.Random |
---|
nextGaussian |
Methods inherited from class java.lang.Object |
---|
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
Constructor Detail |
---|
public XorShiftStarRandom()
public XorShiftStarRandom(long seed)
seed
- a nonzero seed for the generator (if zero, the generator will be seeded with -1).Method Detail |
---|
protected int next(int bits)
next
in class Random
public long nextLong()
nextLong
in class Random
public int nextInt()
nextInt
in class Random
public int nextInt(int n)
nextInt
in class Random
public long nextLong(long n)
public double nextDouble()
nextDouble
in class Random
public float nextFloat()
nextFloat
in class Random
public boolean nextBoolean()
nextBoolean
in class Random
public void nextBytes(byte[] bytes)
nextBytes
in class Random
public void setSeed(long seed)
setSeed
in class Random
|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |