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 }