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     setSeed(System.currentTimeMillis());
 115   }
 116
 117   /**
 118    * Creates a new pseudorandom number generator, starting with the
 119    * specified seed, using <code>setSeed(seed);</code>.
 120    *
 121    * @param seed the initial seed
 122    */
 123   public Random(long seed) {
 124     setSeed(seed);
 125   }
 126
 127   /**
 128    * Sets the seed for this pseudorandom number generator.  As described
 129    * above, two instances of the same random class, starting with the
 130    * same seed, should produce the same results, if the same methods
 131    * are called.  The implementation for java.util.Random is:
 132    *
 133      <pre>public synchronized void setSeed(long seed)
 134      {
 135      this.seed = (seed ^ 0x5DEECE66DL) & ((1L &lt;&lt; 48) - 1);
 136      haveNextNextGaussian = false;
 137      }</pre>
 138    *
 139    * @param seed the new seed
 140    */
 141   public synchronized void setSeed(long seed) {
 142     this.seed = (seed ^ 0x5DEECE66DL) & ((1L << 48) - 1);
 143     haveNextNextGaussian = false;
 144   }
 145
 146   /**
 147    * Generates the next pseudorandom number.  This returns
 148    * an int value whose <code>bits</code> low order bits are
 149    * independent chosen random bits (0 and 1 are equally likely).
 150    * The implementation for java.util.Random is:
 151    *
 152      <pre>protected synchronized int next(int bits)
 153      {
 154      seed = (seed * 0x5DEECE66DL + 0xBL) & ((1L &lt;&lt; 48) - 1);
 155      return (int) (seed &gt;&gt;&gt; (48 - bits));
 156      }</pre>
 157    *
 158    * @param bits the number of random bits to generate, in the range 1..32
 159    * @return the next pseudorandom value
 160    * @since 1.1
 161    */
 162   protected synchronized int next(int bits) {
 163     seed = (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1);
 164     return (int) (seed >>> (48 - bits));
 165   }
 166
 167   /**
 168    * Fills an array of bytes with random numbers.  All possible values
 169    * are (approximately) equally likely.
 170    * The JDK documentation gives no implementation, but it seems to be:
 171    *
 172      <pre>public void nextBytes(byte[] bytes)
 173      {
 174      for (int i = 0; i &lt; bytes.length; i += 4)
 175      {
 176      int random = next(32);
 177      for (int j = 0; i + j &lt; bytes.length && j &lt; 4; j++)
 178      {
 179       bytes[i+j] = (byte) (random & 0xff)
 180       random &gt;&gt;= 8;
 181      }
 182      }
 183      }</pre>
 184    *
 185    * @param bytes the byte array that should be filled
 186    * @throws NullPointerException if bytes is null
 187    * @since 1.1
 188    */
 189   public void nextBytes(byte[] bytes) {
 190     int random;
 191     // Do a little bit unrolling of the above algorithm.
 192     int max = bytes.length & ~0x3;
 193     for (int i = 0; i < max; i += 4)
 194     {
 195       random = next(32);
 196       bytes[i] = (byte) random;
 197       bytes[i + 1] = (byte) (random >> 8);
 198       bytes[i + 2] = (byte) (random >> 16);
 199       bytes[i + 3] = (byte) (random >> 24);
 200     }
 201     if (max < bytes.length){
 202       random = next(32);
 203       for (int j = max; j < bytes.length; j++)
 204       {
 205         bytes[j] = (byte) random;
 206         random >>= 8;
 207       }
 208     }
 209   }
 210
 211   /**
 212    * Generates the next pseudorandom number.  This returns
 213    * an int value whose 32 bits are independent chosen random bits
 214    * (0 and 1 are equally likely).  The implementation for
 215    * java.util.Random is:
 216    *
 217      <pre>public int nextInt()
 218      {
 219      return next(32);
 220      }</pre>
 221    *
 222    * @return the next pseudorandom value
 223    */
 224   public int nextInt() {
 225     return next(32);
 226   }
 227
 228   /**
 229    * Generates the next pseudorandom number.  This returns
 230    * a value between 0(inclusive) and <code>n</code>(exclusive), and
 231    * each value has the same likelihodd (1/<code>n</code>).
 232    * (0 and 1 are equally likely).  The implementation for
 233    * java.util.Random is:
 234    *
 235      <pre>
 236      public int nextInt(int n)
 237      {
 238      if (n &lt;= 0)
 239      throw new IllegalArgumentException("n must be positive");
 240
 241      if ((n & -n) == n)  // i.e., n is a power of 2
 242      return (int)((n * (long) next(31)) &gt;&gt; 31);
 243
 244      int bits, val;
 245      do
 246      {
 247      bits = next(31);
 248      val = bits % n;
 249      }
 250      while(bits - val + (n-1) &lt; 0);
 251
 252      return val;
 253      }</pre>
 254    *
 255    * <p>This algorithm would return every value with exactly the same
 256    * probability, if the next()-method would be a perfect random number
 257    * generator.
 258    *
 259    * The loop at the bottom only accepts a value, if the random
 260    * number was between 0 and the highest number less then 1<<31,
 261    * which is divisible by n.  The probability for this is high for small
 262    * n, and the worst case is 1/2 (for n=(1<<30)+1).
 263    *
 264    * The special treatment for n = power of 2, selects the high bits of
 265    * the random number (the loop at the bottom would select the low order
 266    * bits).  This is done, because the low order bits of linear congruential
 267    * number generators (like the one used in this class) are known to be
 268    * ``less random'' than the high order bits.
 269    *
 270    * @param n the upper bound
 271    * @throws IllegalArgumentException if the given upper bound is negative
 272    * @return the next pseudorandom value
 273    * @since 1.2
 274    */
 275   public int nextInt(int n) {
 276     if (n <= 0)
 277       System.printString("ERROR: n must be positive\n");
 278     if ((n & -n) == n) // i.e., n is a power of 2
 279       return (int) ((n * (long) next(31)) >> 31);
 280     int bits, val;
 281     do {
 282       bits = next(31);
 283       val = bits % n;
 284     } while (bits - val + (n - 1) < 0);
 285     return val;
 286   }
 287
 288   /**
 289    * Generates the next pseudorandom long number.  All bits of this
 290    * long are independently chosen and 0 and 1 have equal likelihood.
 291    * The implementation for java.util.Random is:
 292    *
 293      <pre>public long nextLong()
 294      {
 295      return ((long) next(32) &lt;&lt; 32) + next(32);
 296      }</pre>
 297    *
 298    * @return the next pseudorandom value
 299    */
 300   public long nextLong() {
 301     return ((long) next(32) << 32) + next(32);
 302   }
 303
 304   /**
 305    * Generates the next pseudorandom boolean.  True and false have
 306    * the same probability.  The implementation is:
 307    *
 308      <pre>public boolean nextBoolean()
 309      {
 310      return next(1) != 0;
 311      }</pre>
 312    *
 313    * @return the next pseudorandom boolean
 314    * @since 1.2
 315    */
 316   public boolean nextBoolean() {
 317     return next(1) != 0;
 318   }
 319
 320   /**
 321    * Generates the next pseudorandom float uniformly distributed
 322    * between 0.0f (inclusive) and 1.0f (exclusive).  The
 323    * implementation is as follows.
 324    *
 325      <pre>public float nextFloat()
 326      {
 327      return next(24) / ((float)(1 &lt;&lt; 24));
 328      }</pre>
 329    *
 330    * @return the next pseudorandom float
 331    */
 332   public float nextFloat() {
 333     return next(24) / (float) (1 << 24);
 334   }
 335
 336   /**
 337    * Generates the next pseudorandom double uniformly distributed
 338    * between 0.0 (inclusive) and 1.0 (exclusive).  The
 339    * implementation is as follows.
 340    *
 341      <pre>public double nextDouble()
 342      {
 343      return (((long) next(26) &lt;&lt; 27) + next(27)) / (double)(1L &lt;&lt; 53);
 344      }</pre>
 345    *
 346    * @return the next pseudorandom double
 347    */
 348   public double nextDouble() {
 349     return (((long) next(26) << 27) + next(27)) / (double) (1L << 53);
 350   }
 351
 352   /**
 353    * Generates the next pseudorandom, Gaussian (normally) distributed
 354    * double value, with mean 0.0 and standard deviation 1.0.
 355    * The algorithm is as follows.
 356    *
 357      <pre>public synchronized double nextGaussian()
 358      {
 359      if (haveNextNextGaussian)
 360      {
 361      haveNextNextGaussian = false;
 362      return nextNextGaussian;
 363      }
 364      else
 365      {
 366      double v1, v2, s;
 367      do
 368      {
 369       v1 = 2 * nextDouble() - 1; // between -1.0 and 1.0
 370       v2 = 2 * nextDouble() - 1; // between -1.0 and 1.0
 371       s = v1 * v1 + v2 * v2;
 372      }
 373      while (s >= 1);
 374
 375      double norm = Math.sqrt(-2 * Math.log(s) / s);
 376      nextNextGaussian = v2 * norm;
 377      haveNextNextGaussian = true;
 378      return v1 * norm;
 379      }
 380      }</pre>
 381    *
 382    * <p>This is described in section 3.4.1 of <em>The Art of Computer
 383    * Programming, Volume 2</em> by Donald Knuth.
 384    *
 385    * @return the next pseudorandom Gaussian distributed double
 386    */
 387   public synchronized double nextGaussian() {
 388     if (haveNextNextGaussian){
 389       haveNextNextGaussian = false;
 390       return nextNextGaussian;
 391     }
 392     double v1, v2, s;
 393     do {
 394       v1 = 2 * nextDouble() - 1;   // Between -1.0 and 1.0.
 395       v2 = 2 * nextDouble() - 1;   // Between -1.0 and 1.0.
 396       s = v1 * v1 + v2 * v2;
 397     } while (s >= 1);
 398     double norm = Math.sqrt(-2 * Math.log(s) / s);
 399     nextNextGaussian = v2 * norm;
 400     haveNextNextGaussian = true;
 401     return v1 * norm;
 402   }
 403 }