Random Data Generation

Overview

The Hipparchus random package includes utilities for

• generating random numbers
• generating random vectors
• generating random strings
• generating random samples and permutations
• analyzing distributions of values in an input file and generating values “like” the values in the file
• generating data for grouped frequency distributions or histograms

The source of random data used by the data generation utilities is pluggable. In most cases, the default is a Well generator. Whenever a default is provided, the javadoc indicates what the default is. Other good PRNGs suitable for Monte-Carlo analysis (but not for cryptography) provided by the library in the raondom.

Sections 2.2-2.6 below show how to use the Hipparchus API to generate different kinds of random data. The examples all use the default JDK-supplied PRNG. PRNG pluggability is covered in 2.7. The only modification required to the examples to use alternative PRNGs is to replace the argumentless constructor calls with invocations including a RandomGenerator instance as a parameter.

Random numbers

The RandomDataGenerator class implements methods for generating random sequences of numbers. The API contracts of these methods use the following concepts:

RandomDataGenerator randomDataGenerator = new RandomDataGenerator(1000)
randomDataGenerator.nextNormal(3,1.5)

RandomDataGenerator randomData = new RandomDataGenerator(); 
for (int i = 0; i < 1000; i++) {
    value = randomData.nextLong(1, 1000000);
}

for (int i = 0; i < 1000; i++) {
    RandomDataGenerator randomData = new RandomDataGenerator(); 
    value = randomData.nextLong(1, 1000000);
}

RandomDataGenerator randomData = new RandomDataGenerator(1000); 
for (int i = 0; i = 1000; i++) {
    value = randomData.nextLong(1, 1000000);
}

Random Vectors

Some algorithms require random vectors instead of random scalars. When the components of these vectors are uncorrelated, they may be generated simply one at a time and packed together in the vector. The UncorrelatedRandomVectorGenerator class simplifies this process by setting the mean and deviation of each component once and generating complete vectors. When the components are correlated however, generating them is much more difficult. The CorrelatedRandomVectorGenerator class provides this service. In this case, the user must set up a complete covariance matrix instead of a simple standard deviations vector. This matrix gathers both the variance and the correlation information of the probability law.

The main use for correlated random vector generation is for Monte-Carlo simulation of physical problems with several variables, for example to generate error vectors to be added to a nominal vector. A particularly common case is when the generated vector should be drawn from a Multivariate Normal Distribution.

// Create and seed a RandomGenerator (could use any of the generators in the random package here)
RandomGenerator rg = new JDKRandomGenerator();
rg.setSeed(17399225432l);  // Fixed seed means same results every time

// Create a GassianRandomGenerator using rg as its source of randomness
GaussianRandomGenerator rawGenerator = new GaussianRandomGenerator(rg);

// Create a CorrelatedRandomVectorGenerator using rawGenerator for the components
CorrelatedRandomVectorGenerator generator = 
    new CorrelatedRandomVectorGenerator(mean, covariance,
                                        1.0e-12 * covariance.getNorm(),
                                        rawGenerator);

// Use the generator to generate correlated vectors
double[] randomVector = generator.nextVector();
... 

double[] mean = {1, 2};
double[][] cov = {{9, c}, {c, 16}};
RealMatrix covariance = MatrixUtils.createRealMatrix(cov);

Random Strings

The method nextHexString can be used to generate random strings of hexadecimal characters. It produces sequences of strings with good dispersion properties. The implementation of nextHexString(n) in RandomDataGenerator uses the following simple algorithm to generate a string of n hex digits:

• n/2+1 binary bytes are generated using the underlying RandomGenerator
• Each binary byte is translated into 2 hex digits

Random permutations, combinations, sampling

To select a random sample of objects in a collection, you can use the nextSample method implemented by RandomDataGenerator. Specifically, if c is a collection containing at least k objects, and randomData is a RandomDataGenerator instance randomData.nextSample(c, k) will return an object[] array of length k consisting of elements randomly selected from the collection. If c contains duplicate references, there may be duplicate references in the returned array; otherwise returned elements will be unique – i.e., the sampling is without replacement among the object references in the collection.

If randomData is a RandomDataGenerator instance, and n and k are integers with k <= n, then randomData.nextPermutation(n, k) returns an int[] array of length k whose whose entries are selected randomly, without repetition, from the integers 0 through n-1 (inclusive), i.e., randomData.nextPermutation(n, k) returns a random permutation of n taken k at a time.

Generating data ‘like’ an input file

Using the ValueServer class, you can generate data based on the values in an input file in one of two ways:

      ValueServer vs = new ValueServer();
      vs.setValuesFileURL(url); 
      vs.setMode(ValueServer.REPLAY_MODE);
      vs.resetReplayFile();
      double value = vs.getNext();
      // ...Generate and use more values...
      vs.closeReplayFile();

      ValueServer vs = new ValueServer();
      vs.setValuesFileURL(url); 
      vs.setMode(ValueServer.DIGEST_MODE);
      vs.computeDistribution(500); //Read file and estimate distribution using 500 bins
      double value = vs.getNext();
      // ...Generate and use more values...

PRNG Pluggability

To enable alternative PRNGs to be “plugged in” to the Hipparchus data generation utilities and to provide a generic means to replace java.util.Random in applications, a random generator adaptor framework has been added to Hipparchus. The RandomGenerator interface abstracts the public interface of java.util.Random and any implementation of this interface can be used as the source of random data for the Hipparchus data generation classes. An abstract base class, AbstractRandomGenerator is provided to make implementation easier. This class provides default implementations of “derived” data generation methods based on the primitive, nextDouble(). To support generic replacement of java.util.Random, the RandomAdaptor class is provided, which extends java.util.Random and wraps and delegates calls to a RandomGenerator instance.

Hipparchus provides by itself several implementations of the RandomGenerator interface:

• generating random numbers
• generating random vectors
• generating random strings
• generating random samples and permutations
• analyzing distributions of values in an input file and generating values “like” the values in the file
• generating data for grouped frequency distributions or histograms

The JDK provided generator is a simple one that can be used only for very simple needs. The Mersenne Twister is a fast generator with very good properties well suited for Monte-Carlo simulation. It is equidistributed for generating vectors up to dimension 623 and has a huge period: 2¹⁹⁹³⁷ - 1 (which is a Mersenne prime). This generator is described in a paper by Makoto Matsumoto and Takuji Nishimura in 1998: Mersenne Twister: A 623-Dimensionally Equidistributed Uniform Pseudo-Random Number Generator, ACM Transactions on Modeling and Computer Simulation, Vol. 8, No. 1, January 1998, pp 3–30. The WELL generators are a family of generators with period ranging from 2⁵¹² - 1 to 2⁴⁴⁴⁹⁷ - 1 (this last one is also a Mersenne prime) with even better properties than Mersenne Twister. These generators are described in a paper by François Panneton, Pierre L'Ecuyer and Makoto Matsumoto Improved Long-Period Generators Based on Linear Recurrences Modulo 2 ACM Transactions on Mathematical Software, 32, 1 (2006). The errata for the paper are in wellrng-errata.txt.

For simple sampling, any of these generators is sufficient. For Monte-Carlo simulations the JDK generator does not have any of the good mathematical properties of the other generators, so it should be avoided. The Mersenne twister and WELL generators have equidistribution properties proven according to their bits pool size which is directly linked to their period (all of them have maximal period, i.e. a generator with size n pool has a period 2ⁿ-1). They also have equidistribution properties for 32 bits blocks up to s/32 dimension where s is their pool size. So WELL19937c for exemple is equidistributed up to dimension 623 (19937/32). This means a Monte-Carlo simulation generating a vector of n variables at each iteration has some guarantees on the properties of the vector as long as its dimension does not exceed the limit. However, since we use bits from two successive 32 bits generated integers to create one double, this limit is smaller when the variables are of type double. so for Monte-Carlo simulation where less the 16 doubles are generated at each round, WELL1024 may be sufficient. If a larger number of doubles are needed a generator with a larger pool would be useful.

The WELL generators are more modern then MersenneTwister (the paper describing than has been published in 2006 instead of 1998) and fix some of its (few) drawbacks. If initialization array contains many zero bits, MersenneTwister may take a very long time (several hundreds of thousands of iterations to reach a steady state with a balanced number of zero and one in its bits pool). So the WELL generators are better to escape zeroland as explained by the WELL generators creators. The Well19937a and Well44497a generator are not maximally equidistributed (i.e. there are some dimensions or bits blocks size for which they are not equidistributed). The Well512a, Well1024a, Well19937c and Well44497b are maximally equidistributed for blocks size up to 32 bits (they should behave correctly also for double based on more than 32 bits blocks, but equidistribution is not proven at these blocks sizes).

The MersenneTwister generator uses a 624 elements integer array, so it consumes less than 2.5 kilobytes. The WELL generators use 6 integer arrays with a size equal to the pool size, so for example the WELL44497b generator uses about 33 kilobytes. This may be important if a very large number of generator instances were used at the same time.

All generators are quite fast. As an example, here are some comparisons, obtained on a 64 bits JVM on a linux computer with a 2008 processor (AMD phenom Quad 9550 at 2.2 GHz). The generation rate for MersenneTwister was between 25 and 27 millions doubles per second (remember we generate two 32 bits integers for each double). Generation rates for other PRNG, relative to MersenneTwister:

So for most simulation problems, the better generators like Well19937c and Well44497b are probably very good choices.

Note that none of these generators are suitable for cryptography. They are devoted to simulation, and to generate very long series with strong properties on the series as a whole (equidistribution, no correlation …). They do not attempt to create small series but with very strong properties of unpredictability as needed in cryptography.

Examples:

import edu.cornell.lassp.houle.RngPack.RanMT;

/**
 * AbstractRandomGenerator based on RngPack RanMT generator.
 */
public class RngPackGenerator extends AbstractRandomGenerator {
    
    private RanMT random = new RanMT();
    
    public void setSeed(long seed) {
       random = new RanMT(seed);
    }
    
    public double nextDouble() {
        return random.raw();
    }
    
    public double nextGaussian() {
        return random.gaussian();
    }
    
    public int nextInt(int n) {
        return random.choose(n);
    }
    
    public boolean nextBoolean() {
        return random.coin();
    }
}

RandomData randomData = new RandomDataImpl(new RngPackGenerator());

 RandomGenerator generator = new RngPackGenerator();
 Random random = RandomAdaptor.createAdaptor(generator);
 // random can now be used in place of a Random instance, data generation
 // calls will be delegated to the wrapped Mersenne Twister