| Frames | No Frames |
1: /* Random.java -- a pseudo-random number generator 2: Copyright (C) 1998, 1999, 2000, 2001, 2002 Free Software Foundation, Inc. 3: 4: This file is part of GNU Classpath. 5: 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) 9: any later version. 10: 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. 15: 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 19: 02110-1301 USA. 20: 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 24: combination. 25: 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. */ 37: 38: 39: package java.util; 40: 41: import java.io.Serializable; 42: 43: /** 44: * This class generates pseudorandom numbers. It uses the same 45: * algorithm as the original JDK-class, so that your programs behave 46: * exactly the same way, if started with the same seed. 47: * 48: * The algorithm is described in <em>The Art of Computer Programming, 49: * Volume 2</em> by Donald Knuth in Section 3.2.1. It is a 48-bit seed, 50: * linear congruential formula. 51: * 52: * If two instances of this class are created with the same seed and 53: * the same calls to these classes are made, they behave exactly the 54: * same way. This should be even true for foreign implementations 55: * (like this), so every port must use the same algorithm as described 56: * here. 57: * 58: * If you want to implement your own pseudorandom algorithm, you 59: * should extend this class and overload the <code>next()</code> and 60: * <code>setSeed(long)</code> method. In that case the above 61: * paragraph doesn't apply to you. 62: * 63: * This class shouldn't be used for security sensitive purposes (like 64: * generating passwords or encryption keys. See <code>SecureRandom</code> 65: * in package <code>java.security</code> for this purpose. 66: * 67: * For simple random doubles between 0.0 and 1.0, you may consider using 68: * Math.random instead. 69: * 70: * @see java.security.SecureRandom 71: * @see Math#random() 72: * @author Jochen Hoenicke 73: * @author Eric Blake (ebb9@email.byu.edu) 74: * @status updated to 1.4 75: */ 76: public class Random implements Serializable 77: { 78: /** 79: * True if the next nextGaussian is available. This is used by 80: * nextGaussian, which generates two gaussian numbers by one call, 81: * and returns the second on the second call. 82: * 83: * @serial whether nextNextGaussian is available 84: * @see #nextGaussian() 85: * @see #nextNextGaussian 86: */ 87: private boolean haveNextNextGaussian; 88: 89: /** 90: * The next nextGaussian, when available. This is used by nextGaussian, 91: * which generates two gaussian numbers by one call, and returns the 92: * second on the second call. 93: * 94: * @serial the second gaussian of a pair 95: * @see #nextGaussian() 96: * @see #haveNextNextGaussian 97: */ 98: private double nextNextGaussian; 99: 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: }