Random


1   /*
2    * @(#)Random.java  1.43 04/01/12
3    *
4    * Copyright 2004 Sun Microsystems, Inc. All rights reserved.
5    * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
6    */
7   
8   package java.util;
9   import java.io.*;
10  import java.util.concurrent.atomic.AtomicLong  ;
11  
12  /**
13   * An instance of this class is used to generate a stream of 
14   * pseudorandom numbers. The class uses a 48-bit seed, which is 
15   * modified using a linear congruential formula. (See Donald Knuth, 
16   * <i>The Art of Computer Programming, Volume 2</i>, Section 3.2.1.) 
17   * <p>
18   * If two instances of <code>Random</code> are created with the same 
19   * seed, and the same sequence of method calls is made for each, they 
20   * will generate and return identical sequences of numbers. In order to 
21   * guarantee this property, particular algorithms are specified for the 
22   * class <tt>Random</tt>. Java implementations must use all the algorithms 
23   * shown here for the class <tt>Random</tt>, for the sake of absolute 
24   * portability of Java code. However, subclasses of class <tt>Random</tt> 
25   * are permitted to use other algorithms, so long as they adhere to the 
26   * general contracts for all the methods.
27   * <p>
28   * The algorithms implemented by class <tt>Random</tt> use a 
29   * <tt>protected</tt> utility method that on each invocation can supply 
30   * up to 32 pseudorandomly generated bits.
31   * <p>
32   * Many applications will find the <code>random</code> method in 
33   * class <code>Math</code> simpler to use.
34   *
35   * @author  Frank Yellin
36   * @version 1.43, 01/12/04
37   * @see     java.lang.Math#random()
38   * @since   JDK1.0
39   */
40  public
41  class Random implements java.io.Serializable   {
42      /** use serialVersionUID from JDK 1.1 for interoperability */
43      static final long serialVersionUID = 3905348978240129619L;
44  
45      /**
46       * The internal state associated with this pseudorandom number generator.
47       * (The specs for the methods in this class describe the ongoing
48       * computation of this value.)
49       *
50       * @serial
51       */
52      private AtomicLong   seed;
53  
54      private final static long multiplier = 0x5DEECE66DL;
55      private final static long addend = 0xBL;
56      private final static long mask = (1L << 48) - 1;
57  
58      /**
59       * Creates a new random number generator. This constructor sets
60       * the seed of the random number generator to a value very likely
61       * to be distinct from any other invocation of this constructor.
62       */
63      public Random() { this(++seedUniquifier + System.nanoTime()); }
64      private static volatile long seedUniquifier = 8682522807148012L;
65  
66      /** 
67       * Creates a new random number generator using a single 
68       * <code>long</code> seed:
69       * <blockquote><pre>
70       * public Random(long seed) { setSeed(seed); }</pre></blockquote>
71       * Used by method <tt>next</tt> to hold 
72       * the state of the pseudorandom number generator.
73       *
74       * @param   seed   the initial seed.
75       * @see     java.util.Random#setSeed(long)
76       */
77      public Random(long seed) {
78          this.seed = new AtomicLong  (0L);
79          setSeed(seed);
80      }
81  
82      /**
83       * Sets the seed of this random number generator using a single 
84       * <code>long</code> seed. The general contract of <tt>setSeed</tt> 
85       * is that it alters the state of this random number generator
86       * object so as to be in exactly the same state as if it had just 
87       * been created with the argument <tt>seed</tt> as a seed. The method 
88       * <tt>setSeed</tt> is implemented by class Random as follows:
89       * <blockquote><pre>
90       * synchronized public void setSeed(long seed) {
91       *       this.seed = (seed ^ 0x5DEECE66DL) & ((1L << 48) - 1);
92       *       haveNextNextGaussian = false;
93       * }</pre></blockquote>
94       * The implementation of <tt>setSeed</tt> by class <tt>Random</tt> 
95       * happens to use only 48 bits of the given seed. In general, however, 
96       * an overriding method may use all 64 bits of the long argument
97       * as a seed value. 
98       *
99       * Note: Although the seed value is an AtomicLong, this method
100      *       must still be synchronized to ensure correct semantics
101      *       of haveNextNextGaussian.
102      *
103      * @param   seed   the initial seed.
104      */
105     synchronized public void setSeed(long seed) {
106         seed = (seed ^ multiplier) & mask;
107         this.seed.set(seed);
108         haveNextNextGaussian = false;
109     }
110 
111     /**
112      * Generates the next pseudorandom number. Subclass should
113      * override this, as this is used by all other methods.<p>
114      * The general contract of <tt>next</tt> is that it returns an 
115      * <tt>int</tt> value and if the argument bits is between <tt>1</tt> 
116      * and <tt>32</tt> (inclusive), then that many low-order bits of the 
117      * returned value will be (approximately) independently chosen bit 
118      * values, each of which is (approximately) equally likely to be 
119      * <tt>0</tt> or <tt>1</tt>. The method <tt>next</tt> is implemented 
120      * by class <tt>Random</tt> as follows:
121      * <blockquote><pre>
122      * synchronized protected int next(int bits) {
123      *       seed = (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1);
124      *       return (int)(seed >>> (48 - bits));
125      * }</pre></blockquote>
126      * This is a linear congruential pseudorandom number generator, as 
127      * defined by D. H. Lehmer and described by Donald E. Knuth in <i>The 
128      * Art of Computer Programming,</i> Volume 2: <i>Seminumerical 
129      * Algorithms</i>, section 3.2.1.
130      *
131      * @param   bits random bits
132      * @return  the next pseudorandom value from this random number generator's sequence.
133      * @since   JDK1.1
134      */
135     protected int next(int bits) {
136         long oldseed, nextseed;
137         AtomicLong   seed = this.seed;
138         do {
139         oldseed = seed.get();
140         nextseed = (oldseed * multiplier + addend) & mask;
141         } while (!seed.compareAndSet(oldseed, nextseed));
142         return (int)(nextseed >>> (48 - bits));
143     }
144 
145     private static final int BITS_PER_BYTE = 8;
146     private static final int BYTES_PER_INT = 4;
147 
148     /**
149      * Generates random bytes and places them into a user-supplied 
150      * byte array.  The number of random bytes produced is equal to 
151      * the length of the byte array.
152      * 
153      * @param bytes  the non-null byte array in which to put the 
154      *               random bytes.
155      * @since   JDK1.1
156      */
157     public void nextBytes(byte[] bytes) {
158     int numRequested = bytes.length;
159 
160     int numGot = 0, rnd = 0;
161 
162     while (true) {
163         for (int i = 0; i < BYTES_PER_INT; i++) {
164         if (numGot == numRequested)
165             return;
166 
167         rnd = (i==0 ? next(BITS_PER_BYTE * BYTES_PER_INT)
168                     : rnd >> BITS_PER_BYTE);
169         bytes[numGot++] = (byte)rnd;
170         }
171     }
172     }
173 
174     /**
175      * Returns the next pseudorandom, uniformly distributed <code>int</code>
176      * value from this random number generator's sequence. The general 
177      * contract of <tt>nextInt</tt> is that one <tt>int</tt> value is 
178      * pseudorandomly generated and returned. All 2<font size="-1"><sup>32
179      * </sup></font> possible <tt>int</tt> values are produced with 
180      * (approximately) equal probability. The method <tt>nextInt</tt> is 
181      * implemented by class <tt>Random</tt> as follows:
182      * <blockquote><pre>
183      * public int nextInt() {  return next(32); }</pre></blockquote>
184      *
185      * @return  the next pseudorandom, uniformly distributed <code>int</code>
186      *          value from this random number generator's sequence.
187      */
188     public int nextInt() {  return next(32); }
189 
190     /**
191      * Returns a pseudorandom, uniformly distributed <tt>int</tt> value
192      * between 0 (inclusive) and the specified value (exclusive), drawn from
193      * this random number generator's sequence.  The general contract of
194      * <tt>nextInt</tt> is that one <tt>int</tt> value in the specified range
195      * is pseudorandomly generated and returned.  All <tt>n</tt> possible
196      * <tt>int</tt> values are produced with (approximately) equal
197      * probability.  The method <tt>nextInt(int n)</tt> is implemented by
198      * class <tt>Random</tt> as follows:
199      * <blockquote><pre>
200      * public int nextInt(int n) {
201      *     if (n<=0)
202      *      throw new IllegalArgumentException("n must be positive");
203      *
204      *     if ((n & -n) == n)  // i.e., n is a power of 2
205      *         return (int)((n * (long)next(31)) >> 31);
206      *
207      *     int bits, val;
208      *     do {
209      *         bits = next(31);
210      *         val = bits % n;
211      *     } while(bits - val + (n-1) < 0);
212      *     return val;
213      * }
214      * </pre></blockquote>
215      * <p>
216      * The hedge "approximately" is used in the foregoing description only 
217      * because the next method is only approximately an unbiased source of
218      * independently chosen bits.  If it were a perfect source of randomly 
219      * chosen bits, then the algorithm shown would choose <tt>int</tt> 
220      * values from the stated range with perfect uniformity.
221      * <p>
222      * The algorithm is slightly tricky.  It rejects values that would result
223      * in an uneven distribution (due to the fact that 2^31 is not divisible
224      * by n). The probability of a value being rejected depends on n.  The
225      * worst case is n=2^30+1, for which the probability of a reject is 1/2,
226      * and the expected number of iterations before the loop terminates is 2.
227      * <p>
228      * The algorithm treats the case where n is a power of two specially: it
229      * returns the correct number of high-order bits from the underlying
230      * pseudo-random number generator.  In the absence of special treatment,
231      * the correct number of <i>low-order</i> bits would be returned.  Linear
232      * congruential pseudo-random number generators such as the one
233      * implemented by this class are known to have short periods in the
234      * sequence of values of their low-order bits.  Thus, this special case
235      * greatly increases the length of the sequence of values returned by
236      * successive calls to this method if n is a small power of two.
237      *
238      * @param n the bound on the random number to be returned.  Must be
239      *        positive.
240      * @return  a pseudorandom, uniformly distributed <tt>int</tt>
241      *          value between 0 (inclusive) and n (exclusive).
242      * @exception IllegalArgumentException n is not positive.
243      * @since 1.2
244      */
245 
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     }
260 
261     /**
262      * Returns the next pseudorandom, uniformly distributed <code>long</code>
263      * value from this random number generator's sequence. The general 
264      * contract of <tt>nextLong</tt> is that one long value is pseudorandomly 
265      * generated and returned. All 2<font size="-1"><sup>64</sup></font> 
266      * possible <tt>long</tt> values are produced with (approximately) equal 
267      * probability. The method <tt>nextLong</tt> is implemented by class 
268      * <tt>Random</tt> as follows:
269      * <blockquote><pre>
270      * public long nextLong() {
271      *       return ((long)next(32) << 32) + next(32);
272      * }</pre></blockquote>
273      *
274      * @return  the next pseudorandom, uniformly distributed <code>long</code>
275      *          value from this random number generator's sequence.
276      */
277     public long nextLong() {
278         // it's okay that the bottom word remains signed.
279         return ((long)(next(32)) << 32) + next(32);
280     }
281 
282     /**
283      * Returns the next pseudorandom, uniformly distributed
284      * <code>boolean</code> value from this random number generator's
285      * sequence. The general contract of <tt>nextBoolean</tt> is that one
286      * <tt>boolean</tt> value is pseudorandomly generated and returned.  The
287      * values <code>true</code> and <code>false</code> are produced with
288      * (approximately) equal probability. The method <tt>nextBoolean</tt> is
289      * implemented by class <tt>Random</tt> as follows:
290      * <blockquote><pre>
291      * public boolean nextBoolean() {return next(1) != 0;}
292      * </pre></blockquote>
293      * @return  the next pseudorandom, uniformly distributed
294      *          <code>boolean</code> value from this random number generator's
295      *      sequence.
296      * @since 1.2
297      */
298     public boolean nextBoolean() {return next(1) != 0;}
299 
300     /**
301      * Returns the next pseudorandom, uniformly distributed <code>float</code>
302      * value between <code>0.0</code> and <code>1.0</code> from this random
303      * number generator's sequence. <p>
304      * The general contract of <tt>nextFloat</tt> is that one <tt>float</tt> 
305      * value, chosen (approximately) uniformly from the range <tt>0.0f</tt> 
306      * (inclusive) to <tt>1.0f</tt> (exclusive), is pseudorandomly
307      * generated and returned. All 2<font size="-1"><sup>24</sup></font> 
308      * possible <tt>float</tt> values of the form 
309      * <i>m&nbsp;x&nbsp</i>2<font size="-1"><sup>-24</sup></font>, where 
310      * <i>m</i> is a positive integer less than 2<font size="-1"><sup>24</sup>
311      * </font>, are produced with (approximately) equal probability. The 
312      * method <tt>nextFloat</tt> is implemented by class <tt>Random</tt> as 
313      * follows:
314      * <blockquote><pre>
315      * public float nextFloat() {
316      *      return next(24) / ((float)(1 << 24));
317      * }</pre></blockquote>
318      * The hedge "approximately" is used in the foregoing description only 
319      * because the next method is only approximately an unbiased source of 
320      * independently chosen bits. If it were a perfect source or randomly 
321      * chosen bits, then the algorithm shown would choose <tt>float</tt> 
322      * values from the stated range with perfect uniformity.<p>
323      * [In early versions of Java, the result was incorrectly calculated as:
324      * <blockquote><pre>
325      * return next(30) / ((float)(1 << 30));</pre></blockquote>
326      * This might seem to be equivalent, if not better, but in fact it 
327      * introduced a slight nonuniformity because of the bias in the rounding 
328      * of floating-point numbers: it was slightly more likely that the 
329      * low-order bit of the significand would be 0 than that it would be 1.] 
330      *
331      * @return  the next pseudorandom, uniformly distributed <code>float</code>
332      *          value between <code>0.0</code> and <code>1.0</code> from this
333      *          random number generator's sequence.
334      */
335     public float nextFloat() {
336         int i = next(24);
337         return i / ((float)(1 << 24));
338     }
339 
340     /**
341      * Returns the next pseudorandom, uniformly distributed 
342      * <code>double</code> value between <code>0.0</code> and
343      * <code>1.0</code> from this random number generator's sequence. <p>
344      * The general contract of <tt>nextDouble</tt> is that one 
345      * <tt>double</tt> value, chosen (approximately) uniformly from the 
346      * range <tt>0.0d</tt> (inclusive) to <tt>1.0d</tt> (exclusive), is 
347      * pseudorandomly generated and returned. All 
348      * 2<font size="-1"><sup>53</sup></font> possible <tt>float</tt> 
349      * values of the form <i>m&nbsp;x&nbsp;</i>2<font size="-1"><sup>-53</sup>
350      * </font>, where <i>m</i> is a positive integer less than 
351      * 2<font size="-1"><sup>53</sup></font>, are produced with 
352      * (approximately) equal probability. The method <tt>nextDouble</tt> is 
353      * implemented by class <tt>Random</tt> as follows:
354      * <blockquote><pre>
355      * public double nextDouble() {
356      *       return (((long)next(26) << 27) + next(27))
357      *           / (double)(1L << 53);
358      * }</pre></blockquote><p>
359      * The hedge "approximately" is used in the foregoing description only 
360      * because the <tt>next</tt> method is only approximately an unbiased 
361      * source of independently chosen bits. If it were a perfect source or 
362      * randomly chosen bits, then the algorithm shown would choose 
363      * <tt>double</tt> values from the stated range with perfect uniformity. 
364      * <p>[In early versions of Java, the result was incorrectly calculated as:
365      * <blockquote><pre>
366      *  return (((long)next(27) << 27) + next(27))
367      *      / (double)(1L << 54);</pre></blockquote>
368      * This might seem to be equivalent, if not better, but in fact it 
369      * introduced a large nonuniformity because of the bias in the rounding 
370      * of floating-point numbers: it was three times as likely that the 
371      * low-order bit of the significand would be 0 than that it would be
372      * 1! This nonuniformity probably doesn't matter much in practice, but 
373      * we strive for perfection.] 
374      *
375      * @return  the next pseudorandom, uniformly distributed 
376      *          <code>double</code> value between <code>0.0</code> and
377      *          <code>1.0</code> from this random number generator's sequence.
378      */
379     public double nextDouble() {
380         long l = ((long)(next(26)) << 27) + next(27);
381         return l / (double)(1L << 53);
382     }
383 
384     private double nextNextGaussian;
385     private boolean haveNextNextGaussian = false;
386 
387     /**
388      * Returns the next pseudorandom, Gaussian ("normally") distributed
389      * <code>double</code> value with mean <code>0.0</code> and standard
390      * deviation <code>1.0</code> from this random number generator's sequence.
391      * <p>
392      * The general contract of <tt>nextGaussian</tt> is that one 
393      * <tt>double</tt> value, chosen from (approximately) the usual 
394      * normal distribution with mean <tt>0.0</tt> and standard deviation 
395      * <tt>1.0</tt>, is pseudorandomly generated and returned. The method 
396      * <tt>nextGaussian</tt> is implemented by class <tt>Random</tt> as follows:
397      * <blockquote><pre>
398      * synchronized public double nextGaussian() {
399      *    if (haveNextNextGaussian) {
400      *            haveNextNextGaussian = false;
401      *            return nextNextGaussian;
402      *    } else {
403      *            double v1, v2, s;
404      *            do { 
405      *                    v1 = 2 * nextDouble() - 1;   // between -1.0 and 1.0
406      *                    v2 = 2 * nextDouble() - 1;   // between -1.0 and 1.0
407      *                    s = v1 * v1 + v2 * v2;
408      *            } while (s >= 1 || s == 0);
409      *            double multiplier = Math.sqrt(-2 * Math.log(s)/s);
410      *            nextNextGaussian = v2 * multiplier;
411      *            haveNextNextGaussian = true;
412      *            return v1 * multiplier;
413      *    }
414      * }</pre></blockquote>
415      * This uses the <i>polar method</i> of G. E. P. Box, M. E. Muller, and 
416      * G. Marsaglia, as described by Donald E. Knuth in <i>The Art of 
417      * Computer Programming</i>, Volume 2: <i>Seminumerical Algorithms</i>, 
418      * section 3.4.1, subsection C, algorithm P. Note that it generates two
419      * independent values at the cost of only one call to <tt>Math.log</tt> 
420      * and one call to <tt>Math.sqrt</tt>. 
421      *
422      * @return  the next pseudorandom, Gaussian ("normally") distributed
423      *          <code>double</code> value with mean <code>0.0</code> and
424      *          standard deviation <code>1.0</code> from this random number
425      *          generator's sequence.
426      */
427     synchronized public double nextGaussian() {
428         // See Knuth, ACP, Section 3.4.1 Algorithm C.
429         if (haveNextNextGaussian) {
430             haveNextNextGaussian = false;
431             return nextNextGaussian;
432         } else {
433             double v1, v2, s;
434             do { 
435                 v1 = 2 * nextDouble() - 1; // between -1 and 1
436                 v2 = 2 * nextDouble() - 1; // between -1 and 1 
437                 s = v1 * v1 + v2 * v2;
438             } while (s >= 1 || s == 0);
439             double multiplier = Math.sqrt(-2 * Math.log(s)/s);
440             nextNextGaussian = v2 * multiplier;
441             haveNextNextGaussian = true;
442             return v1 * multiplier;
443         }
444     }
445 
446     /**
447      * Serializable fields for Random.
448      *
449      * @serialField    seed long;
450      *              seed for random computations
451      * @serialField    nextNextGaussian double;
452      *              next Gaussian to be returned
453      * @serialField      haveNextNextGaussian boolean
454      *              nextNextGaussian is valid
455      */
456     private static final ObjectStreamField[] serialPersistentFields = {
457         new ObjectStreamField("seed", Long.TYPE),
458         new ObjectStreamField("nextNextGaussian", Double.TYPE),
459         new ObjectStreamField("haveNextNextGaussian", Boolean.TYPE)
460         };
461 
462     /**
463      * Reconstitute the <tt>Random</tt> instance from a stream (that is,
464      * deserialize it). The seed is read in as long for
465      * historical reasons, but it is converted to an AtomicLong.
466      */
467     private void readObject(java.io.ObjectInputStream   s)
468         throws java.io.IOException  , ClassNotFoundException   {
469 
470         ObjectInputStream.GetField fields = s.readFields();
471         long seedVal;
472 
473         seedVal = (long) fields.get("seed", -1L);
474         if (seedVal < 0)
475           throw new java.io.StreamCorruptedException  (
476                               "Random: invalid seed");
477         seed = new AtomicLong  (seedVal);
478         nextNextGaussian = fields.get("nextNextGaussian", 0.0);
479         haveNextNextGaussian = fields.get("haveNextNextGaussian", false);
480     }
481 
482 
483     /**
484      * Save the <tt>Random</tt> instance to a stream.
485      * The seed of a Random is serialized as a long for
486      * historical reasons.
487      *
488      */
489     synchronized private void writeObject(ObjectOutputStream s) throws IOException {
490         // set the values of the Serializable fields
491         ObjectOutputStream.PutField fields = s.putFields();
492         fields.put("seed", seed.get());
493         fields.put("nextNextGaussian", nextNextGaussian);
494         fields.put("haveNextNextGaussian", haveNextNextGaussian);
495 
496         // save them
497         s.writeFields();
498 
499     }
500 
501 }     
502
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags