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