[Replying to the list ML.]
FYI.
I have set up a composite (XorShift1024Star ^ XorShift1024StarPhi) test
using DieHarder to run overnight with 100 seeds.
If this passes then I'll find more resources and run BigCrush with the
composite.
Alex
On 12/03/2019 14:39, Alex Herbert wrote:
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
<https://github.com/apache/commons-rng/blob/740286662e52b6e0e47fce8ae58bd7c91bbf4763/commons-rng-core/src/main/java/org/apache/commons/rng/core/source64/XorShift1024Star.java#L109>
The method for producing the internal state is the same. So a
composite of internal states (ala TwoCmres) is not possible.
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? This
possibility should be documented if it exists. But how to test that?
Do you mean a bitwise xor of the output from each generator, then
passed through the test suites? 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.
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.
