diff options
Diffstat (limited to 'libjava/java/util/Random.java')
| -rw-r--r-- | libjava/java/util/Random.java | 417 |
1 files changed, 323 insertions, 94 deletions
diff --git a/libjava/java/util/Random.java b/libjava/java/util/Random.java index 5ed4532050a..aa25a697d65 100644 --- a/libjava/java/util/Random.java +++ b/libjava/java/util/Random.java @@ -1,150 +1,379 @@ -/* Copyright (C) 1998, 1999 Free Software Foundation +/* java.util.Random + Copyright (C) 1998, 1999, 2000, 2001 Free Software Foundation, Inc. - This file is part of libgcj. +This file is part of GNU Classpath. -This software is copyrighted work licensed under the terms of the -Libgcj License. Please consult the file "LIBGCJ_LICENSE" for -details. */ +GNU Classpath is free software; you can redistribute it and/or modify +it under the terms of the GNU General Public License as published by +the Free Software Foundation; either version 2, or (at your option) +any later version. -package java.util; +GNU Classpath is distributed in the hope that it will be useful, but +WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +General Public License for more details. + +You should have received a copy of the GNU General Public License +along with GNU Classpath; see the file COPYING. If not, write to the +Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA +02111-1307 USA. + +As a special exception, if you link this library with other files to +produce an executable, this library does not by itself cause the +resulting executable to be covered by the GNU General Public License. +This exception does not however invalidate any other reasons why the +executable file might be covered by the GNU General Public License. */ -import java.io.Serializable; + +package java.util; /** - * @author Warren Levy <warrenl@cygnus.com> - * @date August 25, 1998. - */ -/* Written using "Java Class Libraries", 2nd edition, ISBN 0-201-31002-3 - * "The Java Language Specification", ISBN 0-201-63451-1 - * plus online API docs for JDK 1.2 beta from http://www.javasoft.com. - * Status: Believed complete and correct - */ - -/* This class is completely specified by the spec to ensure absolute - * portability between all implementations of Java - */ -public class Random implements Serializable + * This class generates pseudorandom numbers. It uses the same + * algorithm as the original JDK-class, so that your programs behave + * exactly the same way, if started with the same seed. + * + * The algorithm is described in <em>The Art of Computer Programming, + * Volume 2</em> by Donald Knuth in Section 3.2.1. + * + * If two instances of this class are created with the same seed and + * the same calls to these classes are made, they behave exactly the + * same way. This should be even true for foreign implementations + * (like this), so every port must use the same algorithm as described + * here. + * + * If you want to implement your own pseudorandom algorithm, you + * should extend this class and overload the <code>next()</code> and + * <code>setSeed(long)</code> method. In that case the above + * paragraph doesn't apply to you. + * + * This class shouldn't be used for security sensitive purposes (like + * generating passwords or encryption keys. See <code>SecureRandom</code> + * in package <code>java.security</code> for this purpose. + * + * For simple random doubles between 0.0 and 1.0, you may consider using + * Math.random instead. + * + * @see java.security.SecureRandom + * @see Math#random() + * @author Jochen Hoenicke */ +public class Random implements java.io.Serializable { - /* Used by next() to hold the state of the pseudorandom number generator */ - private long seed; - - /* Used by nextGaussian() to hold a precomputed value */ - /* to be delivered by that method the next time it is called */ + /** + * True if the next nextGaussian is available. This is used by + * nextGaussian, which generates two gaussian numbers by one call, + * and returns the second on the second call. + * @see #nextGaussian. */ + private boolean haveNextNextGaussian; + /** + * The next nextGaussian if available. This is used by nextGaussian, + * which generates two gaussian numbers by one call, and returns the + * second on the second call. + * @see #nextGaussian. + */ private double nextNextGaussian; - - /* Used by nextGaussian() to keep track of whether it is has precomputed */ - /* and stashed away the next value to be delivered by that method */ - private boolean haveNextNextGaussian = false; + /** + * The seed. This is the number set by setSeed and which is used + * in next. + * @see #next + */ + private long seed; private static final long serialVersionUID = 3905348978240129619L; + /** + * Creates a new pseudorandom number generator. The seed is initialized + * to the current time as follows. + * <pre> + * setSeed(System.currentTimeMillis()); + * </pre> + * @see System#currentTimeMillis() + */ public Random() { - this(System.currentTimeMillis()); + setSeed(System.currentTimeMillis()); } + /** + * Creates a new pseudorandom number generator, starting with the + * specified seed. This does: + * <pre> + * setSeed(seed); + * </pre> + * @param seed the initial seed. + */ public Random(long seed) { setSeed(seed); } - protected synchronized int next(int bits) - { - seed = (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1); - return (int)(seed >>> (48 - bits)); - } - - // JDK1.2 - public boolean nextBoolean() - { - return next(1) != 0; - } - - /* The method nextBytes() is not fully specified in the published specs. - * At first I implemented it simply via: - * for (int i = 0; i < buf.length; i++) - * buf[i] = (byte)next(8); - * but a simple test did not yield the same results as the std implementation. - * There seemed to be a relationship where each i byte above was at pos 4*i+3 - * in the std. For efficiency, by reducing calls to the expensive math - * routines, the std probably was calling next(32) once rather than next(8) - * 4 times. Changing the algorithm to the one below based on that assumption - * then yielded identical results to the std. + /** + * Sets the seed for this pseudorandom number generator. As described + * above, two instances of the same random class, starting with the + * same seed, should produce the same results, if the same methods + * are called. The implementation for java.util.Random is: + * <pre> + * public synchronized void setSeed(long seed) { + * this.seed = (seed ^ 0x5DEECE66DL) & ((1L << 48) - 1); + * haveNextNextGaussian = false; + * } + * </pre> */ - public void nextBytes(byte[] buf) - { - int randInt = 0; - - for (int i = 0; i < buf.length; i++) - { - int shift = (i % 4) * 8; - if (shift == 0) - randInt = next(32); - buf[i] = (byte) (randInt >> shift); - } - } - - public double nextDouble() + public synchronized void setSeed(long seed) { - return (((long)next(26) << 27) + next(27)) / (double)(1L << 53); + this.seed = (seed ^ 0x5DEECE66DL) & ((1L << 48) - 1); + haveNextNextGaussian = false; } - public float nextFloat() + /** + * Generates the next pseudorandom number. This returns + * an int value whose <code>bits</code> low order bits are + * independent chosen random bits (0 and 1 are equally likely). + * The implementation for java.util.Random is: + * <pre> + * protected synchronized int next(int bits) { + * seed = (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1); + * return (int) (seed >>> (48 - bits)); + * } + * </pre> + * @param bits the number of random bits to generate. Must be in range + * 1..32. + * @return the next pseudorandom value. + * @since JDK1.1 + */ + protected synchronized int next(int bits) + /*{ require { 1 <= bits && bits <=32 :: + "bits "+bits+" not in range [1..32]" } } */ { - return next(24) / ((float)(1 << 24)); + seed = (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1); + return (int) (seed >>> (48 - bits)); } - public synchronized double nextGaussian() + /** + * Fills an array of bytes with random numbers. All possible values + * are (approximately) equally likely. + * The JDK documentation gives no implementation, but it seems to be: + * <pre> + * public void nextBytes(byte[] bytes) { + * for (int i=0; i< bytes.length; i+=4) { + * int random = next(32); + * for (int j=0; i+j< bytes.length && j<4; j++) + * bytes[i+j] = (byte) (random & 0xff) + * random >>= 8; + * } + * } + * } + * </pre> + * @param bytes The byte array that should be filled. + * @since JDK1.1 + */ + public void nextBytes(byte[] bytes) + /*{ require { bytes != null :: "bytes is null"; } } */ { - if (haveNextNextGaussian) + int random; + /* Do a little bit unrolling of the above algorithm. */ + int max = bytes.length & ~0x3; + for (int i = 0; i < max; i += 4) { - haveNextNextGaussian = false; - return nextNextGaussian; + random = next(32); + bytes[i] = (byte) random; + bytes[i + 1] = (byte) (random >> 8); + bytes[i + 2] = (byte) (random >> 16); + bytes[i + 3] = (byte) (random >> 24); } - else + if (max < bytes.length) { - double v1, v2, s; - do - { - v1 = 2 * nextDouble() - 1; // between -1.0 and 1.0 - v2 = 2 * nextDouble() - 1; // between -1.0 and 1.0 - s = v1 * v1 + v2 * v2; - } while (s >= 1); - double norm = Math.sqrt(-2 * Math.log(s)/s); - nextNextGaussian = v2 * norm; - haveNextNextGaussian = true; - return v1 * norm; + random = next(32); + for (int j = max; j < bytes.length; j++) + { + bytes[j] = (byte) random; + random >>= 8; + } } } + /** + * Generates the next pseudorandom number. This returns + * an int value whose 32 bits are independent chosen random bits + * (0 and 1 are equally likely). The implementation for + * java.util.Random is: + * <pre> + * public int nextInt() { + * return next(32); + * } + * </pre> + * + * @return the next pseudorandom value. */ public int nextInt() { return next(32); } - // JDK1.2 + /** + * Generates the next pseudorandom number. This returns + * a value between 0(inclusive) and <code>n</code>(exclusive), and + * each value has the same likelihodd (1/<code>n</code>). + * (0 and 1 are equally likely). The implementation for + * java.util.Random is: + * <pre> + * public int nextInt(int n) { + * if (n<=0) + * throw new IllegalArgumentException("n must be positive"); + * if ((n & -n) == n) // i.e., n is a power of 2 + * return (int)((n * (long)next(31)) >> 31); + * int bits, val; + * do { + * bits = next(32); + * val = bits % n; + * } while(bits - val + (n-1) < 0); + * return val; + * } + * </pre> + * This algorithm would return every value with exactly the same + * probability, if the next()-method would be a perfect random number + * generator. + * + * The loop at the bottom only accepts a value, if the random + * number was between 0 and the highest number less then 1<<31, + * which is divisible by n. The probability for this is high for small + * n, and the worst case is 1/2 (for n=(1<<30)+1). + * + * The special treatment for n = power of 2, selects the high bits of + * the random number (the loop at the bottom would select the low order + * bits). This is done, because the low order bits of linear congruential + * number generators (like the one used in this class) are known to be + * ``less random'' than the high order bits. + * + * @param n the upper bound. + * @exception IllegalArgumentException if the given upper bound is negative + * @return the next pseudorandom value. + */ public int nextInt(int n) + /*{ require { n > 0 :: "n must be positive"; } } */ { if (n <= 0) throw new IllegalArgumentException("n must be positive"); - + if ((n & -n) == n) // i.e., n is a power of 2 + return (int) ((n * (long) next(31)) >> 31); int bits, val; do { - bits = next(31); - val = bits % n; - } while (bits - val + (n-1) < 0); + bits = next(32); + val = bits % n; + } + while (bits - val + (n - 1) < 0); return val; } + /** + * Generates the next pseudorandom long number. All bits of this + * long are independently chosen and 0 and 1 have equal likelihood. + * The implementation for java.util.Random is: + * <pre> + * public long nextLong() { + * return ((long)next(32) << 32) + next(32); + * } + * </pre> + * @return the next pseudorandom value. + */ public long nextLong() { - return ((long)next(32) << 32) + next(32); + return ((long) next(32) << 32) + next(32); } - public synchronized void setSeed(long seed) + /** + * Generates the next pseudorandom boolean. True and false have + * the same probability. The implementation is: + * <pre> + * public boolean nextBoolean() { + * return next(1) != 0; + * } + * </pre> + * @return the next pseudorandom boolean. + */ + public boolean nextBoolean() { - this.seed = (seed ^ 0x5DEECE66DL) & ((1L << 48) - 1); - haveNextNextGaussian = false; + return next(1) != 0; + } + + /** + * Generates the next pseudorandom float uniformly distributed + * between 0.0f (inclusive) and 1.0 (exclusive). The + * implementation is as follows. + * <pre> + * public float nextFloat() { + * return next(24) / ((float)(1 << 24)); + * } + * </pre> + * @return the next pseudorandom float. */ + public float nextFloat() + { + return next(24) / ((float) (1 << 24)); + } + + /** + * Generates the next pseudorandom double uniformly distributed + * between 0.0f (inclusive) and 1.0 (exclusive). The + * implementation is as follows. + * <pre> + * public double nextDouble() { + * return (((long)next(26) << 27) + next(27)) / (double)(1 << 53); + * } + * </pre> + * @return the next pseudorandom double. */ + public double nextDouble() + { + return (((long) next(26) << 27) + next(27)) / (double) (1L << 53); + } + + /** + * Generates the next pseudorandom, Gaussian (normally) distributed + * double value, with mean 0.0 and standard deviation 1.0. + * The algorithm is as follows. + * <pre> + * public synchronized double nextGaussian() { + * if (haveNextNextGaussian) { + * haveNextNextGaussian = false; + * return nextNextGaussian; + * } else { + * double v1, v2, s; + * do { + * v1 = 2 * nextDouble() - 1; // between -1.0 and 1.0 + * v2 = 2 * nextDouble() - 1; // between -1.0 and 1.0 + * s = v1 * v1 + v2 * v2; + * } while (s >= 1); + * double norm = Math.sqrt(-2 * Math.log(s)/s); + * nextNextGaussian = v2 * norm; + * haveNextNextGaussian = true; + * return v1 * norm; + * } + * } + * </pre> + * This is described in section 3.4.1 of <em>The Art of Computer + * Programming, Volume 2</em> by Donald Knuth. + * + * @return the next pseudorandom Gaussian distributed double. + */ + public synchronized double nextGaussian() + { + if (haveNextNextGaussian) + { + haveNextNextGaussian = false; + return nextNextGaussian; + } + else + { + double v1, v2, s; + do + { + v1 = 2 * nextDouble() - 1; // between -1.0 and 1.0 + v2 = 2 * nextDouble() - 1; // between -1.0 and 1.0 + s = v1 * v1 + v2 * v2; + } + while (s >= 1); + double norm = Math.sqrt(-2 * Math.log(s) / s); + nextNextGaussian = v2 * norm; + haveNextNextGaussian = true; + return v1 * norm; + } } } |