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