Hello Alex.
Le mer. 13 mars 2019 à 15:37, Alex Herbert <alex.d.herb...@gmail.com> a écrit :
>
> On 13/03/2019 02:20, Gilles Sadowski wrote:
> > Le mar. 12 mars 2019 à 22:34, Alex Herbert <alex.d.herb...@gmail.com> a
> > écrit :
> >>
> >>
> >>> On 12 Mar 2019, at 17:12, Gilles Sadowski <gillese...@gmail.com> wrote:
> >>>
> >>> [Replying to list.]
> >>>
> >>> Le mar. 12 mars 2019 à 15:39, Alex Herbert <alex.d.herb...@gmail.com
> >>> <mailto:alex.d.herb...@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.herb...@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.herb...@gmail.com> a
> >>>> écrit :
> >>>>
> >>>> On 6 Mar 2019, at 22:57, Gilles Sadowski <gillese...@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
> >>>> multi-threaded 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/commons-rng/userguide/rng.html#a5._Quality
> >>>>
> >>>> <http://commons.apache.org/proper/commons-rng/userguide/rng.html#a5._Quality>
> >>>> [2] Provided the seed is good enough, but that's a different issue.
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
For additional commands, e-mail: dev-h...@commons.apache.org
