[Replying to list.]
Le mar. 12 mars 2019 à 15:39, Alex Herbert <[email protected]> a écrit :
>
>
> On 12/03/2019 15:33, Gilles Sadowski wrote:
>
> Hi Alex.
>
> Le mar. 12 mars 2019 à 12:53, Alex Herbert <[email protected]> a écrit
> :
>
> On 11/03/2019 23:44, Gilles Sadowski wrote:
>
> Hello.
>
> Le jeu. 7 mars 2019 à 00:44, Alex Herbert <[email protected]> a écrit :
>
> On 6 Mar 2019, at 22:57, Gilles Sadowski <[email protected]> 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).
> 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
> [2] Provided the seed is good enough, but that's a different issue.
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
