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