1 /* Random.java -- a pseudo-random number generator
2 Copyright (C) 1998, 1999, 2000, 2001, 2002 Free Software Foundation, Inc.
4 This file is part of GNU Classpath.
6 GNU Classpath is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2, or (at your option)
11 GNU Classpath is distributed in the hope that it will be useful, but
12 WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with GNU Classpath; see the file COPYING. If not, write to the
18 Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
21 Linking this library statically or dynamically with other modules is
22 making a combined work based on this library. Thus, the terms and
23 conditions of the GNU General Public License cover the whole
26 As a special exception, the copyright holders of this library give you
27 permission to link this library with independent modules to produce an
28 executable, regardless of the license terms of these independent
29 modules, and to copy and distribute the resulting executable under
30 terms of your choice, provided that you also meet, for each linked
31 independent module, the terms and conditions of the license of that
32 module. An independent module is a module which is not derived from
33 or based on this library. If you modify this library, you may extend
34 this exception to your version of the library, but you are not
35 obligated to do so. If you do not wish to do so, delete this
36 exception statement from your version. */
39 * This class generates pseudorandom numbers. It uses the same algorithm as the
40 * original JDK-class, so that your programs behave exactly the same way, if
41 * started with the same seed.
43 * The algorithm is described in <em>The Art of Computer Programming,
44 * Volume 2</em> by Donald Knuth in Section 3.2.1. It is a 48-bit seed, linear
45 * congruential formula.
47 * If two instances of this class are created with the same seed and the same
48 * calls to these classes are made, they behave exactly the same way. This
49 * should be even true for foreign implementations (like this), so every port
50 * must use the same algorithm as described here.
52 * If you want to implement your own pseudorandom algorithm, you should extend
53 * this class and overload the <code>next()</code> and
54 * <code>setSeed(long)</code> method. In that case the above paragraph doesn't
57 * This class shouldn't be used for security sensitive purposes (like generating
58 * passwords or encryption keys. See <code>SecureRandom</code> in package
59 * <code>java.security</code> for this purpose.
61 * For simple random doubles between 0.0 and 1.0, you may consider using
62 * Math.random instead.
64 * @see java.security.SecureRandom
66 * @author Jochen Hoenicke
67 * @author Eric Blake (ebb9@email.byu.edu)
68 * @status updated to 1.4
73 * True if the next nextGaussian is available. This is used by nextGaussian,
74 * which generates two gaussian numbers by one call, and returns the second on
77 * @serial whether nextNextGaussian is available
78 * @see #nextGaussian()
79 * @see #nextNextGaussian
82 private boolean haveNextNextGaussian;
85 * The next nextGaussian, when available. This is used by nextGaussian, which
86 * generates two gaussian numbers by one call, and returns the second on the
89 * @serial the second gaussian of a pair
90 * @see #nextGaussian()
91 * @see #haveNextNextGaussian
94 private double nextNextGaussian;
97 * The seed. This is the number set by setSeed and which is used in next.
99 * @serial the internal state of this generator
106 * Creates a new pseudorandom number generator. The seed is initialized to the
107 * current time, as if by <code>setSeed(System.currentTimeMillis());</code>.
109 * @see System#currentTimeMillis()
112 setSeed(System.currentTimeMillis());
116 * Creates a new pseudorandom number generator, starting with the specified
117 * seed, using <code>setSeed(seed);</code>.
122 public Random(long seed) {
127 * Sets the seed for this pseudorandom number generator. As described above,
128 * two instances of the same random class, starting with the same seed, should
129 * produce the same results, if the same methods are called. The
130 * implementation for java.util.Random is:
133 * public synchronized void setSeed(long seed) {
134 * this.seed = (seed ˆ 0x5DEECE66DL) & ((1L << 48) - 1);
135 * haveNextNextGaussian = false;
142 public synchronized void setSeed(long seed) {
143 this.seed = (seed ^ 0x5DEECE66DL) & ((1L << 48) - 1);
144 haveNextNextGaussian = false;
148 * Generates the next pseudorandom number. This returns an int value whose
149 * <code>bits</code> low order bits are independent chosen random bits (0 and
150 * 1 are equally likely). The implementation for java.util.Random is:
153 * protected synchronized int next(int bits) {
154 * seed = (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1);
155 * return (int) (seed >>> (48 - bits));
160 * the number of random bits to generate, in the range 1..32
161 * @return the next pseudorandom value
164 protected synchronized int next(int bits) {
165 seed = (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1);
166 return (int) (seed >>> (48 - bits));
170 * Fills an array of bytes with random numbers. All possible values are
171 * (approximately) equally likely. The JDK documentation gives no
172 * implementation, but it seems to be:
175 * public void nextBytes(byte[] bytes)
177 * for (int i = 0; i < bytes.length; i += 4)
179 * int random = next(32);
180 * for (int j = 0; i + j < bytes.length && j < 4; j++)
182 * bytes[i+j] = (byte) (random & 0xff)
183 * random >>= 8;
190 * the byte array that should be filled
191 * @throws NullPointerException
195 public void nextBytes(byte[] bytes) {
197 // Do a little bit unrolling of the above algorithm.
198 int max = bytes.length & ~0x3;
199 for (int i = 0; i < max; i += 4) {
201 bytes[i] = (byte) random;
202 bytes[i + 1] = (byte) (random >> 8);
203 bytes[i + 2] = (byte) (random >> 16);
204 bytes[i + 3] = (byte) (random >> 24);
206 if (max < bytes.length) {
208 for (int j = max; j < bytes.length; j++) {
209 bytes[j] = (byte) random;
216 * Generates the next pseudorandom number. This returns an int value whose 32
217 * bits are independent chosen random bits (0 and 1 are equally likely). The
218 * implementation for java.util.Random is:
221 * public int nextInt() {
226 * @return the next pseudorandom value
228 public int nextInt() {
233 * Generates the next pseudorandom number. This returns a value between
234 * 0(inclusive) and <code>n</code>(exclusive), and each value has the same
235 * likelihodd (1/<code>n</code>). (0 and 1 are equally likely). The
236 * implementation for java.util.Random is:
239 * public int nextInt(int n) {
241 * throw new IllegalArgumentException("n must be positive");
243 * if ((n & -n) == n) // i.e., n is a power of 2
244 * return (int) ((n * (long) next(31)) >> 31);
250 * } while (bits - val + (n - 1) < 0);
257 * This algorithm would return every value with exactly the same probability,
258 * if the next()-method would be a perfect random number generator.
260 * The loop at the bottom only accepts a value, if the random number was
261 * between 0 and the highest number less then 1<<31, which is divisible by n.
262 * The probability for this is high for small n, and the worst case is 1/2
265 * The special treatment for n = power of 2, selects the high bits of the
266 * random number (the loop at the bottom would select the low order bits).
267 * This is done, because the low order bits of linear congruential number
268 * generators (like the one used in this class) are known to be ``less
269 * random'' than the high order bits.
273 * @throws IllegalArgumentException
274 * if the given upper bound is negative
275 * @return the next pseudorandom value
278 public int nextInt(int n) {
280 System.printString("ERROR: n must be positive\n");
281 if ((n & -n) == n) // i.e., n is a power of 2
282 return (int) ((n * (long) next(31)) >> 31);
287 } while (bits - val + (n - 1) < 0);
292 * Generates the next pseudorandom long number. All bits of this long are
293 * independently chosen and 0 and 1 have equal likelihood. The implementation
294 * for java.util.Random is:
297 * public long nextLong() {
298 * return ((long) next(32) << 32) + next(32);
302 * @return the next pseudorandom value
304 public long nextLong() {
305 return ((long) next(32) << 32) + next(32);
309 * Generates the next pseudorandom boolean. True and false have the same
310 * probability. The implementation is:
313 * public boolean nextBoolean() {
314 * return next(1) != 0;
318 * @return the next pseudorandom boolean
321 public boolean nextBoolean() {
326 * Generates the next pseudorandom float uniformly distributed between 0.0f
327 * (inclusive) and 1.0f (exclusive). The implementation is as follows.
330 * public float nextFloat() {
331 * return next(24) / ((float) (1 << 24));
335 * @return the next pseudorandom float
337 public float nextFloat() {
338 return next(24) / (float) (1 << 24);
342 * Generates the next pseudorandom double uniformly distributed between 0.0
343 * (inclusive) and 1.0 (exclusive). The implementation is as follows.
346 * public double nextDouble() {
347 * return (((long) next(26) << 27) + next(27)) / (double) (1L << 53);
351 * @return the next pseudorandom double
353 public double nextDouble() {
354 return (((long) next(26) << 27) + next(27)) / (double) (1L << 53);
358 * Generates the next pseudorandom, Gaussian (normally) distributed double
359 * value, with mean 0.0 and standard deviation 1.0. The algorithm is as
363 * public synchronized double nextGaussian() {
364 * if (haveNextNextGaussian) {
365 * haveNextNextGaussian = false;
366 * return nextNextGaussian;
370 * v1 = 2 * nextDouble() - 1; // between -1.0 and 1.0
371 * v2 = 2 * nextDouble() - 1; // between -1.0 and 1.0
372 * s = v1 * v1 + v2 * v2;
373 * } while (s >= 1);
375 * double norm = Math.sqrt(-2 * Math.log(s) / s);
376 * nextNextGaussian = v2 * norm;
377 * haveNextNextGaussian = true;
384 * This is described in section 3.4.1 of <em>The Art of Computer
385 * Programming, Volume 2</em> by Donald Knuth.
387 * @return the next pseudorandom Gaussian distributed double
389 public synchronized double nextGaussian() {
390 if (haveNextNextGaussian) {
391 haveNextNextGaussian = false;
392 return nextNextGaussian;
396 v1 = 2 * nextDouble() - 1; // Between -1.0 and 1.0.
397 v2 = 2 * nextDouble() - 1; // Between -1.0 and 1.0.
398 s = v1 * v1 + v2 * v2;
400 double norm = Math.sqrt(-2 * Math.log(s) / s);
401 nextNextGaussian = v2 * norm;
402 haveNextNextGaussian = true;