Le jeu. 9 mai 2019 à 17:07, Alex Herbert <alex.d.herb...@gmail.com> a écrit : > > > 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.
All fine then. :-) > 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. +1 Gilles > > > 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 For additional commands, e-mail: dev-h...@commons.apache.org
