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.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: 348519 $ $Date: 2005-11-23 12:12:18 -0700 (Wed, 23 Nov 2005) $
    80   */
    81  public class RandomDataImpl implements RandomData, Serializable {
    82
    83      /*** Serializable version identifier */
    84      private 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 }