Robust/Transactions/dstm2src/util/Random.java

   1 /*
   2  * Random.java
   3  *
   4  * Copyright 2006 Sun Microsystems, Inc., 4150 Network Circle, Santa
   5  * Clara, California 95054, U.S.A.  All rights reserved.
   6  *
   7  * Sun Microsystems, Inc. has intellectual property rights relating to
   8  * technology embodied in the product that is described in this
   9  * document.  In particular, and without limitation, these
  10  * intellectual property rights may include one or more of the
  11  * U.S. patents listed at http://www.sun.com/patents and one or more
  12  * additional patents or pending patent applications in the U.S. and
  13  * in other countries.
  14  *
  15  * U.S. Government Rights - Commercial software.
  16  * Government users are subject to the Sun Microsystems, Inc. standard
  17  * license agreement and applicable provisions of the FAR and its
  18  * supplements.  Use is subject to license terms.  Sun, Sun
  19  * Microsystems, the Sun logo and Java are trademarks or registered
  20  * trademarks of Sun Microsystems, Inc. in the U.S. and other
  21  * countries.
  22  *
  23  * This product is covered and controlled by U.S. Export Control laws
  24  * and may be subject to the export or import laws in other countries.
  25  * Nuclear, missile, chemical biological weapons or nuclear maritime
  26  * end uses or end users, whether direct or indirect, are strictly
  27  * prohibited.  Export or reexport to countries subject to
  28  * U.S. embargo or to entities identified on U.S. export exclusion
  29  * lists, including, but not limited to, the denied persons and
  30  * specially designated nationals lists is strictly prohibited.
  31  */
  32
  33 package dstm2.util;
  34
  35 import java.io.*;
  36 import java.util.concurrent.atomic.AtomicLong;
  37
  38 /**
  39  * Lightweight random number generator.  <I>Not thread-safe.</I> Synchronization in the
  40  * <CODE>java.util.Randome</CODE> can distort the performance of multithreaded benchmarks.
  41  */
  42 public class Random extends java.util.Random {
  43
  44   /** use serialVersionUID from JDK 1.1 for interoperability */
  45   static final long serialVersionUID = 3905348978240129619L;
  46
  47   private long seed;
  48
  49   private final static long multiplier = 0x5DEECE66DL;
  50   private final static long addend = 0xBL;
  51   private final static long mask = (1L << 48) - 1;
  52
  53   /**
  54    * Creates a new random number generator. This constructor sets
  55    * the seed of the random number generator to a value very likely
  56    * to be distinct from any other invocation of this constructor.
  57    */
  58   public Random() { this(++seedUniquifier + System.nanoTime()); }
  59   private static volatile long seedUniquifier = 8682522807148012L;
  60
  61   /**
  62    * Creates a new random number generator using a single
  63    * <code>long</code> seed:
  64    * <blockquote><pre>
  65    * public Random(long seed) { setSeed(seed); }</pre></blockquote>
  66    * Used by method <tt>next</tt> to hold
  67    * the state of the pseudorandom number generator.
  68    *
  69    * @param   seed   the initial seed.
  70    * @see     java.util.Random#setSeed(long)
  71    */
  72   public Random(long seed) {
  73     this.seed = 0L;
  74     setSeed(seed);
  75   }
  76
  77   /**
  78    * Sets the seed of this random number generator using a single
  79    * <code>long</code> seed. The general contract of <tt>setSeed</tt>
  80    * is that it alters the state of this random number generator
  81    * object so as to be in exactly the same state as if it had just
  82    * been created with the argument <tt>seed</tt> as a seed. The method
  83    * <tt>setSeed</tt> is implemented by class Random as follows:
  84    * <blockquote><pre>
  85    * synchronized public void setSeed(long seed) {
  86    *       this.seed = (seed ^ 0x5DEECE66DL) & ((1L << 48) - 1);
  87    *       haveNextNextGaussian = false;
  88    * }</pre></blockquote>
  89    * The implementation of <tt>setSeed</tt> by class <tt>Random</tt>
  90    * happens to use only 48 bits of the given seed. In general, however,
  91    * an overriding method may use all 64 bits of the long argument
  92    * as a seed value.
  93    *
  94    * Note: Although the seed value is an AtomicLong, this method
  95    *       must still be synchronized to ensure correct semantics
  96    *       of haveNextNextGaussian.
  97    *
  98    * @param   seed   the initial seed.
  99    */
 100   public void setSeed(long seed) {
 101     seed = (seed ^ multiplier) & mask;
 102     this.seed = seed;
 103     haveNextNextGaussian = false;
 104   }
 105
 106   /**
 107    * Generates the next pseudorandom number. Subclass should
 108    * override this, as this is used by all other methods.<p>
 109    * The general contract of <tt>next</tt> is that it returns an
 110    * <tt>int</tt> value and if the argument bits is between <tt>1</tt>
 111    * and <tt>32</tt> (inclusive), then that many low-order bits of the
 112    * returned value will be (approximately) independently chosen bit
 113    * values, each of which is (approximately) equally likely to be
 114    * <tt>0</tt> or <tt>1</tt>. The method <tt>next</tt> is implemented
 115    * by class <tt>Random</tt> as follows:
 116    * <blockquote><pre>
 117    * synchronized protected int next(int bits) {
 118    *       seed = (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1);
 119    *       return (int)(seed >>> (48 - bits));
 120    * }</pre></blockquote>
 121    * This is a linear congruential pseudorandom number generator, as
 122    * defined by D. H. Lehmer and described by Donald E. Knuth in <i>The
 123    * Art of Computer Programming,</i> Volume 2: <i>Seminumerical
 124    * Algorithms</i>, section 3.2.1.
 125    *
 126    * @param   bits random bits
 127    * @return  the next pseudorandom value from this random number generator's sequence.
 128    * @since   JDK1.1
 129    */
 130   protected int next(int bits) {
 131     seed = (seed * multiplier + addend) & mask;
 132     return (int)(seed >>> (48 - bits));
 133   }
 134
 135   private static final int BITS_PER_BYTE = 8;
 136   private static final int BYTES_PER_INT = 4;
 137
 138   private double nextNextGaussian;
 139   private boolean haveNextNextGaussian = false;
 140
 141   /**
 142    * Returns the next pseudorandom, Gaussian ("normally") distributed
 143    * <code>double</code> value with mean <code>0.0</code> and standard
 144    * deviation <code>1.0</code> from this random number generator's sequence.
 145    * <p>
 146    * The general contract of <tt>nextGaussian</tt> is that one
 147    * <tt>double</tt> value, chosen from (approximately) the usual
 148    * normal distribution with mean <tt>0.0</tt> and standard deviation
 149    * <tt>1.0</tt>, is pseudorandomly generated and returned. The method
 150    * <tt>nextGaussian</tt> is implemented by class <tt>Random</tt> as follows:
 151    * <blockquote><pre>
 152    * synchronized public double nextGaussian() {
 153    *    if (haveNextNextGaussian) {
 154    *            haveNextNextGaussian = false;
 155    *            return nextNextGaussian;
 156    *    } else {
 157    *            double v1, v2, s;
 158    *            do {
 159    *                    v1 = 2 * nextDouble() - 1;   // between -1.0 and 1.0
 160    *                    v2 = 2 * nextDouble() - 1;   // between -1.0 and 1.0
 161    *                    s = v1 * v1 + v2 * v2;
 162    *            } while (s >= 1 || s == 0);
 163    *            double multiplier = Math.sqrt(-2 * Math.log(s)/s);
 164    *            nextNextGaussian = v2 * multiplier;
 165    *            haveNextNextGaussian = true;
 166    *            return v1 * multiplier;
 167    *    }
 168    * }</pre></blockquote>
 169    * This uses the <i>polar method</i> of G. E. P. Box, M. E. Muller, and
 170    * G. Marsaglia, as described by Donald E. Knuth in <i>The Art of
 171    * Computer Programming</i>, Volume 2: <i>Seminumerical Algorithms</i>,
 172    * section 3.4.1, subsection C, algorithm P. Note that it generates two
 173    * independent values at the cost of only one call to <tt>Math.log</tt>
 174    * and one call to <tt>Math.sqrt</tt>.
 175    *
 176    * @return  the next pseudorandom, Gaussian ("normally") distributed
 177    *          <code>double</code> value with mean <code>0.0</code> and
 178    *          standard deviation <code>1.0</code> from this random number
 179    *          generator's sequence.
 180    */
 181   public double nextGaussian() {
 182     // See Knuth, ACP, Section 3.4.1 Algorithm C.
 183     if (haveNextNextGaussian) {
 184       haveNextNextGaussian = false;
 185       return nextNextGaussian;
 186     } else {
 187       double v1, v2, s;
 188       do {
 189         v1 = 2 * nextDouble() - 1; // between -1 and 1
 190         v2 = 2 * nextDouble() - 1; // between -1 and 1
 191         s = v1 * v1 + v2 * v2;
 192       } while (s >= 1 || s == 0);
 193       double multiplier = Math.sqrt(-2 * Math.log(s)/s);
 194       nextNextGaussian = v2 * multiplier;
 195       haveNextNextGaussian = true;
 196       return v1 * multiplier;
 197     }
 198   }
 199
 200   /**
 201    * Serializable fields for Random.
 202    *
 203    * @serialField    seed long;
 204    *              seed for random computations
 205    * @serialField    nextNextGaussian double;
 206    *              next Gaussian to be returned
 207    * @serialField      haveNextNextGaussian boolean
 208    *              nextNextGaussian is valid
 209    */
 210   private static final ObjectStreamField[] serialPersistentFields = {
 211     new ObjectStreamField("seed", Long.TYPE),
 212         new ObjectStreamField("nextNextGaussian", Double.TYPE),
 213         new ObjectStreamField("haveNextNextGaussian", Boolean.TYPE)
 214   };
 215
 216   /**
 217    * Reconstitute the <tt>Random</tt> instance from a stream (that is,
 218    * deserialize it). The seed is read in as long for
 219    * historical reasons, but it is converted to an AtomicLong.
 220    */
 221   private void readObject(java.io.ObjectInputStream s)
 222   throws java.io.IOException, ClassNotFoundException {
 223
 224     ObjectInputStream.GetField fields = s.readFields();
 225     long seedVal;
 226
 227     seedVal = (long) fields.get("seed", -1L);
 228     if (seedVal < 0)
 229       throw new java.io.StreamCorruptedException(
 230           "Random: invalid seed");
 231     seed = seedVal;
 232     nextNextGaussian = fields.get("nextNextGaussian", 0.0);
 233     haveNextNextGaussian = fields.get("haveNextNextGaussian", false);
 234   }
 235
 236
 237   /**
 238    * Save the <tt>Random</tt> instance to a stream.
 239    * The seed of a Random is serialized as a long for
 240    * historical reasons.
 241    *
 242    */
 243   synchronized private void writeObject(ObjectOutputStream s) throws IOException {
 244     // set the values of the Serializable fields
 245     ObjectOutputStream.PutField fields = s.putFields();
 246     fields.put("seed", seed);
 247     fields.put("nextNextGaussian", nextNextGaussian);
 248     fields.put("haveNextNextGaussian", haveNextNextGaussian);
 249
 250     // save them
 251     s.writeFields();
 252
 253   }
 254
 255 }