001    /* Random.java -- a pseudo-random number generator
002       Copyright (C) 1998, 1999, 2000, 2001, 2002 Free Software Foundation, Inc.
003    
004    This file is part of GNU Classpath.
005    
006    GNU Classpath is free software; you can redistribute it and/or modify
007    it under the terms of the GNU General Public License as published by
008    the Free Software Foundation; either version 2, or (at your option)
009    any later version.
010    
011    GNU Classpath is distributed in the hope that it will be useful, but
012    WITHOUT ANY WARRANTY; without even the implied warranty of
013    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
014    General Public License for more details.
015    
016    You should have received a copy of the GNU General Public License
017    along with GNU Classpath; see the file COPYING.  If not, write to the
018    Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
019    02110-1301 USA.
020    
021    Linking this library statically or dynamically with other modules is
022    making a combined work based on this library.  Thus, the terms and
023    conditions of the GNU General Public License cover the whole
024    combination.
025    
026    As a special exception, the copyright holders of this library give you
027    permission to link this library with independent modules to produce an
028    executable, regardless of the license terms of these independent
029    modules, and to copy and distribute the resulting executable under
030    terms of your choice, provided that you also meet, for each linked
031    independent module, the terms and conditions of the license of that
032    module.  An independent module is a module which is not derived from
033    or based on this library.  If you modify this library, you may extend
034    this exception to your version of the library, but you are not
035    obligated to do so.  If you do not wish to do so, delete this
036    exception statement from your version. */
037    
038    
039    package java.util;
040    
041    import java.io.Serializable;
042    
043    /**
044     * This class generates pseudorandom numbers.  It uses the same
045     * algorithm as the original JDK-class, so that your programs behave
046     * exactly the same way, if started with the same seed.
047     *
048     * The algorithm is described in <em>The Art of Computer Programming,
049     * Volume 2</em> by Donald Knuth in Section 3.2.1.  It is a 48-bit seed,
050     * linear congruential formula.
051     *
052     * If two instances of this class are created with the same seed and
053     * the same calls to these classes are made, they behave exactly the
054     * same way.  This should be even true for foreign implementations
055     * (like this), so every port must use the same algorithm as described
056     * here.
057     *
058     * If you want to implement your own pseudorandom algorithm, you
059     * should extend this class and overload the <code>next()</code> and
060     * <code>setSeed(long)</code> method.  In that case the above
061     * paragraph doesn't apply to you.
062     *
063     * This class shouldn't be used for security sensitive purposes (like
064     * generating passwords or encryption keys.  See <code>SecureRandom</code>
065     * in package <code>java.security</code> for this purpose.
066     *
067     * For simple random doubles between 0.0 and 1.0, you may consider using
068     * Math.random instead.
069     *
070     * @see java.security.SecureRandom
071     * @see Math#random()
072     * @author Jochen Hoenicke
073     * @author Eric Blake (ebb9@email.byu.edu)
074     * @status updated to 1.4
075     */
076    public class Random implements Serializable
077    {
078      /**
079       * True if the next nextGaussian is available.  This is used by
080       * nextGaussian, which generates two gaussian numbers by one call,
081       * and returns the second on the second call.
082       *
083       * @serial whether nextNextGaussian is available
084       * @see #nextGaussian()
085       * @see #nextNextGaussian
086       */
087      private boolean haveNextNextGaussian;
088    
089      /**
090       * The next nextGaussian, when available.  This is used by nextGaussian,
091       * which generates two gaussian numbers by one call, and returns the
092       * second on the second call.
093       *
094       * @serial the second gaussian of a pair
095       * @see #nextGaussian()
096       * @see #haveNextNextGaussian
097       */
098      private double nextNextGaussian;
099    
100      /**
101       * The seed.  This is the number set by setSeed and which is used
102       * in next.
103       *
104       * @serial the internal state of this generator
105       * @see #next(int)
106       */
107      private long seed;
108    
109      /**
110       * Compatible with JDK 1.0+.
111       */
112      private static final long serialVersionUID = 3905348978240129619L;
113    
114      /**
115       * Creates a new pseudorandom number generator.  The seed is initialized
116       * to the current time, as if by
117       * <code>setSeed(System.currentTimeMillis());</code>.
118       *
119       * @see System#currentTimeMillis()
120       */
121      public Random()
122      {
123        this(System.currentTimeMillis());
124      }
125    
126      /**
127       * Creates a new pseudorandom number generator, starting with the
128       * specified seed, using <code>setSeed(seed);</code>.
129       *
130       * @param seed the initial seed
131       */
132      public Random(long seed)
133      {
134        setSeed(seed);
135      }
136    
137      /**
138       * Sets the seed for this pseudorandom number generator.  As described
139       * above, two instances of the same random class, starting with the
140       * same seed, should produce the same results, if the same methods
141       * are called.  The implementation for java.util.Random is:
142       *
143    <pre>public synchronized void setSeed(long seed)
144    {
145      this.seed = (seed ^ 0x5DEECE66DL) & ((1L &lt;&lt; 48) - 1);
146      haveNextNextGaussian = false;
147    }</pre>
148       *
149       * @param seed the new seed
150       */
151      public synchronized void setSeed(long seed)
152      {
153        this.seed = (seed ^ 0x5DEECE66DL) & ((1L << 48) - 1);
154        haveNextNextGaussian = false;
155      }
156    
157      /**
158       * Generates the next pseudorandom number.  This returns
159       * an int value whose <code>bits</code> low order bits are
160       * independent chosen random bits (0 and 1 are equally likely).
161       * The implementation for java.util.Random is:
162       *
163    <pre>protected synchronized int next(int bits)
164    {
165      seed = (seed * 0x5DEECE66DL + 0xBL) & ((1L &lt;&lt; 48) - 1);
166      return (int) (seed &gt;&gt;&gt; (48 - bits));
167    }</pre>
168       *
169       * @param bits the number of random bits to generate, in the range 1..32
170       * @return the next pseudorandom value
171       * @since 1.1
172       */
173      protected synchronized int next(int bits)
174      {
175        seed = (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1);
176        return (int) (seed >>> (48 - bits));
177      }
178    
179      /**
180       * Fills an array of bytes with random numbers.  All possible values
181       * are (approximately) equally likely.
182       * The JDK documentation gives no implementation, but it seems to be:
183       *
184    <pre>public void nextBytes(byte[] bytes)
185    {
186      for (int i = 0; i &lt; bytes.length; i += 4)
187      {
188        int random = next(32);
189        for (int j = 0; i + j &lt; bytes.length && j &lt; 4; j++)
190        {
191          bytes[i+j] = (byte) (random & 0xff)
192          random &gt;&gt;= 8;
193        }
194      }
195    }</pre>
196       *
197       * @param bytes the byte array that should be filled
198       * @throws NullPointerException if bytes is null
199       * @since 1.1
200       */
201      public void nextBytes(byte[] bytes)
202      {
203        int random;
204        // Do a little bit unrolling of the above algorithm.
205        int max = bytes.length & ~0x3;
206        for (int i = 0; i < max; i += 4)
207          {
208            random = next(32);
209            bytes[i] = (byte) random;
210            bytes[i + 1] = (byte) (random >> 8);
211            bytes[i + 2] = (byte) (random >> 16);
212            bytes[i + 3] = (byte) (random >> 24);
213          }
214        if (max < bytes.length)
215          {
216            random = next(32);
217            for (int j = max; j < bytes.length; j++)
218              {
219                bytes[j] = (byte) random;
220                random >>= 8;
221              }
222          }
223      }
224    
225      /**
226       * Generates the next pseudorandom number.  This returns
227       * an int value whose 32 bits are independent chosen random bits
228       * (0 and 1 are equally likely).  The implementation for
229       * java.util.Random is:
230       * 
231    <pre>public int nextInt()
232    {
233      return next(32);
234    }</pre>
235       *
236       * @return the next pseudorandom value
237       */
238      public int nextInt()
239      {
240        return next(32);
241      }
242    
243      /**
244       * Generates the next pseudorandom number.  This returns
245       * a value between 0(inclusive) and <code>n</code>(exclusive), and
246       * each value has the same likelihodd (1/<code>n</code>).
247       * (0 and 1 are equally likely).  The implementation for
248       * java.util.Random is:
249       * 
250    <pre>
251    public int nextInt(int n)
252    {
253      if (n &lt;= 0)
254        throw new IllegalArgumentException("n must be positive");
255    
256      if ((n & -n) == n)  // i.e., n is a power of 2
257        return (int)((n * (long) next(31)) &gt;&gt; 31);
258    
259      int bits, val;
260      do
261      {
262        bits = next(31);
263        val = bits % n;
264      }
265      while(bits - val + (n-1) &lt; 0);
266    
267      return val;
268    }</pre>
269       *   
270       * <p>This algorithm would return every value with exactly the same
271       * probability, if the next()-method would be a perfect random number
272       * generator.
273       *
274       * The loop at the bottom only accepts a value, if the random
275       * number was between 0 and the highest number less then 1<<31,
276       * which is divisible by n.  The probability for this is high for small
277       * n, and the worst case is 1/2 (for n=(1<<30)+1).
278       *
279       * The special treatment for n = power of 2, selects the high bits of
280       * the random number (the loop at the bottom would select the low order
281       * bits).  This is done, because the low order bits of linear congruential
282       * number generators (like the one used in this class) are known to be
283       * ``less random'' than the high order bits.
284       *
285       * @param n the upper bound
286       * @throws IllegalArgumentException if the given upper bound is negative
287       * @return the next pseudorandom value
288       * @since 1.2
289       */
290      public int nextInt(int n)
291      {
292        if (n <= 0)
293          throw new IllegalArgumentException("n must be positive");
294        if ((n & -n) == n) // i.e., n is a power of 2
295          return (int) ((n * (long) next(31)) >> 31);
296        int bits, val;
297        do
298          {
299            bits = next(31);
300            val = bits % n;
301          }
302        while (bits - val + (n - 1) < 0);
303        return val;
304      }
305    
306      /**
307       * Generates the next pseudorandom long number.  All bits of this
308       * long are independently chosen and 0 and 1 have equal likelihood.
309       * The implementation for java.util.Random is:
310       *
311    <pre>public long nextLong()
312    {
313      return ((long) next(32) &lt;&lt; 32) + next(32);
314    }</pre>
315       *
316       * @return the next pseudorandom value
317       */
318      public long nextLong()
319      {
320        return ((long) next(32) << 32) + next(32);
321      }
322    
323      /**
324       * Generates the next pseudorandom boolean.  True and false have
325       * the same probability.  The implementation is:
326       * 
327    <pre>public boolean nextBoolean()
328    {
329      return next(1) != 0;
330    }</pre>
331       *
332       * @return the next pseudorandom boolean
333       * @since 1.2
334       */
335      public boolean nextBoolean()
336      {
337        return next(1) != 0;
338      }
339    
340      /**
341       * Generates the next pseudorandom float uniformly distributed
342       * between 0.0f (inclusive) and 1.0f (exclusive).  The
343       * implementation is as follows.
344       * 
345    <pre>public float nextFloat()
346    {
347      return next(24) / ((float)(1 &lt;&lt; 24));
348    }</pre>
349       *
350       * @return the next pseudorandom float
351       */
352      public float nextFloat()
353      {
354        return next(24) / (float) (1 << 24);
355      }
356    
357      /**
358       * Generates the next pseudorandom double uniformly distributed
359       * between 0.0 (inclusive) and 1.0 (exclusive).  The
360       * implementation is as follows.
361       *
362    <pre>public double nextDouble()
363    {
364      return (((long) next(26) &lt;&lt; 27) + next(27)) / (double)(1L &lt;&lt; 53);
365    }</pre>
366       *
367       * @return the next pseudorandom double
368       */
369      public double nextDouble()
370      {
371        return (((long) next(26) << 27) + next(27)) / (double) (1L << 53);
372      }
373    
374      /**
375       * Generates the next pseudorandom, Gaussian (normally) distributed
376       * double value, with mean 0.0 and standard deviation 1.0.
377       * The algorithm is as follows.
378       * 
379    <pre>public synchronized double nextGaussian()
380    {
381      if (haveNextNextGaussian)
382      {
383        haveNextNextGaussian = false;
384        return nextNextGaussian;
385      }
386      else
387      {
388        double v1, v2, s;
389        do
390        {
391          v1 = 2 * nextDouble() - 1; // between -1.0 and 1.0
392          v2 = 2 * nextDouble() - 1; // between -1.0 and 1.0
393          s = v1 * v1 + v2 * v2;
394        }
395        while (s >= 1);
396    
397        double norm = Math.sqrt(-2 * Math.log(s) / s);
398        nextNextGaussian = v2 * norm;
399        haveNextNextGaussian = true;
400        return v1 * norm;
401      }
402    }</pre>
403       *
404       * <p>This is described in section 3.4.1 of <em>The Art of Computer
405       * Programming, Volume 2</em> by Donald Knuth.
406       *
407       * @return the next pseudorandom Gaussian distributed double
408       */
409      public synchronized double nextGaussian()
410      {
411        if (haveNextNextGaussian)
412          {
413            haveNextNextGaussian = false;
414            return nextNextGaussian;
415          }
416        double v1, v2, s;
417        do
418          {
419            v1 = 2 * nextDouble() - 1; // Between -1.0 and 1.0.
420            v2 = 2 * nextDouble() - 1; // Between -1.0 and 1.0.
421            s = v1 * v1 + v2 * v2;
422          }
423        while (s >= 1);
424        double norm = Math.sqrt(-2 * Math.log(s) / s);
425        nextNextGaussian = v2 * norm;
426        haveNextNextGaussian = true;
427        return v1 * norm;
428      }
429    }