libjava/java/util/Random.java

   1 /* java.util.Random
   2    Copyright (C) 1998, 1999, 2000, 2001 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 /**
  42  * This class generates pseudorandom numbers.  It uses the same
  43  * algorithm as the original JDK-class, so that your programs behave
  44  * exactly the same way, if started with the same seed.
  45  *
  46  * The algorithm is described in <em>The Art of Computer Programming,
  47  * Volume 2</em> by Donald Knuth in Section 3.2.1.
  48  *
  49  * If two instances of this class are created with the same seed and
  50  * the same calls to these classes are made, they behave exactly the
  51  * same way.  This should be even true for foreign implementations
  52  * (like this), so every port must use the same algorithm as described
  53  * here.
  54  *
  55  * If you want to implement your own pseudorandom algorithm, you
  56  * should extend this class and overload the <code>next()</code> and
  57  * <code>setSeed(long)</code> method.  In that case the above
  58  * paragraph doesn't apply to you.
  59  *
  60  * This class shouldn't be used for security sensitive purposes (like
  61  * generating passwords or encryption keys.  See <code>SecureRandom</code>
  62  * in package <code>java.security</code> for this purpose.
  63  *
  64  * For simple random doubles between 0.0 and 1.0, you may consider using
  65  * Math.random instead.
  66  *
  67  * @see java.security.SecureRandom
  68  * @see Math#random()
  69  * @author Jochen Hoenicke */
  70 public class Random implements java.io.Serializable
  71 {
  72   /**
  73    * True if the next nextGaussian is available.  This is used by
  74    * nextGaussian, which generates two gaussian numbers by one call,
  75    * and returns the second on the second call.
  76    * @see #nextGaussian.  */
  77   private boolean haveNextNextGaussian;
  78   /**
  79    * The next nextGaussian if available.  This is used by nextGaussian,
  80    * which generates two gaussian numbers by one call, and returns the
  81    * second on the second call.
  82    * @see #nextGaussian.
  83    */
  84   private double nextNextGaussian;
  85   /**
  86    * The seed.  This is the number set by setSeed and which is used
  87    * in next.
  88    * @see #next
  89    */
  90   private long seed;
  91
  92   private static final long serialVersionUID = 3905348978240129619L;
  93
  94   /**
  95    * Creates a new pseudorandom number generator.  The seed is initialized
  96    * to the current time as follows.
  97    * <pre>
  98    * setSeed(System.currentTimeMillis());
  99    * </pre>
 100    * @see System#currentTimeMillis()
 101    */
 102   public Random()
 103   {
 104     setSeed(System.currentTimeMillis());
 105   }
 106
 107   /**
 108    * Creates a new pseudorandom number generator, starting with the
 109    * specified seed. This does:
 110    * <pre>
 111    * setSeed(seed);
 112    * </pre>
 113    * @param seed the initial seed.
 114    */
 115   public Random(long seed)
 116   {
 117     setSeed(seed);
 118   }
 119
 120   /**
 121    * Sets the seed for this pseudorandom number generator.  As described
 122    * above, two instances of the same random class, starting with the
 123    * same seed, should produce the same results, if the same methods
 124    * are called.  The implementation for java.util.Random is:
 125    * <pre>
 126    * public synchronized void setSeed(long seed) {
 127    *     this.seed = (seed ^ 0x5DEECE66DL) & ((1L << 48) - 1);
 128    *     haveNextNextGaussian = false;
 129    * }
 130    * </pre>
 131    */
 132   public synchronized void setSeed(long seed)
 133   {
 134     this.seed = (seed ^ 0x5DEECE66DL) & ((1L << 48) - 1);
 135     haveNextNextGaussian = false;
 136   }
 137
 138   /**
 139    * Generates the next pseudorandom number.  This returns
 140    * an int value whose <code>bits</code> low order bits are
 141    * independent chosen random bits (0 and 1 are equally likely).
 142    * The implementation for java.util.Random is:
 143    * <pre>
 144    * protected synchronized int next(int bits) {
 145    *     seed = (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1);
 146    *     return (int) (seed >>> (48 - bits));
 147    * }
 148    * </pre>
 149    * @param bits the number of random bits to generate.  Must be in range
 150    * 1..32.
 151    * @return the next pseudorandom value.
 152    * @since JDK1.1
 153    */
 154   protected synchronized int next(int bits)
 155     /*{ require { 1 <= bits && bits <=32 ::
 156        "bits "+bits+" not in range [1..32]" } } */
 157   {
 158     seed = (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1);
 159     return (int) (seed >>> (48 - bits));
 160   }
 161
 162   /**
 163    * Fills an array of bytes with random numbers.  All possible values
 164    * are (approximately) equally likely.
 165    * The JDK documentation gives no implementation, but it seems to be:
 166    * <pre>
 167    * public void nextBytes(byte[] bytes) {
 168    *     for (int i=0; i< bytes.length; i+=4) {
 169    *         int random = next(32);
 170    *         for (int j=0; i+j< bytes.length && j<4; j++)
 171    *             bytes[i+j] = (byte) (random & 0xff)
 172    *             random >>= 8;
 173    *         }
 174    *     }
 175    * }
 176    * </pre>
 177    * @param bytes The byte array that should be filled.
 178    * @since JDK1.1
 179    */
 180   public void nextBytes(byte[] bytes)
 181     /*{ require { bytes != null :: "bytes is null"; } } */
 182   {
 183     int random;
 184     /* Do a little bit unrolling of the above algorithm. */
 185     int max = bytes.length & ~0x3;
 186     for (int i = 0; i < max; i += 4)
 187       {
 188         random = next(32);
 189         bytes[i] = (byte) random;
 190         bytes[i + 1] = (byte) (random >> 8);
 191         bytes[i + 2] = (byte) (random >> 16);
 192         bytes[i + 3] = (byte) (random >> 24);
 193       }
 194     if (max < bytes.length)
 195       {
 196         random = next(32);
 197         for (int j = max; j < bytes.length; j++)
 198           {
 199             bytes[j] = (byte) random;
 200             random >>= 8;
 201           }
 202       }
 203   }
 204
 205   /**
 206    * Generates the next pseudorandom number.  This returns
 207    * an int value whose 32 bits are independent chosen random bits
 208    * (0 and 1 are equally likely).  The implementation for
 209    * java.util.Random is:
 210    * <pre>
 211    * public int nextInt() {
 212    *     return next(32);
 213    * }
 214    * </pre>
 215    *
 216    * @return the next pseudorandom value.  */
 217   public int nextInt()
 218   {
 219     return next(32);
 220   }
 221
 222   /**
 223    * Generates the next pseudorandom number.  This returns
 224    * a value between 0(inclusive) and <code>n</code>(exclusive), and
 225    * each value has the same likelihodd (1/<code>n</code>).
 226    * (0 and 1 are equally likely).  The implementation for
 227    * java.util.Random is:
 228    * <pre>
 229    * public int nextInt(int n) {
 230    *     if (n<=0)
 231    *         throw new IllegalArgumentException("n must be positive");
 232    *     if ((n & -n) == n)  // i.e., n is a power of 2
 233    *         return (int)((n * (long)next(31)) >> 31);
 234    *     int bits, val;
 235    *     do {
 236    *         bits = next(32);
 237    *         val = bits % n;
 238    *     } while(bits - val + (n-1) < 0);
 239    *     return val;
 240    * }
 241    * </pre>
 242    * This algorithm would return every value with exactly the same
 243    * probability, if the next()-method would be a perfect random number
 244    * generator.
 245    *
 246    * The loop at the bottom only accepts a value, if the random
 247    * number was between 0 and the highest number less then 1<<31,
 248    * which is divisible by n.  The probability for this is high for small
 249    * n, and the worst case is 1/2 (for n=(1<<30)+1).
 250    *
 251    * The special treatment for n = power of 2, selects the high bits of
 252    * the random number (the loop at the bottom would select the low order
 253    * bits).  This is done, because the low order bits of linear congruential
 254    * number generators (like the one used in this class) are known to be
 255    * ``less random'' than the high order bits.
 256    *
 257    * @param n the upper bound.
 258    * @exception IllegalArgumentException if the given upper bound is negative
 259    * @return the next pseudorandom value.
 260    */
 261   public int nextInt(int n)
 262     /*{ require { n > 0 :: "n must be positive"; } } */
 263   {
 264     if (n <= 0)
 265       throw new IllegalArgumentException("n must be positive");
 266     if ((n & -n) == n)          // i.e., n is a power of 2
 267       return (int) ((n * (long) next(31)) >> 31);
 268     int bits, val;
 269     do
 270       {
 271         bits = next(32);
 272         val = bits % n;
 273       }
 274     while (bits - val + (n - 1) < 0);
 275     return val;
 276   }
 277
 278   /**
 279    * Generates the next pseudorandom long number.  All bits of this
 280    * long are independently chosen and 0 and 1 have equal likelihood.
 281    * The implementation for java.util.Random is:
 282    * <pre>
 283    * public long nextLong() {
 284    *     return ((long)next(32) << 32) + next(32);
 285    * }
 286    * </pre>
 287    * @return the next pseudorandom value.
 288    */
 289   public long nextLong()
 290   {
 291     return ((long) next(32) << 32) + next(32);
 292   }
 293
 294   /**
 295    * Generates the next pseudorandom boolean.  True and false have
 296    * the same probability.  The implementation is:
 297    * <pre>
 298    * public boolean nextBoolean() {
 299    *     return next(1) != 0;
 300    * }
 301    * </pre>
 302    * @return the next pseudorandom boolean.
 303    */
 304   public boolean nextBoolean()
 305   {
 306     return next(1) != 0;
 307   }
 308
 309   /**
 310    * Generates the next pseudorandom float uniformly distributed
 311    * between 0.0f (inclusive) and 1.0 (exclusive).  The
 312    * implementation is as follows.
 313    * <pre>
 314    * public float nextFloat() {
 315    *     return next(24) / ((float)(1 << 24));
 316    * }
 317    * </pre>
 318    * @return the next pseudorandom float.  */
 319   public float nextFloat()
 320   {
 321     return next(24) / ((float) (1 << 24));
 322   }
 323
 324   /**
 325    * Generates the next pseudorandom double uniformly distributed
 326    * between 0.0f (inclusive) and 1.0 (exclusive).  The
 327    * implementation is as follows.
 328    * <pre>
 329    * public double nextDouble() {
 330    *     return (((long)next(26) << 27) + next(27)) / (double)(1 << 53);
 331    * }
 332    * </pre>
 333    * @return the next pseudorandom double.  */
 334   public double nextDouble()
 335   {
 336     return (((long) next(26) << 27) + next(27)) / (double) (1L << 53);
 337   }
 338
 339   /**
 340    * Generates the next pseudorandom, Gaussian (normally) distributed
 341    * double value, with mean 0.0 and standard deviation 1.0.
 342    * The algorithm is as follows.
 343    * <pre>
 344    * public synchronized double nextGaussian() {
 345    *     if (haveNextNextGaussian) {
 346    *         haveNextNextGaussian = false;
 347    *         return nextNextGaussian;
 348    *     } else {
 349    *         double v1, v2, s;
 350    *         do {
 351    *             v1 = 2 * nextDouble() - 1; // between -1.0 and 1.0
 352    *             v2 = 2 * nextDouble() - 1; // between -1.0 and 1.0
 353    *             s = v1 * v1 + v2 * v2;
 354    *         } while (s >= 1);
 355    *         double norm = Math.sqrt(-2 * Math.log(s)/s);
 356    *         nextNextGaussian = v2 * norm;
 357    *         haveNextNextGaussian = true;
 358    *         return v1 * norm;
 359    *     }
 360    * }
 361    * </pre>
 362    * This is described in section 3.4.1 of <em>The Art of Computer
 363    * Programming, Volume 2</em> by Donald Knuth.
 364    *
 365    * @return the next pseudorandom Gaussian distributed double.
 366    */
 367   public synchronized double nextGaussian()
 368   {
 369     if (haveNextNextGaussian)
 370       {
 371         haveNextNextGaussian = false;
 372         return nextNextGaussian;
 373       }
 374     else
 375       {
 376         double v1, v2, s;
 377         do
 378           {
 379             v1 = 2 * nextDouble() - 1;  // between -1.0 and 1.0
 380             v2 = 2 * nextDouble() - 1;  // between -1.0 and 1.0
 381             s = v1 * v1 + v2 * v2;
 382           }
 383         while (s >= 1);
 384         double norm = Math.sqrt(-2 * Math.log(s) / s);
 385         nextNextGaussian = v2 * norm;
 386         haveNextNextGaussian = true;
 387         return v1 * norm;
 388       }
 389   }
 390 }