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 Re: [rng] Utility for creating permutations of hex digits
Date Thu, 09 May 2019 12:30:06 GMT


> On 9 May 2019, at 12:58, Gilles Sadowski <gilleseran@gmail.com> wrote:
> 
> Hi.
> 
> Le jeu. 9 mai 2019 à 13:31, Alex Herbert <alex.d.herbert@gmail.com <mailto:alex.d.herbert@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-unsubscribe@commons.apache.org <mailto:dev-unsubscribe@commons.apache.org>
> For additional commands, e-mail: dev-help@commons.apache.org <mailto:dev-help@commons.apache.org>

Mime
  • Unnamed multipart/alternative (inline, None, 0 bytes)
View raw message