jaroslav@597: * If two instances of {@code Random} are created with the same jaroslav@597: * seed, and the same sequence of method calls is made for each, they jaroslav@597: * will generate and return identical sequences of numbers. In order to jaroslav@597: * guarantee this property, particular algorithms are specified for the jaroslav@597: * class {@code Random}. Java implementations must use all the algorithms jaroslav@597: * shown here for the class {@code Random}, for the sake of absolute jaroslav@597: * portability of Java code. However, subclasses of class {@code Random} jaroslav@597: * are permitted to use other algorithms, so long as they adhere to the jaroslav@597: * general contracts for all the methods. jaroslav@597: *
jaroslav@597: * The algorithms implemented by class {@code Random} use a jaroslav@597: * {@code protected} utility method that on each invocation can supply jaroslav@597: * up to 32 pseudorandomly generated bits. jaroslav@597: *
jaroslav@597: * Many applications will find the method {@link Math#random} simpler to use. jaroslav@597: * jaroslav@597: *
Instances of {@code java.util.Random} are threadsafe. jaroslav@597: * However, the concurrent use of the same {@code java.util.Random} jaroslav@597: * instance across threads may encounter contention and consequent jaroslav@597: * poor performance. Consider instead using jaroslav@597: * {@link java.util.concurrent.ThreadLocalRandom} in multithreaded jaroslav@597: * designs. jaroslav@597: * jaroslav@597: *
Instances of {@code java.util.Random} are not cryptographically jaroslav@597: * secure. Consider instead using {@link java.security.SecureRandom} to jaroslav@597: * get a cryptographically secure pseudo-random number generator for use jaroslav@597: * by security-sensitive applications. jaroslav@597: * jaroslav@597: * @author Frank Yellin jaroslav@597: * @since 1.0 jaroslav@597: */ jaroslav@597: public jaroslav@597: class Random implements java.io.Serializable { jaroslav@597: /** use serialVersionUID from JDK 1.1 for interoperability */ jaroslav@597: static final long serialVersionUID = 3905348978240129619L; jaroslav@597: jaroslav@597: /** jaroslav@597: * The internal state associated with this pseudorandom number generator. jaroslav@597: * (The specs for the methods in this class describe the ongoing jaroslav@597: * computation of this value.) jaroslav@597: */ jaroslav@599: private long seed; jaroslav@597: jaroslav@597: private static final long multiplier = 0x5DEECE66DL; jaroslav@597: private static final long addend = 0xBL; jaroslav@597: private static final long mask = (1L << 48) - 1; jaroslav@597: jaroslav@597: /** jaroslav@597: * Creates a new random number generator. This constructor sets jaroslav@597: * the seed of the random number generator to a value very likely jaroslav@597: * to be distinct from any other invocation of this constructor. jaroslav@597: */ jaroslav@597: public Random() { jaroslav@597: this(seedUniquifier() ^ System.nanoTime()); jaroslav@597: } jaroslav@599: jaroslav@599: private static synchronized long seedUniquifier() { jaroslav@597: // L'Ecuyer, "Tables of Linear Congruential Generators of jaroslav@597: // Different Sizes and Good Lattice Structure", 1999 jaroslav@599: long current = seedUniquifier; jaroslav@599: long next = current * 181783497276652981L; jaroslav@599: seedUniquifier = next; jaroslav@599: return next; jaroslav@597: } jaroslav@597: jaroslav@599: private static long seedUniquifier = 8682522807148012L; jaroslav@597: jaroslav@597: /** jaroslav@597: * Creates a new random number generator using a single {@code long} seed. jaroslav@597: * The seed is the initial value of the internal state of the pseudorandom jaroslav@597: * number generator which is maintained by method {@link #next}. jaroslav@597: * jaroslav@597: *
The invocation {@code new Random(seed)} is equivalent to: jaroslav@597: *
{@code
jaroslav@597: * Random rnd = new Random();
jaroslav@597: * rnd.setSeed(seed);}
jaroslav@597: *
jaroslav@597: * @param seed the initial seed
jaroslav@597: * @see #setSeed(long)
jaroslav@597: */
jaroslav@597: public Random(long seed) {
jaroslav@599: this.seed = initialScramble(seed);
jaroslav@597: }
jaroslav@597:
jaroslav@597: private static long initialScramble(long seed) {
jaroslav@597: return (seed ^ multiplier) & mask;
jaroslav@597: }
jaroslav@597:
jaroslav@597: /**
jaroslav@597: * Sets the seed of this random number generator using a single
jaroslav@597: * {@code long} seed. The general contract of {@code setSeed} is
jaroslav@597: * that it alters the state of this random number generator object
jaroslav@597: * so as to be in exactly the same state as if it had just been
jaroslav@597: * created with the argument {@code seed} as a seed. The method
jaroslav@597: * {@code setSeed} is implemented by class {@code Random} by
jaroslav@597: * atomically updating the seed to
jaroslav@597: * {@code (seed ^ 0x5DEECE66DL) & ((1L << 48) - 1)}
jaroslav@597: * and clearing the {@code haveNextNextGaussian} flag used by {@link
jaroslav@597: * #nextGaussian}.
jaroslav@597: *
jaroslav@597: * The implementation of {@code setSeed} by class {@code Random} jaroslav@597: * happens to use only 48 bits of the given seed. In general, however, jaroslav@597: * an overriding method may use all 64 bits of the {@code long} jaroslav@597: * argument as a seed value. jaroslav@597: * jaroslav@597: * @param seed the initial seed jaroslav@597: */ jaroslav@597: synchronized public void setSeed(long seed) { jaroslav@599: this.seed = initialScramble(seed); jaroslav@597: haveNextNextGaussian = false; jaroslav@597: } jaroslav@597: jaroslav@597: /** jaroslav@597: * Generates the next pseudorandom number. Subclasses should jaroslav@597: * override this, as this is used by all other methods. jaroslav@597: * jaroslav@597: *
The general contract of {@code next} is that it returns an jaroslav@597: * {@code int} value and if the argument {@code bits} is between jaroslav@597: * {@code 1} and {@code 32} (inclusive), then that many low-order jaroslav@597: * bits of the returned value will be (approximately) independently jaroslav@597: * chosen bit values, each of which is (approximately) equally jaroslav@597: * likely to be {@code 0} or {@code 1}. The method {@code next} is jaroslav@597: * implemented by class {@code Random} by atomically updating the seed to jaroslav@597: *
{@code (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1)}
jaroslav@597: * and returning
jaroslav@597: * {@code (int)(seed >>> (48 - bits))}.
jaroslav@597: *
jaroslav@597: * This is a linear congruential pseudorandom number generator, as
jaroslav@597: * defined by D. H. Lehmer and described by Donald E. Knuth in
jaroslav@597: * The Art of Computer Programming, Volume 3:
jaroslav@597: * Seminumerical Algorithms, section 3.2.1.
jaroslav@597: *
jaroslav@597: * @param bits random bits
jaroslav@597: * @return the next pseudorandom value from this random number
jaroslav@597: * generator's sequence
jaroslav@597: * @since 1.1
jaroslav@597: */
jaroslav@599: protected synchronized int next(int bits) {
jaroslav@597: long oldseed, nextseed;
jaroslav@599: long seed = this.seed;
jaroslav@599: oldseed = seed;
jaroslav@599: nextseed = (oldseed * multiplier + addend) & mask;
jaroslav@599: this.seed = nextseed;
jaroslav@597: return (int)(nextseed >>> (48 - bits));
jaroslav@597: }
jaroslav@597:
jaroslav@597: /**
jaroslav@597: * Generates random bytes and places them into a user-supplied
jaroslav@597: * byte array. The number of random bytes produced is equal to
jaroslav@597: * the length of the byte array.
jaroslav@597: *
jaroslav@597: * The method {@code nextBytes} is implemented by class {@code Random} jaroslav@597: * as if by: jaroslav@597: *
{@code
jaroslav@597: * public void nextBytes(byte[] bytes) {
jaroslav@597: * for (int i = 0; i < bytes.length; )
jaroslav@597: * for (int rnd = nextInt(), n = Math.min(bytes.length - i, 4);
jaroslav@597: * n-- > 0; rnd >>= 8)
jaroslav@597: * bytes[i++] = (byte)rnd;
jaroslav@597: * }}
jaroslav@597: *
jaroslav@597: * @param bytes the byte array to fill with random bytes
jaroslav@597: * @throws NullPointerException if the byte array is null
jaroslav@597: * @since 1.1
jaroslav@597: */
jaroslav@597: public void nextBytes(byte[] bytes) {
jaroslav@597: for (int i = 0, len = bytes.length; i < len; )
jaroslav@597: for (int rnd = nextInt(),
jaroslav@597: n = Math.min(len - i, Integer.SIZE/Byte.SIZE);
jaroslav@597: n-- > 0; rnd >>= Byte.SIZE)
jaroslav@597: bytes[i++] = (byte)rnd;
jaroslav@597: }
jaroslav@597:
jaroslav@597: /**
jaroslav@597: * Returns the next pseudorandom, uniformly distributed {@code int}
jaroslav@597: * value from this random number generator's sequence. The general
jaroslav@597: * contract of {@code nextInt} is that one {@code int} value is
jaroslav@597: * pseudorandomly generated and returned. All 232
jaroslav@597: * possible {@code int} values are produced with
jaroslav@597: * (approximately) equal probability.
jaroslav@597: *
jaroslav@597: * The method {@code nextInt} is implemented by class {@code Random} jaroslav@597: * as if by: jaroslav@597: *
{@code
jaroslav@597: * public int nextInt() {
jaroslav@597: * return next(32);
jaroslav@597: * }}
jaroslav@597: *
jaroslav@597: * @return the next pseudorandom, uniformly distributed {@code int}
jaroslav@597: * value from this random number generator's sequence
jaroslav@597: */
jaroslav@597: public int nextInt() {
jaroslav@597: return next(32);
jaroslav@597: }
jaroslav@597:
jaroslav@597: /**
jaroslav@597: * Returns a pseudorandom, uniformly distributed {@code int} value
jaroslav@597: * between 0 (inclusive) and the specified value (exclusive), drawn from
jaroslav@597: * this random number generator's sequence. The general contract of
jaroslav@597: * {@code nextInt} is that one {@code int} value in the specified range
jaroslav@597: * is pseudorandomly generated and returned. All {@code n} possible
jaroslav@597: * {@code int} values are produced with (approximately) equal
jaroslav@597: * probability. The method {@code nextInt(int n)} is implemented by
jaroslav@597: * class {@code Random} as if by:
jaroslav@597: * {@code
jaroslav@597: * public int nextInt(int n) {
jaroslav@597: * if (n <= 0)
jaroslav@597: * throw new IllegalArgumentException("n must be positive");
jaroslav@597: *
jaroslav@597: * if ((n & -n) == n) // i.e., n is a power of 2
jaroslav@597: * return (int)((n * (long)next(31)) >> 31);
jaroslav@597: *
jaroslav@597: * int bits, val;
jaroslav@597: * do {
jaroslav@597: * bits = next(31);
jaroslav@597: * val = bits % n;
jaroslav@597: * } while (bits - val + (n-1) < 0);
jaroslav@597: * return val;
jaroslav@597: * }}
jaroslav@597: *
jaroslav@597: * The hedge "approximately" is used in the foregoing description only jaroslav@597: * because the next method is only approximately an unbiased source of jaroslav@597: * independently chosen bits. If it were a perfect source of randomly jaroslav@597: * chosen bits, then the algorithm shown would choose {@code int} jaroslav@597: * values from the stated range with perfect uniformity. jaroslav@597: *
jaroslav@597: * The algorithm is slightly tricky. It rejects values that would result jaroslav@597: * in an uneven distribution (due to the fact that 2^31 is not divisible jaroslav@597: * by n). The probability of a value being rejected depends on n. The jaroslav@597: * worst case is n=2^30+1, for which the probability of a reject is 1/2, jaroslav@597: * and the expected number of iterations before the loop terminates is 2. jaroslav@597: *
jaroslav@597: * The algorithm treats the case where n is a power of two specially: it jaroslav@597: * returns the correct number of high-order bits from the underlying jaroslav@597: * pseudo-random number generator. In the absence of special treatment, jaroslav@597: * the correct number of low-order bits would be returned. Linear jaroslav@597: * congruential pseudo-random number generators such as the one jaroslav@597: * implemented by this class are known to have short periods in the jaroslav@597: * sequence of values of their low-order bits. Thus, this special case jaroslav@597: * greatly increases the length of the sequence of values returned by jaroslav@597: * successive calls to this method if n is a small power of two. jaroslav@597: * jaroslav@597: * @param n the bound on the random number to be returned. Must be jaroslav@597: * positive. jaroslav@597: * @return the next pseudorandom, uniformly distributed {@code int} jaroslav@597: * value between {@code 0} (inclusive) and {@code n} (exclusive) jaroslav@597: * from this random number generator's sequence jaroslav@597: * @throws IllegalArgumentException if n is not positive jaroslav@597: * @since 1.2 jaroslav@597: */ jaroslav@597: jaroslav@597: public int nextInt(int n) { jaroslav@597: if (n <= 0) jaroslav@597: throw new IllegalArgumentException("n must be positive"); jaroslav@597: jaroslav@597: if ((n & -n) == n) // i.e., n is a power of 2 jaroslav@597: return (int)((n * (long)next(31)) >> 31); jaroslav@597: jaroslav@597: int bits, val; jaroslav@597: do { jaroslav@597: bits = next(31); jaroslav@597: val = bits % n; jaroslav@597: } while (bits - val + (n-1) < 0); jaroslav@597: return val; jaroslav@597: } jaroslav@597: jaroslav@597: /** jaroslav@597: * Returns the next pseudorandom, uniformly distributed {@code long} jaroslav@597: * value from this random number generator's sequence. The general jaroslav@597: * contract of {@code nextLong} is that one {@code long} value is jaroslav@597: * pseudorandomly generated and returned. jaroslav@597: * jaroslav@597: *
The method {@code nextLong} is implemented by class {@code Random} jaroslav@597: * as if by: jaroslav@597: *
{@code
jaroslav@597: * public long nextLong() {
jaroslav@597: * return ((long)next(32) << 32) + next(32);
jaroslav@597: * }}
jaroslav@597: *
jaroslav@597: * Because class {@code Random} uses a seed with only 48 bits,
jaroslav@597: * this algorithm will not return all possible {@code long} values.
jaroslav@597: *
jaroslav@597: * @return the next pseudorandom, uniformly distributed {@code long}
jaroslav@597: * value from this random number generator's sequence
jaroslav@597: */
jaroslav@597: public long nextLong() {
jaroslav@597: // it's okay that the bottom word remains signed.
jaroslav@597: return ((long)(next(32)) << 32) + next(32);
jaroslav@597: }
jaroslav@597:
jaroslav@597: /**
jaroslav@597: * Returns the next pseudorandom, uniformly distributed
jaroslav@597: * {@code boolean} value from this random number generator's
jaroslav@597: * sequence. The general contract of {@code nextBoolean} is that one
jaroslav@597: * {@code boolean} value is pseudorandomly generated and returned. The
jaroslav@597: * values {@code true} and {@code false} are produced with
jaroslav@597: * (approximately) equal probability.
jaroslav@597: *
jaroslav@597: * The method {@code nextBoolean} is implemented by class {@code Random} jaroslav@597: * as if by: jaroslav@597: *
{@code
jaroslav@597: * public boolean nextBoolean() {
jaroslav@597: * return next(1) != 0;
jaroslav@597: * }}
jaroslav@597: *
jaroslav@597: * @return the next pseudorandom, uniformly distributed
jaroslav@597: * {@code boolean} value from this random number generator's
jaroslav@597: * sequence
jaroslav@597: * @since 1.2
jaroslav@597: */
jaroslav@597: public boolean nextBoolean() {
jaroslav@597: return next(1) != 0;
jaroslav@597: }
jaroslav@597:
jaroslav@597: /**
jaroslav@597: * Returns the next pseudorandom, uniformly distributed {@code float}
jaroslav@597: * value between {@code 0.0} and {@code 1.0} from this random
jaroslav@597: * number generator's sequence.
jaroslav@597: *
jaroslav@597: * The general contract of {@code nextFloat} is that one jaroslav@597: * {@code float} value, chosen (approximately) uniformly from the jaroslav@597: * range {@code 0.0f} (inclusive) to {@code 1.0f} (exclusive), is jaroslav@597: * pseudorandomly generated and returned. All 224 possible {@code float} values jaroslav@597: * of the form m x 2-24, where m is a positive jaroslav@597: * integer less than 224 , are jaroslav@597: * produced with (approximately) equal probability. jaroslav@597: * jaroslav@597: *
The method {@code nextFloat} is implemented by class {@code Random} jaroslav@597: * as if by: jaroslav@597: *
{@code
jaroslav@597: * public float nextFloat() {
jaroslav@597: * return next(24) / ((float)(1 << 24));
jaroslav@597: * }}
jaroslav@597: *
jaroslav@597: * The hedge "approximately" is used in the foregoing description only jaroslav@597: * because the next method is only approximately an unbiased source of jaroslav@597: * independently chosen bits. If it were a perfect source of randomly jaroslav@597: * chosen bits, then the algorithm shown would choose {@code float} jaroslav@597: * values from the stated range with perfect uniformity.
jaroslav@597: * [In early versions of Java, the result was incorrectly calculated as: jaroslav@597: *
{@code
jaroslav@597: * return next(30) / ((float)(1 << 30));}
jaroslav@597: * This might seem to be equivalent, if not better, but in fact it
jaroslav@597: * introduced a slight nonuniformity because of the bias in the rounding
jaroslav@597: * of floating-point numbers: it was slightly more likely that the
jaroslav@597: * low-order bit of the significand would be 0 than that it would be 1.]
jaroslav@597: *
jaroslav@597: * @return the next pseudorandom, uniformly distributed {@code float}
jaroslav@597: * value between {@code 0.0} and {@code 1.0} from this
jaroslav@597: * random number generator's sequence
jaroslav@597: */
jaroslav@597: public float nextFloat() {
jaroslav@597: return next(24) / ((float)(1 << 24));
jaroslav@597: }
jaroslav@597:
jaroslav@597: /**
jaroslav@597: * Returns the next pseudorandom, uniformly distributed
jaroslav@597: * {@code double} value between {@code 0.0} and
jaroslav@597: * {@code 1.0} from this random number generator's sequence.
jaroslav@597: *
jaroslav@597: * The general contract of {@code nextDouble} is that one jaroslav@597: * {@code double} value, chosen (approximately) uniformly from the jaroslav@597: * range {@code 0.0d} (inclusive) to {@code 1.0d} (exclusive), is jaroslav@597: * pseudorandomly generated and returned. jaroslav@597: * jaroslav@597: *
The method {@code nextDouble} is implemented by class {@code Random} jaroslav@597: * as if by: jaroslav@597: *
{@code
jaroslav@597: * public double nextDouble() {
jaroslav@597: * return (((long)next(26) << 27) + next(27))
jaroslav@597: * / (double)(1L << 53);
jaroslav@597: * }}
jaroslav@597: *
jaroslav@597: * The hedge "approximately" is used in the foregoing description only jaroslav@597: * because the {@code next} method is only approximately an unbiased jaroslav@597: * source of independently chosen bits. If it were a perfect source of jaroslav@597: * randomly chosen bits, then the algorithm shown would choose jaroslav@597: * {@code double} values from the stated range with perfect uniformity. jaroslav@597: *
[In early versions of Java, the result was incorrectly calculated as: jaroslav@597: *
{@code
jaroslav@597: * return (((long)next(27) << 27) + next(27))
jaroslav@597: * / (double)(1L << 54);}
jaroslav@597: * This might seem to be equivalent, if not better, but in fact it
jaroslav@597: * introduced a large nonuniformity because of the bias in the rounding
jaroslav@597: * of floating-point numbers: it was three times as likely that the
jaroslav@597: * low-order bit of the significand would be 0 than that it would be 1!
jaroslav@597: * This nonuniformity probably doesn't matter much in practice, but we
jaroslav@597: * strive for perfection.]
jaroslav@597: *
jaroslav@597: * @return the next pseudorandom, uniformly distributed {@code double}
jaroslav@597: * value between {@code 0.0} and {@code 1.0} from this
jaroslav@597: * random number generator's sequence
jaroslav@597: * @see Math#random
jaroslav@597: */
jaroslav@597: public double nextDouble() {
jaroslav@597: return (((long)(next(26)) << 27) + next(27))
jaroslav@597: / (double)(1L << 53);
jaroslav@597: }
jaroslav@597:
jaroslav@597: private double nextNextGaussian;
jaroslav@597: private boolean haveNextNextGaussian = false;
jaroslav@597:
jaroslav@597: /**
jaroslav@597: * Returns the next pseudorandom, Gaussian ("normally") distributed
jaroslav@597: * {@code double} value with mean {@code 0.0} and standard
jaroslav@597: * deviation {@code 1.0} from this random number generator's sequence.
jaroslav@597: * jaroslav@597: * The general contract of {@code nextGaussian} is that one jaroslav@597: * {@code double} value, chosen from (approximately) the usual jaroslav@597: * normal distribution with mean {@code 0.0} and standard deviation jaroslav@597: * {@code 1.0}, is pseudorandomly generated and returned. jaroslav@597: * jaroslav@597: *
The method {@code nextGaussian} is implemented by class jaroslav@597: * {@code Random} as if by a threadsafe version of the following: jaroslav@597: *
{@code
jaroslav@597: * private double nextNextGaussian;
jaroslav@597: * private boolean haveNextNextGaussian = false;
jaroslav@597: *
jaroslav@597: * public double nextGaussian() {
jaroslav@597: * if (haveNextNextGaussian) {
jaroslav@597: * haveNextNextGaussian = false;
jaroslav@597: * return nextNextGaussian;
jaroslav@597: * } else {
jaroslav@597: * double v1, v2, s;
jaroslav@597: * do {
jaroslav@597: * v1 = 2 * nextDouble() - 1; // between -1.0 and 1.0
jaroslav@597: * v2 = 2 * nextDouble() - 1; // between -1.0 and 1.0
jaroslav@597: * s = v1 * v1 + v2 * v2;
jaroslav@597: * } while (s >= 1 || s == 0);
jaroslav@597: * double multiplier = StrictMath.sqrt(-2 * StrictMath.log(s)/s);
jaroslav@597: * nextNextGaussian = v2 * multiplier;
jaroslav@597: * haveNextNextGaussian = true;
jaroslav@597: * return v1 * multiplier;
jaroslav@597: * }
jaroslav@597: * }}
jaroslav@597: * This uses the polar method of G. E. P. Box, M. E. Muller, and
jaroslav@597: * G. Marsaglia, as described by Donald E. Knuth in The Art of
jaroslav@597: * Computer Programming, Volume 3: Seminumerical Algorithms,
jaroslav@597: * section 3.4.1, subsection C, algorithm P. Note that it generates two
jaroslav@597: * independent values at the cost of only one call to {@code StrictMath.log}
jaroslav@597: * and one call to {@code StrictMath.sqrt}.
jaroslav@597: *
jaroslav@597: * @return the next pseudorandom, Gaussian ("normally") distributed
jaroslav@597: * {@code double} value with mean {@code 0.0} and
jaroslav@597: * standard deviation {@code 1.0} from this random number
jaroslav@597: * generator's sequence
jaroslav@597: */
jaroslav@597: synchronized public double nextGaussian() {
jaroslav@597: // See Knuth, ACP, Section 3.4.1 Algorithm C.
jaroslav@597: if (haveNextNextGaussian) {
jaroslav@597: haveNextNextGaussian = false;
jaroslav@597: return nextNextGaussian;
jaroslav@597: } else {
jaroslav@597: double v1, v2, s;
jaroslav@597: do {
jaroslav@597: v1 = 2 * nextDouble() - 1; // between -1 and 1
jaroslav@597: v2 = 2 * nextDouble() - 1; // between -1 and 1
jaroslav@597: s = v1 * v1 + v2 * v2;
jaroslav@597: } while (s >= 1 || s == 0);
jaroslav@599: double multiplier = Math.sqrt(-2 * Math.log(s)/s);
jaroslav@597: nextNextGaussian = v2 * multiplier;
jaroslav@597: haveNextNextGaussian = true;
jaroslav@597: return v1 * multiplier;
jaroslav@597: }
jaroslav@597: }
jaroslav@597: }