1
2
3
4
5
6
7
8
9
10
11
12
13
14
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
109 Random ran = getRan();
110
111
112 StringBuffer outBuffer = new StringBuffer();
113
114
115 byte[] randomBytes = new byte[(len / 2) + 1];
116 ran.nextBytes(randomBytes);
117
118
119 for (int i = 0; i < randomBytes.length; i++) {
120 Integer c = new Integer(randomBytes[i]);
121
122
123
124
125
126
127 String hex = Integer.toHexString(c.intValue() + 128);
128
129
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
192 SecureRandom secRan = getSecRan();
193 MessageDigest alg = null;
194 try {
195 alg = MessageDigest.getInstance("SHA-1");
196 } catch (NoSuchAlgorithmException ex) {
197 return null;
198 }
199 alg.reset();
200
201
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
211 byte hash[] = alg.digest();
212
213
214 for (int i = 0; i < hash.length; i++) {
215 Integer c = new Integer(hash[i]);
216
217
218
219
220
221
222 String hex = Integer.toHexString(c.intValue() + 128);
223
224
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
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
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 }