/*
* Licensed to the Apache Software Foundation (ASF) under one or more
* contributor license agreements. See the NOTICE file distributed with
* this work for additional information regarding copyright ownership.
* The ASF licenses this file to You under the Apache License, Version 2.0
* (the "License"); you may not use this file except in compliance with
* the License. You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
package org.apache.commons.math.random;
import java.io.Serializable;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.security.NoSuchProviderException;
import java.security.SecureRandom;
import java.util.Collection;
import org.apache.commons.math.MathException;
import org.apache.commons.math.distribution.BetaDistributionImpl;
import org.apache.commons.math.distribution.BinomialDistributionImpl;
import org.apache.commons.math.distribution.CauchyDistributionImpl;
import org.apache.commons.math.distribution.ChiSquaredDistributionImpl;
import org.apache.commons.math.distribution.ContinuousDistribution;
import org.apache.commons.math.distribution.FDistributionImpl;
import org.apache.commons.math.distribution.GammaDistributionImpl;
import org.apache.commons.math.distribution.HypergeometricDistributionImpl;
import org.apache.commons.math.distribution.IntegerDistribution;
import org.apache.commons.math.distribution.PascalDistributionImpl;
import org.apache.commons.math.distribution.TDistributionImpl;
import org.apache.commons.math.distribution.WeibullDistributionImpl;
import org.apache.commons.math.distribution.ZipfDistributionImpl;
import org.apache.commons.math.exception.MathInternalError;
import org.apache.commons.math.exception.NotStrictlyPositiveException;
import org.apache.commons.math.exception.NumberIsTooLargeException;
import org.apache.commons.math.exception.util.LocalizedFormats;
import org.apache.commons.math.util.FastMath;
import org.apache.commons.math.util.MathUtils;
/**
* Implements the {@link RandomData} interface using a {@link RandomGenerator}
* instance to generate non-secure data and a {@link java.security.SecureRandom}
* instance to provide data for the nextSecureXxx
methods. If no
* RandomGenerator
is provided in the constructor, the default is
* to use a generator based on {@link java.util.Random}. To plug in a different
* implementation, either implement RandomGenerator
directly or
* extend {@link AbstractRandomGenerator}.
*
* Supports reseeding the underlying pseudo-random number generator (PRNG). The
* SecurityProvider
and Algorithm
used by the
* SecureRandom
instance can also be reset.
*
* For details on the default PRNGs, see {@link java.util.Random} and * {@link java.security.SecureRandom}. *
** Usage Notes: *
RandomGenerator
and
* SecureRandom
instances used in data generation. Therefore, to
* generate a random sequence of values or strings, you should use just
* one RandomDataImpl
instance repeatedly.RandomDataImpl
is created, the underlying random
* number generators are not initialized. If you do not
* explicitly seed the default non-secure generator, it is seeded with the
* current time in milliseconds on first use. The same holds for the secure
* generator. If you provide a RandomGenerator
to the constructor,
* however, this generator is not reseeded by the constructor nor is it reseeded
* on first use.reSeed
and reSeedSecure
methods delegate to the
* corresponding methods on the underlying RandomGenerator
and
* SecureRandom
instances. Therefore, reSeed(long)
* fully resets the initial state of the non-secure random number generator (so
* that reseeding with a specific value always results in the same subsequent
* random sequence); whereas reSeedSecure(long) does not
* reinitialize the secure random number generator (so secure sequences started
* with calls to reseedSecure(long) won't be identical).* Algorithm Description: hex strings are generated using a * 2-step process. *
lower
and upper
, inclusive.
*
* @param lower
* the lower bound.
* @param upper
* the upper bound.
* @return the random integer.
* @throws NumberIsTooLargeException if {@code lower >= upper}.
*/
public int nextInt(int lower, int upper) {
if (lower >= upper) {
throw new NumberIsTooLargeException(LocalizedFormats.LOWER_BOUND_NOT_BELOW_UPPER_BOUND,
lower, upper, false);
}
double r = getRan().nextDouble();
return (int) ((r * upper) + ((1.0 - r) * lower) + r);
}
/**
* Generate a random long value uniformly distributed between
* lower
and upper
, inclusive.
*
* @param lower
* the lower bound.
* @param upper
* the upper bound.
* @return the random integer.
* @throws NumberIsTooLargeException if {@code lower >= upper}.
*/
public long nextLong(long lower, long upper) {
if (lower >= upper) {
throw new NumberIsTooLargeException(LocalizedFormats.LOWER_BOUND_NOT_BELOW_UPPER_BOUND,
lower, upper, false);
}
double r = getRan().nextDouble();
return (long) ((r * upper) + ((1.0 - r) * lower) + r);
}
/**
* {@inheritDoc}
* * Algorithm Description: hex strings are generated in * 40-byte segments using a 3-step process. *
SecureRandom
.lower
and upper
, inclusive. This algorithm uses
* a secure random number generator.
*
* @param lower
* the lower bound.
* @param upper
* the upper bound.
* @return the random integer.
* @throws NumberIsTooLargeException if {@code lower >= upper}.
*/
public int nextSecureInt(int lower, int upper) {
if (lower >= upper) {
throw new NumberIsTooLargeException(LocalizedFormats.LOWER_BOUND_NOT_BELOW_UPPER_BOUND,
lower, upper, false);
}
SecureRandom sec = getSecRan();
return lower + (int) (sec.nextDouble() * (upper - lower + 1));
}
/**
* Generate a random long value uniformly distributed between
* lower
and upper
, inclusive. This algorithm uses
* a secure random number generator.
*
* @param lower
* the lower bound.
* @param upper
* the upper bound.
* @return the random integer.
* @throws NumberIsTooLargeException if {@code lower >= upper}.
*/
public long nextSecureLong(long lower, long upper) {
if (lower >= upper) {
throw new NumberIsTooLargeException(LocalizedFormats.LOWER_BOUND_NOT_BELOW_UPPER_BOUND,
lower, upper, false);
}
SecureRandom sec = getSecRan();
return lower + (long) (sec.nextDouble() * (upper - lower + 1));
}
/**
* {@inheritDoc}
* * Algorithm Description: *
mu
and the given standard deviation,
* sigma
.
*
* @param mu
* the mean of the distribution
* @param sigma
* the standard deviation of the distribution
* @return the random Normal value
* @throws NotStrictlyPositiveException if {@code sigma <= 0}.
*/
public double nextGaussian(double mu, double sigma) {
if (sigma <= 0) {
throw new NotStrictlyPositiveException(LocalizedFormats.STANDARD_DEVIATION, sigma);
}
return sigma * getRan().nextGaussian() + mu;
}
/**
* Returns a random value from an Exponential distribution with the given
* mean.
* * Algorithm Description: Uses the Inversion * Method to generate exponentially distributed random values from * uniform deviates. *
* * @param mean the mean of the distribution * @return the random Exponential value * @throws NotStrictlyPositiveException if {@code mean <= 0}. */ public double nextExponential(double mean) { if (mean <= 0.0) { throw new NotStrictlyPositiveException(LocalizedFormats.MEAN, mean); } final RandomGenerator generator = getRan(); double unif = generator.nextDouble(); while (unif == 0.0d) { unif = generator.nextDouble(); } return -mean * FastMath.log(unif); } /** * {@inheritDoc} ** Algorithm Description: scales the output of * Random.nextDouble(), but rejects 0 values (i.e., will generate another * random double if Random.nextDouble() returns 0). This is necessary to * provide a symmetric output interval (both endpoints excluded). *
* * @param lower * the lower bound. * @param upper * the upper bound. * @return a uniformly distributed random value from the interval (lower, * upper) * @throws NumberIsTooLargeException if {@code lower >= upper}. */ public double nextUniform(double lower, double upper) { if (lower >= upper) { throw new NumberIsTooLargeException(LocalizedFormats.LOWER_BOUND_NOT_BELOW_UPPER_BOUND, lower, upper, false); } final RandomGenerator generator = getRan(); // ensure nextDouble() isn't 0.0 double u = generator.nextDouble(); while (u <= 0.0) { u = generator.nextDouble(); } return lower + u * (upper - lower); } /** * Generates a random value from the {@link BetaDistributionImpl Beta Distribution}. * This implementation uses {@link #nextInversionDeviate(ContinuousDistribution) inversion} * to generate random values. * * @param alpha first distribution shape parameter * @param beta second distribution shape parameter * @return random value sampled from the beta(alpha, beta) distribution * @throws MathException if an error occurs generating the random value * @since 2.2 */ public double nextBeta(double alpha, double beta) throws MathException { return nextInversionDeviate(new BetaDistributionImpl(alpha, beta)); } /** * Generates a random value from the {@link BinomialDistributionImpl Binomial Distribution}. * This implementation uses {@link #nextInversionDeviate(ContinuousDistribution) inversion} * to generate random values. * * @param numberOfTrials number of trials of the Binomial distribution * @param probabilityOfSuccess probability of success of the Binomial distribution * @return random value sampled from the Binomial(numberOfTrials, probabilityOfSuccess) distribution * @throws MathException if an error occurs generating the random value * @since 2.2 */ public int nextBinomial(int numberOfTrials, double probabilityOfSuccess) throws MathException { return nextInversionDeviate(new BinomialDistributionImpl(numberOfTrials, probabilityOfSuccess)); } /** * Generates a random value from the {@link CauchyDistributionImpl Cauchy Distribution}. * This implementation uses {@link #nextInversionDeviate(ContinuousDistribution) inversion} * to generate random values. * * @param median the median of the Cauchy distribution * @param scale the scale parameter of the Cauchy distribution * @return random value sampled from the Cauchy(median, scale) distribution * @throws MathException if an error occurs generating the random value * @since 2.2 */ public double nextCauchy(double median, double scale) throws MathException { return nextInversionDeviate(new CauchyDistributionImpl(median, scale)); } /** * Generates a random value from the {@link ChiSquaredDistributionImpl ChiSquare Distribution}. * This implementation uses {@link #nextInversionDeviate(ContinuousDistribution) inversion} * to generate random values. * * @param df the degrees of freedom of the ChiSquare distribution * @return random value sampled from the ChiSquare(df) distribution * @throws MathException if an error occurs generating the random value * @since 2.2 */ public double nextChiSquare(double df) throws MathException { return nextInversionDeviate(new ChiSquaredDistributionImpl(df)); } /** * Generates a random value from the {@link FDistributionImpl F Distribution}. * This implementation uses {@link #nextInversionDeviate(ContinuousDistribution) inversion} * to generate random values. * * @param numeratorDf the numerator degrees of freedom of the F distribution * @param denominatorDf the denominator degrees of freedom of the F distribution * @return random value sampled from the F(numeratorDf, denominatorDf) distribution * @throws MathException if an error occurs generating the random value * @since 2.2 */ public double nextF(double numeratorDf, double denominatorDf) throws MathException { return nextInversionDeviate(new FDistributionImpl(numeratorDf, denominatorDf)); } /** * Generates a random value from the {@link GammaDistributionImpl Gamma Distribution}. * This implementation uses {@link #nextInversionDeviate(ContinuousDistribution) inversion} * to generate random values. * * @param shape the median of the Gamma distribution * @param scale the scale parameter of the Gamma distribution * @return random value sampled from the Gamma(shape, scale) distribution * @throws MathException if an error occurs generating the random value * @since 2.2 */ public double nextGamma(double shape, double scale) throws MathException { return nextInversionDeviate(new GammaDistributionImpl(shape, scale)); } /** * Generates a random value from the {@link HypergeometricDistributionImpl Hypergeometric Distribution}. * This implementation uses {@link #nextInversionDeviate(IntegerDistribution) inversion} * to generate random values. * * @param populationSize the population size of the Hypergeometric distribution * @param numberOfSuccesses number of successes in the population of the Hypergeometric distribution * @param sampleSize the sample size of the Hypergeometric distribution * @return random value sampled from the Hypergeometric(numberOfSuccesses, sampleSize) distribution * @throws MathException if an error occurs generating the random value * @since 2.2 */ public int nextHypergeometric(int populationSize, int numberOfSuccesses, int sampleSize) throws MathException { return nextInversionDeviate(new HypergeometricDistributionImpl(populationSize, numberOfSuccesses, sampleSize)); } /** * Generates a random value from the {@link PascalDistributionImpl Pascal Distribution}. * This implementation uses {@link #nextInversionDeviate(IntegerDistribution) inversion} * to generate random values. * * @param r the number of successes of the Pascal distribution * @param p the probability of success of the Pascal distribution * @return random value sampled from the Pascal(r, p) distribution * @throws MathException if an error occurs generating the random value * @since 2.2 */ public int nextPascal(int r, double p) throws MathException { return nextInversionDeviate(new PascalDistributionImpl(r, p)); } /** * Generates a random value from the {@link TDistributionImpl T Distribution}. * This implementation uses {@link #nextInversionDeviate(ContinuousDistribution) inversion} * to generate random values. * * @param df the degrees of freedom of the T distribution * @return random value from the T(df) distribution * @throws MathException if an error occurs generating the random value * @since 2.2 */ public double nextT(double df) throws MathException { return nextInversionDeviate(new TDistributionImpl(df)); } /** * Generates a random value from the {@link WeibullDistributionImpl Weibull Distribution}. * This implementation uses {@link #nextInversionDeviate(ContinuousDistribution) inversion} * to generate random values. * * @param shape the shape parameter of the Weibull distribution * @param scale the scale parameter of the Weibull distribution * @return random value sampled from the Weibull(shape, size) distribution * @throws MathException if an error occurs generating the random value * @since 2.2 */ public double nextWeibull(double shape, double scale) throws MathException { return nextInversionDeviate(new WeibullDistributionImpl(shape, scale)); } /** * Generates a random value from the {@link ZipfDistributionImpl Zipf Distribution}. * This implementation uses {@link #nextInversionDeviate(IntegerDistribution) inversion} * to generate random values. * * @param numberOfElements the number of elements of the ZipfDistribution * @param exponent the exponent of the ZipfDistribution * @return random value sampled from the Zipf(numberOfElements, exponent) distribution * @throws MathException if an error occurs generating the random value * @since 2.2 */ public int nextZipf(int numberOfElements, double exponent) throws MathException { return nextInversionDeviate(new ZipfDistributionImpl(numberOfElements, exponent)); } /** * Returns the RandomGenerator used to generate non-secure random data. ** Creates and initializes a default generator if null. *
* * @return the Random used to generate random data * @since 1.1 */ private RandomGenerator getRan() { if (rand == null) { rand = new JDKRandomGenerator(); rand.setSeed(System.currentTimeMillis()); } return rand; } /** * Returns the SecureRandom used to generate secure random data. ** Creates and initializes if null. *
* * @return the SecureRandom used to generate secure random data */ private SecureRandom getSecRan() { if (secRand == null) { secRand = new SecureRandom(); secRand.setSeed(System.currentTimeMillis()); } return secRand; } /** * Reseeds the random number generator with the supplied seed. ** Will create and initialize if null. *
* * @param seed * the seed value to use */ public void reSeed(long seed) { if (rand == null) { rand = new JDKRandomGenerator(); } rand.setSeed(seed); } /** * Reseeds the secure random number generator with the current time in * milliseconds. ** Will create and initialize if null. *
*/ public void reSeedSecure() { if (secRand == null) { secRand = new SecureRandom(); } secRand.setSeed(System.currentTimeMillis()); } /** * Reseeds the secure random number generator with the supplied seed. ** Will create and initialize if null. *
* * @param seed * the seed value to use */ public void reSeedSecure(long seed) { if (secRand == null) { secRand = new SecureRandom(); } secRand.setSeed(seed); } /** * Reseeds the random number generator with the current time in * milliseconds. */ public void reSeed() { if (rand == null) { rand = new JDKRandomGenerator(); } rand.setSeed(System.currentTimeMillis()); } /** * Sets the PRNG algorithm for the underlying SecureRandom instance using * the Security Provider API. The Security Provider API is defined in * Java Cryptography Architecture API Specification & Reference. ** USAGE NOTE: This method carries significant * overhead and may take several seconds to execute. *
* * @param algorithm * the name of the PRNG algorithm * @param provider * the name of the provider * @throws NoSuchAlgorithmException * if the specified algorithm is not available * @throws NoSuchProviderException * if the specified provider is not installed */ public void setSecureAlgorithm(String algorithm, String provider) throws NoSuchAlgorithmException, NoSuchProviderException { secRand = SecureRandom.getInstance(algorithm, provider); } /** * Generates an integer array of lengthk
whose entries are
* selected randomly, without repetition, from the integers
* 0 through n-1
(inclusive).
*
* Generated arrays represent permutations of n
taken
* k
at a time.
*
* Preconditions: *
k <= n
n > 0
* Uses a 2-cycle permutation shuffle. The shuffling process is described * here. *
* * @param n * domain of the permutation (must be positive) * @param k * size of the permutation (must satisfy 0 < k <= n). * @return the random permutation as an int array * @throws NumberIsTooLargeException if {@code k > n}. * @throws NotStrictlyPositiveException if {@code k <= 0}. */ public int[] nextPermutation(int n, int k) { if (k > n) { throw new NumberIsTooLargeException(LocalizedFormats.PERMUTATION_EXCEEDS_N, k, n, true); } if (k == 0) { throw new NotStrictlyPositiveException(LocalizedFormats.PERMUTATION_SIZE, k); } int[] index = getNatural(n); shuffle(index, n - k); int[] result = new int[k]; for (int i = 0; i < k; i++) { result[i] = index[n - i - 1]; } return result; } /** * Uses a 2-cycle permutation shuffle to generate a random permutation. * Algorithm Description: Uses a 2-cycle permutation * shuffle to generate a random permutation ofc.size()
and
* then returns the elements whose indexes correspond to the elements of the
* generated permutation. This technique is described, and proven to
* generate random samples,
* here
*
* @param c
* Collection to sample from.
* @param k
* sample size.
* @return the random sample.
* @throws NumberIsTooLargeException if {@code k > c.size()}.
* @throws NotStrictlyPositiveException if {@code k <= 0}.
*/
public Object[] nextSample(Collection> c, int k) {
int len = c.size();
if (k > len) {
throw new NumberIsTooLargeException(LocalizedFormats.SAMPLE_SIZE_EXCEEDS_COLLECTION_SIZE,
k, len, true);
}
if (k <= 0) {
throw new NotStrictlyPositiveException(LocalizedFormats.NUMBER_OF_SAMPLES, k);
}
Object[] objects = c.toArray();
int[] index = nextPermutation(len, k);
Object[] result = new Object[k];
for (int i = 0; i < k; i++) {
result[i] = objects[index[i]];
}
return result;
}
/**
* Generate a random deviate from the given distribution using the
* inversion method.
*
* @param distribution Continuous distribution to generate a random value from
* @return a random value sampled from the given distribution
* @throws MathException if an error occurs computing the inverse cumulative distribution function
* @since 2.2
*/
public double nextInversionDeviate(ContinuousDistribution distribution) throws MathException {
return distribution.inverseCumulativeProbability(nextUniform(0, 1));
}
/**
* Generate a random deviate from the given distribution using the
* inversion method.
*
* @param distribution Integer distribution to generate a random value from
* @return a random value sampled from the given distribution
* @throws MathException if an error occurs computing the inverse cumulative distribution function
* @since 2.2
*/
public int nextInversionDeviate(IntegerDistribution distribution) throws MathException {
final double target = nextUniform(0, 1);
final int glb = distribution.inverseCumulativeProbability(target);
if (distribution.cumulativeProbability(glb) == 1.0d) { // No mass above
return glb;
} else {
return glb + 1;
}
}
// ------------------------Private methods----------------------------------
/**
* Uses a 2-cycle permutation shuffle to randomly re-order the last elements
* of list.
*
* @param list
* list to be shuffled
* @param end
* element past which shuffling begins
*/
private void shuffle(int[] list, int end) {
int target = 0;
for (int i = list.length - 1; i >= end; i--) {
if (i == 0) {
target = 0;
} else {
target = nextInt(0, i);
}
int temp = list[target];
list[target] = list[i];
list[i] = temp;
}
}
/**
* Returns an array representing n.
*
* @param n
* the natural number to represent
* @return array with entries = elements of n
*/
private int[] getNatural(int n) {
int[] natural = new int[n];
for (int i = 0; i < n; i++) {
natural[i] = i;
}
return natural;
}
}