commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Alex Herbert <alex.d.herb...@gmail.com>
Subject [rng] Change default seeding in MiddleSquareWeylSequence
Date Sat, 14 Sep 2019 20:50:50 GMT
I’ve been looking into fixing some of the sonar issues. One highlighted a test of the MiddleSquareWeylSequence
which just executes a code path but has no assertions. This is for the default seeding (i.e.
a seed less than the correct seed length). Currently the generator uses the same method as
all the others for array seeds. It fills it with random numbers using the fillState method:

public MiddleSquareWeylSequence(long[] seed) {
    if (seed.length < SEED_SIZE) {
        final long[] tmp = new long[SEED_SIZE];
        fillState(tmp, seed);
        setSeedInternal(tmp);
    } else {
        setSeedInternal(seed);
    }
}

When I added an assertion it shows that a zero length seed requires over 2^29 cycles to produce
non zero long output. This is 2^58 int outputs, which is the primary output of the generator.

This is because the default seeding fillState method results in a low complexity increment
for the Weyl sequence. The full seed is actually [0, 0, 2] and the increment ends up as 3
(as it is forced to be odd). This has only 2 bits set in the 64 bit increment and a single
0 to 1 transition of the bit state. FYI increments used in the Weyl sequence in SplittableRandom
recommend at least 24 bit state transitions in the 64 bit increment.

I suggest changing the constructor to use a default seed that contains a good Weyl increment.
This seed is overwritten with the input seed values if present. Something like this:

public MiddleSquareWeylSequence(long[] seed) {
    if (seed.length < SEED_SIZE) {
        // Default high quality seed
        final long[] tmp = {0x012de1babb3c4104L, 0xc8161b4202294965L, 0xb5ad4eceda1ce2a9L};
        for (int i = 0; i < seed.length; i++) {
            tmp[i] = seed[i];
        }
        setSeedInternal(tmp);
    } else {
        setSeedInternal(seed);
    }
}

This ensures that the generator cannot be created with a bad Weyl increment unless it is explicitly
passed in via the seed as the increment is the final position in the input seed array.

Note that this generator requires special seeding in commons-rng-simple module that creates
generators. It would seem appropriate to make a better effort to avoid a bad generator in
the core component too.

Alex


---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org


Mime
View raw message