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