libjava/java/util/Random.java

   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., 59 Temple Place, Suite 330, Boston, MA
  19 02111-1307 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()
 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 }