001 /* Random.java -- a pseudo-random number generator 002 Copyright (C) 1998, 1999, 2000, 2001, 2002 Free Software Foundation, Inc. 003 004 This file is part of GNU Classpath. 005 006 GNU Classpath is free software; you can redistribute it and/or modify 007 it under the terms of the GNU General Public License as published by 008 the Free Software Foundation; either version 2, or (at your option) 009 any later version. 010 011 GNU Classpath is distributed in the hope that it will be useful, but 012 WITHOUT ANY WARRANTY; without even the implied warranty of 013 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 014 General Public License for more details. 015 016 You should have received a copy of the GNU General Public License 017 along with GNU Classpath; see the file COPYING. If not, write to the 018 Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 019 02110-1301 USA. 020 021 Linking this library statically or dynamically with other modules is 022 making a combined work based on this library. Thus, the terms and 023 conditions of the GNU General Public License cover the whole 024 combination. 025 026 As a special exception, the copyright holders of this library give you 027 permission to link this library with independent modules to produce an 028 executable, regardless of the license terms of these independent 029 modules, and to copy and distribute the resulting executable under 030 terms of your choice, provided that you also meet, for each linked 031 independent module, the terms and conditions of the license of that 032 module. An independent module is a module which is not derived from 033 or based on this library. If you modify this library, you may extend 034 this exception to your version of the library, but you are not 035 obligated to do so. If you do not wish to do so, delete this 036 exception statement from your version. */ 037 038 039 package java.util; 040 041 import java.io.Serializable; 042 043 /** 044 * This class generates pseudorandom numbers. It uses the same 045 * algorithm as the original JDK-class, so that your programs behave 046 * exactly the same way, if started with the same seed. 047 * 048 * The algorithm is described in <em>The Art of Computer Programming, 049 * Volume 2</em> by Donald Knuth in Section 3.2.1. It is a 48-bit seed, 050 * linear congruential formula. 051 * 052 * If two instances of this class are created with the same seed and 053 * the same calls to these classes are made, they behave exactly the 054 * same way. This should be even true for foreign implementations 055 * (like this), so every port must use the same algorithm as described 056 * here. 057 * 058 * If you want to implement your own pseudorandom algorithm, you 059 * should extend this class and overload the <code>next()</code> and 060 * <code>setSeed(long)</code> method. In that case the above 061 * paragraph doesn't apply to you. 062 * 063 * This class shouldn't be used for security sensitive purposes (like 064 * generating passwords or encryption keys. See <code>SecureRandom</code> 065 * in package <code>java.security</code> for this purpose. 066 * 067 * For simple random doubles between 0.0 and 1.0, you may consider using 068 * Math.random instead. 069 * 070 * @see java.security.SecureRandom 071 * @see Math#random() 072 * @author Jochen Hoenicke 073 * @author Eric Blake (ebb9@email.byu.edu) 074 * @status updated to 1.4 075 */ 076 public class Random implements Serializable 077 { 078 /** 079 * True if the next nextGaussian is available. This is used by 080 * nextGaussian, which generates two gaussian numbers by one call, 081 * and returns the second on the second call. 082 * 083 * @serial whether nextNextGaussian is available 084 * @see #nextGaussian() 085 * @see #nextNextGaussian 086 */ 087 private boolean haveNextNextGaussian; 088 089 /** 090 * The next nextGaussian, when available. This is used by nextGaussian, 091 * which generates two gaussian numbers by one call, and returns the 092 * second on the second call. 093 * 094 * @serial the second gaussian of a pair 095 * @see #nextGaussian() 096 * @see #haveNextNextGaussian 097 */ 098 private double nextNextGaussian; 099 100 /** 101 * The seed. This is the number set by setSeed and which is used 102 * in next. 103 * 104 * @serial the internal state of this generator 105 * @see #next(int) 106 */ 107 private long seed; 108 109 /** 110 * Compatible with JDK 1.0+. 111 */ 112 private static final long serialVersionUID = 3905348978240129619L; 113 114 /** 115 * Creates a new pseudorandom number generator. The seed is initialized 116 * to the current time, as if by 117 * <code>setSeed(System.currentTimeMillis());</code>. 118 * 119 * @see System#currentTimeMillis() 120 */ 121 public Random() 122 { 123 this(System.currentTimeMillis()); 124 } 125 126 /** 127 * Creates a new pseudorandom number generator, starting with the 128 * specified seed, using <code>setSeed(seed);</code>. 129 * 130 * @param seed the initial seed 131 */ 132 public Random(long seed) 133 { 134 setSeed(seed); 135 } 136 137 /** 138 * Sets the seed for this pseudorandom number generator. As described 139 * above, two instances of the same random class, starting with the 140 * same seed, should produce the same results, if the same methods 141 * are called. The implementation for java.util.Random is: 142 * 143 <pre>public synchronized void setSeed(long seed) 144 { 145 this.seed = (seed ^ 0x5DEECE66DL) & ((1L << 48) - 1); 146 haveNextNextGaussian = false; 147 }</pre> 148 * 149 * @param seed the new seed 150 */ 151 public synchronized void setSeed(long seed) 152 { 153 this.seed = (seed ^ 0x5DEECE66DL) & ((1L << 48) - 1); 154 haveNextNextGaussian = false; 155 } 156 157 /** 158 * Generates the next pseudorandom number. This returns 159 * an int value whose <code>bits</code> low order bits are 160 * independent chosen random bits (0 and 1 are equally likely). 161 * The implementation for java.util.Random is: 162 * 163 <pre>protected synchronized int next(int bits) 164 { 165 seed = (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1); 166 return (int) (seed >>> (48 - bits)); 167 }</pre> 168 * 169 * @param bits the number of random bits to generate, in the range 1..32 170 * @return the next pseudorandom value 171 * @since 1.1 172 */ 173 protected synchronized int next(int bits) 174 { 175 seed = (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1); 176 return (int) (seed >>> (48 - bits)); 177 } 178 179 /** 180 * Fills an array of bytes with random numbers. All possible values 181 * are (approximately) equally likely. 182 * The JDK documentation gives no implementation, but it seems to be: 183 * 184 <pre>public void nextBytes(byte[] bytes) 185 { 186 for (int i = 0; i < bytes.length; i += 4) 187 { 188 int random = next(32); 189 for (int j = 0; i + j < bytes.length && j < 4; j++) 190 { 191 bytes[i+j] = (byte) (random & 0xff) 192 random >>= 8; 193 } 194 } 195 }</pre> 196 * 197 * @param bytes the byte array that should be filled 198 * @throws NullPointerException if bytes is null 199 * @since 1.1 200 */ 201 public void nextBytes(byte[] bytes) 202 { 203 int random; 204 // Do a little bit unrolling of the above algorithm. 205 int max = bytes.length & ~0x3; 206 for (int i = 0; i < max; i += 4) 207 { 208 random = next(32); 209 bytes[i] = (byte) random; 210 bytes[i + 1] = (byte) (random >> 8); 211 bytes[i + 2] = (byte) (random >> 16); 212 bytes[i + 3] = (byte) (random >> 24); 213 } 214 if (max < bytes.length) 215 { 216 random = next(32); 217 for (int j = max; j < bytes.length; j++) 218 { 219 bytes[j] = (byte) random; 220 random >>= 8; 221 } 222 } 223 } 224 225 /** 226 * Generates the next pseudorandom number. This returns 227 * an int value whose 32 bits are independent chosen random bits 228 * (0 and 1 are equally likely). The implementation for 229 * java.util.Random is: 230 * 231 <pre>public int nextInt() 232 { 233 return next(32); 234 }</pre> 235 * 236 * @return the next pseudorandom value 237 */ 238 public int nextInt() 239 { 240 return next(32); 241 } 242 243 /** 244 * Generates the next pseudorandom number. This returns 245 * a value between 0(inclusive) and <code>n</code>(exclusive), and 246 * each value has the same likelihodd (1/<code>n</code>). 247 * (0 and 1 are equally likely). The implementation for 248 * java.util.Random is: 249 * 250 <pre> 251 public int nextInt(int n) 252 { 253 if (n <= 0) 254 throw new IllegalArgumentException("n must be positive"); 255 256 if ((n & -n) == n) // i.e., n is a power of 2 257 return (int)((n * (long) next(31)) >> 31); 258 259 int bits, val; 260 do 261 { 262 bits = next(31); 263 val = bits % n; 264 } 265 while(bits - val + (n-1) < 0); 266 267 return val; 268 }</pre> 269 * 270 * <p>This algorithm would return every value with exactly the same 271 * probability, if the next()-method would be a perfect random number 272 * generator. 273 * 274 * The loop at the bottom only accepts a value, if the random 275 * number was between 0 and the highest number less then 1<<31, 276 * which is divisible by n. The probability for this is high for small 277 * n, and the worst case is 1/2 (for n=(1<<30)+1). 278 * 279 * The special treatment for n = power of 2, selects the high bits of 280 * the random number (the loop at the bottom would select the low order 281 * bits). This is done, because the low order bits of linear congruential 282 * number generators (like the one used in this class) are known to be 283 * ``less random'' than the high order bits. 284 * 285 * @param n the upper bound 286 * @throws IllegalArgumentException if the given upper bound is negative 287 * @return the next pseudorandom value 288 * @since 1.2 289 */ 290 public int nextInt(int n) 291 { 292 if (n <= 0) 293 throw new IllegalArgumentException("n must be positive"); 294 if ((n & -n) == n) // i.e., n is a power of 2 295 return (int) ((n * (long) next(31)) >> 31); 296 int bits, val; 297 do 298 { 299 bits = next(31); 300 val = bits % n; 301 } 302 while (bits - val + (n - 1) < 0); 303 return val; 304 } 305 306 /** 307 * Generates the next pseudorandom long number. All bits of this 308 * long are independently chosen and 0 and 1 have equal likelihood. 309 * The implementation for java.util.Random is: 310 * 311 <pre>public long nextLong() 312 { 313 return ((long) next(32) << 32) + next(32); 314 }</pre> 315 * 316 * @return the next pseudorandom value 317 */ 318 public long nextLong() 319 { 320 return ((long) next(32) << 32) + next(32); 321 } 322 323 /** 324 * Generates the next pseudorandom boolean. True and false have 325 * the same probability. The implementation is: 326 * 327 <pre>public boolean nextBoolean() 328 { 329 return next(1) != 0; 330 }</pre> 331 * 332 * @return the next pseudorandom boolean 333 * @since 1.2 334 */ 335 public boolean nextBoolean() 336 { 337 return next(1) != 0; 338 } 339 340 /** 341 * Generates the next pseudorandom float uniformly distributed 342 * between 0.0f (inclusive) and 1.0f (exclusive). The 343 * implementation is as follows. 344 * 345 <pre>public float nextFloat() 346 { 347 return next(24) / ((float)(1 << 24)); 348 }</pre> 349 * 350 * @return the next pseudorandom float 351 */ 352 public float nextFloat() 353 { 354 return next(24) / (float) (1 << 24); 355 } 356 357 /** 358 * Generates the next pseudorandom double uniformly distributed 359 * between 0.0 (inclusive) and 1.0 (exclusive). The 360 * implementation is as follows. 361 * 362 <pre>public double nextDouble() 363 { 364 return (((long) next(26) << 27) + next(27)) / (double)(1L << 53); 365 }</pre> 366 * 367 * @return the next pseudorandom double 368 */ 369 public double nextDouble() 370 { 371 return (((long) next(26) << 27) + next(27)) / (double) (1L << 53); 372 } 373 374 /** 375 * Generates the next pseudorandom, Gaussian (normally) distributed 376 * double value, with mean 0.0 and standard deviation 1.0. 377 * The algorithm is as follows. 378 * 379 <pre>public synchronized double nextGaussian() 380 { 381 if (haveNextNextGaussian) 382 { 383 haveNextNextGaussian = false; 384 return nextNextGaussian; 385 } 386 else 387 { 388 double v1, v2, s; 389 do 390 { 391 v1 = 2 * nextDouble() - 1; // between -1.0 and 1.0 392 v2 = 2 * nextDouble() - 1; // between -1.0 and 1.0 393 s = v1 * v1 + v2 * v2; 394 } 395 while (s >= 1); 396 397 double norm = Math.sqrt(-2 * Math.log(s) / s); 398 nextNextGaussian = v2 * norm; 399 haveNextNextGaussian = true; 400 return v1 * norm; 401 } 402 }</pre> 403 * 404 * <p>This is described in section 3.4.1 of <em>The Art of Computer 405 * Programming, Volume 2</em> by Donald Knuth. 406 * 407 * @return the next pseudorandom Gaussian distributed double 408 */ 409 public synchronized double nextGaussian() 410 { 411 if (haveNextNextGaussian) 412 { 413 haveNextNextGaussian = false; 414 return nextNextGaussian; 415 } 416 double v1, v2, s; 417 do 418 { 419 v1 = 2 * nextDouble() - 1; // Between -1.0 and 1.0. 420 v2 = 2 * nextDouble() - 1; // Between -1.0 and 1.0. 421 s = v1 * v1 + v2 * v2; 422 } 423 while (s >= 1); 424 double norm = Math.sqrt(-2 * Math.log(s) / s); 425 nextNextGaussian = v2 * norm; 426 haveNextNextGaussian = true; 427 return v1 * norm; 428 } 429 }