001: /*
002: * Copyright 2003-2004 The Apache Software Foundation.
003: *
004: * Licensed under the Apache License, Version 2.0 (the "License");
005: * you may not use this file except in compliance with the License.
006: * You may obtain a copy of the License at
007: *
008: * http://www.apache.org/licenses/LICENSE-2.0
009: *
010: * Unless required by applicable law or agreed to in writing, software
011: * distributed under the License is distributed on an "AS IS" BASIS,
012: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013: * See the License for the specific language governing permissions and
014: * limitations under the License.
015: */
016:
017: package org.apache.commons.math.random;
018:
019: import java.io.Serializable;
020: import java.security.MessageDigest;
021: import java.security.SecureRandom;
022: import java.security.NoSuchAlgorithmException;
023: import java.security.NoSuchProviderException;
024: import java.util.Collection;
025:
026: /**
027: * Implements the {@link RandomData} interface using a {@link RandomGenerator}
028: * instance to generate non-secure data and a
029: * {@link java.security.SecureRandom} instance to provide data for the
030: * <code>nextSecureXxx</code> methods. If no <code>RandomGenerator</code>
031: * is provided in the constructor, the default is to use a generator based on
032: * {@link java.util.Random}. To plug in a different implementation,
033: * either implement <code>RandomGenerator</code> directly or extend
034: * {@link AbstractRandomGenerator}.
035: * <p>
036: * Supports reseeding the underlying pseudo-random number generator (PRNG).
037: * The <code>SecurityProvider</code> and <code>Algorithm</code>
038: * used by the <code>SecureRandom</code> instance can also be reset.
039: * <p>
040: * For details on the default PRNGs, see {@link java.util.Random} and
041: * {@link java.security.SecureRandom}.
042: * <p>
043: * <strong>Usage Notes</strong>: <ul>
044: * <li>
045: * Instance variables are used to maintain <code>RandomGenerator</code> and
046: * <code>SecureRandom</code> instances used in data generation. Therefore,
047: * to generate a random sequence of values or strings, you should use just
048: * <strong>one</strong> <code>RandomDataImpl</code> instance repeatedly.</li>
049: * <li>
050: * The "secure" methods are *much* slower. These should be used only when a
051: * cryptographically secure random sequence is required. A secure random
052: * sequence is a sequence of pseudo-random values which, in addition to being
053: * well-dispersed (so no subsequence of values is an any more likely than other
054: * subsequence of the the same length), also has the additional property that
055: * knowledge of values generated up to any point in the sequence does not make
056: * it any easier to predict subsequent values.</li>
057: * <li>
058: * When a new <code>RandomDataImpl</code> is created, the underlying random
059: * number generators are <strong>not</strong> intialized. If you do not
060: * explicitly seed the default non-secure generator, it is seeded with the current time
061: * in milliseconds on first use. The same holds for the secure generator.
062: * If you provide a <code>RandomGenerator</code> to the constructor, however,
063: * this generator is not reseeded by the constructor nor is it reseeded on
064: * first use. </li>
065: * <li>
066: * The <code>reSeed</code> and <code>reSeedSecure</code> methods delegate
067: * to the corresponding methods on the underlying <code>RandomGenerator</code>
068: * and<code>SecureRandom</code> instances. Therefore,
069: * <code>reSeed(long)</code> fully resets the initial state of the non-secure
070: * random number generator (so that reseeding with a specific value always
071: * results in the same subsequent random sequence); whereas reSeedSecure(long)
072: * does <strong>not</strong> reinitialize the secure random number generator
073: * (so secure sequences started with calls to reseedSecure(long) won't be
074: * identical).</li>
075: * <li>
076: * This implementation is not synchronized.
077: * </ul>
078: *
079: * @version $Revision: 348519 $ $Date: 2005-11-23 12:12:18 -0700 (Wed, 23 Nov 2005) $
080: */
081: public class RandomDataImpl implements RandomData, Serializable {
082:
083: /** Serializable version identifier */
084: private static final long serialVersionUID = -626730818244969716L;
085:
086: /** underlying random number generator */
087: private RandomGenerator rand = null;
088:
089: /** underlying secure random number generator */
090: private SecureRandom secRand = null;
091:
092: /**
093: * Construct a RandomDataImpl.
094: */
095: public RandomDataImpl() {
096: }
097:
098: /**
099: * 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(
123: "length must be positive");
124: }
125:
126: //Get a random number generator
127: RandomGenerator ran = getRan();
128:
129: //Initialize output buffer
130: StringBuffer outBuffer = new StringBuffer();
131:
132: //Get int(len/2)+1 random bytes
133: byte[] randomBytes = new byte[(len / 2) + 1];
134: ran.nextBytes(randomBytes);
135:
136: //Convert each byte to 2 hex digits
137: for (int i = 0; i < randomBytes.length; i++) {
138: Integer c = new Integer(randomBytes[i]);
139:
140: /* Add 128 to byte value to make interval 0-255 before
141: * doing hex conversion.
142: * This guarantees <= 2 hex digits from toHexString()
143: * toHexString would otherwise add 2^32 to negative arguments.
144: */
145: String hex = Integer.toHexString(c.intValue() + 128);
146:
147: // Make sure we add 2 hex digits for each byte
148: if (hex.length() == 1) {
149: hex = "0" + hex;
150: }
151: outBuffer.append(hex);
152: }
153: return outBuffer.toString().substring(0, len);
154: }
155:
156: /**
157: * Generate a random int value uniformly distributed between
158: * <code>lower</code> and <code>upper</code>, inclusive.
159: *
160: * @param lower the lower bound.
161: * @param upper the upper bound.
162: * @return the random integer.
163: */
164: public int nextInt(int lower, int upper) {
165: if (lower >= upper) {
166: throw new IllegalArgumentException(
167: "upper bound must be > lower bound");
168: }
169: RandomGenerator rand = getRan();
170: return lower + (int) (rand.nextDouble() * (upper - lower + 1));
171: }
172:
173: /**
174: * Generate a random long value uniformly distributed between
175: * <code>lower</code> and <code>upper</code>, inclusive.
176: *
177: * @param lower the lower bound.
178: * @param upper the upper bound.
179: * @return the random integer.
180: */
181: public long nextLong(long lower, long upper) {
182: if (lower >= upper) {
183: throw new IllegalArgumentException(
184: "upper bound must be > lower bound");
185: }
186: RandomGenerator rand = getRan();
187: return lower + (long) (rand.nextDouble() * (upper - lower + 1));
188: }
189:
190: /**
191: * <strong>Algorithm Description:</strong> hex strings are generated in
192: * 40-byte segments using a 3-step process. <ol>
193: * <li>
194: * 20 random bytes are generated using the underlying
195: * <code>SecureRandom</code>.</li>
196: * <li>
197: * SHA-1 hash is applied to yield a 20-byte binary digest.</li>
198: * <li>
199: * Each byte of the binary digest is converted to 2 hex digits.</li></ol>
200: *
201: * @param len the length of the generated string
202: * @return the random string
203: */
204: public String nextSecureHexString(int len) {
205: if (len <= 0) {
206: throw new IllegalArgumentException(
207: "length must be positive");
208: }
209:
210: // Get SecureRandom and setup Digest provider
211: SecureRandom secRan = getSecRan();
212: MessageDigest alg = null;
213: try {
214: alg = MessageDigest.getInstance("SHA-1");
215: } catch (NoSuchAlgorithmException ex) {
216: return null; // gulp FIXME? -- this *should* never fail.
217: }
218: alg.reset();
219:
220: //Compute number of iterations required (40 bytes each)
221: int numIter = (len / 40) + 1;
222:
223: StringBuffer outBuffer = new StringBuffer();
224: for (int iter = 1; iter < numIter + 1; iter++) {
225: byte[] randomBytes = new byte[40];
226: secRan.nextBytes(randomBytes);
227: alg.update(randomBytes);
228:
229: //Compute hash -- will create 20-byte binary hash
230: byte hash[] = alg.digest();
231:
232: //Loop over the hash, converting each byte to 2 hex digits
233: for (int i = 0; i < hash.length; i++) {
234: Integer c = new Integer(hash[i]);
235:
236: /* Add 128 to byte value to make interval 0-255
237: * This guarantees <= 2 hex digits from toHexString()
238: * toHexString would otherwise add 2^32 to negative
239: * arguments
240: */
241: String hex = Integer.toHexString(c.intValue() + 128);
242:
243: //Keep strings uniform length -- guarantees 40 bytes
244: if (hex.length() == 1) {
245: hex = "0" + hex;
246: }
247: outBuffer.append(hex);
248: }
249: }
250: return outBuffer.toString().substring(0, len);
251: }
252:
253: /**
254: * Generate a random int value uniformly distributed between
255: * <code>lower</code> and <code>upper</code>, inclusive. This algorithm
256: * uses a secure random number generator.
257: *
258: * @param lower the lower bound.
259: * @param upper the upper bound.
260: * @return the random integer.
261: */
262: public int nextSecureInt(int lower, int upper) {
263: if (lower >= upper) {
264: throw new IllegalArgumentException(
265: "lower bound must be < upper bound");
266: }
267: SecureRandom sec = getSecRan();
268: return lower + (int) (sec.nextDouble() * (upper - lower + 1));
269: }
270:
271: /**
272: * Generate a random long value uniformly distributed between
273: * <code>lower</code> and <code>upper</code>, inclusive. This algorithm
274: * uses a secure random number generator.
275: *
276: * @param lower the lower bound.
277: * @param upper the upper bound.
278: * @return the random integer.
279: */
280: public long nextSecureLong(long lower, long upper) {
281: if (lower >= upper) {
282: throw new IllegalArgumentException(
283: "lower bound must be < upper bound");
284: }
285: SecureRandom sec = getSecRan();
286: return lower + (long) (sec.nextDouble() * (upper - lower + 1));
287: }
288:
289: /**
290: * Generates a random long value from the Poisson distribution with the
291: * given mean.
292: * <p>
293: * <strong>Algorithm Description</strong>:
294: * Uses simulation of a Poisson process using Uniform deviates, as
295: * described
296: * <a href="http://irmi.epfl.ch/cmos/Pmmi/interactive/rng7.htm">
297: * here.</a>
298: * <p>
299: * The Poisson process (and hence value returned) is bounded by
300: * 1000 * mean.
301: *
302: * @param mean mean of the Poisson distribution.
303: * @return the random Poisson value.
304: */
305: public long nextPoisson(double mean) {
306: if (mean <= 0) {
307: throw new IllegalArgumentException(
308: "Poisson mean must be > 0");
309: }
310: double p = Math.exp(-mean);
311: long n = 0;
312: double r = 1.0d;
313: double rnd = 1.0d;
314: RandomGenerator rand = getRan();
315: while (n < 1000 * mean) {
316: rnd = rand.nextDouble();
317: r = r * rnd;
318: if (r >= p) {
319: n++;
320: } else {
321: return n;
322: }
323: }
324: return n;
325: }
326:
327: /**
328: * Generate a random value from a Normal (a.k.a. Gaussian) distribution
329: * with the given mean, <code>mu</code> and the given standard deviation,
330: * <code>sigma</code>.
331: *
332: * @param mu the mean of the distribution
333: * @param sigma the standard deviation of the distribution
334: * @return the random Normal value
335: */
336: public double nextGaussian(double mu, double sigma) {
337: if (sigma <= 0) {
338: throw new IllegalArgumentException(
339: "Gaussian std dev must be > 0");
340: }
341: RandomGenerator rand = getRan();
342: return sigma * rand.nextGaussian() + mu;
343: }
344:
345: /**
346: * Returns a random value from an Exponential distribution with the given
347: * mean.
348: * <p>
349: * <strong>Algorithm Description</strong>: Uses the
350: * <a href="http://www.jesus.ox.ac.uk/~clifford/a5/chap1/node5.html">
351: * Inversion Method</a> to generate exponentially distributed random values
352: * from uniform deviates.
353: *
354: * @param mean the mean of the distribution
355: * @return the random Exponential value
356: */
357: public double nextExponential(double mean) {
358: if (mean < 0.0) {
359: throw new IllegalArgumentException(
360: "Exponential mean must be >= 0");
361: }
362: RandomGenerator rand = getRan();
363: double unif = rand.nextDouble();
364: while (unif == 0.0d) {
365: unif = rand.nextDouble();
366: }
367: return -mean * Math.log(unif);
368: }
369:
370: /**
371: * <strong>Algorithm Description</strong>: scales the output of
372: * Random.nextDouble(), but rejects 0 values (i.e., will generate another
373: * random double if Random.nextDouble() returns 0).
374: * This is necessary to provide a symmetric output interval
375: * (both endpoints excluded).
376: *
377: * @param lower the lower bound.
378: * @param upper the upper bound.
379: * @return a uniformly distributed random value from the interval (lower, upper)
380: */
381: public double nextUniform(double lower, double upper) {
382: if (lower >= upper) {
383: throw new IllegalArgumentException(
384: "lower bound must be <= upper bound");
385: }
386: RandomGenerator rand = getRan();
387:
388: // ensure nextDouble() isn't 0.0
389: double u = rand.nextDouble();
390: while (u <= 0.0) {
391: u = rand.nextDouble();
392: }
393:
394: return lower + u * (upper - lower);
395: }
396:
397: /**
398: * Returns the RandomGenerator used to generate non-secure
399: * random data.
400: * <p>
401: * Creates and initializes a default generator if null.
402: *
403: * @return the Random used to generate random data
404: * @since 1.1
405: */
406: private RandomGenerator getRan() {
407: if (rand == null) {
408: rand = new JDKRandomGenerator();
409: rand.setSeed(System.currentTimeMillis());
410: }
411: return rand;
412: }
413:
414: /**
415: * Returns the SecureRandom used to generate secure random data.
416: * <p>
417: * Creates and initializes if null.
418: *
419: * @return the SecureRandom used to generate secure random data
420: */
421: private SecureRandom getSecRan() {
422: if (secRand == null) {
423: secRand = new SecureRandom();
424: secRand.setSeed(System.currentTimeMillis());
425: }
426: return secRand;
427: }
428:
429: /**
430: * Reseeds the random number generator with the supplied seed.
431: * <p>
432: * Will create and initialize if null.
433: *
434: * @param seed the seed value to use
435: */
436: public void reSeed(long seed) {
437: if (rand == null) {
438: rand = new JDKRandomGenerator();
439: }
440: rand.setSeed(seed);
441: }
442:
443: /**
444: * Reseeds the secure random number generator with the current time
445: * in milliseconds.
446: * <p>
447: * Will create and initialize if null.
448: */
449: public void reSeedSecure() {
450: if (secRand == null) {
451: secRand = new SecureRandom();
452: }
453: secRand.setSeed(System.currentTimeMillis());
454: }
455:
456: /**
457: * Reseeds the secure random number generator with the supplied seed.
458: * <p>
459: * Will create and initialize if null.
460: *
461: * @param seed the seed value to use
462: */
463: public void reSeedSecure(long seed) {
464: if (secRand == null) {
465: secRand = new SecureRandom();
466: }
467: secRand.setSeed(seed);
468: }
469:
470: /**
471: * Reseeds the random number generator with the current time
472: * in milliseconds.
473: */
474: public void reSeed() {
475: if (rand == null) {
476: rand = new JDKRandomGenerator();
477: }
478: rand.setSeed(System.currentTimeMillis());
479: }
480:
481: /**
482: * Sets the PRNG algorithm for the underlying SecureRandom instance
483: * using the Security Provider API. The Security Provider API is defined in
484: * <a href="http://java.sun.com/j2se/1.3/docs/guide/security/CryptoSpec.html#AppA">
485: * Java Cryptography Architecture API Specification & Reference.</a>
486: * <p>
487: * <strong>USAGE NOTE:</strong> This method carries <i>significant</i>
488: * overhead and may take several seconds to execute.
489: * </p>
490: *
491: * @param algorithm the name of the PRNG algorithm
492: * @param provider the name of the provider
493: * @throws NoSuchAlgorithmException if the specified algorithm
494: * is not available
495: * @throws NoSuchProviderException if the specified provider
496: * is not installed
497: */
498: public void setSecureAlgorithm(String algorithm, String provider)
499: throws NoSuchAlgorithmException, NoSuchProviderException {
500: secRand = SecureRandom.getInstance(algorithm, provider);
501: }
502:
503: /**
504: * Uses a 2-cycle permutation shuffle to generate a random permutation.
505: * The shuffling process is described
506: * <a href="http://www.maths.abdn.ac.uk/~igc/tch/mx4002/notes/node83.html">
507: * here</a>.
508: * @param n the population size.
509: * @param k the number to choose.
510: * @return the random permutation.
511: */
512: public int[] nextPermutation(int n, int k) {
513: if (k > n) {
514: throw new IllegalArgumentException(
515: "permutation k exceeds n");
516: }
517: if (k == 0) {
518: throw new IllegalArgumentException(
519: "permutation k must be > 0");
520: }
521:
522: int[] index = getNatural(n);
523: shuffle(index, n - k);
524: int[] result = new int[k];
525: for (int i = 0; i < k; i++) {
526: result[i] = index[n - i - 1];
527: }
528:
529: return result;
530: }
531:
532: /**
533: * Uses a 2-cycle permutation shuffle to generate a random permutation.
534: * <strong>Algorithm Description</strong>: Uses a 2-cycle permutation
535: * shuffle to generate a random permutation of <code>c.size()</code> and
536: * then returns the elements whose indexes correspond to the elements of
537: * the generated permutation.
538: * This technique is described, and proven to generate random samples,
539: * <a href="http://www.maths.abdn.ac.uk/~igc/tch/mx4002/notes/node83.html">
540: * here</a>
541: * @param c Collection to sample from.
542: * @param k sample size.
543: * @return the random sample.
544: */
545: public Object[] nextSample(Collection c, int k) {
546: int len = c.size();
547: if (k > len) {
548: throw new IllegalArgumentException(
549: "sample size exceeds collection size");
550: }
551: if (k == 0) {
552: throw new IllegalArgumentException(
553: "sample size must be > 0");
554: }
555:
556: Object[] objects = c.toArray();
557: int[] index = nextPermutation(len, k);
558: Object[] result = new Object[k];
559: for (int i = 0; i < k; i++) {
560: result[i] = objects[index[i]];
561: }
562: return result;
563: }
564:
565: //------------------------Private methods----------------------------------
566:
567: /**
568: * Uses a 2-cycle permutation shuffle to randomly re-order the last elements
569: * of list.
570: *
571: * @param list list to be shuffled
572: * @param end element past which shuffling begins
573: */
574: private void shuffle(int[] list, int end) {
575: int target = 0;
576: for (int i = list.length - 1; i >= end; i--) {
577: if (i == 0) {
578: target = 0;
579: } else {
580: target = nextInt(0, i);
581: }
582: int temp = list[target];
583: list[target] = list[i];
584: list[i] = temp;
585: }
586: }
587:
588: /**
589: * Returns an array representing n.
590: *
591: * @param n the natural number to represent
592: * @return array with entries = elements of n
593: */
594: private int[] getNatural(int n) {
595: int[] natural = new int[n];
596: for (int i = 0; i < n; i++) {
597: natural[i] = i;
598: }
599: return natural;
600: }
601: }
|