The Middle Square Weyl Sequence (MSWS) generator uses an internal Weyl sequence
[1] to create randomness. This is basically a linear increment added to a sum
that will eventually wrap (due to overflow) to restart at the beginning. The
MSWS paper recommends an increment with a high number of different bits set in
a random pattern across the 64-bit of the long. The paper recommends using a
permutation of 8 from the 16 hex digits for the upper and lower 32-bits.
The source code for the MSWS provides a routine that generates a permutation.
Unfortunately:
- The code is GPL 3 so restricting it from use under the Apache licence
(without jumping through some hoops)
- The algorithm is a simple rejection method that suffers from high rejection
probability when approaching 8 digits already chosen
I have created an alternative faster implementation for use when seeding the
MSWS generator. However it may be a function to be reused in other places.
The question is where to put this utility function. It requires a source of
randomness to create the permutation. It has the following signature:
/**
* Creates an {@code int} containing a permutation of 8 hex digits chosen from
16.
*
* @param rng Source of randomness.
* @return Hex digit permutation.
*/
public static int createIntHexPermutation(UniformRandomProvider rng);
Likewise:
/**
* Creates a {@code long} containing a permutation of 8 hex digits chosen from
16 in
* the upper and lower 32-bits.
*
* @param rng Source of randomness.
* @return Hex digit permutation.
*/
public static long createLongHexPermutation(UniformRandomProvider rng);
Options:
- Put it as a package private function inside the MSWS generator to be used
only when creating this generator. Package private allows unit testing the
algorithm does provides the random permutation 16-choose-8
- Put it as a helper function in org.apache.commons.rng.core.util
Note that the function is an alternative to that used by the SplittableRandom
to create an increment for its own Weyl sequence. That uses a fast method that
is prone to weak randomness in potential output.
If other methods will potentially be added to the helper class a more generic
name should be used. Possibilities are:
PermutationUtils
SequenceUtils
IncrementUtils
SeedUtils
Given that the method is for seeding Weyl sequences then I am favouring
SeedUtils.
[1] https://en.wikipedia.org/wiki/Weyl_sequence
<https://en.wikipedia.org/wiki/Weyl_sequence>
