Source for java.util.Random

   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 &lt;&lt; 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 &lt;&lt; 48) - 1);
 166:   return (int) (seed &gt;&gt;&gt; (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 &lt; bytes.length; i += 4)
 187:   {
 188:     int random = next(32);
 189:     for (int j = 0; i + j &lt; bytes.length && j &lt; 4; j++)
 190:     {
 191:       bytes[i+j] = (byte) (random & 0xff)
 192:       random &gt;&gt;= 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 &lt;= 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)) &gt;&gt; 31);
 258: 
 259:   int bits, val;
 260:   do
 261:   {
 262:     bits = next(31);
 263:     val = bits % n;
 264:   }
 265:   while(bits - val + (n-1) &lt; 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) &lt;&lt; 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 &lt;&lt; 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) &lt;&lt; 27) + next(27)) / (double)(1L &lt;&lt; 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: }