Hello Alex.
Le mer. 13 mars 2019 à 15:37, Alex Herbert <alex.d.herbert@gmail.com> a écrit :
>
> On 13/03/2019 02:20, Gilles Sadowski wrote:
> > Le mar. 12 mars 2019 à 22:34, Alex Herbert <alex.d.herbert@gmail.com> a écrit
:
> >>
> >>
> >>> On 12 Mar 2019, at 17:12, Gilles Sadowski <gilleseran@gmail.com> wrote:
> >>>
> >>> [Replying to list.]
> >>>
> >>> Le mar. 12 mars 2019 à 15:39, Alex Herbert <alex.d.herbert@gmail.com
<mailto:alex.d.herbert@gmail.com>> a écrit :
> >>>>
> >>>> On 12/03/2019 15:33, Gilles Sadowski wrote:
> >>>>
> >>>> Hi Alex.
> >>>>
> >>>> Le mar. 12 mars 2019 à 12:53, Alex Herbert <alex.d.herbert@gmail.com>
a écrit :
> >>>>
> >>>> On 11/03/2019 23:44, Gilles Sadowski wrote:
> >>>>
> >>>> Hello.
> >>>>
> >>>> Le jeu. 7 mars 2019 à 00:44, Alex Herbert <alex.d.herbert@gmail.com>
a écrit :
> >>>>
> >>>> On 6 Mar 2019, at 22:57, Gilles Sadowski <gilleseran@gmail.com>
wrote:
> >>>>
> >>>> However I will test if XorShift1024Star and XorShift1024StarPhi are
correlated just for completeness.
> >>>>
> >>>> Did a test of 100 repeats of a correlation of 50 longs from the XorShift1024Star
and XorShift1024StarPhi, new seed each time:
> >>>>
> >>>> SummaryStatistics:
> >>>> n: 100
> >>>> min: 0.30893547071559685
> >>>> max: 0.37616626218398586
> >>>> sum: 3.300079237520435
> >>>> mean: 0.033000792375204355
> >>>> geometric mean: NaN
> >>>> variance: 0.022258533475114764
> >>>> population variance: 0.022035948140363616
> >>>> second moment: 2.2035948140363617
> >>>> sum of squares: 2.312500043775496
> >>>> standard deviation: 0.14919294043323486
> >>>> sum of logs: NaN
> >>>>
> >>>> Note that the algorithm is the same except the final step when the multiplier
is used to scale the final output long:
> >>>>
> >>>> return state[index] * multiplier;
> >>>>
> >>>> So if it was outputting a double the correlation would be 1. But it
is a long generator so the long arithmetic wraps to negative on large multiplications. The
result is that the mean correlation is close to 0.
> >>>>
> >>>> A single repeat using 1,000,000 numbers has a correlation of 0.002.
> >>>>
> >>>> Am I missing something here with this type of test?
> >>>>
> >>>> I'm afraid I don't follow: If the state is the same then I'd assume
that
> >>>> the two generators are the same (i.e. totally correlated).
> >>>>
> >>>> The state is totally correlated (it is identical). The output sequence
is not due to wrapping in long arithmetic. Here’s a mock example:
> >>>>
> >>>> positive number * medium positive number = big positive number (close
to Long.MAX_VALUE)
> >>>>
> >>>> Vs
> >>>>
> >>>> positive number * bigger positive number = negative number (due to wrapping)
> >>>>
> >>>> So by changing the multiplier this wrapping causes the output bits to
be different. This is why the new variant "eliminates linear dependencies from one of the
lowest bits” (quoted from the authors c code).
> >>>>
> >>>> The multiplier was changed from 1181783497276652981L to 0x9e3779b97f4a7c13L.
These numbers are big:
> >>>>
> >>>> Long.MAX_VALUE / 1181783497276652981L = 7.8046207770792755
> >>>> Long.MAX_VALUE / 0x9e3779b97f4a7c13L = 1.3090169943749475
> >>>>
> >>>> Big enough such that wrapping will occur on every multiplication unless
the positive number is <8, or now <2. So basically all the time.
> >>>>
> >>>> So, IIUC, the output is thus a truncated product formed by the wrapping
long arithmetic and not correlated.
> >>>>
> >>>> I wonder: Would that mean that any choice of a "big" number creates
a new RNG?
> >>>> IOW, if we create a composite one from such generators (i.e. pick one
> >>>> number from
> >>>> each in order to compose the composite source), will it be as good as
> >>>> any of them
> >>>> on the stress test suites?
> >>>>
> >>>> I don't know. These are the numbers that the authors have come up with
> >>>> after testing.
> >>>>
> >>>> Sure. The "TWO_CMRES" variants also results from the author's
> >>>> experiments.
> >>>> Some numbers make "good" generators, others not; but that still
> >>>> does not say whether any two RNGs from the same family are
> >>>> correlated. In the case of "TWO_CMRES", the states differ by the
> >>>> choice of *2* numbers, whereas here we change only one.
> >>>> So the question is whether it is sufficient.
> >>>>
> >>>> Perhaps other large numbers are worse.
> >>>>
> >>>> These numbers are not prime but they are odd:
> >>>>
> >>>> 1181783497276652981L % 769 == 0
> >>>>
> >>>> 0x9e3779b97f4a7c13L == 7046029254386353133
> >>>>
> >>>> 7046029254386353133 % 3 == 0
> >>>>
> >>>>
> >>>> In the code for SplittableRandom after a split the large value that
is
> >>>> used to add to the state to get the next state is created by a mixing
> >>>> operation on the current state. Then the bit count is checked to ensure
> >>>> enough transitions are present:
> >>>>
> >>>> /**
> >>>> * Returns the gamma value to use for a new split instance.
> >>>> */
> >>>> private static long mixGamma(long z) {
> >>>> z = (z ^ (z >>> 33)) * 0xff51afd7ed558ccdL; // MurmurHash3
mix
> >>>> constants
> >>>> z = (z ^ (z >>> 33)) * 0xc4ceb9fe1a85ec53L;
> >>>> z = (z ^ (z >>> 33))  1L; // force to
be odd
> >>>> int n = Long.bitCount(z ^ (z >>> 1)); // ensure
enough
> >>>> transitions
> >>>> return (n < 24) ? z ^ 0xaaaaaaaaaaaaaaaaL : z;
> >>>> }
> >>>>
> >>>>
> >>>> So the requirements for a big number may be that it is odd, close to
> >>>> Long.MAX_VALUE (such that Long.MAX_VALUE / number < 2), and has a
lot of
> >>>> transitions.
> >>>>
> >>>> What is a "transition"?
> >>>>
> >>>> A change in the bits from 1 to 0 or 0 to 1 as you move across the binary
representation.
> >>>>
> >>>> So for example this has 3 transitions:
> >>>>
> >>>> 0101
> >>>>
> >>>> I think the point is to avoid numbers that look like this in binary:
> >>>>
> >>>> 0000000011111111110000000001111111
> >>>>
> >>>> (still 3 transitions)
> >>>>
> >>>> Instead preferring a number that has lots of 0 to 1 flips. Here are
the numbers we are discussing using Long.toBinaryString(long):
> >>>>
> >>>> 1181783497276652981 0x1000001100110100010011101010001010100100101111111110110110101
= 35
> >>>> 7046029254386353131 0x1001111000110111011110011011100101111111010010100111110000010101
= 31
> >>>> 7046029254386353133 0x1001111000110111011110011011100101111111010010100111110000010011
= 29
> >>>>
> >>>> Transitions:
> >>>>
> >>>> 1181783497276652981 = 35
> >>>> 7046029254386353131 = 31
> >>>> 7046029254386353133 = 29
> >>>>
> >>>> Note: 7046029254386353131 is the 0x9e3779b97f4a7c15L factor used in
the
> >>>> SplitMix64 algorithm. This is a variant of the new Phi factor for the
> >>>> XorShift1024StarPhi algorithm and it has more transitions.
> >>>>
> >>>>
> >>>> Anyway the new code for the XorShift1024StarPhi algorithm is a variant
> >>>> of the original. The question is should we update the original or add
> >>>> the alternative?
> >>>>
> >>>> Modifying "XOR_SHIFT_1024_S" would breach the contract: the
> >>>> source will return a different sequence. This should be done only
> >>>> in a major version.
> >>>>
> >>>> We should certainly add the newer/better version (under a different
> >>>> "enum").
> >>>>
> >>>> My question was indeed whether we should deprecate the
> >>>> "XOR_SHIFT_1024_S" generator.
> >>>> Not because it is not good enough (judging from its score on
> >>>> the stress tests[1], it is still one of the best even if the new
> >>>> "XOR_SHIFT_1024_STAR_PHI" is supposedly better).
> >>>> The issue is whether we want "RandomSource" to only provide
> >>>> independent generators (so that e.g. that can be safely used in a
> >>>> multithreaded application  i.e. using a different implementation
> >>>> in each thread is sufficient to ensure uncorrelated output[2]).
> >>>>
> >>>> Does that make sense?
> >>>> If so, one way would be to make the experiment of creating a
> >>>> composite RNG (with the current and new variants) and pass it
> >>>> through the test suites.
> >>>>
> >>>> I don't think there is anything to composite. The code is exactly the
same except for a final multiplier:
> >>>>
> >>>> XorShift1024Star.java L109
> >>>>
> >>>> The method for producing the internal state is the same. So a composite
of internal states (ala TwoCmres) is not possible.
> >>>
> >>> What I mean by "composite" is a new RNG class (code untested):
> >>>
> >>> public class Composite implements RandomLongSource {
> >>> private final UniformRandomProvider rng[] = new UniformRandomProvider[2];
> >>> private int flip = 0;
> >>>
> >>> public Composite(long[] seed) {
> >>> rng[0] = new XorShiftStar1024Star(seed);
> >>> rng[1] = new XorShiftStar1024StarPhi(seed);
> >>> }
> >>>
> >>> public long nextLong() {
> >>> return rng[flip++ % 2].nextLong();
> >>> }
> >>> }
> >>>
> >>>
> >>>> So your concern is that a user may use a XOR_SHIFT_1024_S and XOR_SHIFT_1024_S_PHI
with possibly the same seed in different threads and experience correlated sequences producing
biased results?
> >>> Yes.
> >>>
> >>>> This possibility should be documented if it exists. But how to test
that?
> >>> By submitting the "Composite" to BigCrush.
> >>>
> >>>> Do you mean a bitwise xor of the output from each generator, then passed
through the test suites?
> >>> No just using the output of each alternatively (cf. above).
> >> OK. I’ll do that next.
> > Thanks.
> >
> >> I’ve just checked how the xor composite is progressing. It is not happy. 82
PASSED and 766 FAILED from 8 incomplete runs. It seems to be stuck in an infinite loop in
the rgb_kstest_test. The whole suite usually takes 100 minutes and they have all been running
just that test for 5 hours. Reading the summary info (dieharder d 204 h)I cannot tell what
is it about this test that has stalled.
> > Strange, but I have no idea about the internals of the test suites...
>
> Dieharder did eventually finish the first 8 runs. Perhaps the test took
> a long time to determine if it was a pass/fail since it was borderline.
> Anyway they all eventually failed that test.
>
>
> I tried the following:
>
> XorComposite: A composite of two rngs using the xor operation:
>
> return new IntProvider() {
> @Override
> public int next() {
> return rng1.nextInt() ^ rng2.nextInt();
> }
> };
>
> SerialComposite: A composite of two rngs using alternating output:
>
> return new IntProvider() {
> int flip;
> @Override
> public int next() {
> return ((flip++ & 1) == 0) ? rng1.nextInt() : rng2.nextInt();
> }
> };
>
>
> I ran:
>
> XorShiftXorComposite: XorComposite using XorShift1024Star +
> XorShift1024StarPhi with the same seed
>
> XorShiftSerialComposite: SerialComposite using XorShift1024Star +
> XorShift1024StarPhi with the same seed
>
> SplitXorComposite: XorComposite using XorShift1024Star + TwoCmres (this
> is a control)
>
>
> FAILURE counts for Dieharder:
>
> XorShiftXorComposite : 89, 105, 104, 104, 105, 106, 105, 104
> XorShiftSerialComposite : 27, 23, 22
> SplitXorComposite : 0, 0, 0
Thanks for doing the experiment.
>
> This shows that a combined generator using two different variants of
> XorShift1024 is not good. So the two XorShift1024 generators are
> correlated.
No miracle then. :}
> Evidence for deprecation.
Seems so.
Best,
Gilles
>
>
> BigCrush takes longer so I'll try that next. It may just be a whole load
> of failures. I'll add the results to the Jira ticket.
>
>
> >
> >> I’ll let it go until the morning and then kill it. I think this xor composite
generator is bad. I’ll check if it even works for two unrelated generators.
> >>
> >> I think the serial composite (chained together output) should be an IntProvider
instead given that the test suites use nextInt()? If you use a LongProvider then you will
get 2 ints from one then 2 from the other.
> > Yes, although that should not impact the ability of BigCrush to
> > provide a verdict.
> >
> >> Note that % 2 will break if it overflows to negative.
> > Right. What I intended was something like:
> >
> > public long nextLong() {
> > flip = (flip + 1) % 2;
> > return rng[flip].nextLong();
> > }
> >
> > Gilles
> >
> >> This works with negatives: [flip++ & 0x1]. I read somewhere that BigCrush
consumes about 2^32 ints so it would be far into the test before you found that one.
> >>
> >>
> >>>> IIUC if the bits are more similar than not then the xor will make them
zero more often than not. This should fail the tests.
> >>>>
> >>>> Maybe one to think about before deprecating a good generator. So I would
vote for putting the new XOR_SHIFT_1024_S_PHI along side the XOR_SHIFT_1024_S. Then perhaps
a Jira ticket to do some investigation of the properties of them run side by side as a composite.
> >>> That's the point, if they are independent, no need to deprecate;
> >>> if they are not, then the better version should be advertised as
> >>> a replacement (as done on the author's web site IIUC).
> >>>
> >>> Regards,
> >>> Gilles
> >>>
> >>>> WDYT?
> >>>>
> >>>> Alex
> >>>>
> >>>>
> >>>>
> >>>> Regards,
> >>>> Gilles
> >>>>
> >>>> [1] http://commons.apache.org/proper/commonsrng/userguide/rng.html#a5._Quality
<http://commons.apache.org/proper/commonsrng/userguide/rng.html#a5._Quality>
> >>>> [2] Provided the seed is good enough, but that's a different issue.

To unsubscribe, email: devunsubscribe@commons.apache.org
For additional commands, email: devhelp@commons.apache.org
