de.lmu.ifi.dbs.elki.utilities.random

Class FastNonThreadsafeRandom

java.lang.Object

java.util.Random

de.lmu.ifi.dbs.elki.utilities.random.FastNonThreadsafeRandom

All Implemented Interfaces:

java.io.Serializable

public class FastNonThreadsafeRandom
extends java.util.Random

Drop-in replacement for Random, but not using atomic long seeds. This implementation is no longer thread-safe (but faster)!

It is still the same Linear Congruential Generator (LCG), with a cycle length of 2⁴⁸, of which we only use 32 bits at a time. Given the same seed, it is expected to produce the exact same random sequence as Java's Random.

Since:

0.6.0

Author:

Erich Schubert

See Also:

Serialized Form

Field Summary

Fields

Modifier and Type	Field and Description
private static long	addend
protected static java.lang.String	BADBOUND Exception message for non-positive bounds
private static long	mask
private static long	multiplier
private long	seed The random seed.
private static long	serialVersionUID Serial version number.

Constructor Summary

Constructors

Constructor and Description
FastNonThreadsafeRandom() Constructor called only by localRandom.initialValue.
FastNonThreadsafeRandom(long seed) Constructor.

Method Summary

Modifier and Type	Method and Description
protected int	next(int bits)
double	nextDouble()
int	nextInt()
int	nextInt(int n) Returns a pseudorandom, uniformly distributed int value between 0 (inclusive) and the specified value (exclusive), drawn from this random number generator's sequence.
int	nextIntRefined(int n) Returns a pseudorandom, uniformly distributed int value between 0 (inclusive) and the specified value (exclusive), drawn from this random number generator's sequence.
void	setSeed(long seed)

Methods inherited from class java.util.Random

doubles, doubles, doubles, doubles, ints, ints, ints, ints, longs, longs, longs, longs, nextBoolean, nextBytes, nextFloat, nextGaussian, nextLong

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

serialVersionUID

private static final long serialVersionUID

Serial version number.

See Also:

Constant Field Values

multiplier

private static final long multiplier

See Also:

Constant Field Values

addend

private static final long addend

See Also:

Constant Field Values

mask

private static final long mask

See Also:

Constant Field Values

seed

private long seed

The random seed. We can't use super.seed.

BADBOUND

protected static final java.lang.String BADBOUND

Exception message for non-positive bounds

See Also:

Constant Field Values

Constructor Detail

FastNonThreadsafeRandom

public FastNonThreadsafeRandom()

Constructor called only by localRandom.initialValue.

FastNonThreadsafeRandom

public FastNonThreadsafeRandom(long seed)

Constructor.

Parameters:

seed - Random generator seed.

Method Detail

setSeed

public void setSeed(long seed)

Overrides:

setSeed in class java.util.Random

next

protected int next(int bits)

Overrides:

next in class java.util.Random

nextInt

public int nextInt()

Overrides:

nextInt in class java.util.Random

nextDouble

public double nextDouble()

Overrides:

nextDouble in class java.util.Random

nextInt

@Reference(authors="D. Lemire",
           title="Fast random shuffling",
           booktitle="Daniel Lemire\'s blog",
           url="http://lemire.me/blog/2016/06/30/fast-random-shuffling/",
           bibkey="blog/Lemire16")
public int nextInt(int n)

Returns a pseudorandom, uniformly distributed int value between 0 (inclusive) and the specified value (exclusive), drawn from this random number generator's sequence. The general contract of nextInt is that one int value in the specified range is pseudorandomly generated and returned. All n possible int values are produced with (approximately) equal probability.

In contrast to the Java version, we use an approach that tries to avoid divisions for performance. We will have a slightly worse distribution in this fast version (see the XorShift generators for higher quality with rejection sampling) discussed in:

D. Lemire
Fast random shuffling
http://lemire.me/blog/2016/06/30/fast-random-shuffling/

Overrides:

nextInt in class java.util.Random

nextIntRefined

@Reference(authors="D. Lemire",
           title="Fast random shuffling",
           booktitle="Daniel Lemire\'s blog",
           url="http://lemire.me/blog/2016/06/30/fast-random-shuffling/",
           bibkey="blog/Lemire16")
public int nextIntRefined(int n)

Returns a pseudorandom, uniformly distributed int value between 0 (inclusive) and the specified value (exclusive), drawn from this random number generator's sequence. The general contract of nextInt is that one int value in the specified range is pseudorandomly generated and returned. All n possible int values are produced with (approximately) equal probability.

In contrast to the Java version, we use an approach that tries to avoid divisions for performance. In this method, we also employ rejection sampling (for marginal improvement) as discussed in:

D. Lemire
Fast random shuffling
http://lemire.me/blog/2016/06/30/fast-random-shuffling/

In our experiments, the difference was negligible, as the rejections are quite rare events at least for our use case.