ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/jsr166/jsr166/src/main/java/util/Random.java
Revision: 1.12
Committed: Sun Nov 6 07:47:51 2005 UTC (18 years, 6 months ago) by jsr166
Branch: MAIN
Changes since 1.11: +260 -236 lines
Log Message:
sync with mustang

File Contents

# Content
1 /*
2 * %W% %E%
3 *
4 * Copyright 2005 Sun Microsystems, Inc. All rights reserved.
5 * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
6 */
7
8 package java.util;
9 import java.io.*;
10 import java.util.concurrent.atomic.AtomicLong;
11
12 /**
13 * An instance of this class is used to generate a stream of
14 * pseudorandom numbers. The class uses a 48-bit seed, which is
15 * modified using a linear congruential formula. (See Donald Knuth,
16 * <i>The Art of Computer Programming, Volume 3</i>, Section 3.2.1.)
17 * <p>
18 * If two instances of {@code Random} are created with the same
19 * seed, and the same sequence of method calls is made for each, they
20 * will generate and return identical sequences of numbers. In order to
21 * guarantee this property, particular algorithms are specified for the
22 * class {@code Random}. Java implementations must use all the algorithms
23 * shown here for the class {@code Random}, for the sake of absolute
24 * portability of Java code. However, subclasses of class {@code Random}
25 * are permitted to use other algorithms, so long as they adhere to the
26 * general contracts for all the methods.
27 * <p>
28 * The algorithms implemented by class {@code Random} use a
29 * {@code protected} utility method that on each invocation can supply
30 * up to 32 pseudorandomly generated bits.
31 * <p>
32 * Many applications will find the method {@link Math#random} simpler to use.
33 *
34 * @author Frank Yellin
35 * @version %I%, %G%
36 * @since 1.0
37 */
38 public
39 class Random implements java.io.Serializable {
40 /** use serialVersionUID from JDK 1.1 for interoperability */
41 static final long serialVersionUID = 3905348978240129619L;
42
43 /**
44 * The internal state associated with this pseudorandom number generator.
45 * (The specs for the methods in this class describe the ongoing
46 * computation of this value.)
47 *
48 * @serial
49 */
50 private AtomicLong seed;
51
52 private final static long multiplier = 0x5DEECE66DL;
53 private final static long addend = 0xBL;
54 private final static long mask = (1L << 48) - 1;
55
56 /**
57 * Creates a new random number generator. This constructor sets
58 * the seed of the random number generator to a value very likely
59 * to be distinct from any other invocation of this constructor.
60 */
61 public Random() { this(++seedUniquifier + System.nanoTime()); }
62 private static volatile long seedUniquifier = 8682522807148012L;
63
64 /**
65 * Creates a new random number generator using a single {@code long} seed.
66 * The seed is the initial value of the internal state of the pseudorandom
67 * number generator which is maintained by method {@link #next}.
68 *
69 * <p>The invocation {@code new Random(seed)} is equivalent to:
70 * <pre> {@code
71 * Random rnd = new Random();
72 * rnd.setSeed(seed);}</pre>
73 *
74 * @param seed the initial seed
75 * @see #setSeed(long)
76 */
77 public Random(long seed) {
78 this.seed = new AtomicLong(0L);
79 setSeed(seed);
80 }
81
82 /**
83 * Sets the seed of this random number generator using a single
84 * {@code long} seed. The general contract of {@code setSeed} is
85 * that it alters the state of this random number generator object
86 * so as to be in exactly the same state as if it had just been
87 * created with the argument {@code seed} as a seed. The method
88 * {@code setSeed} is implemented by class {@code Random} by
89 * atomically updating the seed to
90 * <pre>{@code (seed ^ 0x5DEECE66DL) & ((1L << 48) - 1)}</pre>
91 * and clearing the {@code haveNextNextGaussian} flag used by {@link
92 * #nextGaussian}.
93 *
94 * <p>The implementation of {@code setSeed} by class {@code Random}
95 * happens to use only 48 bits of the given seed. In general, however,
96 * an overriding method may use all 64 bits of the {@code long}
97 * argument as a seed value.
98 *
99 * @param seed the initial seed
100 */
101 synchronized public void setSeed(long seed) {
102 seed = (seed ^ multiplier) & mask;
103 this.seed.set(seed);
104 haveNextNextGaussian = false;
105 }
106
107 /**
108 * Generates the next pseudorandom number. Subclasses should
109 * override this, as this is used by all other methods.
110 *
111 * <p>The general contract of {@code next} is that it returns an
112 * {@code int} value and if the argument {@code bits} is between
113 * {@code 1} and {@code 32} (inclusive), then that many low-order
114 * bits of the returned value will be (approximately) independently
115 * chosen bit values, each of which is (approximately) equally
116 * likely to be {@code 0} or {@code 1}. The method {@code next} is
117 * implemented by class {@code Random} by atomically updating the seed to
118 * <pre>{@code (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1)}</pre>
119 * and returning
120 * <pre>{@code (int)(seed >>> (48 - bits))}.</pre>
121 *
122 * This is a linear congruential pseudorandom number generator, as
123 * defined by D. H. Lehmer and described by Donald E. Knuth in
124 * <i>The Art of Computer Programming,</i> Volume 3:
125 * <i>Seminumerical Algorithms</i>, section 3.2.1.
126 *
127 * @param bits random bits
128 * @return the next pseudorandom value from this random number
129 * generator's sequence
130 * @since 1.1
131 */
132 protected int next(int bits) {
133 long oldseed, nextseed;
134 AtomicLong seed = this.seed;
135 do {
136 oldseed = seed.get();
137 nextseed = (oldseed * multiplier + addend) & mask;
138 } while (!seed.compareAndSet(oldseed, nextseed));
139 return (int)(nextseed >>> (48 - bits));
140 }
141
142 /**
143 * Generates random bytes and places them into a user-supplied
144 * byte array. The number of random bytes produced is equal to
145 * the length of the byte array.
146 *
147 * <p>The method {@code nextBytes} is implemented by class {@code Random}
148 * as if by:
149 * <pre> {@code
150 * public void nextBytes(byte[] bytes) {
151 * for (int i = 0; i < bytes.length; )
152 * for (int rnd = nextInt(), n = Math.min(bytes.length - i, 4);
153 * n-- > 0; rnd >>= 8)
154 * bytes[i++] = (byte)rnd;
155 * }}</pre>
156 *
157 * @param bytes the byte array to fill with random bytes
158 * @throws NullPointerException if the byte array is null
159 * @since 1.1
160 */
161 public void nextBytes(byte[] bytes) {
162 for (int i = 0, len = bytes.length; i < len; )
163 for (int rnd = nextInt(),
164 n = Math.min(len - i, Integer.SIZE/Byte.SIZE);
165 n-- > 0; rnd >>= Byte.SIZE)
166 bytes[i++] = (byte)rnd;
167 }
168
169 /**
170 * Returns the next pseudorandom, uniformly distributed {@code int}
171 * value from this random number generator's sequence. The general
172 * contract of {@code nextInt} is that one {@code int} value is
173 * pseudorandomly generated and returned. All 2<font size="-1"><sup>32
174 * </sup></font> possible {@code int} values are produced with
175 * (approximately) equal probability.
176 *
177 * <p>The method {@code nextInt} is implemented by class {@code Random}
178 * as if by:
179 * <pre> {@code
180 * public int nextInt() {
181 * return next(32);
182 * }}</pre>
183 *
184 * @return the next pseudorandom, uniformly distributed {@code int}
185 * value from this random number generator's sequence
186 */
187 public int nextInt() {
188 return next(32);
189 }
190
191 /**
192 * Returns a pseudorandom, uniformly distributed {@code int} value
193 * between 0 (inclusive) and the specified value (exclusive), drawn from
194 * this random number generator's sequence. The general contract of
195 * {@code nextInt} is that one {@code int} value in the specified range
196 * is pseudorandomly generated and returned. All {@code n} possible
197 * {@code int} values are produced with (approximately) equal
198 * probability. The method {@code nextInt(int n)} is implemented by
199 * class {@code Random} as if by:
200 * <pre> {@code
201 * public int nextInt(int n) {
202 * if (n <= 0)
203 * throw new IllegalArgumentException("n must be positive");
204 *
205 * if ((n & -n) == n) // i.e., n is a power of 2
206 * return (int)((n * (long)next(31)) >> 31);
207 *
208 * int bits, val;
209 * do {
210 * bits = next(31);
211 * val = bits % n;
212 * } while (bits - val + (n-1) < 0);
213 * return val;
214 * }}</pre>
215 *
216 * <p>The hedge "approximately" is used in the foregoing description only
217 * because the next method is only approximately an unbiased source of
218 * independently chosen bits. If it were a perfect source of randomly
219 * chosen bits, then the algorithm shown would choose {@code int}
220 * values from the stated range with perfect uniformity.
221 * <p>
222 * The algorithm is slightly tricky. It rejects values that would result
223 * in an uneven distribution (due to the fact that 2^31 is not divisible
224 * by n). The probability of a value being rejected depends on n. The
225 * worst case is n=2^30+1, for which the probability of a reject is 1/2,
226 * and the expected number of iterations before the loop terminates is 2.
227 * <p>
228 * The algorithm treats the case where n is a power of two specially: it
229 * returns the correct number of high-order bits from the underlying
230 * pseudo-random number generator. In the absence of special treatment,
231 * the correct number of <i>low-order</i> bits would be returned. Linear
232 * congruential pseudo-random number generators such as the one
233 * implemented by this class are known to have short periods in the
234 * sequence of values of their low-order bits. Thus, this special case
235 * greatly increases the length of the sequence of values returned by
236 * successive calls to this method if n is a small power of two.
237 *
238 * @param n the bound on the random number to be returned. Must be
239 * positive.
240 * @return the next pseudorandom, uniformly distributed {@code int}
241 * value between {@code 0} (inclusive) and {@code n} (exclusive)
242 * from this random number generator's sequence
243 * @exception IllegalArgumentException if n is not positive
244 * @since 1.2
245 */
246
247 public int nextInt(int n) {
248 if (n <= 0)
249 throw new IllegalArgumentException("n must be positive");
250
251 if ((n & -n) == n) // i.e., n is a power of 2
252 return (int)((n * (long)next(31)) >> 31);
253
254 int bits, val;
255 do {
256 bits = next(31);
257 val = bits % n;
258 } while (bits - val + (n-1) < 0);
259 return val;
260 }
261
262 /**
263 * Returns the next pseudorandom, uniformly distributed {@code long}
264 * value from this random number generator's sequence. The general
265 * contract of {@code nextLong} is that one {@code long} value is
266 * pseudorandomly generated and returned.
267 *
268 * <p>The method {@code nextLong} is implemented by class {@code Random}
269 * as if by:
270 * <pre> {@code
271 * public long nextLong() {
272 * return ((long)next(32) << 32) + next(32);
273 * }}</pre>
274 *
275 * Because class {@code Random} uses a seed with only 48 bits,
276 * this algorithm will not return all possible {@code long} values.
277 *
278 * @return the next pseudorandom, uniformly distributed {@code long}
279 * value from this random number generator's sequence
280 */
281 public long nextLong() {
282 // it's okay that the bottom word remains signed.
283 return ((long)(next(32)) << 32) + next(32);
284 }
285
286 /**
287 * Returns the next pseudorandom, uniformly distributed
288 * {@code boolean} value from this random number generator's
289 * sequence. The general contract of {@code nextBoolean} is that one
290 * {@code boolean} value is pseudorandomly generated and returned. The
291 * values {@code true} and {@code false} are produced with
292 * (approximately) equal probability.
293 *
294 * <p>The method {@code nextBoolean} is implemented by class {@code Random}
295 * as if by:
296 * <pre> {@code
297 * public boolean nextBoolean() {
298 * return next(1) != 0;
299 * }}</pre>
300 *
301 * @return the next pseudorandom, uniformly distributed
302 * {@code boolean} value from this random number generator's
303 * sequence
304 * @since 1.2
305 */
306 public boolean nextBoolean() {
307 return next(1) != 0;
308 }
309
310 /**
311 * Returns the next pseudorandom, uniformly distributed {@code float}
312 * value between {@code 0.0} and {@code 1.0} from this random
313 * number generator's sequence.
314 *
315 * <p>The general contract of {@code nextFloat} is that one
316 * {@code float} value, chosen (approximately) uniformly from the
317 * range {@code 0.0f} (inclusive) to {@code 1.0f} (exclusive), is
318 * pseudorandomly generated and returned. All 2<font
319 * size="-1"><sup>24</sup></font> possible {@code float} values
320 * of the form <i>m&nbsp;x&nbsp</i>2<font
321 * size="-1"><sup>-24</sup></font>, where <i>m</i> is a positive
322 * integer less than 2<font size="-1"><sup>24</sup> </font>, are
323 * produced with (approximately) equal probability.
324 *
325 * <p>The method {@code nextFloat} is implemented by class {@code Random}
326 * as if by:
327 * <pre> {@code
328 * public float nextFloat() {
329 * return next(24) / ((float)(1 << 24));
330 * }}</pre>
331 *
332 * <p>The hedge "approximately" is used in the foregoing description only
333 * because the next method is only approximately an unbiased source of
334 * independently chosen bits. If it were a perfect source of randomly
335 * chosen bits, then the algorithm shown would choose {@code float}
336 * values from the stated range with perfect uniformity.<p>
337 * [In early versions of Java, the result was incorrectly calculated as:
338 * <pre> {@code
339 * return next(30) / ((float)(1 << 30));}</pre>
340 * This might seem to be equivalent, if not better, but in fact it
341 * introduced a slight nonuniformity because of the bias in the rounding
342 * of floating-point numbers: it was slightly more likely that the
343 * low-order bit of the significand would be 0 than that it would be 1.]
344 *
345 * @return the next pseudorandom, uniformly distributed {@code float}
346 * value between {@code 0.0} and {@code 1.0} from this
347 * random number generator's sequence
348 */
349 public float nextFloat() {
350 return next(24) / ((float)(1 << 24));
351 }
352
353 /**
354 * Returns the next pseudorandom, uniformly distributed
355 * {@code double} value between {@code 0.0} and
356 * {@code 1.0} from this random number generator's sequence.
357 *
358 * <p>The general contract of {@code nextDouble} is that one
359 * {@code double} value, chosen (approximately) uniformly from the
360 * range {@code 0.0d} (inclusive) to {@code 1.0d} (exclusive), is
361 * pseudorandomly generated and returned.
362 *
363 * <p>The method {@code nextDouble} is implemented by class {@code Random}
364 * as if by:
365 * <pre> {@code
366 * public double nextDouble() {
367 * return (((long)next(26) << 27) + next(27))
368 * / (double)(1L << 53);
369 * }}</pre>
370 *
371 * <p>The hedge "approximately" is used in the foregoing description only
372 * because the {@code next} method is only approximately an unbiased
373 * source of independently chosen bits. If it were a perfect source of
374 * randomly chosen bits, then the algorithm shown would choose
375 * {@code double} values from the stated range with perfect uniformity.
376 * <p>[In early versions of Java, the result was incorrectly calculated as:
377 * <pre> {@code
378 * return (((long)next(27) << 27) + next(27))
379 * / (double)(1L << 54);}</pre>
380 * This might seem to be equivalent, if not better, but in fact it
381 * introduced a large nonuniformity because of the bias in the rounding
382 * of floating-point numbers: it was three times as likely that the
383 * low-order bit of the significand would be 0 than that it would be 1!
384 * This nonuniformity probably doesn't matter much in practice, but we
385 * strive for perfection.]
386 *
387 * @return the next pseudorandom, uniformly distributed {@code double}
388 * value between {@code 0.0} and {@code 1.0} from this
389 * random number generator's sequence
390 * @see Math#random
391 */
392 public double nextDouble() {
393 return (((long)(next(26)) << 27) + next(27))
394 / (double)(1L << 53);
395 }
396
397 private double nextNextGaussian;
398 private boolean haveNextNextGaussian = false;
399
400 /**
401 * Returns the next pseudorandom, Gaussian ("normally") distributed
402 * {@code double} value with mean {@code 0.0} and standard
403 * deviation {@code 1.0} from this random number generator's sequence.
404 * <p>
405 * The general contract of {@code nextGaussian} is that one
406 * {@code double} value, chosen from (approximately) the usual
407 * normal distribution with mean {@code 0.0} and standard deviation
408 * {@code 1.0}, is pseudorandomly generated and returned.
409 *
410 * <p>The method {@code nextGaussian} is implemented by class
411 * {@code Random} as if by a threadsafe version of the following:
412 * <pre> {@code
413 * private double nextNextGaussian;
414 * private boolean haveNextNextGaussian = false;
415 *
416 * public double nextGaussian() {
417 * if (haveNextNextGaussian) {
418 * haveNextNextGaussian = false;
419 * return nextNextGaussian;
420 * } else {
421 * double v1, v2, s;
422 * do {
423 * v1 = 2 * nextDouble() - 1; // between -1.0 and 1.0
424 * v2 = 2 * nextDouble() - 1; // between -1.0 and 1.0
425 * s = v1 * v1 + v2 * v2;
426 * } while (s >= 1 || s == 0);
427 * double multiplier = StrictMath.sqrt(-2 * StrictMath.log(s)/s);
428 * nextNextGaussian = v2 * multiplier;
429 * haveNextNextGaussian = true;
430 * return v1 * multiplier;
431 * }
432 * }}</pre>
433 * This uses the <i>polar method</i> of G. E. P. Box, M. E. Muller, and
434 * G. Marsaglia, as described by Donald E. Knuth in <i>The Art of
435 * Computer Programming</i>, Volume 3: <i>Seminumerical Algorithms</i>,
436 * section 3.4.1, subsection C, algorithm P. Note that it generates two
437 * independent values at the cost of only one call to {@code StrictMath.log}
438 * and one call to {@code StrictMath.sqrt}.
439 *
440 * @return the next pseudorandom, Gaussian ("normally") distributed
441 * {@code double} value with mean {@code 0.0} and
442 * standard deviation {@code 1.0} from this random number
443 * generator's sequence
444 */
445 synchronized public double nextGaussian() {
446 // See Knuth, ACP, Section 3.4.1 Algorithm C.
447 if (haveNextNextGaussian) {
448 haveNextNextGaussian = false;
449 return nextNextGaussian;
450 } else {
451 double v1, v2, s;
452 do {
453 v1 = 2 * nextDouble() - 1; // between -1 and 1
454 v2 = 2 * nextDouble() - 1; // between -1 and 1
455 s = v1 * v1 + v2 * v2;
456 } while (s >= 1 || s == 0);
457 double multiplier = StrictMath.sqrt(-2 * StrictMath.log(s)/s);
458 nextNextGaussian = v2 * multiplier;
459 haveNextNextGaussian = true;
460 return v1 * multiplier;
461 }
462 }
463
464 /**
465 * Serializable fields for Random.
466 *
467 * @serialField seed long;
468 * seed for random computations
469 * @serialField nextNextGaussian double;
470 * next Gaussian to be returned
471 * @serialField haveNextNextGaussian boolean
472 * nextNextGaussian is valid
473 */
474 private static final ObjectStreamField[] serialPersistentFields = {
475 new ObjectStreamField("seed", Long.TYPE),
476 new ObjectStreamField("nextNextGaussian", Double.TYPE),
477 new ObjectStreamField("haveNextNextGaussian", Boolean.TYPE)
478 };
479
480 /**
481 * Reconstitute the {@code Random} instance from a stream (that is,
482 * deserialize it).
483 */
484 private void readObject(java.io.ObjectInputStream s)
485 throws java.io.IOException, ClassNotFoundException {
486
487 ObjectInputStream.GetField fields = s.readFields();
488
489 // The seed is read in as {@code long} for
490 // historical reasons, but it is converted to an AtomicLong.
491 long seedVal = (long) fields.get("seed", -1L);
492 if (seedVal < 0)
493 throw new java.io.StreamCorruptedException(
494 "Random: invalid seed");
495 seed = new AtomicLong(seedVal);
496 nextNextGaussian = fields.get("nextNextGaussian", 0.0);
497 haveNextNextGaussian = fields.get("haveNextNextGaussian", false);
498 }
499
500 /**
501 * Save the {@code Random} instance to a stream.
502 */
503 synchronized private void writeObject(ObjectOutputStream s)
504 throws IOException {
505
506 // set the values of the Serializable fields
507 ObjectOutputStream.PutField fields = s.putFields();
508
509 // The seed is serialized as a long for historical reasons.
510 fields.put("seed", seed.get());
511 fields.put("nextNextGaussian", nextNextGaussian);
512 fields.put("haveNextNextGaussian", haveNextNextGaussian);
513
514 // save them
515 s.writeFields();
516 }
517
518 }