> 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()
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>
