random_seeding.adoc

Random seeding

The PRNGs, used by the PRNGine library, needs to be initialized with a proper seed value before they can be used. The usual way for doing this, is to take the current time stamp.

public static long seed() {
    return System.nanoTime();
}

Before applying this method throughout the whole library, I decided to perform some statistical tests. For this purpose I treated the seed() method itself as PRNG and analyzed the created long values with the DieHarder class. The seed() method has been wrapped into the NanoTimeRandom class. Assuming that the dieharder tool is in the search path, calling

$ java -cp prngine-<version>.jar \
      io.jenetics.prngine.internal.DieHarder \
      NanoTimeRandom -a

will perform the statistical tests for the nano time random engine. The statistical quality is rather bad: every single test failed. Table Nano time seeding quality shows the summary of the dieharder report.

Table 1. Nano time seeding quality

Passed tests	Weak tests	Failed tests
0	0	114

An alternative source of entropy, for generating seed values, would be the /dev/random or /dev/urandom file. But this approach is not portable, which was a prerequisite for the library.

The next attempt tries to fetch the seeds from the JVM, via the Object.hashCode() method. Since the hash code of an Object is available for every operating system and most likely "randomly" distributed.

static long seed() {
    final long a = new Object().hashCode();
    final long b = new Object().hashCode();
    return mixStafford13(a << 32 | b);
}
private static long mixStafford13(final long z) {
    long v = (z^(z >>> 30))*0xbf58476d1ce4e5b9L;
    v = (v^(v >>> 27))*0x94d049bb133111ebL;
    return v^(v >>> 31);
}

This seed method has been wrapped into the ObjectHashRandom class and tested as well with

$ java -cp prngine-<version>.jar \
      io.jenetics.prngine.internal.DieHarder \
      ObjectHashRandom -a

Table Object hash seeding quality shows the summary of the dieharder report, which looks better than the nano time seeding, but 86 failing tests was still not very satisfying.

Table 2. Object hash seeding quality

Passed tests	Weak tests	Failed tests
28	0	86

After additional experimentation, a combination of the nano time seed and the object hash seeding seems to be the "right" solution. The rational behind this was, that the PRNG seed shouldn’t rely on a single source of entropy.

public static long seed() {
    final long a = mixStafford13(System.currentTimeMillis());
    final long b = mixStafford13(System.nanoTime());
    return seed(mix(a, b));
}
private static long seed(final long base) {
    return mix(base, ObjectSeedSource.seed());
}
private static long mix(final long a, final long b) {
    long c = a^b;
    c ^= c << 17;
    c ^= c >>> 31;
    c ^= c << 8;
    return c;
}
static long objectSeed() {
    final long a = new Object().hashCode();
    final long b = new Object().hashCode();
    return mixStafford13(a << 32 | b);
}
private static long mixStafford13(final long z) {
    long v = (z^(z >>> 30))*0xbf58476d1ce4e5b9L;
    v = (v^(v >>> 27))*0x94d049bb133111ebL;
    return v^(v >>> 31);
}

The code above shows how the nano time seed is mixed with the object seed. Running the tests with

$ java -cp prngine-<version>.jar \
      io.jenetics.prngine.internal.DieHarder \
      SeedRandom -a

leads to the statistics following summary

Table 3. Combined random seeding quality

Passed tests	Weak tests	Failed tests
112	2	0

The statistical performance of this seeding is better, according to the dieharder test suite, than some of the real random engines, including the default Java Random engine. Using the proposed seed() method is in any case preferable to the simple System.nanoTime() call.