Save This Page
Home » openjdk-7 » java » util » [javadoc | source]
    1   /*
    2    * Copyright (c) 1995, 2010, Oracle and/or its affiliates. All rights reserved.
    3    * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
    4    *
    5    * This code is free software; you can redistribute it and/or modify it
    6    * under the terms of the GNU General Public License version 2 only, as
    7    * published by the Free Software Foundation.  Oracle designates this
    8    * particular file as subject to the "Classpath" exception as provided
    9    * by Oracle in the LICENSE file that accompanied this code.
   10    *
   11    * This code is distributed in the hope that it will be useful, but WITHOUT
   12    * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
   13    * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
   14    * version 2 for more details (a copy is included in the LICENSE file that
   15    * accompanied this code).
   16    *
   17    * You should have received a copy of the GNU General Public License version
   18    * 2 along with this work; if not, write to the Free Software Foundation,
   19    * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
   20    *
   21    * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
   22    * or visit www.oracle.com if you need additional information or have any
   23    * questions.
   24    */
   25   
   26   package java.util;
   27   import java.io;
   28   import java.util.concurrent.atomic.AtomicLong;
   29   import sun.misc.Unsafe;
   30   
   31   /**
   32    * An instance of this class is used to generate a stream of
   33    * pseudorandom numbers. The class uses a 48-bit seed, which is
   34    * modified using a linear congruential formula. (See Donald Knuth,
   35    * <i>The Art of Computer Programming, Volume 2</i>, Section 3.2.1.)
   36    * <p>
   37    * If two instances of {@code Random} are created with the same
   38    * seed, and the same sequence of method calls is made for each, they
   39    * will generate and return identical sequences of numbers. In order to
   40    * guarantee this property, particular algorithms are specified for the
   41    * class {@code Random}. Java implementations must use all the algorithms
   42    * shown here for the class {@code Random}, for the sake of absolute
   43    * portability of Java code. However, subclasses of class {@code Random}
   44    * are permitted to use other algorithms, so long as they adhere to the
   45    * general contracts for all the methods.
   46    * <p>
   47    * The algorithms implemented by class {@code Random} use a
   48    * {@code protected} utility method that on each invocation can supply
   49    * up to 32 pseudorandomly generated bits.
   50    * <p>
   51    * Many applications will find the method {@link Math#random} simpler to use.
   52    *
   53    * <p>Instances of {@code java.util.Random} are threadsafe.
   54    * However, the concurrent use of the same {@code java.util.Random}
   55    * instance across threads may encounter contention and consequent
   56    * poor performance. Consider instead using
   57    * {@link java.util.concurrent.ThreadLocalRandom} in multithreaded
   58    * designs.
   59    *
   60    * <p>Instances of {@code java.util.Random} are not cryptographically
   61    * secure.  Consider instead using {@link java.security.SecureRandom} to
   62    * get a cryptographically secure pseudo-random number generator for use
   63    * by security-sensitive applications.
   64    *
   65    * @author  Frank Yellin
   66    * @since   1.0
   67    */
   68   public
   69   class Random implements java.io.Serializable {
   70       /** use serialVersionUID from JDK 1.1 for interoperability */
   71       static final long serialVersionUID = 3905348978240129619L;
   72   
   73       /**
   74        * The internal state associated with this pseudorandom number generator.
   75        * (The specs for the methods in this class describe the ongoing
   76        * computation of this value.)
   77        */
   78       private final AtomicLong seed;
   79   
   80       private static final long multiplier = 0x5DEECE66DL;
   81       private static final long addend = 0xBL;
   82       private static final long mask = (1L << 48) - 1;
   83   
   84       /**
   85        * Creates a new random number generator. This constructor sets
   86        * the seed of the random number generator to a value very likely
   87        * to be distinct from any other invocation of this constructor.
   88        */
   89       public Random() {
   90           this(seedUniquifier() ^ System.nanoTime());
   91       }
   92   
   93       private static long seedUniquifier() {
   94           // L'Ecuyer, "Tables of Linear Congruential Generators of
   95           // Different Sizes and Good Lattice Structure", 1999
   96           for (;;) {
   97               long current = seedUniquifier.get();
   98               long next = current * 181783497276652981L;
   99               if (seedUniquifier.compareAndSet(current, next))
  100                   return next;
  101           }
  102       }
  103   
  104       private static final AtomicLong seedUniquifier
  105           = new AtomicLong(8682522807148012L);
  106   
  107       /**
  108        * Creates a new random number generator using a single {@code long} seed.
  109        * The seed is the initial value of the internal state of the pseudorandom
  110        * number generator which is maintained by method {@link #next}.
  111        *
  112        * <p>The invocation {@code new Random(seed)} is equivalent to:
  113        *  <pre> {@code
  114        * Random rnd = new Random();
  115        * rnd.setSeed(seed);}</pre>
  116        *
  117        * @param seed the initial seed
  118        * @see   #setSeed(long)
  119        */
  120       public Random(long seed) {
  121           this.seed = new AtomicLong(initialScramble(seed));
  122       }
  123   
  124       private static long initialScramble(long seed) {
  125           return (seed ^ multiplier) & mask;
  126       }
  127   
  128       /**
  129        * Sets the seed of this random number generator using a single
  130        * {@code long} seed. The general contract of {@code setSeed} is
  131        * that it alters the state of this random number generator object
  132        * so as to be in exactly the same state as if it had just been
  133        * created with the argument {@code seed} as a seed. The method
  134        * {@code setSeed} is implemented by class {@code Random} by
  135        * atomically updating the seed to
  136        *  <pre>{@code (seed ^ 0x5DEECE66DL) & ((1L << 48) - 1)}</pre>
  137        * and clearing the {@code haveNextNextGaussian} flag used by {@link
  138        * #nextGaussian}.
  139        *
  140        * <p>The implementation of {@code setSeed} by class {@code Random}
  141        * happens to use only 48 bits of the given seed. In general, however,
  142        * an overriding method may use all 64 bits of the {@code long}
  143        * argument as a seed value.
  144        *
  145        * @param seed the initial seed
  146        */
  147       synchronized public void setSeed(long seed) {
  148           this.seed.set(initialScramble(seed));
  149           haveNextNextGaussian = false;
  150       }
  151   
  152       /**
  153        * Generates the next pseudorandom number. Subclasses should
  154        * override this, as this is used by all other methods.
  155        *
  156        * <p>The general contract of {@code next} is that it returns an
  157        * {@code int} value and if the argument {@code bits} is between
  158        * {@code 1} and {@code 32} (inclusive), then that many low-order
  159        * bits of the returned value will be (approximately) independently
  160        * chosen bit values, each of which is (approximately) equally
  161        * likely to be {@code 0} or {@code 1}. The method {@code next} is
  162        * implemented by class {@code Random} by atomically updating the seed to
  163        *  <pre>{@code (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1)}</pre>
  164        * and returning
  165        *  <pre>{@code (int)(seed >>> (48 - bits))}.</pre>
  166        *
  167        * This is a linear congruential pseudorandom number generator, as
  168        * defined by D. H. Lehmer and described by Donald E. Knuth in
  169        * <i>The Art of Computer Programming,</i> Volume 3:
  170        * <i>Seminumerical Algorithms</i>, section 3.2.1.
  171        *
  172        * @param  bits random bits
  173        * @return the next pseudorandom value from this random number
  174        *         generator's sequence
  175        * @since  1.1
  176        */
  177       protected int next(int bits) {
  178           long oldseed, nextseed;
  179           AtomicLong seed = this.seed;
  180           do {
  181               oldseed = seed.get();
  182               nextseed = (oldseed * multiplier + addend) & mask;
  183           } while (!seed.compareAndSet(oldseed, nextseed));
  184           return (int)(nextseed >>> (48 - bits));
  185       }
  186   
  187       /**
  188        * Generates random bytes and places them into a user-supplied
  189        * byte array.  The number of random bytes produced is equal to
  190        * the length of the byte array.
  191        *
  192        * <p>The method {@code nextBytes} is implemented by class {@code Random}
  193        * as if by:
  194        *  <pre> {@code
  195        * public void nextBytes(byte[] bytes) {
  196        *   for (int i = 0; i < bytes.length; )
  197        *     for (int rnd = nextInt(), n = Math.min(bytes.length - i, 4);
  198        *          n-- > 0; rnd >>= 8)
  199        *       bytes[i++] = (byte)rnd;
  200        * }}</pre>
  201        *
  202        * @param  bytes the byte array to fill with random bytes
  203        * @throws NullPointerException if the byte array is null
  204        * @since  1.1
  205        */
  206       public void nextBytes(byte[] bytes) {
  207           for (int i = 0, len = bytes.length; i < len; )
  208               for (int rnd = nextInt(),
  209                        n = Math.min(len - i, Integer.SIZE/Byte.SIZE);
  210                    n-- > 0; rnd >>= Byte.SIZE)
  211                   bytes[i++] = (byte)rnd;
  212       }
  213   
  214       /**
  215        * Returns the next pseudorandom, uniformly distributed {@code int}
  216        * value from this random number generator's sequence. The general
  217        * contract of {@code nextInt} is that one {@code int} value is
  218        * pseudorandomly generated and returned. All 2<font size="-1"><sup>32
  219        * </sup></font> possible {@code int} values are produced with
  220        * (approximately) equal probability.
  221        *
  222        * <p>The method {@code nextInt} is implemented by class {@code Random}
  223        * as if by:
  224        *  <pre> {@code
  225        * public int nextInt() {
  226        *   return next(32);
  227        * }}</pre>
  228        *
  229        * @return the next pseudorandom, uniformly distributed {@code int}
  230        *         value from this random number generator's sequence
  231        */
  232       public int nextInt() {
  233           return next(32);
  234       }
  235   
  236       /**
  237        * Returns a pseudorandom, uniformly distributed {@code int} value
  238        * between 0 (inclusive) and the specified value (exclusive), drawn from
  239        * this random number generator's sequence.  The general contract of
  240        * {@code nextInt} is that one {@code int} value in the specified range
  241        * is pseudorandomly generated and returned.  All {@code n} possible
  242        * {@code int} values are produced with (approximately) equal
  243        * probability.  The method {@code nextInt(int n)} is implemented by
  244        * class {@code Random} as if by:
  245        *  <pre> {@code
  246        * public int nextInt(int n) {
  247        *   if (n <= 0)
  248        *     throw new IllegalArgumentException("n must be positive");
  249        *
  250        *   if ((n & -n) == n)  // i.e., n is a power of 2
  251        *     return (int)((n * (long)next(31)) >> 31);
  252        *
  253        *   int bits, val;
  254        *   do {
  255        *       bits = next(31);
  256        *       val = bits % n;
  257        *   } while (bits - val + (n-1) < 0);
  258        *   return val;
  259        * }}</pre>
  260        *
  261        * <p>The hedge "approximately" is used in the foregoing description only
  262        * because the next method is only approximately an unbiased source of
  263        * independently chosen bits.  If it were a perfect source of randomly
  264        * chosen bits, then the algorithm shown would choose {@code int}
  265        * values from the stated range with perfect uniformity.
  266        * <p>
  267        * The algorithm is slightly tricky.  It rejects values that would result
  268        * in an uneven distribution (due to the fact that 2^31 is not divisible
  269        * by n). The probability of a value being rejected depends on n.  The
  270        * worst case is n=2^30+1, for which the probability of a reject is 1/2,
  271        * and the expected number of iterations before the loop terminates is 2.
  272        * <p>
  273        * The algorithm treats the case where n is a power of two specially: it
  274        * returns the correct number of high-order bits from the underlying
  275        * pseudo-random number generator.  In the absence of special treatment,
  276        * the correct number of <i>low-order</i> bits would be returned.  Linear
  277        * congruential pseudo-random number generators such as the one
  278        * implemented by this class are known to have short periods in the
  279        * sequence of values of their low-order bits.  Thus, this special case
  280        * greatly increases the length of the sequence of values returned by
  281        * successive calls to this method if n is a small power of two.
  282        *
  283        * @param n the bound on the random number to be returned.  Must be
  284        *        positive.
  285        * @return the next pseudorandom, uniformly distributed {@code int}
  286        *         value between {@code 0} (inclusive) and {@code n} (exclusive)
  287        *         from this random number generator's sequence
  288        * @throws IllegalArgumentException if n is not positive
  289        * @since 1.2
  290        */
  291   
  292       public int nextInt(int n) {
  293           if (n <= 0)
  294               throw new IllegalArgumentException("n must be positive");
  295   
  296           if ((n & -n) == n)  // i.e., n is a power of 2
  297               return (int)((n * (long)next(31)) >> 31);
  298   
  299           int bits, val;
  300           do {
  301               bits = next(31);
  302               val = bits % n;
  303           } while (bits - val + (n-1) < 0);
  304           return val;
  305       }
  306   
  307       /**
  308        * Returns the next pseudorandom, uniformly distributed {@code long}
  309        * value from this random number generator's sequence. The general
  310        * contract of {@code nextLong} is that one {@code long} value is
  311        * pseudorandomly generated and returned.
  312        *
  313        * <p>The method {@code nextLong} is implemented by class {@code Random}
  314        * as if by:
  315        *  <pre> {@code
  316        * public long nextLong() {
  317        *   return ((long)next(32) << 32) + next(32);
  318        * }}</pre>
  319        *
  320        * Because class {@code Random} uses a seed with only 48 bits,
  321        * this algorithm will not return all possible {@code long} values.
  322        *
  323        * @return the next pseudorandom, uniformly distributed {@code long}
  324        *         value from this random number generator's sequence
  325        */
  326       public long nextLong() {
  327           // it's okay that the bottom word remains signed.
  328           return ((long)(next(32)) << 32) + next(32);
  329       }
  330   
  331       /**
  332        * Returns the next pseudorandom, uniformly distributed
  333        * {@code boolean} value from this random number generator's
  334        * sequence. The general contract of {@code nextBoolean} is that one
  335        * {@code boolean} value is pseudorandomly generated and returned.  The
  336        * values {@code true} and {@code false} are produced with
  337        * (approximately) equal probability.
  338        *
  339        * <p>The method {@code nextBoolean} is implemented by class {@code Random}
  340        * as if by:
  341        *  <pre> {@code
  342        * public boolean nextBoolean() {
  343        *   return next(1) != 0;
  344        * }}</pre>
  345        *
  346        * @return the next pseudorandom, uniformly distributed
  347        *         {@code boolean} value from this random number generator's
  348        *         sequence
  349        * @since 1.2
  350        */
  351       public boolean nextBoolean() {
  352           return next(1) != 0;
  353       }
  354   
  355       /**
  356        * Returns the next pseudorandom, uniformly distributed {@code float}
  357        * value between {@code 0.0} and {@code 1.0} from this random
  358        * number generator's sequence.
  359        *
  360        * <p>The general contract of {@code nextFloat} is that one
  361        * {@code float} value, chosen (approximately) uniformly from the
  362        * range {@code 0.0f} (inclusive) to {@code 1.0f} (exclusive), is
  363        * pseudorandomly generated and returned. All 2<font
  364        * size="-1"><sup>24</sup></font> possible {@code float} values
  365        * of the form <i>m&nbsp;x&nbsp</i>2<font
  366        * size="-1"><sup>-24</sup></font>, where <i>m</i> is a positive
  367        * integer less than 2<font size="-1"><sup>24</sup> </font>, are
  368        * produced with (approximately) equal probability.
  369        *
  370        * <p>The method {@code nextFloat} is implemented by class {@code Random}
  371        * as if by:
  372        *  <pre> {@code
  373        * public float nextFloat() {
  374        *   return next(24) / ((float)(1 << 24));
  375        * }}</pre>
  376        *
  377        * <p>The hedge "approximately" is used in the foregoing description only
  378        * because the next method is only approximately an unbiased source of
  379        * independently chosen bits. If it were a perfect source of randomly
  380        * chosen bits, then the algorithm shown would choose {@code float}
  381        * values from the stated range with perfect uniformity.<p>
  382        * [In early versions of Java, the result was incorrectly calculated as:
  383        *  <pre> {@code
  384        *   return next(30) / ((float)(1 << 30));}</pre>
  385        * This might seem to be equivalent, if not better, but in fact it
  386        * introduced a slight nonuniformity because of the bias in the rounding
  387        * of floating-point numbers: it was slightly more likely that the
  388        * low-order bit of the significand would be 0 than that it would be 1.]
  389        *
  390        * @return the next pseudorandom, uniformly distributed {@code float}
  391        *         value between {@code 0.0} and {@code 1.0} from this
  392        *         random number generator's sequence
  393        */
  394       public float nextFloat() {
  395           return next(24) / ((float)(1 << 24));
  396       }
  397   
  398       /**
  399        * Returns the next pseudorandom, uniformly distributed
  400        * {@code double} value between {@code 0.0} and
  401        * {@code 1.0} from this random number generator's sequence.
  402        *
  403        * <p>The general contract of {@code nextDouble} is that one
  404        * {@code double} value, chosen (approximately) uniformly from the
  405        * range {@code 0.0d} (inclusive) to {@code 1.0d} (exclusive), is
  406        * pseudorandomly generated and returned.
  407        *
  408        * <p>The method {@code nextDouble} is implemented by class {@code Random}
  409        * as if by:
  410        *  <pre> {@code
  411        * public double nextDouble() {
  412        *   return (((long)next(26) << 27) + next(27))
  413        *     / (double)(1L << 53);
  414        * }}</pre>
  415        *
  416        * <p>The hedge "approximately" is used in the foregoing description only
  417        * because the {@code next} method is only approximately an unbiased
  418        * source of independently chosen bits. If it were a perfect source of
  419        * randomly chosen bits, then the algorithm shown would choose
  420        * {@code double} values from the stated range with perfect uniformity.
  421        * <p>[In early versions of Java, the result was incorrectly calculated as:
  422        *  <pre> {@code
  423        *   return (((long)next(27) << 27) + next(27))
  424        *     / (double)(1L << 54);}</pre>
  425        * This might seem to be equivalent, if not better, but in fact it
  426        * introduced a large nonuniformity because of the bias in the rounding
  427        * of floating-point numbers: it was three times as likely that the
  428        * low-order bit of the significand would be 0 than that it would be 1!
  429        * This nonuniformity probably doesn't matter much in practice, but we
  430        * strive for perfection.]
  431        *
  432        * @return the next pseudorandom, uniformly distributed {@code double}
  433        *         value between {@code 0.0} and {@code 1.0} from this
  434        *         random number generator's sequence
  435        * @see Math#random
  436        */
  437       public double nextDouble() {
  438           return (((long)(next(26)) << 27) + next(27))
  439               / (double)(1L << 53);
  440       }
  441   
  442       private double nextNextGaussian;
  443       private boolean haveNextNextGaussian = false;
  444   
  445       /**
  446        * Returns the next pseudorandom, Gaussian ("normally") distributed
  447        * {@code double} value with mean {@code 0.0} and standard
  448        * deviation {@code 1.0} from this random number generator's sequence.
  449        * <p>
  450        * The general contract of {@code nextGaussian} is that one
  451        * {@code double} value, chosen from (approximately) the usual
  452        * normal distribution with mean {@code 0.0} and standard deviation
  453        * {@code 1.0}, is pseudorandomly generated and returned.
  454        *
  455        * <p>The method {@code nextGaussian} is implemented by class
  456        * {@code Random} as if by a threadsafe version of the following:
  457        *  <pre> {@code
  458        * private double nextNextGaussian;
  459        * private boolean haveNextNextGaussian = false;
  460        *
  461        * public double nextGaussian() {
  462        *   if (haveNextNextGaussian) {
  463        *     haveNextNextGaussian = false;
  464        *     return nextNextGaussian;
  465        *   } else {
  466        *     double v1, v2, s;
  467        *     do {
  468        *       v1 = 2 * nextDouble() - 1;   // between -1.0 and 1.0
  469        *       v2 = 2 * nextDouble() - 1;   // between -1.0 and 1.0
  470        *       s = v1 * v1 + v2 * v2;
  471        *     } while (s >= 1 || s == 0);
  472        *     double multiplier = StrictMath.sqrt(-2 * StrictMath.log(s)/s);
  473        *     nextNextGaussian = v2 * multiplier;
  474        *     haveNextNextGaussian = true;
  475        *     return v1 * multiplier;
  476        *   }
  477        * }}</pre>
  478        * This uses the <i>polar method</i> of G. E. P. Box, M. E. Muller, and
  479        * G. Marsaglia, as described by Donald E. Knuth in <i>The Art of
  480        * Computer Programming</i>, Volume 3: <i>Seminumerical Algorithms</i>,
  481        * section 3.4.1, subsection C, algorithm P. Note that it generates two
  482        * independent values at the cost of only one call to {@code StrictMath.log}
  483        * and one call to {@code StrictMath.sqrt}.
  484        *
  485        * @return the next pseudorandom, Gaussian ("normally") distributed
  486        *         {@code double} value with mean {@code 0.0} and
  487        *         standard deviation {@code 1.0} from this random number
  488        *         generator's sequence
  489        */
  490       synchronized public double nextGaussian() {
  491           // See Knuth, ACP, Section 3.4.1 Algorithm C.
  492           if (haveNextNextGaussian) {
  493               haveNextNextGaussian = false;
  494               return nextNextGaussian;
  495           } else {
  496               double v1, v2, s;
  497               do {
  498                   v1 = 2 * nextDouble() - 1; // between -1 and 1
  499                   v2 = 2 * nextDouble() - 1; // between -1 and 1
  500                   s = v1 * v1 + v2 * v2;
  501               } while (s >= 1 || s == 0);
  502               double multiplier = StrictMath.sqrt(-2 * StrictMath.log(s)/s);
  503               nextNextGaussian = v2 * multiplier;
  504               haveNextNextGaussian = true;
  505               return v1 * multiplier;
  506           }
  507       }
  508   
  509       /**
  510        * Serializable fields for Random.
  511        *
  512        * @serialField    seed long
  513        *              seed for random computations
  514        * @serialField    nextNextGaussian double
  515        *              next Gaussian to be returned
  516        * @serialField      haveNextNextGaussian boolean
  517        *              nextNextGaussian is valid
  518        */
  519       private static final ObjectStreamField[] serialPersistentFields = {
  520           new ObjectStreamField("seed", Long.TYPE),
  521           new ObjectStreamField("nextNextGaussian", Double.TYPE),
  522           new ObjectStreamField("haveNextNextGaussian", Boolean.TYPE)
  523       };
  524   
  525       /**
  526        * Reconstitute the {@code Random} instance from a stream (that is,
  527        * deserialize it).
  528        */
  529       private void readObject(java.io.ObjectInputStream s)
  530           throws java.io.IOException, ClassNotFoundException {
  531   
  532           ObjectInputStream.GetField fields = s.readFields();
  533   
  534           // The seed is read in as {@code long} for
  535           // historical reasons, but it is converted to an AtomicLong.
  536           long seedVal = fields.get("seed", -1L);
  537           if (seedVal < 0)
  538             throw new java.io.StreamCorruptedException(
  539                                 "Random: invalid seed");
  540           resetSeed(seedVal);
  541           nextNextGaussian = fields.get("nextNextGaussian", 0.0);
  542           haveNextNextGaussian = fields.get("haveNextNextGaussian", false);
  543       }
  544   
  545       /**
  546        * Save the {@code Random} instance to a stream.
  547        */
  548       synchronized private void writeObject(ObjectOutputStream s)
  549           throws IOException {
  550   
  551           // set the values of the Serializable fields
  552           ObjectOutputStream.PutField fields = s.putFields();
  553   
  554           // The seed is serialized as a long for historical reasons.
  555           fields.put("seed", seed.get());
  556           fields.put("nextNextGaussian", nextNextGaussian);
  557           fields.put("haveNextNextGaussian", haveNextNextGaussian);
  558   
  559           // save them
  560           s.writeFields();
  561       }
  562   
  563       // Support for resetting seed while deserializing
  564       private static final Unsafe unsafe = Unsafe.getUnsafe();
  565       private static final long seedOffset;
  566       static {
  567           try {
  568               seedOffset = unsafe.objectFieldOffset
  569                   (Random.class.getDeclaredField("seed"));
  570           } catch (Exception ex) { throw new Error(ex); }
  571       }
  572       private void resetSeed(long seedVal) {
  573           unsafe.putObjectVolatile(this, seedOffset, new AtomicLong(seedVal));
  574       }
  575   }

Save This Page
Home » openjdk-7 » java » util » [javadoc | source]