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