[rng] Change default seeding in MiddleSquareWeylSequence

classic Classic list List threaded Threaded
1 message Options
Reply | Threaded
Open this post in threaded view
|

[rng] Change default seeding in MiddleSquareWeylSequence

Alex Herbert
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: [hidden email]
For additional commands, e-mail: [hidden email]