RandomDataImpl


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