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. */
40 * This class generates pseudorandom numbers. It uses the same
41 * algorithm as the original JDK-class, so that your programs behave
42 * exactly the same way, if started with the same seed.
44 * The algorithm is described in <em>The Art of Computer Programming,
45 * Volume 2</em> by Donald Knuth in Section 3.2.1. It is a 48-bit seed,
46 * linear congruential formula.
48 * If two instances of this class are created with the same seed and
49 * the same calls to these classes are made, they behave exactly the
50 * same way. This should be even true for foreign implementations
51 * (like this), so every port must use the same algorithm as described
54 * If you want to implement your own pseudorandom algorithm, you
55 * should extend this class and overload the <code>next()</code> and
56 * <code>setSeed(long)</code> method. In that case the above
57 * paragraph doesn't apply to you.
59 * This class shouldn't be used for security sensitive purposes (like
60 * generating passwords or encryption keys. See <code>SecureRandom</code>
61 * in package <code>java.security</code> for this purpose.
63 * For simple random doubles between 0.0 and 1.0, you may consider using
64 * Math.random instead.
66 * @see java.security.SecureRandom
68 * @author Jochen Hoenicke
69 * @author Eric Blake (ebb9@email.byu.edu)
70 * @status updated to 1.4
75 * True if the next nextGaussian is available. This is used by
76 * nextGaussian, which generates two gaussian numbers by one call,
77 * and returns the second on the second call.
79 * @serial whether nextNextGaussian is available
80 * @see #nextGaussian()
81 * @see #nextNextGaussian
83 private boolean haveNextNextGaussian;
86 * The next nextGaussian, when available. This is used by nextGaussian,
87 * which generates two gaussian numbers by one call, and returns the
88 * second on the second call.
90 * @serial the second gaussian of a pair
91 * @see #nextGaussian()
92 * @see #haveNextNextGaussian
94 private double nextNextGaussian;
97 * The seed. This is the number set by setSeed and which is used
100 * @serial the internal state of this generator
107 * Creates a new pseudorandom number generator. The seed is initialized
108 * to the current time, as if by
109 * <code>setSeed(System.currentTimeMillis());</code>.
111 * @see System#currentTimeMillis()
114 setSeed(System.currentTimeMillis());
118 * Creates a new pseudorandom number generator, starting with the
119 * specified seed, using <code>setSeed(seed);</code>.
121 * @param seed the initial seed
123 public Random(long seed) {
128 * Sets the seed for this pseudorandom number generator. As described
129 * above, two instances of the same random class, starting with the
130 * same seed, should produce the same results, if the same methods
131 * are called. The implementation for java.util.Random is:
133 <pre>public synchronized void setSeed(long seed)
135 this.seed = (seed ^ 0x5DEECE66DL) & ((1L << 48) - 1);
136 haveNextNextGaussian = false;
139 * @param seed the new seed
141 public synchronized void setSeed(long seed) {
142 this.seed = (seed ^ 0x5DEECE66DL) & ((1L << 48) - 1);
143 haveNextNextGaussian = false;
147 * Generates the next pseudorandom number. This returns
148 * an int value whose <code>bits</code> low order bits are
149 * independent chosen random bits (0 and 1 are equally likely).
150 * The implementation for java.util.Random is:
152 <pre>protected synchronized int next(int bits)
154 seed = (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1);
155 return (int) (seed >>> (48 - bits));
158 * @param bits the number of random bits to generate, in the range 1..32
159 * @return the next pseudorandom value
162 protected synchronized int next(int bits) {
163 seed = (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1);
164 return (int) (seed >>> (48 - bits));
168 * Fills an array of bytes with random numbers. All possible values
169 * are (approximately) equally likely.
170 * The JDK documentation gives no implementation, but it seems to be:
172 <pre>public void nextBytes(byte[] bytes)
174 for (int i = 0; i < bytes.length; i += 4)
176 int random = next(32);
177 for (int j = 0; i + j < bytes.length && j < 4; j++)
179 bytes[i+j] = (byte) (random & 0xff)
185 * @param bytes the byte array that should be filled
186 * @throws NullPointerException if bytes is null
189 public void nextBytes(byte[] bytes) {
191 // Do a little bit unrolling of the above algorithm.
192 int max = bytes.length & ~0x3;
193 for (int i = 0; i < max; i += 4) {
195 bytes[i] = (byte) random;
196 bytes[i + 1] = (byte) (random >> 8);
197 bytes[i + 2] = (byte) (random >> 16);
198 bytes[i + 3] = (byte) (random >> 24);
200 if (max < bytes.length) {
202 for (int j = max; j < bytes.length; j++) {
203 bytes[j] = (byte) random;
210 * Generates the next pseudorandom number. This returns
211 * an int value whose 32 bits are independent chosen random bits
212 * (0 and 1 are equally likely). The implementation for
213 * java.util.Random is:
215 <pre>public int nextInt()
220 * @return the next pseudorandom value
222 public int nextInt() {
227 * Generates the next pseudorandom number. This returns
228 * a value between 0(inclusive) and <code>n</code>(exclusive), and
229 * each value has the same likelihodd (1/<code>n</code>).
230 * (0 and 1 are equally likely). The implementation for
231 * java.util.Random is:
234 public int nextInt(int n)
237 throw new IllegalArgumentException("n must be positive");
239 if ((n & -n) == n) // i.e., n is a power of 2
240 return (int)((n * (long) next(31)) >> 31);
248 while(bits - val + (n-1) < 0);
253 * <p>This algorithm would return every value with exactly the same
254 * probability, if the next()-method would be a perfect random number
257 * The loop at the bottom only accepts a value, if the random
258 * number was between 0 and the highest number less then 1<<31,
259 * which is divisible by n. The probability for this is high for small
260 * n, and the worst case is 1/2 (for n=(1<<30)+1).
262 * The special treatment for n = power of 2, selects the high bits of
263 * the random number (the loop at the bottom would select the low order
264 * bits). This is done, because the low order bits of linear congruential
265 * number generators (like the one used in this class) are known to be
266 * ``less random'' than the high order bits.
268 * @param n the upper bound
269 * @throws IllegalArgumentException if the given upper bound is negative
270 * @return the next pseudorandom value
273 public int nextInt(int n) {
275 System.printString("ERROR: n must be positive\n");
276 if ((n & -n) == n) // i.e., n is a power of 2
277 return (int) ((n * (long) next(31)) >> 31);
282 } while (bits - val + (n - 1) < 0);
287 * Generates the next pseudorandom long number. All bits of this
288 * long are independently chosen and 0 and 1 have equal likelihood.
289 * The implementation for java.util.Random is:
291 <pre>public long nextLong()
293 return ((long) next(32) << 32) + next(32);
296 * @return the next pseudorandom value
298 public long nextLong() {
299 return ((long) next(32) << 32) + next(32);
303 * Generates the next pseudorandom boolean. True and false have
304 * the same probability. The implementation is:
306 <pre>public boolean nextBoolean()
311 * @return the next pseudorandom boolean
314 public boolean nextBoolean() {
319 * Generates the next pseudorandom float uniformly distributed
320 * between 0.0f (inclusive) and 1.0f (exclusive). The
321 * implementation is as follows.
323 <pre>public float nextFloat()
325 return next(24) / ((float)(1 << 24));
328 * @return the next pseudorandom float
330 public float nextFloat() {
331 return next(24) / (float) (1 << 24);
335 * Generates the next pseudorandom double uniformly distributed
336 * between 0.0 (inclusive) and 1.0 (exclusive). The
337 * implementation is as follows.
339 <pre>public double nextDouble()
341 return (((long) next(26) << 27) + next(27)) / (double)(1L << 53);
344 * @return the next pseudorandom double
346 public double nextDouble() {
347 return (((long) next(26) << 27) + next(27)) / (double) (1L << 53);
351 * Generates the next pseudorandom, Gaussian (normally) distributed
352 * double value, with mean 0.0 and standard deviation 1.0.
353 * The algorithm is as follows.
355 <pre>public synchronized double nextGaussian()
357 if (haveNextNextGaussian)
359 haveNextNextGaussian = false;
360 return nextNextGaussian;
367 v1 = 2 * nextDouble() - 1; // between -1.0 and 1.0
368 v2 = 2 * nextDouble() - 1; // between -1.0 and 1.0
369 s = v1 * v1 + v2 * v2;
373 double norm = Math.sqrt(-2 * Math.log(s) / s);
374 nextNextGaussian = v2 * norm;
375 haveNextNextGaussian = true;
380 * <p>This is described in section 3.4.1 of <em>The Art of Computer
381 * Programming, Volume 2</em> by Donald Knuth.
383 * @return the next pseudorandom Gaussian distributed double
385 public synchronized double nextGaussian() {
386 if (haveNextNextGaussian) {
387 haveNextNextGaussian = false;
388 return nextNextGaussian;
392 v1 = 2 * nextDouble() - 1; // Between -1.0 and 1.0.
393 v2 = 2 * nextDouble() - 1; // Between -1.0 and 1.0.
394 s = v1 * v1 + v2 * v2;
396 double norm = Math.sqrt(-2 * Math.log(s) / s);
397 nextNextGaussian = v2 * norm;
398 haveNextNextGaussian = true;