On 09/05/2019 15:46, Gilles Sadowski wrote:
Le jeu. 9 mai 2019 à 14:30, Alex Herbert <alex.d.herb...@gmail.com> a écrit :
On 9 May 2019, at 12:58, Gilles Sadowski <gillese...@gmail.com> wrote:
Hi.
Le jeu. 9 mai 2019 à 13:31, Alex Herbert <alex.d.herb...@gmail.com
<mailto:alex.d.herb...@gmail.com>> a écrit :
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
- In "SeedFactory" (?).
For MSWS ("core" module), the increment would be an argument to the constructor
(allowing the user to shoot himself in the foot, like when passing a
bad seed), and
"RandomSource" ("simple" module) would offer to provide an instance
for which the
increment was computed according to the recommendation.
OK. That makes it easier to build the reference implementation in Core as it
just matches the C reference code. I can add the seeding function to
SeedFactory in the Simple module. So if a user passes anything to be used as
the seed then it passes through unchanged (or converted). But if they do not
provide a seed then it should be generated appropriately.
This means I should really get on with updating the RandomSourceInternal and
ProviderBuilder (RNG 75 [1]). It currently does not support creating seeds
based on the exact RandomSource. It just uses the native seed type of the
RandomSource. Here are the current use cases that should be handled:
- MSWS recommends a seed with a permutation of hex digits.
- XorShiRo family of generators all require seeds with at least some non-zero
elements.
My idea was to target this part of the ProviderBuilder createSeed method:
if (seed == null) {
// Create a random seed of the appropriate native type.
if (source.getSeed().equals(Integer.class)) {
nativeSeed = SeedFactory.createInt();
} else if (source.getSeed().equals(Long.class)) {
nativeSeed = SeedFactory.createLong();
To change it to:
if (seed == null) {
// Delegate to the source to create an appropriate seed (since it knows
best)
return source.createSeed()
But IIUC, that would mean that the code for computing the seed
is in "core", not "simple" (where "SeedFactory" is defined).
Sorry, my code snippet was not fully qualified. This is from
org.apache.commons.rng.simple.internal.ProviderBuilder.createSeed
This is the place where a seed is currently made so your point is
satisfied.
The current process for the seed creation is a bit limited. It just
builds int, long, int[], or long[]. It is not currently able to build
arrays of the correct length or build seeds with specific requirements
based on the source. That is what I would like to change. So if the
source was a MSWS then it would build the seed using the hex digit
permutation method. If the source was a XorShiRo family it would build
seeds with no zeros.
My idea was to move the null seed creation pathway into
RandomSourceInternal. So if the RandomSource has specific needs for the
seed then the internal enum can override the default method to create
the seed.
My point was that, even though the designer of the algorithm indeed
"knows best", the user should be allowed to pass any seed/increment
(even if it is "not recommended").
The "simple" API's role is to provide recommended values as defaults.
Gilles
The RandomSourceInternal which already has knowledge of the native type of the
seed for the generator will be extended to know the length for array seeds, and
a default implementation of create for each native seed type allowing override
for generators with specific requirements.
[1] https://issues.apache.org/jira/browse/RNG-75
<https://issues.apache.org/jira/browse/RNG-75>
Regards,
Gilles
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>
<https://en.wikipedia.org/wiki/Weyl_sequence
<https://en.wikipedia.org/wiki/Weyl_sequence>>
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
<mailto:dev-unsubscr...@commons.apache.org>
For additional commands, e-mail: dev-h...@commons.apache.org
<mailto:dev-h...@commons.apache.org>
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
For additional commands, e-mail: dev-h...@commons.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
For additional commands, e-mail: dev-h...@commons.apache.org
