View Javadoc

1   /*
2    * Copyright 2003-2004 The Apache Software Foundation.
3    *
4    * Licensed under the Apache License, Version 2.0 (the "License");
5    * you may not use this file except in compliance with the License.
6    * You may obtain a copy of the License at
7    *
8    *      http://www.apache.org/licenses/LICENSE-2.0
9    *
10   * Unless required by applicable law or agreed to in writing, software
11   * distributed under the License is distributed on an "AS IS" BASIS,
12   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13   * See the License for the specific language governing permissions and
14   * limitations under the License.
15   */
16  
17  package org.apache.commons.math.random;
18  
19  import java.io.Serializable;
20  import java.security.MessageDigest;
21  import java.security.SecureRandom;
22  import java.security.NoSuchAlgorithmException;
23  import java.security.NoSuchProviderException;
24  import java.util.Random;
25  import java.util.Collection;
26  
27  /***
28   * Implements the {@link RandomData} interface using
29   * {@link java.util.Random} and {@link java.util.Random.SecureRandom} instances
30   * to generate data.
31   * <p>
32   * Supports reseeding the underlying pseudo-random number generator (PRNG). 
33   * The <code>SecurityProvider</code> and <code>Algorithm</code>
34   * used by the <code>SecureRandom</code> instance can also be reset.
35   * <p>
36   * For details on the PRNGs, see {@link java.util.Random} and
37   * {@link java.util.Random.SecureRandom}.
38   * <p>
39   * <strong>Usage Notes</strong>: <ul>
40   * <li>
41   * Instance variables are used to maintain <code>Random</code> and
42   * <code>SecureRandom</code> instances used in data generation. Therefore,
43   * to generate a random sequence of values or strings, you should use just
44   * <strong>one</strong> <code>RandomDataImpl</code> instance repeatedly.</li>
45   * <li>
46   * The "secure" methods are *much* slower.  These should be used only when a
47   * cryptographically secure random sequence is required.  A secure random
48   * sequence is a sequence of pseudo-random values which, in addition to being
49   * well-dispersed (so no subsequence of values is an any more likely than other
50   * subsequence of the the same length), also has the additional property that
51   * knowledge of values generated up to any point in the sequence does not make
52   * it any easier to predict subsequent values.</li>
53   * <li>
54   * When a new <code>RandomDataImpl</code> is created, the underlying random
55   * number generators are <strong>not</strong> intialized.  The first call to a
56   * data generation method, or to a <code>reSeed()</code> method instantiates
57   * the appropriate generator.  If you do not explicitly seed the generator, it
58   * is by default seeded with the current time in milliseconds</li>
59   * <li>
60   * The <code>reSeed</code> and <code>reSeedSecure</code> methods delegate
61   * to the corresponding methods on the underlying <code>Random</code> and
62   * <code>SecureRandom</code> instances.  Therefore, the contracts of these
63   * methods are as defined in the JDK documentation.  In particular,
64   * <code>reSeed(long)</code> fully resets the initial state of the non-secure
65   * random number generator (so that reseeding with a specific value always
66   * results in the same subsequent random sequence); whereas reSeedSecure(long)
67   * does <strong>not</strong> reinitialize the secure random number generator
68   * (so secure sequences started with calls to reseedSecure(long) won't be
69   * identical).</li>
70   * <li>
71   * This implementation is not synchronized.
72   * </ul>
73   *
74   * @version $Revision: 1.16 $ $Date: 2004/07/22 02:34:25 $
75   */
76  public class RandomDataImpl implements RandomData, Serializable {
77  
78      /*** Serializable version identifier */
79      static final long serialVersionUID = -626730818244969716L;
80  
81      /*** underlying random number generator */
82      private Random rand = null;
83  
84      /*** underlying secure random number generator */
85      private SecureRandom secRand = null;
86  
87      /***
88       * Construct a RandomDataImpl.
89       */
90      public RandomDataImpl() {
91      }
92  
93      /***
94       * <strong>Algorithm Description:</strong> hex strings are generated
95       * using a 2-step process. <ol>
96       * <li>
97       * len/2+1 binary bytes are generated using the underlying Random</li>
98       * <li>
99       * Each binary byte is translated into 2 hex digits</li></ol>
100      * @param len the desired string length.
101      * @return the random string.
102      */
103     public String nextHexString(int len) {
104         if (len <= 0) {
105             throw new IllegalArgumentException("length must be positive");
106         }
107 
108         //Get a random number generator
109         Random ran = getRan();
110 
111         //Initialize output buffer
112         StringBuffer outBuffer = new StringBuffer();
113 
114         //Get int(len/2)+1 random bytes
115         byte[] randomBytes = new byte[(len / 2) + 1];
116         ran.nextBytes(randomBytes);
117 
118         //Convert each byte to 2 hex digits
119         for (int i = 0; i < randomBytes.length; i++) {
120             Integer c = new Integer(randomBytes[i]);
121 
122             /* Add 128 to byte value to make interval 0-255 before
123              * doing hex conversion.
124              * This guarantees <= 2 hex digits from toHexString()
125              * toHexString would otherwise add 2^32 to negative arguments.
126              */
127              String hex = Integer.toHexString(c.intValue() + 128);
128 
129              // Make sure we add 2 hex digits for each byte
130              if (hex.length() == 1)  {
131                  hex = "0" + hex;
132              }
133              outBuffer.append(hex);
134         }
135         return outBuffer.toString().substring(0, len);
136     }
137 
138     /***
139      * Generate a random int value uniformly distributed between
140      * <code>lower</code> and <code>upper</code>, inclusive.
141      * 
142      * @param lower the lower bound.
143      * @param upper the upper bound.
144      * @return the random integer.
145      */
146     public int nextInt(int lower, int upper) {
147         if (lower >= upper) {
148             throw new IllegalArgumentException
149                 ("upper bound must be > lower bound");
150         }
151         Random rand = getRan();
152         return lower + (int) (rand.nextDouble() * (upper - lower + 1));
153     }
154 
155     /***
156      * Generate a random long value uniformly distributed between
157      * <code>lower</code> and <code>upper</code>, inclusive.
158      * 
159      * @param lower the lower bound.
160      * @param upper the upper bound.
161      * @return the random integer.
162      */
163     public long nextLong(long lower, long upper) {
164         if (lower >= upper) {
165             throw new IllegalArgumentException
166                 ("upper bound must be > lower bound");
167         }
168         Random rand = getRan();
169         return lower + (long) (rand.nextDouble() * (upper - lower + 1));
170     }
171 
172      /***
173      * <strong>Algorithm Description:</strong> hex strings are generated in
174      * 40-byte segments using a 3-step process. <ol>
175      * <li>
176      * 20 random bytes are generated using the underlying
177      * <code>SecureRandom</code>.</li>
178      * <li>
179      * SHA-1 hash is applied to yield a 20-byte binary digest.</li>
180      * <li>
181      * Each byte of the binary digest is converted to 2 hex digits.</li></ol>
182      *
183      * @param len the length of the generated string
184      * @return the random string
185      */
186     public String nextSecureHexString(int len) {
187         if (len <= 0) {
188             throw new IllegalArgumentException("length must be positive");
189         }
190 
191        // Get SecureRandom and setup Digest provider
192        SecureRandom secRan = getSecRan();
193        MessageDigest alg = null;
194        try {
195             alg = MessageDigest.getInstance("SHA-1");
196        } catch (NoSuchAlgorithmException ex) {
197            return null; // gulp FIXME? -- this *should* never fail.
198        }
199        alg.reset();
200 
201        //Compute number of iterations required (40 bytes each)
202        int numIter = (len / 40) + 1;
203 
204        StringBuffer outBuffer = new StringBuffer();
205        for (int iter = 1; iter < numIter + 1; iter++) {
206             byte[] randomBytes = new byte[40];
207             secRan.nextBytes(randomBytes);
208             alg.update(randomBytes);
209 
210             //Compute hash -- will create 20-byte binary hash
211             byte hash[] = alg.digest();
212 
213             //Loop over the hash, converting each byte to 2 hex digits
214             for (int i = 0; i < hash.length; i++) {
215                 Integer c = new Integer(hash[i]);
216 
217                 /* Add 128 to byte value to make interval 0-255
218                  * This guarantees <= 2 hex digits from toHexString()
219                  * toHexString would otherwise add 2^32 to negative
220                  * arguments
221                  */
222                 String hex = Integer.toHexString(c.intValue() + 128);
223 
224                //Keep strings uniform length -- guarantees 40 bytes
225                 if (hex.length() == 1) {
226                     hex = "0" + hex;
227                 }
228                outBuffer.append(hex);
229             }
230         }
231         return outBuffer.toString().substring(0, len);
232     }
233 
234     /***
235      * Generate a random int value uniformly distributed between
236      * <code>lower</code> and <code>upper</code>, inclusive.  This algorithm
237      * uses a secure random number generator.
238      * 
239      * @param lower the lower bound.
240      * @param upper the upper bound.
241      * @return the random integer.
242      */
243     public int nextSecureInt(int lower, int upper) {
244           if (lower >= upper) {
245               throw new IllegalArgumentException
246                 ("lower bound must be < upper bound");
247           }
248           SecureRandom sec = getSecRan();
249           return lower + (int) (sec.nextDouble() * (upper - lower + 1));
250     }
251 
252     /***
253      * Generate a random long value uniformly distributed between
254      * <code>lower</code> and <code>upper</code>, inclusive.  This algorithm
255      * uses a secure random number generator.
256      * 
257      * @param lower the lower bound.
258      * @param upper the upper bound.
259      * @return the random integer.
260      */
261     public long nextSecureLong(long lower, long upper) {
262         if (lower >= upper) {
263             throw new IllegalArgumentException
264             ("lower bound must be < upper bound");
265         }
266         SecureRandom sec = getSecRan();
267         return lower + (long) (sec.nextDouble() * (upper - lower + 1));
268     }
269 
270     /***
271      * Generates a random long value from the Poisson distribution with the
272      * given mean.
273      * <p>
274      * <strong>Algorithm Description</strong>:
275      * Uses simulation of a Poisson process using Uniform deviates, as
276      * described
277      * <a href ="http://dmawww.epfl.ch/benarous/Pmmi/interactive/rng7.htm">
278      * here.</a>
279      * <p>
280      * The Poisson process (and hence value returned) is bounded by 
281      * 1000 * mean.
282      * 
283      * @param mean mean of the Poisson distribution.
284      * @return the random Poisson value.
285      */
286     public long nextPoisson(double mean) {
287         if (mean <= 0) {
288             throw new IllegalArgumentException("Poisson mean must be > 0");
289         }
290         double p = Math.exp(-mean);
291         long n = 0;
292         double r = 1.0d;
293         double rnd = 1.0d;
294         Random rand = getRan();
295         while (n < 1000 * mean) {
296             rnd = rand.nextDouble();
297             r = r * rnd;
298             if (r >= p) {
299                 n++;
300             } else {
301                 return n;
302             }
303         }
304         return n;
305     }
306 
307     /***
308      * Generate a random value from a Normal (a.k.a. Gaussian) distribution
309      * with the given mean, <code>mu</code> and the given standard deviation,
310      * <code>sigma</code>.
311      * 
312      * @param mu the mean of the distribution
313      * @param sigma the standard deviation of the distribution
314      * @return the random Normal value
315      */
316     public double nextGaussian(double mu, double sigma) {
317         if (sigma <= 0) {
318             throw new IllegalArgumentException("Gaussian std dev must be > 0");
319         }
320         Random rand = getRan();
321         return sigma * rand.nextGaussian() + mu;
322     }
323 
324     /***
325      * Returns a random value from an Exponential distribution with the given
326      * mean.
327      * <p>
328      * <strong>Algorithm Description</strong>:  Uses the
329      * <a href="http://www.jesus.ox.ac.uk/~clifford/a5/chap1/node5.html">
330      * Inversion Method</a> to generate exponentially distributed random values
331      * from uniform deviates.
332      * 
333      * @param mean the mean of the distribution
334      * @return the random Exponential value
335      */
336     public double nextExponential(double mean)  {
337         if (mean < 0.0)  {
338             throw new IllegalArgumentException
339                 ("Exponential mean must be >= 0");
340         }
341         Random rand = getRan();
342         double unif = rand.nextDouble();
343         while (unif == 0.0d) {
344             unif = rand.nextDouble();
345         }
346         return -mean * Math.log(unif);
347     }
348 
349     /***
350      * <strong>Algorithm Description</strong>: scales the output of
351      * Random.nextDouble(), but rejects 0 values (i.e., will generate another
352      * random double if Random.nextDouble() returns 0).
353      * This is necessary to provide a symmetric output interval
354      * (both endpoints excluded).
355      * @param lower the lower bound.
356      * @param upper the upper bound.
357      * @return the random value.
358      */
359     public double nextUniform(double lower, double upper) {
360         if (lower >= upper) {
361             throw new IllegalArgumentException
362             ("lower bound must be <= upper bound");
363         }
364         Random rand = getRan();
365 
366         // insure nextDouble() isn't 0.0
367         double u = rand.nextDouble();
368         while(u <= 0.0){
369             u = rand.nextDouble();
370         }
371 
372         return lower + u * (upper - lower);
373     }
374 
375     /***
376      * Returns the static Random used to generate random data.
377      * <p>
378      * Creates and initializes if null.
379      *
380      * @return the static Random used to generate random data
381      */
382     private Random getRan() {
383         if (rand == null) {
384             rand = new Random();
385             rand.setSeed(System.currentTimeMillis());
386         }
387         return rand;
388     }
389 
390     /***
391      * Returns the static SecureRandom used to generate secure random data.
392      * <p>
393      * Creates and initializes if null.
394      *
395      * @return the static SecureRandom used to generate secure random data
396      */
397     private SecureRandom getSecRan() {
398         if (secRand == null) {
399             secRand = new SecureRandom();
400             secRand.setSeed(System.currentTimeMillis());
401         }
402         return secRand;
403     }
404 
405     /***
406      * Reseeds the random number generator with the supplied seed.
407      * <p>
408      * Will create and initialize if null.
409      *
410      * @param seed the seed value to use
411      */
412     public void reSeed(long seed) {
413         if (rand == null) {
414             rand = new Random();
415         }
416         rand.setSeed(seed);
417     }
418 
419     /***
420      * Reseeds the secure random number generator with the current time
421      * in milliseconds.
422      * <p>
423      * Will create and initialize if null.
424      */
425     public void reSeedSecure() {
426         if (secRand == null) {
427             secRand = new SecureRandom();
428         }
429         secRand.setSeed(System.currentTimeMillis());
430     }
431 
432     /***
433      * Reseeds the secure random number generator with the supplied seed.
434      * <p>
435      * Will create and initialize if null.
436      *
437      * @param seed the seed value to use
438      */
439     public void reSeedSecure(long seed) {
440         if (secRand == null) {
441             secRand = new SecureRandom();
442         }
443         secRand.setSeed(seed);
444     }
445 
446     /***
447      * Reseeds the random number generator with the current time
448      * in milliseconds.
449      */
450     public void reSeed() {
451         if (rand == null) {
452             rand = new Random();
453         }
454         rand.setSeed(System.currentTimeMillis());
455     }
456 
457     /***
458      * Sets the PRNG algorithm for the underlying SecureRandom instance
459      * using the Security Provider API.  The Security Provider API is defined in
460      * <a href="http://java.sun.com/j2se/1.3/docs/guide/security/CryptoSpec.html#AppA">
461      * Java Cryptography Architecture API Specification & Reference.</a>
462      * <p>
463      * <strong>USAGE NOTE:</strong> This method carries <i>significant</i>
464      * overhead and may take several seconds to execute.
465      * </p>
466      *
467      * @param algorithm the name of the PRNG algorithm
468      * @param provider the name of the provider
469      * @throws NoSuchAlgorithmException if the specified algorithm
470      * is not available
471      * @throws NoSuchProviderException if the specified provider
472      * is not installed
473      */
474     public void setSecureAlgorithm(String algorithm, String provider)
475         throws NoSuchAlgorithmException, NoSuchProviderException {
476         secRand = SecureRandom.getInstance(algorithm, provider);
477     }
478 
479     /***
480      * Uses a 2-cycle permutation shuffle to generate a random permutation.
481      * The shuffling process is described
482      * <a href="http://www.maths.abdn.ac.uk/~igc/tch/mx4002/notes/node83.html">
483      * here</a>.
484      * @param n the population size.
485      * @param k the number to choose.
486      * @return the random permutation.
487      */
488     public int[] nextPermutation(int n, int k) {
489         if (k > n) {
490             throw new IllegalArgumentException
491                 ("permutation k exceeds n");
492         }
493         if (k == 0) {
494             throw new IllegalArgumentException
495                 ("permutation k must be > 0");
496         }
497 
498         int[] index = getNatural(n);
499         shuffle(index, n - k);
500         int[] result = new int[k];
501         for (int i = 0; i < k; i++) {
502             result[i] = index[n - i - 1];
503         }
504 
505         return result;
506     }
507 
508     /***
509      * Uses a 2-cycle permutation shuffle to generate a random permutation.
510      * <strong>Algorithm Description</strong>: Uses a 2-cycle permutation
511      * shuffle to generate a random permutation of <code>c.size()</code> and
512      * then returns the elements whose indexes correspond to the elements of
513      * the generated permutation.
514      * This technique is described, and proven to generate random samples,
515      * <a href="http://www.maths.abdn.ac.uk/~igc/tch/mx4002/notes/node83.html">
516      * here</a>
517      * @param c Collection to sample from.
518      * @param k sample size.
519      * @return the random sample.
520      */
521     public Object[] nextSample(Collection c, int k) {
522         int len = c.size();
523         if (k > len) {
524             throw new IllegalArgumentException
525                 ("sample size exceeds collection size");
526         }
527         if (k == 0) {
528             throw new IllegalArgumentException
529                 ("sample size must be > 0");
530         }
531 
532        Object[] objects = c.toArray();
533        int[] index = nextPermutation(len, k);
534        Object[] result = new Object[k];
535        for (int i = 0; i < k; i++) {
536            result[i] = objects[index[i]];
537        }
538        return result;
539     }
540 
541     //------------------------Private methods----------------------------------
542 
543     /***
544      * Uses a 2-cycle permutation shuffle to randomly re-order the last elements
545      * of list.
546      *
547      * @param list list to be shuffled
548      * @param end element past which shuffling begins
549      */
550     private void shuffle(int[] list, int end) {
551         int target = 0;
552         for (int i = list.length - 1 ; i >= end; i--) {
553             if (i == 0) {
554                 target = 0;
555             } else {
556                 target = nextInt(0, i);
557             }
558             int temp = list[target];
559             list[target] = list[i];
560             list[i] = temp;
561         }
562     }
563 
564     /***
565      * Returns an array representing n.
566      *
567      * @param n the natural number to represent
568      * @return array with entries = elements of n
569      */
570     private int[] getNatural(int n) {
571         int[] natural = new int[n];
572         for (int i = 0; i < n; i++) {
573             natural[i] = i;
574         }
575         return natural;
576     }
577 
578 }