commons-issues mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Alex D Herbert (JIRA)" <j...@apache.org>
Subject [jira] [Commented] (RNG-85) Middle Square Weyl Sequence generator
Date Wed, 10 Apr 2019 16:20:00 GMT

    [ https://issues.apache.org/jira/browse/RNG-85?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16814611#comment-16814611
] 

Alex D Herbert commented on RNG-85:
-----------------------------------

I've put together an implementation of this generator without using the original code to do
the seeding.

To check it against a reference implementation I currently have the RNG constructor accept
a single {{long}}. This is used to create the increment for the Weyl sequence. The only condition
for this input is that is an odd number. However it helps if this increment has good randomness
in the bits (more on this later). So the input seed is checked for complexity using a method
similar to {{SplittableRandom}} (which is also based on a Weyl sequence). The check counts
the number of transitions in the seed from 0 to 1 or vice versa.
{code:java}
  static int countTransitions(long value) {
    // Sign-extending shift properly counts bits at the ends
    return Long.bitCount(value ^ (value >> 1));
  }
{code}
If it passes a critical value then the value goes through untouched. So it can be seeded using
any of the example seeds in the original paper or source code which have good complexity.

If the seed is low complexity then the complexity is boosted by {{xor}} ing the seed with
an alternating bit mask {{0xaaaaaaaa}} for the upper and lower 32-bits separately. The SplittableRandom
defines complexity as less than 24 transitions in the 64-bit seed. I have modelled the possible
transitions as a Binomial distribution (BD) with n the number of changes and p set to 0.5.
Dividing the seed into upper and lower bits this is then modelled using a BD(n=31,p=0.5).
This has a mean of np which is 15.5. The cumulative probabilty is readily computed. The cut-off
of 24 used in the SplittableRandom corresponds to approximately 1.6% of possible values. (Note:
This value is computed empirically from a distribution of random numbers as the SplittableRandom
uses an unsigned bit shift when computing transitions leading to overcounting by approximately
0.5. As such it cannot be modelled using a binomial distribution.) I have set the threshold
as 0.5% of possible values in the upper and lower 32-bit separately. This requires at least
9 transitions. The result is approximately 1% of seeds are not good enough and must be adjusted.

This allows it to pass the tests in Core and Simple modules and a quick run using 8 trials
passes SmallCrush with no failures. So this seeding approach is working.

JMH results verses SplitMix:
||randomSourceName||Method||Score||Error||Median||Error/Score||
|BASELINE|nextDouble|2.657|0.339|2.587|0.128|
|MSWS|nextDouble|5.312|0.006|5.311|0.001|
|SPLIT_MIX_64|nextDouble|4.539|0.013|4.537|0.003|
| |baselineDouble|2.349|0.305|2.287|0.130|
| |baselineVoid|0.269|0.006|0.267|0.022|
|BASELINE|nextInt|2.363|0.002|2.363|0.001|
|MSWS|nextInt|3.209|0.003|3.208|0.001|
|SPLIT_MIX_64|nextInt|3.581|0.044|3.572|0.012|
| |baselineInt|2.045|0.007|2.043|0.003|
| |baselineVoid|0.266|0.000|0.266|0.000|

Note using these results you can subtract the baseline from each score since it measures the
overhead within JMH for testing methods that produce a primitive value.

So not as fast for double generation but much faster for int generation.

Regarding the seeding.

The MSWS paper states that:
{noformat}
"The constant s should be an irregular bit pattern with roughly half of the
bits set to one and half of the bits set to zero. The best statistics have been
obtained with this type of pattern. Unduly sparse or dense values do not
produce good results."
{noformat}
So we could just seed the generator using any random number, as long as the number of bit
transitions is not too low. Defining the level for low is vague and currently the low value
is set at about 1% of all possible random numbers.

The paper suggests seeding using random hexadecimal digits:
{noformat}
"The digits are chosen so that the upper 8 are different and the lower 8 are
different and then 1 is ored into the result to make the constant odd."
{noformat}
The example source code provides a method to do this. The source code is GPL3 so cannot be
copied unless we get permission. But the method is described in the paper so could be re-implemented.
The seeding method uses an internal random generator to create the seed for the Weyl sequence.
So seeding is slow relative to just checking for complexity in the provided seed and boosting
it if necessary.

Note that the original code provides a set of 25000 example seeds using their method. This
can be analysed for bit transitions.

The histogram looks like this:
{noformat}
Transitions  Count
19           2
20           0
21           18
22           0
23           129
24           0
25           632
26           0
27           1918
28           0
29           4083
30           0
31           5812
32           0
33           5770
34           0
35           3971
36           0
37           1951
38           0
39           573
40           0
41           113
42           0
43           25
44           0
45           3
{noformat}
Note that the method creates no seeds with an odd number of state transitions and no seeds
with less than 19 transitions. So using a cut-off for upper and lower 32-bits of 9 transitions
is roughly equivalent.

Since the seeding routine ensures all 8 hex digits in the upper and lower 32-bits are unique
the output seed will be assured of altering each 4 bit section of the Weyl sequence with each
iteration (with the exception of the use of the 0x0 hex digit).

The author's have also verified that their seeding routine is suitable for parallel computation
as the first 3 billion input values starting from 0 produce unique seeds.

Ideally I would like to avoid a complex seeding routine inside the core generator implementation.
Using the simple method of boosting the number of bit transitions is working.

If the generator is to be used for parallel computations then a user can create n generators
and just check that each input seed is unique. They can even be referred to the original paper
to produce seeds using that code. Currently my routine would modify 30 of those 25000 example
seeds (0.12%). The lowest transition count found in the 32-bits is 6 which happens because
the final bit is forced to 1 (note the double 0xf at the end).
{noformat}
0xc  0x3  0x8  0x0  0x6  0x7  0xf  0xf
1100 0011 1000 0000 0110 0111 1111 1111
{noformat}
To avoid the modified input seed creating an non unique generator the unmodified seed can
be used to set the initial state of the generator. Thus all possible random seeds should create
a unique generator, although the sequences may overlap if the input seed has been modified.

Since we do not currently support construction of parallel generators that do not overlap
via the factory method in {{RandomSource.create}} I do not think it a priority to exactly
implement the original source seeding routine.

 

> Middle Square Weyl Sequence generator
> -------------------------------------
>
>                 Key: RNG-85
>                 URL: https://issues.apache.org/jira/browse/RNG-85
>             Project: Commons RNG
>          Issue Type: Sub-task
>          Components: core
>            Reporter: Gilles
>            Priority: Minor
>              Labels: gsoc2019
>
> https://en.wikipedia.org/wiki/Middle_square_method#Middle_Square_Weyl_Sequence_PRNG



--
This message was sent by Atlassian JIRA
(v7.6.3#76005)

Mime
View raw message