You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@commons.apache.org by Alex Herbert <al...@gmail.com> on 2019/03/06 15:50:03 UTC
[Rng] New XoShiRo generators
I would like to merge this PR introducing the new XoShiRo generators:
https://github.com/apache/commons-rng/pull/20 <https://github.com/apache/commons-rng/pull/20>
Can I get a review to check that nothing is obviously bad.
Thanks,
Alex
Re: [Rng] New XoShiRo generators
Posted by Alex Herbert <al...@gmail.com>.
> On 6 Mar 2019, at 17:13, Gilles Sadowski <gi...@gmail.com> wrote:
>
> Le mer. 6 mars 2019 à 16:50, Alex Herbert <al...@gmail.com> a écrit :
>>
>> I would like to merge this PR introducing the new XoShiRo generators:
>>
>> https://github.com/apache/commons-rng/pull/20 <https://github.com/apache/commons-rng/pull/20>
>>
>> Can I get a review to check that nothing is obviously bad.
>
> In the PR, you mention:
>> Further changes to the other projects to add the extra providers will be required when accepted.
>
> What changes are you referring to?
I have not yet updated the benchmarking examples to add the new generators. I was going to add them later. Should I do this in the PR too?
I plan to squash all the changes in the current PR to clean it up and move the updated XorShift1024StarPhi to different PR.
>
> Gilles
>
>>
>> Thanks,
>>
>> Alex
>>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
> For additional commands, e-mail: dev-help@commons.apache.org
>
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [Rng] New XoShiRo generators
Posted by Gilles Sadowski <gi...@gmail.com>.
Le mer. 6 mars 2019 à 16:50, Alex Herbert <al...@gmail.com> a écrit :
>
> I would like to merge this PR introducing the new XoShiRo generators:
>
> https://github.com/apache/commons-rng/pull/20 <https://github.com/apache/commons-rng/pull/20>
>
> Can I get a review to check that nothing is obviously bad.
In the PR, you mention:
> Further changes to the other projects to add the extra providers will be required when accepted.
What changes are you referring to?
Gilles
>
> Thanks,
>
> Alex
>
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [Rng] New XoShiRo generators
Posted by Alex Herbert <al...@gmail.com>.
[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<al...@gmail.com> a écrit :
>>> On 11/03/2019 23:44, Gilles Sadowski wrote:
>>>> Hello.
>>>>
>>>> Le jeu. 7 mars 2019 à 00:44, Alex Herbert<al...@gmail.com> a écrit :
>>>>>> On 6 Mar 2019, at 22:57, Gilles Sadowski<gi...@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.
Re: [Rng] New XoShiRo generators
Posted by Gilles Sadowski <gi...@gmail.com>.
Le ven. 15 mars 2019 à 19:03, Alex Herbert <al...@gmail.com> a écrit :
>
> PS. Did you try this test program to check the size of the unsigned long?
I'm on 64-bits Debian GNU/Linux, so...
sizeof(int) = 4
sizeof(long) = 8
sizeof(unsigned long) = 8
sizeof(uint32_t) = 4
sizeof(double) = 8
[... same as yours, below ... ]
Gilles
> >
> >
> > The c standard for long states that it can be 32-bits or more! So to check what happens on my 64-bit test machine:
> >
> > #include <stdio.h>
> > #include <limits.h>
> > #include <stdint.h>
> >
> > int main(void){
> > printf("sizeof(int) = %d\n", (int)sizeof(int));
> > printf("sizeof(long) = %d\n", (int)sizeof(long));
> > printf("sizeof(unsigned long) = %d\n", (int)sizeof(unsigned long));
> > printf("sizeof(uint32_t) = %d\n", (int)sizeof(uint32_t));
> > printf("sizeof(double) = %d\n", (int)sizeof(double));
> > unsigned long value = 1;
> > for (int i = 1; i <= 8 * (int)sizeof(unsigned long); i++) {
> > printf("[%d] %lu = %u\n", i, value, (uint32_t) value);
> > value = (value << 1);
> > }
> > return 0;
> > }
> >
> > > gcc test.c && ./a.out
> >
> > sizeof(int) = 4
> > sizeof(long) = 8
> > sizeof(unsigned long) = 8
> > sizeof(uint32_t) = 4
> > sizeof(double) = 8
> > …
> > [31] 1073741824 = 1073741824
> > [32] 2147483648 = 2147483648
> > [33] 4294967296 = 0
> > [34] 8589934592 = 0
> > …
> >
> >
>
>
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [Rng] New XoShiRo generators
Posted by Alex Herbert <al...@gmail.com>.
PS. Did you try this test program to check the size of the unsigned long?
>
>
> The c standard for long states that it can be 32-bits or more! So to check what happens on my 64-bit test machine:
>
> #include <stdio.h>
> #include <limits.h>
> #include <stdint.h>
>
> int main(void){
> printf("sizeof(int) = %d\n", (int)sizeof(int));
> printf("sizeof(long) = %d\n", (int)sizeof(long));
> printf("sizeof(unsigned long) = %d\n", (int)sizeof(unsigned long));
> printf("sizeof(uint32_t) = %d\n", (int)sizeof(uint32_t));
> printf("sizeof(double) = %d\n", (int)sizeof(double));
> unsigned long value = 1;
> for (int i = 1; i <= 8 * (int)sizeof(unsigned long); i++) {
> printf("[%d] %lu = %u\n", i, value, (uint32_t) value);
> value = (value << 1);
> }
> return 0;
> }
>
> > gcc test.c && ./a.out
>
> sizeof(int) = 4
> sizeof(long) = 8
> sizeof(unsigned long) = 8
> sizeof(uint32_t) = 4
> sizeof(double) = 8
> …
> [31] 1073741824 = 1073741824
> [32] 2147483648 = 2147483648
> [33] 4294967296 = 0
> [34] 8589934592 = 0
> …
>
>
Re: [Rng] New XoShiRo generators
Posted by Alex Herbert <al...@gmail.com>.
On 20/03/2019 11:14, Gilles Sadowski wrote:
>>
>> I have updated the PR for the XorShift1024 variant to deprecate the old XOR_SHIFT_1024_S enum.
>>
>> Please take a look to see if the wording is OK:
>>
>> https://github.com/apache/commons-rng/pull/30/files#diff-630495e26d73fa22ada841dabde0ab47 <https://github.com/apache/commons-rng/pull/30/files#diff-630495e26d73fa22ada841dabde0ab47>
> How about:
>
> /**
> * @deprecated Since 1.3, where it is recommended to use {@code
> XOR_SHIFT_1024_S_PHI},
> * instead, due to its slightly better (more uniform) output.
> * {@code XOR_SHIFT_1024_S} is still quite usable but both versions
> share the exact same
> * internal state, so that their outputs are correlated (and thus
> should not be used together when
> * independent sequences are assumed).
> */
>
> ?
That is better as it states that the existing version is not broken and
can still be used.
I've rearranged the text about sharing internal state as it could be
misinterpreted since instances do not share state, only the method to
maintain it. So I've changed it to variants of the same algorithm:
* @deprecated Since 1.3, where it is recommended to use {@code
XOR_SHIFT_1024_S_PHI}
* instead due to its slightly better (more uniform) output. {@code
XOR_SHIFT_1024_S}
* is still quite usable but both are variants of the same
algorithm and maintain their
* internal state identically. Their outputs are correlated and the
two should not be
* used together when independent sequences are assumed.
I have missed off stating that they are correlated when identically
seeded. When not identically seeded I presume it correct to say they are
correlated given some defined lag? It's probably best to not mention it
so a user does not think that using them together is OK with different
seeds.
So I will remove the 'identically seeded' text from the class definition
too and change it to:
* <p>Note: This supersedes {@link XorShift1024Star}. The sequences
emitted by both
* generators are correlated.</p>
*
* <p>This generator differs only in the final multiplier (a
fixed-point representation
* of the golden ratio), which eliminates linear dependencies from one
of the lowest
* bits.</p>
I find the two paragraphs make it clearer they are correlated than if
all in one paragraph.
I'll also add a note to XorShift1024Star that it has been superseded by:
* <p>Note: This has been superseded by {@link XorShift1024StarPhi}.
The sequences emitted
* by both generators are correlated.</p>
Thus the recommendation is clear. Do not use them together to be assured
of independence.
Alex
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [Rng] New XoShiRo generators
Posted by Gilles Sadowski <gi...@gmail.com>.
Hi Alex.
Le mer. 20 mars 2019 à 01:32, Alex Herbert <al...@gmail.com> a écrit :
>
>
>
> > On 19 Mar 2019, at 15:24, Gilles Sadowski <gi...@gmail.com> wrote:
> >>
> >> I am currently rerunning the dieharder test for the XorShift1024Star
> >> composites since that requires a little endian format on my machine. So
> >> far there are not as many failures when the byte order is reversed.
> >>
> >> Once that is done I think we can wrap this up by:
> >>
> >> - updating the stress test to support little/big endian format as input
> >> for the test suite
> >>
> >> - updating the stress test GeneratorsList to match the RandomSource enum
> >> order
> >>
> >> - merging the modified XorShift1024StarPhi generator
> >>
> >> - deprecating the XOR_SHIFT_1024_S enum in favour of XOR_SHIFT_1024_S_PHI
>
> I have updated the PR for the XorShift1024 variant to deprecate the old XOR_SHIFT_1024_S enum.
>
> Please take a look to see if the wording is OK:
>
> https://github.com/apache/commons-rng/pull/30/files#diff-630495e26d73fa22ada841dabde0ab47 <https://github.com/apache/commons-rng/pull/30/files#diff-630495e26d73fa22ada841dabde0ab47>
How about:
/**
* @deprecated Since 1.3, where it is recommended to use {@code
XOR_SHIFT_1024_S_PHI},
* instead, due to its slightly better (more uniform) output.
* {@code XOR_SHIFT_1024_S} is still quite usable but both versions
share the exact same
* internal state, so that their outputs are correlated (and thus
should not be used together when
* independent sequences are assumed).
*/
?
>
> I have not deprecated the XorShift1024Star generator. That still works and is the base for the new one. Just deprecating the enum value serves as a warning for users to update, or use that generator with wisely.
+1
That's what the above text tries to convey.
Gilles
>
> Alex
>
>
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [Rng] New XoShiRo generators
Posted by Alex Herbert <al...@gmail.com>.
> On 19 Mar 2019, at 15:24, Gilles Sadowski <gi...@gmail.com> wrote:
>>
>> I am currently rerunning the dieharder test for the XorShift1024Star
>> composites since that requires a little endian format on my machine. So
>> far there are not as many failures when the byte order is reversed.
>>
>> Once that is done I think we can wrap this up by:
>>
>> - updating the stress test to support little/big endian format as input
>> for the test suite
>>
>> - updating the stress test GeneratorsList to match the RandomSource enum
>> order
>>
>> - merging the modified XorShift1024StarPhi generator
>>
>> - deprecating the XOR_SHIFT_1024_S enum in favour of XOR_SHIFT_1024_S_PHI
I have updated the PR for the XorShift1024 variant to deprecate the old XOR_SHIFT_1024_S enum.
Please take a look to see if the wording is OK:
https://github.com/apache/commons-rng/pull/30/files#diff-630495e26d73fa22ada841dabde0ab47 <https://github.com/apache/commons-rng/pull/30/files#diff-630495e26d73fa22ada841dabde0ab47>
I have not deprecated the XorShift1024Star generator. That still works and is the base for the new one. Just deprecating the enum value serves as a warning for users to update, or use that generator with wisely.
Alex
Re: [Rng] New XoShiRo generators
Posted by Gilles Sadowski <gi...@gmail.com>.
Hello.
> >>>>> [...]
> >>>> Given all the stress tests will be rerun shall I go ahead and reorder the existing files, user guide .apt file and the GeneratorsList to be in the order of the RandomSource enum?
> >>> We could wait for the new results before updating the site.
> >> I was going to rearrange it all and test all the links in the local site are all ok. I have this scripted but have not yet run it.
> > Are you going to upload this script to the repository?
>
> I wasn't going to. I've put it into my branch here:
>
> https://github.com/aherbert/commons-rng/blob/userguide-rename/rename.pl
IIUC, this one is only for updating the current site (?).
I was thinking of a utility for taking the output (of several runs) of the test
suites and generate the table in "apt" format (with correct links).
> It generates two files that should do all the rearrangement. It's a work
> in progress. I've just tried it out and it seems to work, although I've
> not looked at the generated site.
>
> The 'git mv' command when viewed using 'git log -M --summary' shows the
> renames, e.g.
>
> commit c8b8903c00ab6d2c1403667048f27d9cbad4de46
> Author: aherbert <ah...@apache.org>
> Date: Tue Mar 19 12:14:13 2019 +0000
>
> Updated stress test results files
>
> rename src/site/resources/txt/userguide/stress/dh/run_1/{dh_K =>
> dh_10} (100%)
> rename src/site/resources/txt/userguide/stress/dh/run_1/{dh_L =>
> dh_11} (100%)
> rename src/site/resources/txt/userguide/stress/dh/run_1/{dh_M =>
> dh_12} (100%)
> rename src/site/resources/txt/userguide/stress/dh/run_1/{dh_J =>
> dh_13} (100%)
> rename src/site/resources/txt/userguide/stress/dh/run_1/{dh_C => dh_2}
> (100%)
>
>
> However it is probably easiest to leave it as is and have the source
> repo results files out of sync with the GeneratorsList until the next
> benchmark results are done.
>
I think so.
> >
> >> When new results are ready they can be written over the existing ones. Either way I am fine. So let’s leave it until new results have been done and then check the site.
> >>
> >> I will update the GeneratorsList to be autogenerated from the RandomSource enum.
> > Thanks.
> > Let me know when everything is in place, and I'll try and start a stress test
> > run on my side.
>
> OK.
>
> I am currently rerunning the dieharder test for the XorShift1024Star
> composites since that requires a little endian format on my machine. So
> far there are not as many failures when the byte order is reversed.
>
> Once that is done I think we can wrap this up by:
>
> - updating the stress test to support little/big endian format as input
> for the test suite
>
> - updating the stress test GeneratorsList to match the RandomSource enum
> order
>
> - merging the modified XorShift1024StarPhi generator
>
> - deprecating the XOR_SHIFT_1024_S enum in favour of XOR_SHIFT_1024_S_PHI
>
> - merging the new XorShiRo generators
>
> Then it should be ready for a new stress test benchmark.
> >>>>
> >>>> Big/Little Endian for Dieharder:
> >>>>
> >>>> [...]
> >>>>
> >>>> Reversing the bytes in the Java code is the easiest option.
> >>> +1
> >>> [With an option flag for selecting whether the output should be BE or LE.]
> >>>
> >> OK. I will consolidate all this and update the stress_test.md instructions to make it clear that endianness needs to be considered.
> >>
> >> Should I add the raw data dumper to the source base? This runs a named RandomSource for a given number of iterations with a provided seed and outputs 4 files: Dieharder text format and raw binary, with standard order and byte reversed. It may be useful if debugging the output of RNGs ever needs to be done again.
> > Sure. Can this be also added as an option to the "RandomStressTester"
> > class? E.g. with a flag like
> > --dump file_prefix,sequence_length
> > where
> > "file_prefix" is the basename of the output files, and
> > "sequence_length" is the number of ints to generate.
>
> The RandomStressTester uses a list of generators. I built the
> RawDataDumper to run using a maven profile where it works for a single
> named RandomSource. Arguments are:
>
> RandomSource name, long seed, sequence length, file prefix.
>
> So all the functionality is there. If the file is included in the shaded
> jar you should be able to do:
>
> > java -cp examples-stress.jar
> org.apache.commons.rng.examples.stress.RawDataDumper SPLIT_MIX_64 123L
> 1000 splitmix.out
>
> Instead of running in a maven profile it could be built into a shaded
> package to allow:
>
> > java -jar raw-data-dumper.jar SPLIT_MIX_64 123L 1000 splitmix.out
I like that.
One build should generate all application (dumper and stress test launcher).
> I think the functionality is better as two programs to avoid doing too
> much in the RandomStressTester. Also I do not see the need to dump
> output from a list of 15+ generators.
+1
> I can add flag arguments to be used to specify which file to write:
>
> .dh (text output using the dieharder format (uses unsigned int))
>
> .txt (text output)
>
> .raw (raw binary output)
>
> .bin (2s complement binary output)
>
> .hex (text output using hex)
>
>
> And options for:
>
> - int output
>
> - long output
>
> - byte reversed
>
> - bit reversed
>
> You then have a utility for dumping output of any random source to file
> in a variety of formats.
>
> Although long output is not needed for the test suites it is useful for
> native long generators.
>
> WDYT?
Looks good!
Thanks,
Gilles
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [Rng] New XoShiRo generators
Posted by Alex Herbert <al...@gmail.com>.
On 19/03/2019 11:38, Gilles Sadowski wrote:
> Le mar. 19 mars 2019 à 10:26, Alex Herbert <al...@gmail.com> a écrit :
>>
>>
>>> On 19 Mar 2019, at 10:35, Gilles Sadowski <gi...@gmail.com> wrote:
>>>
>>>>> [...]
>>>> Given all the stress tests will be rerun shall I go ahead and reorder the existing files, user guide .apt file and the GeneratorsList to be in the order of the RandomSource enum?
>>> We could wait for the new results before updating the site.
>> I was going to rearrange it all and test all the links in the local site are all ok. I have this scripted but have not yet run it.
> Are you going to upload this script to the repository?
I wasn't going to. I've put it into my branch here:
https://github.com/aherbert/commons-rng/blob/userguide-rename/rename.pl
It generates two files that should do all the rearrangement. It's a work
in progress. I've just tried it out and it seems to work, although I've
not looked at the generated site.
The 'git mv' command when viewed using 'git log -M --summary' shows the
renames, e.g.
commit c8b8903c00ab6d2c1403667048f27d9cbad4de46
Author: aherbert <ah...@apache.org>
Date: Tue Mar 19 12:14:13 2019 +0000
Updated stress test results files
rename src/site/resources/txt/userguide/stress/dh/run_1/{dh_K =>
dh_10} (100%)
rename src/site/resources/txt/userguide/stress/dh/run_1/{dh_L =>
dh_11} (100%)
rename src/site/resources/txt/userguide/stress/dh/run_1/{dh_M =>
dh_12} (100%)
rename src/site/resources/txt/userguide/stress/dh/run_1/{dh_J =>
dh_13} (100%)
rename src/site/resources/txt/userguide/stress/dh/run_1/{dh_C => dh_2}
(100%)
However it is probably easiest to leave it as is and have the source
repo results files out of sync with the GeneratorsList until the next
benchmark results are done.
>
>> When new results are ready they can be written over the existing ones. Either way I am fine. So let’s leave it until new results have been done and then check the site.
>>
>> I will update the GeneratorsList to be autogenerated from the RandomSource enum.
> Thanks.
> Let me know when everything is in place, and I'll try and start a stress test
> run on my side.
OK.
I am currently rerunning the dieharder test for the XorShift1024Star
composites since that requires a little endian format on my machine. So
far there are not as many failures when the byte order is reversed.
Once that is done I think we can wrap this up by:
- updating the stress test to support little/big endian format as input
for the test suite
- updating the stress test GeneratorsList to match the RandomSource enum
order
- merging the modified XorShift1024StarPhi generator
- deprecating the XOR_SHIFT_1024_S enum in favour of XOR_SHIFT_1024_S_PHI
- merging the new XorShiRo generators
Then it should be ready for a new stress test benchmark.
>>>>
>>>> Big/Little Endian for Dieharder:
>>>>
>>>> [...]
>>>>
>>>> Reversing the bytes in the Java code is the easiest option.
>>> +1
>>> [With an option flag for selecting whether the output should be BE or LE.]
>>>
>> OK. I will consolidate all this and update the stress_test.md instructions to make it clear that endianness needs to be considered.
>>
>> Should I add the raw data dumper to the source base? This runs a named RandomSource for a given number of iterations with a provided seed and outputs 4 files: Dieharder text format and raw binary, with standard order and byte reversed. It may be useful if debugging the output of RNGs ever needs to be done again.
> Sure. Can this be also added as an option to the "RandomStressTester"
> class? E.g. with a flag like
> --dump file_prefix,sequence_length
> where
> "file_prefix" is the basename of the output files, and
> "sequence_length" is the number of ints to generate.
The RandomStressTester uses a list of generators. I built the
RawDataDumper to run using a maven profile where it works for a single
named RandomSource. Arguments are:
RandomSource name, long seed, sequence length, file prefix.
So all the functionality is there. If the file is included in the shaded
jar you should be able to do:
> java -cp examples-stress.jar
org.apache.commons.rng.examples.stress.RawDataDumper SPLIT_MIX_64 123L
1000 splitmix.out
Instead of running in a maven profile it could be built into a shaded
package to allow:
> java -jar raw-data-dumper.jar SPLIT_MIX_64 123L 1000 splitmix.out
I think the functionality is better as two programs to avoid doing too
much in the RandomStressTester. Also I do not see the need to dump
output from a list of 15+ generators.
I can add flag arguments to be used to specify which file to write:
.dh (text output using the dieharder format (uses unsigned int))
.txt (text output)
.raw (raw binary output)
.bin (2s complement binary output)
.hex (text output using hex)
And options for:
- int output
- long output
- byte reversed
- bit reversed
You then have a utility for dumping output of any random source to file
in a variety of formats.
Although long output is not needed for the test suites it is useful for
native long generators.
WDYT?
Alex
>
> Gilles
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
> For additional commands, e-mail: dev-help@commons.apache.org
>
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [Rng] New XoShiRo generators
Posted by Gilles Sadowski <gi...@gmail.com>.
Le mar. 19 mars 2019 à 10:26, Alex Herbert <al...@gmail.com> a écrit :
>
>
>
> > On 19 Mar 2019, at 10:35, Gilles Sadowski <gi...@gmail.com> wrote:
> >
> >>> [...]
> >>
> >> Given all the stress tests will be rerun shall I go ahead and reorder the existing files, user guide .apt file and the GeneratorsList to be in the order of the RandomSource enum?
> >
> > We could wait for the new results before updating the site.
>
> I was going to rearrange it all and test all the links in the local site are all ok. I have this scripted but have not yet run it.
Are you going to upload this script to the repository?
> When new results are ready they can be written over the existing ones. Either way I am fine. So let’s leave it until new results have been done and then check the site.
>
> I will update the GeneratorsList to be autogenerated from the RandomSource enum.
Thanks.
Let me know when everything is in place, and I'll try and start a stress test
run on my side.
> >>
> >>
> >> Big/Little Endian for Dieharder:
> >>
> >> [...]
> >>
> >> Reversing the bytes in the Java code is the easiest option.
> >
> > +1
> > [With an option flag for selecting whether the output should be BE or LE.]
> >
>
> OK. I will consolidate all this and update the stress_test.md instructions to make it clear that endianness needs to be considered.
>
> Should I add the raw data dumper to the source base? This runs a named RandomSource for a given number of iterations with a provided seed and outputs 4 files: Dieharder text format and raw binary, with standard order and byte reversed. It may be useful if debugging the output of RNGs ever needs to be done again.
Sure. Can this be also added as an option to the "RandomStressTester"
class? E.g. with a flag like
--dump file_prefix,sequence_length
where
"file_prefix" is the basename of the output files, and
"sequence_length" is the number of ints to generate.
Gilles
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [Rng] New XoShiRo generators
Posted by Alex Herbert <al...@gmail.com>.
> On 19 Mar 2019, at 10:35, Gilles Sadowski <gi...@gmail.com> wrote:
>
>>> [...]
>>>> So leave the testing to just ints and document on the user guide that is
>>>> what we are testing.
>>>
>>> +1
>>
>> OK. That seems simplest.
>>
>> Given all the stress tests will be rerun shall I go ahead and reorder the existing files, user guide .apt file and the GeneratorsList to be in the order of the RandomSource enum?
>
> We could wait for the new results before updating the site.
I was going to rearrange it all and test all the links in the local site are all ok. I have this scripted but have not yet run it. When new results are ready they can be written over the existing ones. Either way I am fine. So let’s leave it until new results have been done and then check the site.
I will update the GeneratorsList to be autogenerated from the RandomSource enum.
>
>>
>>
>> Big/Little Endian for Dieharder:
>>
>> I’ve spent some time looking at the source code for Dieharder. It reads binary file data using this (taken from libdieharder/rng_file_input_raw.c):
>>
>> unsigned int iret;
>> // ...
>> fread(&iret,sizeof(uint),1,state->fp);
>>
>> So it reads single unsigned integers using fread().
>>
>> Given that it is possible to run die harder using numbers from ascii and binary input files I set up a test. I created them using a RNG with the same seed with the standard output from a DataOutputStream and the byte reversed output using Integer.reverseBytes. Here’s what happens:
>>
>>> dieharder -g 201 -d 0 -f raw.bin.rev
>> diehard_birthdays| 0| 100| 100|0.89220858| PASSED
>>> dieharder -g 202 -d 0 -f raw.txt
>> diehard_birthdays| 0| 100| 100|0.89220858| PASSED
>>
>>> dieharder -g 201 -d 0 -f raw.bin
>> diehard_birthdays| 0| 100| 100|0.30776452| PASSED
>>> dieharder -g 202 -d 0 -f raw.txt.rev
>> diehard_birthdays| 0| 100| 100|0.30776452| PASSED
>>
>>> cat raw.bin | dieharder -g 200 -d 0
>> diehard_birthdays| 0| 100| 100|0.30776452| PASSED
>>
>>
>> Note the reversed byte sequence (.rev suffix) is required to get the same results from the binary (.bin) file as from the text (.txt) file.
>>
>> So the binary read of Dieharder is using the little endian representation, as was required for TestU01.
>>
>> I had modified the stdin2testu01.c bridge to detect if the system was little endian and then correct the input data by reversing the bytes. It may be a better idea to write a test c program to detect the endianness of the system for reference. Then update the stress test benchmark to have an argument for little or big endian output when piping the int data to the command line program.
>>
>> I think it is important to get the endianness of the data correct. At least for Dieharder it runs tests using tuples of bits from the data which can span multiple bytes. For example the sts_serial test (-d 102) uses overlapping n-tuples of bits with n from 1 to 16. Other tests using non overlapping tuples such as rgb_bitdist (-d 200) use n 1 to 12.
>>
>> Reversing the bytes in the Java code is the easiest option.
>
> +1
> [With an option flag for selecting whether the output should be BE or LE.]
>
OK. I will consolidate all this and update the stress_test.md instructions to make it clear that endianness needs to be considered.
Should I add the raw data dumper to the source base? This runs a named RandomSource for a given number of iterations with a provided seed and outputs 4 files: Dieharder text format and raw binary, with standard order and byte reversed. It may be useful if debugging the output of RNGs ever needs to be done again.
Alex
Re: [Rng] New XoShiRo generators
Posted by Gilles Sadowski <gi...@gmail.com>.
> > [...]
> >> So leave the testing to just ints and document on the user guide that is
> >> what we are testing.
> >
> > +1
>
> OK. That seems simplest.
>
> Given all the stress tests will be rerun shall I go ahead and reorder the existing files, user guide .apt file and the GeneratorsList to be in the order of the RandomSource enum?
We could wait for the new results before updating the site.
>
>
> Big/Little Endian for Dieharder:
>
> I’ve spent some time looking at the source code for Dieharder. It reads binary file data using this (taken from libdieharder/rng_file_input_raw.c):
>
> unsigned int iret;
> // ...
> fread(&iret,sizeof(uint),1,state->fp);
>
> So it reads single unsigned integers using fread().
>
> Given that it is possible to run die harder using numbers from ascii and binary input files I set up a test. I created them using a RNG with the same seed with the standard output from a DataOutputStream and the byte reversed output using Integer.reverseBytes. Here’s what happens:
>
> > dieharder -g 201 -d 0 -f raw.bin.rev
> diehard_birthdays| 0| 100| 100|0.89220858| PASSED
> > dieharder -g 202 -d 0 -f raw.txt
> diehard_birthdays| 0| 100| 100|0.89220858| PASSED
>
> > dieharder -g 201 -d 0 -f raw.bin
> diehard_birthdays| 0| 100| 100|0.30776452| PASSED
> > dieharder -g 202 -d 0 -f raw.txt.rev
> diehard_birthdays| 0| 100| 100|0.30776452| PASSED
>
> > cat raw.bin | dieharder -g 200 -d 0
> diehard_birthdays| 0| 100| 100|0.30776452| PASSED
>
>
> Note the reversed byte sequence (.rev suffix) is required to get the same results from the binary (.bin) file as from the text (.txt) file.
>
> So the binary read of Dieharder is using the little endian representation, as was required for TestU01.
>
> I had modified the stdin2testu01.c bridge to detect if the system was little endian and then correct the input data by reversing the bytes. It may be a better idea to write a test c program to detect the endianness of the system for reference. Then update the stress test benchmark to have an argument for little or big endian output when piping the int data to the command line program.
>
> I think it is important to get the endianness of the data correct. At least for Dieharder it runs tests using tuples of bits from the data which can span multiple bytes. For example the sts_serial test (-d 102) uses overlapping n-tuples of bits with n from 1 to 16. Other tests using non overlapping tuples such as rgb_bitdist (-d 200) use n 1 to 12.
>
> Reversing the bytes in the Java code is the easiest option.
+1
[With an option flag for selecting whether the output should be BE or LE.]
Best,
Gilles
> Others are:
>
> - Write binary data to file and then run it using that. This will end up looping the file though and repeating the sequence unless the binary file is huge.
> - Call Dieharder from a bridge program using the libdieharder API. I’ve not checked if there is an API method call for Dieharder to run everything.
>
> Alex
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [Rng] New XoShiRo generators
Posted by Alex Herbert <al...@gmail.com>.
> On 18 Mar 2019, at 19:27, Gilles Sadowski <gi...@gmail.com> wrote:
>
> Le lun. 18 mars 2019 à 16:49, Alex Herbert <alex.d.herbert@gmail.com <ma...@gmail.com>> a écrit :
>>
>>
>> On 18/03/2019 14:12, Gilles Sadowski wrote:
>>> Hi.
>>>
>>>>>> [...]
>>>>>>
>>>>>> One actual issue is that we are testing long providers using the long to create 2 int values. Should we test using a series of the upper 32 bits and then a series of the lower 32 bits?
>>>>> Is that useful since the test now sees the integers as they are produced (i.e. 2
>>>>> values per long)?
>>>>>
>>>> It is not relevant if you are concerned about int quality. But if you are concerned about long quality then it is relevant. The long quality is important for the quality of nextDouble(). Although in that case only the upper 53 bits of the long. This means that the quality of a long from an int provider is also not covered by the benchmark as that would require testing alternating ints twice using the series: 1, 3, 5…, 2n+1 and 2, 4, 6, … 2n.
>>> I don't follow: I'd think that if the full sequence passes the test,
>>> then "decimated"
>>> sequences will too.
>>
>> My position was that if a series of int values is random, that does not
>> mean a subset of the int values is random due to bias in the subset sample.
>
> Doesn't this statement contradict...
>
>>
>> However I acknowledge that:
>>
>> - the test suites may have this covered already
>>
>> - if it really is random then any subset will also be random, even if it
>> is a systematic subset such as alternating values
>
> ... this one?
Yes but my get out clause is that there are a lot of IFs. Basically I don’t know which is right. It is easiest to assume that the test suite has this covered and we just test RNGs passing all the bits through.
>
>>
>>>> Given that half of the int values were previously discarded from the BigCrush analysis, the current results on the user guide page actually represent BigCrush running on the upper 32-bits of the long, byte reversed due to the big/little endian interpretation of the bytes in Java and linux.
>>>>
>>>> So maybe the an update to the RandomStressTester to support analysis for int or long quality is needed.
>>> I'm not convinced.
>>
>> I'm not totally convinced either. It is a lot more work to test upper
>> and lower bits separately.
>>
>> It may be that a producer of long values has better randomness in the
>> upper bits. Or put another way has less than 64-bits of randomness.
>>
>> The question is whether running the test suite on all the bits (as we
>> currently do) or targetting just the upper or lower 32-bits is useful.
>> E.g. would a RNG that fails a few tests using all the bits pass with
>> just the upper 32-bits,
>
> Since the RNG outputs all the bits, passing the test with part
> of them would have no particular value (except if the goal is to
> create a new implementation based on that observation).
>
>> and fail more with just the lower 32-bits, or
>> would the fails be the same?
>>
>> Note: The current results for long providers do not test the lower
>> 32-bits at all, and currently test alternating values from any int
>> providers. So they will have to be rerun anyway.
>
> +1
> [For the sake of consistency, but I don't think that the results
> will be different.]
>
>> Previously I looked at systematic failures in the test suite (where the
>> same test always fails). IIRC the MersenneTwister has some systematic
>> failures. Since we are not doing systematic failure analysis for the
>> user guide, and we are not developing the algorithms, then I agree that
>> a more detailed analysis of the failures and their origins is beyond the
>> scope of the quality section.
>
> We already provide a wider choice of good implementations than
> any other Java library; indeed, I think that time is better spent in
> porting more algorithms (even "bad" ones).
>
>>
>> So leave the testing to just ints and document on the user guide that is
>> what we are testing.
>
> +1
OK. That seems simplest.
Given all the stress tests will be rerun shall I go ahead and reorder the existing files, user guide .apt file and the GeneratorsList to be in the order of the RandomSource enum?
Big/Little Endian for Dieharder:
I’ve spent some time looking at the source code for Dieharder. It reads binary file data using this (taken from libdieharder/rng_file_input_raw.c):
unsigned int iret;
// ...
fread(&iret,sizeof(uint),1,state->fp);
So it reads single unsigned integers using fread().
Given that it is possible to run die harder using numbers from ascii and binary input files I set up a test. I created them using a RNG with the same seed with the standard output from a DataOutputStream and the byte reversed output using Integer.reverseBytes. Here’s what happens:
> dieharder -g 201 -d 0 -f raw.bin.rev
diehard_birthdays| 0| 100| 100|0.89220858| PASSED
> dieharder -g 202 -d 0 -f raw.txt
diehard_birthdays| 0| 100| 100|0.89220858| PASSED
> dieharder -g 201 -d 0 -f raw.bin
diehard_birthdays| 0| 100| 100|0.30776452| PASSED
> dieharder -g 202 -d 0 -f raw.txt.rev
diehard_birthdays| 0| 100| 100|0.30776452| PASSED
> cat raw.bin | dieharder -g 200 -d 0
diehard_birthdays| 0| 100| 100|0.30776452| PASSED
Note the reversed byte sequence (.rev suffix) is required to get the same results from the binary (.bin) file as from the text (.txt) file.
So the binary read of Dieharder is using the little endian representation, as was required for TestU01.
I had modified the stdin2testu01.c bridge to detect if the system was little endian and then correct the input data by reversing the bytes. It may be a better idea to write a test c program to detect the endianness of the system for reference. Then update the stress test benchmark to have an argument for little or big endian output when piping the int data to the command line program.
I think it is important to get the endianness of the data correct. At least for Dieharder it runs tests using tuples of bits from the data which can span multiple bytes. For example the sts_serial test (-d 102) uses overlapping n-tuples of bits with n from 1 to 16. Other tests using non overlapping tuples such as rgb_bitdist (-d 200) use n 1 to 12.
Reversing the bytes in the Java code is the easiest option. Others are:
- Write binary data to file and then run it using that. This will end up looping the file though and repeating the sequence unless the binary file is huge.
- Call Dieharder from a bridge program using the libdieharder API. I’ve not checked if there is an API method call for Dieharder to run everything.
Alex
Re: [Rng] New XoShiRo generators
Posted by Gilles Sadowski <gi...@gmail.com>.
Le lun. 18 mars 2019 à 16:49, Alex Herbert <al...@gmail.com> a écrit :
>
>
> On 18/03/2019 14:12, Gilles Sadowski wrote:
> > Hi.
> >
> >>>> [...]
> >>>>
> >>>> One actual issue is that we are testing long providers using the long to create 2 int values. Should we test using a series of the upper 32 bits and then a series of the lower 32 bits?
> >>> Is that useful since the test now sees the integers as they are produced (i.e. 2
> >>> values per long)?
> >>>
> >> It is not relevant if you are concerned about int quality. But if you are concerned about long quality then it is relevant. The long quality is important for the quality of nextDouble(). Although in that case only the upper 53 bits of the long. This means that the quality of a long from an int provider is also not covered by the benchmark as that would require testing alternating ints twice using the series: 1, 3, 5…, 2n+1 and 2, 4, 6, … 2n.
> > I don't follow: I'd think that if the full sequence passes the test,
> > then "decimated"
> > sequences will too.
>
> My position was that if a series of int values is random, that does not
> mean a subset of the int values is random due to bias in the subset sample.
Doesn't this statement contradict...
>
> However I acknowledge that:
>
> - the test suites may have this covered already
>
> - if it really is random then any subset will also be random, even if it
> is a systematic subset such as alternating values
... this one?
>
> >> Given that half of the int values were previously discarded from the BigCrush analysis, the current results on the user guide page actually represent BigCrush running on the upper 32-bits of the long, byte reversed due to the big/little endian interpretation of the bytes in Java and linux.
> >>
> >> So maybe the an update to the RandomStressTester to support analysis for int or long quality is needed.
> > I'm not convinced.
>
> I'm not totally convinced either. It is a lot more work to test upper
> and lower bits separately.
>
> It may be that a producer of long values has better randomness in the
> upper bits. Or put another way has less than 64-bits of randomness.
>
> The question is whether running the test suite on all the bits (as we
> currently do) or targetting just the upper or lower 32-bits is useful.
> E.g. would a RNG that fails a few tests using all the bits pass with
> just the upper 32-bits,
Since the RNG outputs all the bits, passing the test with part
of them would have no particular value (except if the goal is to
create a new implementation based on that observation).
> and fail more with just the lower 32-bits, or
> would the fails be the same?
>
> Note: The current results for long providers do not test the lower
> 32-bits at all, and currently test alternating values from any int
> providers. So they will have to be rerun anyway.
+1
[For the sake of consistency, but I don't think that the results
will be different.]
> Previously I looked at systematic failures in the test suite (where the
> same test always fails). IIRC the MersenneTwister has some systematic
> failures. Since we are not doing systematic failure analysis for the
> user guide, and we are not developing the algorithms, then I agree that
> a more detailed analysis of the failures and their origins is beyond the
> scope of the quality section.
We already provide a wider choice of good implementations than
any other Java library; indeed, I think that time is better spent in
porting more algorithms (even "bad" ones).
>
> So leave the testing to just ints and document on the user guide that is
> what we are testing.
+1
Gilles
>
> >> For now the quality section on the website should just state that the quality is for the ‘nextInt()’ method of the RNG.
> >>
> >> I have the results of BigCrush using the new bridge c program:
> >>
> >> XorShiftSerialComposite : 40, 39, 39 : 608.2 +/- 3.9
> > Makes sense now. :-}
> >
> >> So it fails.
> >>
> >> The XorShiftXorComposite crashed after 2 hours about 1/4 of the results file complete. I am running again so I can monitor it for memory usage. Something in the BigCrush suite just cannot handle this generator output.
> > Strange...
>
> Yep. I restarted it and it crashed after 3 hours again! Monitoring every
> minute found no obvious memory issues. The BigCrush process never
> exceeded 2.7% of memory and Java never exceeded 0.1%.
>
> The footer is written by the Java program so this indicates that the
> TestU01 bridge is stopping then the Java process writes the footer,
> wraps everything up and stops.
>
> Weirdly my process to follow the output also stopped which is
> unexpected. I am investigating if my system has some strange walltime
> limits I do not know about. Since the other composite generators work
> using the same code I am thinking it may be a bug in TestU01 when the
> generator is bad (which DieHarder thinks it definitely is). But I am
> prepared to be wrong on that and also to never find out.
>
> I've changed RandomStressTester to redirect the stderr to stdout (in
> case that contains any info) and added a line to get the exit code from
> the Java Process that is running BigCrush. Maybe that will be non-zero.
> So I re-run and wait 3+ hours again...
>
> Alex
>
>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
> For additional commands, e-mail: dev-help@commons.apache.org
>
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [Rng] New XoShiRo generators
Posted by Alex Herbert <al...@gmail.com>.
On 18/03/2019 14:12, Gilles Sadowski wrote:
> Hi.
>
>>>> [...]
>>>>
>>>> One actual issue is that we are testing long providers using the long to create 2 int values. Should we test using a series of the upper 32 bits and then a series of the lower 32 bits?
>>> Is that useful since the test now sees the integers as they are produced (i.e. 2
>>> values per long)?
>>>
>> It is not relevant if you are concerned about int quality. But if you are concerned about long quality then it is relevant. The long quality is important for the quality of nextDouble(). Although in that case only the upper 53 bits of the long. This means that the quality of a long from an int provider is also not covered by the benchmark as that would require testing alternating ints twice using the series: 1, 3, 5…, 2n+1 and 2, 4, 6, … 2n.
> I don't follow: I'd think that if the full sequence passes the test,
> then "decimated"
> sequences will too.
My position was that if a series of int values is random, that does not
mean a subset of the int values is random due to bias in the subset sample.
However I acknowledge that:
- the test suites may have this covered already
- if it really is random then any subset will also be random, even if it
is a systematic subset such as alternating values
>> Given that half of the int values were previously discarded from the BigCrush analysis, the current results on the user guide page actually represent BigCrush running on the upper 32-bits of the long, byte reversed due to the big/little endian interpretation of the bytes in Java and linux.
>>
>> So maybe the an update to the RandomStressTester to support analysis for int or long quality is needed.
> I'm not convinced.
I'm not totally convinced either. It is a lot more work to test upper
and lower bits separately.
It may be that a producer of long values has better randomness in the
upper bits. Or put another way has less than 64-bits of randomness.
The question is whether running the test suite on all the bits (as we
currently do) or targetting just the upper or lower 32-bits is useful.
E.g. would a RNG that fails a few tests using all the bits pass with
just the upper 32-bits and fail more with just the lower 32-bits, or
would the fails be the same?
Note: The current results for long providers do not test the lower
32-bits at all, and currently test alternating values from any int
providers. So they will have to be rerun anyway.
Previously I looked at systematic failures in the test suite (where the
same test always fails). IIRC the MersenneTwister has some systematic
failures. Since we are not doing systematic failure analysis for the
user guide, and we are not developing the algorithms, then I agree that
a more detailed analysis of the failures and their origins is beyond the
scope of the quality section.
So leave the testing to just ints and document on the user guide that is
what we are testing.
>> For now the quality section on the website should just state that the quality is for the ‘nextInt()’ method of the RNG.
>>
>> I have the results of BigCrush using the new bridge c program:
>>
>> XorShiftSerialComposite : 40, 39, 39 : 608.2 +/- 3.9
> Makes sense now. :-}
>
>> So it fails.
>>
>> The XorShiftXorComposite crashed after 2 hours about 1/4 of the results file complete. I am running again so I can monitor it for memory usage. Something in the BigCrush suite just cannot handle this generator output.
> Strange...
Yep. I restarted it and it crashed after 3 hours again! Monitoring every
minute found no obvious memory issues. The BigCrush process never
exceeded 2.7% of memory and Java never exceeded 0.1%.
The footer is written by the Java program so this indicates that the
TestU01 bridge is stopping then the Java process writes the footer,
wraps everything up and stops.
Weirdly my process to follow the output also stopped which is
unexpected. I am investigating if my system has some strange walltime
limits I do not know about. Since the other composite generators work
using the same code I am thinking it may be a bug in TestU01 when the
generator is bad (which DieHarder thinks it definitely is). But I am
prepared to be wrong on that and also to never find out.
I've changed RandomStressTester to redirect the stderr to stdout (in
case that contains any info) and added a line to get the exit code from
the Java Process that is running BigCrush. Maybe that will be non-zero.
So I re-run and wait 3+ hours again...
Alex
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [Rng] New XoShiRo generators
Posted by Gilles Sadowski <gi...@gmail.com>.
Hi.
>>> [...]
> >>
> >> One actual issue is that we are testing long providers using the long to create 2 int values. Should we test using a series of the upper 32 bits and then a series of the lower 32 bits?
> >
> > Is that useful since the test now sees the integers as they are produced (i.e. 2
> > values per long)?
> >
>
> It is not relevant if you are concerned about int quality. But if you are concerned about long quality then it is relevant. The long quality is important for the quality of nextDouble(). Although in that case only the upper 53 bits of the long. This means that the quality of a long from an int provider is also not covered by the benchmark as that would require testing alternating ints twice using the series: 1, 3, 5…, 2n+1 and 2, 4, 6, … 2n.
I don't follow: I'd think that if the full sequence passes the test,
then "decimated"
sequences will too.
>
> Given that half of the int values were previously discarded from the BigCrush analysis, the current results on the user guide page actually represent BigCrush running on the upper 32-bits of the long, byte reversed due to the big/little endian interpretation of the bytes in Java and linux.
>
> So maybe the an update to the RandomStressTester to support analysis for int or long quality is needed.
I'm not convinced.
> For now the quality section on the website should just state that the quality is for the ‘nextInt()’ method of the RNG.
>
> I have the results of BigCrush using the new bridge c program:
>
> XorShiftSerialComposite : 40, 39, 39 : 608.2 +/- 3.9
Makes sense now. :-}
> So it fails.
>
> The XorShiftXorComposite crashed after 2 hours about 1/4 of the results file complete. I am running again so I can monitor it for memory usage. Something in the BigCrush suite just cannot handle this generator output.
Strange...
Regards,
Gilles
>>> [...]
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [Rng] New XoShiRo generators
Posted by Alex Herbert <al...@gmail.com>.
> On 18 Mar 2019, at 10:20, Gilles Sadowski <gi...@gmail.com> wrote:
>
> Le dim. 17 mars 2019 à 01:01, Alex Herbert <alex.d.herbert@gmail.com <ma...@gmail.com>> a écrit :
>>
>>
>>
>>> On 16 Mar 2019, at 23:10, Alex Herbert <alex.d.herbert@gmail.com <ma...@gmail.com>> wrote:
>>>
>>>
>>>
>>>> On 16 Mar 2019, at 02:54, Gilles Sadowski <gilleseran@gmail.com <ma...@gmail.com> <mailto:gilleseran@gmail.com <ma...@gmail.com>>> wrote:
>>>>> This is read by dieharder which directly reads from stdin. This worked to collect all the generated bits and the serial and xor composites failed the test suite.
>>>>>
>>>>> It is also read by the stdin2testu01.c program to pass to TestU01.
>>>>>
>>>>> What is happening is that the stdin2testu01.c is reading 64-bits using an unsigned long.
>>>>
>>>> I don't remember why I wrote that, but as you pointed outit now looks
>>>> like a plain bug.
>>>
>>> It may be more complicated again...
>>>
>>> I’ve had a play around with the data being pushed through to the testU01 library using the c bridge. I wanted to check that the int value that is generated by the RNG is passed through to the c program. So I wrote a simple BridgeTester class to do this. It writes all the int values to a data file (for reference) then passes them to the c executable with the same method as the RandomStressTester. I then modified the stdin2testu01.c program to have an extra hidden debug mode where all the data is just written to stdout.
>>>
>>> I found the data file written from Java did not match the data that the c program had. I bit more digging found that the problem was that Java uses a big endian representation and the c program is little endian. This is true on my linux and Mac OSX platforms. So the raw bytes read from stdin are in the wrong order.
>>>
>>> When I updated the program to self detect endianness and swap the byte order of each set of 4 bytes from the stdin then the data in the c program matched the original.
>>>
>>> Since it was non destructive to the module I added all this to master. You can see this working by rebuilding the c bridge and running the new profile to test it:
>>>
>>>> cd commons-rng-examples/examples-stress
>>>> gcc src/main/c/stdin2testu01.c -o stdin2testu01 -ltestu01 -ltestu01probdist -ltestu01mylib -lm
>>>> mvn test -P bridge
>>>
>>> You should see two files:
>>>
>>> target/bridge.data
>>> target/bridge.out
>>>
>>> These should have the same contents. The .data file is written by the java program, and the .out file is the stdout captured from the c program with its view of the data.
>>>
>>> This should fix running TestU01.
>>>
>>> BUT I’ve not had time to determine how Dieharder is reading the stdin. Given it is a c library it may be reading it using little endian as well. I’ll look into that next.
>>>
>>> Composite update:
>>>
>>> For some reason all my BigCrush simulations crashed. It could be a RAM issue. The runs did take longer than expected but I did not monitor memory usage. I’ve started them again but using only the serial composite. I think the xor one is really broken.
>>>
>>> FYI. Using the new bridge code with 3 runs of SmallCrush finds [6, 6, 6] / 15 failed tested for the serial composite and [9, 9, 10] / 15 for the xor composite.
>>>
>>> I’m expecting BigCrush to fail a lot. I’m now more interested in seeing if it will complete.
>>>
>>> Alex
>>>
>>
>>
>> PS. Thinking about the endianness it might not matter. The test suite ideally will be able to detect if the bits are not random in the lower or upper most significant byte of the 32 bits. I.e. it should always find a problem. I am not clear if this is the case. I have read that some generators can pass BigCrush but fail if the bits are reversed (not the bytes but the bits). I’m happy to think that endianness is not an issue.
>>
>> It was a good exercise in debugging if the bridge was working though.
>>
>> One actual issue is that we are testing long providers using the long to create 2 int values. Should we test using a series of the upper 32 bits and then a series of the lower 32 bits?
>
> Is that useful since the test now sees the integers as they are produced (i.e. 2
> values per long)?
>
It is not relevant if you are concerned about int quality. But if you are concerned about long quality then it is relevant. The long quality is important for the quality of nextDouble(). Although in that case only the upper 53 bits of the long. This means that the quality of a long from an int provider is also not covered by the benchmark as that would require testing alternating ints twice using the series: 1, 3, 5…, 2n+1 and 2, 4, 6, … 2n.
Given that half of the int values were previously discarded from the BigCrush analysis, the current results on the user guide page actually represent BigCrush running on the upper 32-bits of the long, byte reversed due to the big/little endian interpretation of the bytes in Java and linux.
So maybe the an update to the RandomStressTester to support analysis for int or long quality is needed. For now the quality section on the website should just state that the quality is for the ‘nextInt()’ method of the RNG.
I have the results of BigCrush using the new bridge c program:
XorShiftSerialComposite : 40, 39, 39 : 608.2 +/- 3.9
So it fails.
The XorShiftXorComposite crashed after 2 hours about 1/4 of the results file complete. I am running again so I can monitor it for memory usage. Something in the BigCrush suite just cannot handle this generator output.
Alex
> Gilles
>
>> I may set an unused workstation on this task to see what happens.
>>
>> Alex
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org <ma...@commons.apache.org>
> For additional commands, e-mail: dev-help@commons.apache.org <ma...@commons.apache.org>
Re: [Rng] New XoShiRo generators
Posted by Gilles Sadowski <gi...@gmail.com>.
Le dim. 17 mars 2019 à 01:01, Alex Herbert <al...@gmail.com> a écrit :
>
>
>
> > On 16 Mar 2019, at 23:10, Alex Herbert <al...@gmail.com> wrote:
> >
> >
> >
> >> On 16 Mar 2019, at 02:54, Gilles Sadowski <gilleseran@gmail.com <ma...@gmail.com>> wrote:
> >>> This is read by dieharder which directly reads from stdin. This worked to collect all the generated bits and the serial and xor composites failed the test suite.
> >>>
> >>> It is also read by the stdin2testu01.c program to pass to TestU01.
> >>>
> >>> What is happening is that the stdin2testu01.c is reading 64-bits using an unsigned long.
> >>
> >> I don't remember why I wrote that, but as you pointed outit now looks
> >> like a plain bug.
> >
> > It may be more complicated again...
> >
> > I’ve had a play around with the data being pushed through to the testU01 library using the c bridge. I wanted to check that the int value that is generated by the RNG is passed through to the c program. So I wrote a simple BridgeTester class to do this. It writes all the int values to a data file (for reference) then passes them to the c executable with the same method as the RandomStressTester. I then modified the stdin2testu01.c program to have an extra hidden debug mode where all the data is just written to stdout.
> >
> > I found the data file written from Java did not match the data that the c program had. I bit more digging found that the problem was that Java uses a big endian representation and the c program is little endian. This is true on my linux and Mac OSX platforms. So the raw bytes read from stdin are in the wrong order.
> >
> > When I updated the program to self detect endianness and swap the byte order of each set of 4 bytes from the stdin then the data in the c program matched the original.
> >
> > Since it was non destructive to the module I added all this to master. You can see this working by rebuilding the c bridge and running the new profile to test it:
> >
> > > cd commons-rng-examples/examples-stress
> > > gcc src/main/c/stdin2testu01.c -o stdin2testu01 -ltestu01 -ltestu01probdist -ltestu01mylib -lm
> > > mvn test -P bridge
> >
> > You should see two files:
> >
> > target/bridge.data
> > target/bridge.out
> >
> > These should have the same contents. The .data file is written by the java program, and the .out file is the stdout captured from the c program with its view of the data.
> >
> > This should fix running TestU01.
> >
> > BUT I’ve not had time to determine how Dieharder is reading the stdin. Given it is a c library it may be reading it using little endian as well. I’ll look into that next.
> >
> > Composite update:
> >
> > For some reason all my BigCrush simulations crashed. It could be a RAM issue. The runs did take longer than expected but I did not monitor memory usage. I’ve started them again but using only the serial composite. I think the xor one is really broken.
> >
> > FYI. Using the new bridge code with 3 runs of SmallCrush finds [6, 6, 6] / 15 failed tested for the serial composite and [9, 9, 10] / 15 for the xor composite.
> >
> > I’m expecting BigCrush to fail a lot. I’m now more interested in seeing if it will complete.
> >
> > Alex
> >
>
>
> PS. Thinking about the endianness it might not matter. The test suite ideally will be able to detect if the bits are not random in the lower or upper most significant byte of the 32 bits. I.e. it should always find a problem. I am not clear if this is the case. I have read that some generators can pass BigCrush but fail if the bits are reversed (not the bytes but the bits). I’m happy to think that endianness is not an issue.
>
> It was a good exercise in debugging if the bridge was working though.
>
> One actual issue is that we are testing long providers using the long to create 2 int values. Should we test using a series of the upper 32 bits and then a series of the lower 32 bits?
Is that useful since the test now sees the integers as they are produced (i.e. 2
values per long)?
Gilles
> I may set an unused workstation on this task to see what happens.
>
> Alex
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [Rng] New XoShiRo generators
Posted by Alex Herbert <al...@gmail.com>.
> On 16 Mar 2019, at 23:10, Alex Herbert <al...@gmail.com> wrote:
>
>
>
>> On 16 Mar 2019, at 02:54, Gilles Sadowski <gilleseran@gmail.com <ma...@gmail.com>> wrote:
>>> This is read by dieharder which directly reads from stdin. This worked to collect all the generated bits and the serial and xor composites failed the test suite.
>>>
>>> It is also read by the stdin2testu01.c program to pass to TestU01.
>>>
>>> What is happening is that the stdin2testu01.c is reading 64-bits using an unsigned long.
>>
>> I don't remember why I wrote that, but as you pointed outit now looks
>> like a plain bug.
>
> It may be more complicated again...
>
> I’ve had a play around with the data being pushed through to the testU01 library using the c bridge. I wanted to check that the int value that is generated by the RNG is passed through to the c program. So I wrote a simple BridgeTester class to do this. It writes all the int values to a data file (for reference) then passes them to the c executable with the same method as the RandomStressTester. I then modified the stdin2testu01.c program to have an extra hidden debug mode where all the data is just written to stdout.
>
> I found the data file written from Java did not match the data that the c program had. I bit more digging found that the problem was that Java uses a big endian representation and the c program is little endian. This is true on my linux and Mac OSX platforms. So the raw bytes read from stdin are in the wrong order.
>
> When I updated the program to self detect endianness and swap the byte order of each set of 4 bytes from the stdin then the data in the c program matched the original.
>
> Since it was non destructive to the module I added all this to master. You can see this working by rebuilding the c bridge and running the new profile to test it:
>
> > cd commons-rng-examples/examples-stress
> > gcc src/main/c/stdin2testu01.c -o stdin2testu01 -ltestu01 -ltestu01probdist -ltestu01mylib -lm
> > mvn test -P bridge
>
> You should see two files:
>
> target/bridge.data
> target/bridge.out
>
> These should have the same contents. The .data file is written by the java program, and the .out file is the stdout captured from the c program with its view of the data.
>
> This should fix running TestU01.
>
> BUT I’ve not had time to determine how Dieharder is reading the stdin. Given it is a c library it may be reading it using little endian as well. I’ll look into that next.
>
> Composite update:
>
> For some reason all my BigCrush simulations crashed. It could be a RAM issue. The runs did take longer than expected but I did not monitor memory usage. I’ve started them again but using only the serial composite. I think the xor one is really broken.
>
> FYI. Using the new bridge code with 3 runs of SmallCrush finds [6, 6, 6] / 15 failed tested for the serial composite and [9, 9, 10] / 15 for the xor composite.
>
> I’m expecting BigCrush to fail a lot. I’m now more interested in seeing if it will complete.
>
> Alex
>
PS. Thinking about the endianness it might not matter. The test suite ideally will be able to detect if the bits are not random in the lower or upper most significant byte of the 32 bits. I.e. it should always find a problem. I am not clear if this is the case. I have read that some generators can pass BigCrush but fail if the bits are reversed (not the bytes but the bits). I’m happy to think that endianness is not an issue.
It was a good exercise in debugging if the bridge was working though.
One actual issue is that we are testing long providers using the long to create 2 int values. Should we test using a series of the upper 32 bits and then a series of the lower 32 bits? I may set an unused workstation on this task to see what happens.
Alex
Re: [Rng] New XoShiRo generators
Posted by Alex Herbert <al...@gmail.com>.
> On 16 Mar 2019, at 02:54, Gilles Sadowski <gi...@gmail.com> wrote:
>> This is read by dieharder which directly reads from stdin. This worked to collect all the generated bits and the serial and xor composites failed the test suite.
>>
>> It is also read by the stdin2testu01.c program to pass to TestU01.
>>
>> What is happening is that the stdin2testu01.c is reading 64-bits using an unsigned long.
>
> I don't remember why I wrote that, but as you pointed outit now looks
> like a plain bug.
It may be more complicated again...
I’ve had a play around with the data being pushed through to the testU01 library using the c bridge. I wanted to check that the int value that is generated by the RNG is passed through to the c program. So I wrote a simple BridgeTester class to do this. It writes all the int values to a data file (for reference) then passes them to the c executable with the same method as the RandomStressTester. I then modified the stdin2testu01.c program to have an extra hidden debug mode where all the data is just written to stdout.
I found the data file written from Java did not match the data that the c program had. I bit more digging found that the problem was that Java uses a big endian representation and the c program is little endian. This is true on my linux and Mac OSX platforms. So the raw bytes read from stdin are in the wrong order.
When I updated the program to self detect endianness and swap the byte order of each set of 4 bytes from the stdin then the data in the c program matched the original.
Since it was non destructive to the module I added all this to master. You can see this working by rebuilding the c bridge and running the new profile to test it:
> cd commons-rng-examples/examples-stress
> gcc src/main/c/stdin2testu01.c -o stdin2testu01 -ltestu01 -ltestu01probdist -ltestu01mylib -lm
> mvn test -P bridge
You should see two files:
target/bridge.data
target/bridge.out
These should have the same contents. The .data file is written by the java program, and the .out file is the stdout captured from the c program with its view of the data.
This should fix running TestU01.
BUT I’ve not had time to determine how Dieharder is reading the stdin. Given it is a c library it may be reading it using little endian as well. I’ll look into that next.
Composite update:
For some reason all my BigCrush simulations crashed. It could be a RAM issue. The runs did take longer than expected but I did not monitor memory usage. I’ve started them again but using only the serial composite. I think the xor one is really broken.
FYI. Using the new bridge code with 3 runs of SmallCrush finds [6, 6, 6] / 15 failed tested for the serial composite and [9, 9, 10] / 15 for the xor composite.
I’m expecting BigCrush to fail a lot. I’m now more interested in seeing if it will complete.
Alex
Re: [Rng] New XoShiRo generators
Posted by Gilles Sadowski <gi...@gmail.com>.
Hi.
Le ven. 15 mars 2019 à 19:00, Alex Herbert <al...@gmail.com> a écrit :
>
>
>
> > On 15 Mar 2019, at 17:37, Gilles Sadowski <gi...@gmail.com> wrote:
> >
> > Hi Alex.
> >
> > Le ven. 15 mars 2019 à 14:08, Alex Herbert <al...@gmail.com> a écrit :
> >>
> >> FYI.
> >>
> >>> I am going to update stdin2testu01.c so that it passes all the input bits to TestU01 and try again.
> >>>
> >>> I’ve read some of the code and manual of TestU01 and the values that are returned from the unif01_Gen->GetBits method (unsigned long) are assumed to be 32-bit unsigned. So I think just changing stdin2testu01.c to read the buffer using uint32_t should work.
> >>>
> >>
> >> When reading the stdin using a uint32_t for BigCrush I am already seeing a lot of failures for the composites.
> >
> > Thanks for the update.
> > It's not clear to me why the other version of the interfacing code
> > would be more forgiving.
> >
>
> The benchmark program RandomStressTester exclusively uses nextInt() to write to the output.
Yes. I recall this was mandated to allow testing with DieHarder.
>
> This is read by dieharder which directly reads from stdin. This worked to collect all the generated bits and the serial and xor composites failed the test suite.
>
> It is also read by the stdin2testu01.c program to pass to TestU01.
>
> What is happening is that the stdin2testu01.c is reading 64-bits using an unsigned long.
I don't remember why I wrote that, but as you pointed outit now looks
like a plain bug.
> This is then cast to an unsigned int at 32-bits and given to TestU01. This leads to loss of 32-bits of information.
>
> So every second int from the RNG nextInt() method is ignored.
>
> This means that the serial composite I created that was testing alternate generators was in fact only testing one generator as all the ints from the second generator were skipped.
Got it. Thanks.
Gilles
>
> It does not however explain why the xor composite passed (with a few failures) as this would have an int created from a xor of both generators. However the composite ints would still have every second sample discarded so the xor was testing a xor of the upper 32-bits of the long from each generator. This had enough variability to pass the tests. The lower 32-bits (which Dieharder was also using) may not.
>
> Anyway the serial tests are now about 2/3 of the way through and there are currently the following rough counts of failures:
>
> grep -c ' \*\*\*\*\*' serial_* xor*
> serial_1:85
> serial_2:64
> serial_3:82
>
> Lots. The xor composite has been stalled on the current test (no more output) for the last 6 hours. So the generator takes a long time to be tested although I’m not sure why.
>
> > Gilles
> >
> >>
> >> Results should be complete before the end of today.
> >>
> >> Alex
> >>
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [Rng] New XoShiRo generators
Posted by Alex Herbert <al...@gmail.com>.
> On 15 Mar 2019, at 17:37, Gilles Sadowski <gi...@gmail.com> wrote:
>
> Hi Alex.
>
> Le ven. 15 mars 2019 à 14:08, Alex Herbert <al...@gmail.com> a écrit :
>>
>> FYI.
>>
>>> I am going to update stdin2testu01.c so that it passes all the input bits to TestU01 and try again.
>>>
>>> I’ve read some of the code and manual of TestU01 and the values that are returned from the unif01_Gen->GetBits method (unsigned long) are assumed to be 32-bit unsigned. So I think just changing stdin2testu01.c to read the buffer using uint32_t should work.
>>>
>>
>> When reading the stdin using a uint32_t for BigCrush I am already seeing a lot of failures for the composites.
>
> Thanks for the update.
> It's not clear to me why the other version of the interfacing code
> would be more forgiving.
>
The benchmark program RandomStressTester exclusively uses nextInt() to write to the output.
This is read by dieharder which directly reads from stdin. This worked to collect all the generated bits and the serial and xor composites failed the test suite.
It is also read by the stdin2testu01.c program to pass to TestU01.
What is happening is that the stdin2testu01.c is reading 64-bits using an unsigned long. This is then cast to an unsigned int at 32-bits and given to TestU01. This leads to loss of 32-bits of information.
So every second int from the RNG nextInt() method is ignored.
This means that the serial composite I created that was testing alternate generators was in fact only testing one generator as all the ints from the second generator were skipped.
It does not however explain why the xor composite passed (with a few failures) as this would have an int created from a xor of both generators. However the composite ints would still have every second sample discarded so the xor was testing a xor of the upper 32-bits of the long from each generator. This had enough variability to pass the tests. The lower 32-bits (which Dieharder was also using) may not.
Anyway the serial tests are now about 2/3 of the way through and there are currently the following rough counts of failures:
grep -c ' \*\*\*\*\*' serial_* xor*
serial_1:85
serial_2:64
serial_3:82
Lots. The xor composite has been stalled on the current test (no more output) for the last 6 hours. So the generator takes a long time to be tested although I’m not sure why.
> Gilles
>
>>
>> Results should be complete before the end of today.
>>
>> Alex
>>
>>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
> For additional commands, e-mail: dev-help@commons.apache.org
>
Re: [Rng] New XoShiRo generators
Posted by Gilles Sadowski <gi...@gmail.com>.
Hi Alex.
Le ven. 15 mars 2019 à 14:08, Alex Herbert <al...@gmail.com> a écrit :
>
> FYI.
>
> > I am going to update stdin2testu01.c so that it passes all the input bits to TestU01 and try again.
> >
> > I’ve read some of the code and manual of TestU01 and the values that are returned from the unif01_Gen->GetBits method (unsigned long) are assumed to be 32-bit unsigned. So I think just changing stdin2testu01.c to read the buffer using uint32_t should work.
> >
>
> When reading the stdin using a uint32_t for BigCrush I am already seeing a lot of failures for the composites.
Thanks for the update.
It's not clear to me why the other version of the interfacing code
would be more forgiving.
Gilles
>
> Results should be complete before the end of today.
>
> Alex
>
>
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [Rng] New XoShiRo generators
Posted by Alex Herbert <al...@gmail.com>.
FYI.
> I am going to update stdin2testu01.c so that it passes all the input bits to TestU01 and try again.
>
> I’ve read some of the code and manual of TestU01 and the values that are returned from the unif01_Gen->GetBits method (unsigned long) are assumed to be 32-bit unsigned. So I think just changing stdin2testu01.c to read the buffer using uint32_t should work.
>
When reading the stdin using a uint32_t for BigCrush I am already seeing a lot of failures for the composites.
Results should be complete before the end of today.
Alex
Re: [Rng] New XoShiRo generators
Posted by Alex Herbert <al...@gmail.com>.
> On 14 Mar 2019, at 14:10, Alex Herbert <al...@gmail.com> wrote:
>
> Sorry, my earlier message was truncated.
>
> On 13/03/2019 18:31, Gilles Sadowski wrote:
>>
>>> 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
> BigCrush has finally finished:
>
> XorShiftXorComposite : 0, 3, 0
> XorShiftSerialComposite : 0, 0, 0
> SplitXorComposite : 0, 1, 0
>
> These results are actually not bad.
>
> I am wondering about the Dieharder results. I think that originally I did a xor operation on nextLong for the XorShiftXorComposite. Although it should not matter (due to caching of nextLong() to produce ints) I will redo this using nextInt for all composites as I just did for BigCrush. Dieharder did take an extremely long time so to make sure I will repeat Dieharder after a machine reboot. A linux update to c libraries may have affected it.
>
> Alex
>
I re-ran Dieharder. It still fails a lot.
XorShiftXorComposite : 88, 105, 89 : 396.2 +/- 9.9
XorShiftSerialComposite : 24, 25, 23 : 134.1 +/- 16.1
SplitXorComposite : 0, 0, 0 : 90.8 +/- 21.9
The numbers at the end are the average and SD of the run time in minutes.
So the good generator passes the test suite OK in 90 minutes. The bad generator takes over 6 hours and fails a lot. When I was periodically checking the results for completion I think this time is mainly spent in the rgb_kstest_test. But why that takes so long I do not know. It fails for the XorShiftXorComposite but passes for the XorShiftSerialComposite.
All results are now posted to the RNG-82 jira ticket.
Q. Whether to deprecate the XOR_SHIFT_1024_S?
- Dieharder says yes
- BigCrush says no (WHY?)
I have investigated whether the c code for calling TestU01 is not passing the values through. A quick look at the stdin2testu01.c code here:
unsigned long nextInt(void *par,
void *sta) {
StdinReader_state *state = (StdinReader_state *) sta;
if (state->index >= BUFFER_LENGTH) {
/* Refill. */
fread(state->buffer, sizeof(unsigned long), BUFFER_LENGTH, stdin);
state->index = 0;
}
uint32_t random = state->buffer[state->index];
++state->index; /* Next request. */
return random;
}
state->buffer is a long and is read as a long. This is then used to return a uint32_t which is a 32-bit unsigned.
The c standard for long states that it can be 32-bits or more! So to check what happens on my 64-bit test machine:
#include <stdio.h>
#include <limits.h>
#include <stdint.h>
int main(void){
printf("sizeof(int) = %d\n", (int)sizeof(int));
printf("sizeof(long) = %d\n", (int)sizeof(long));
printf("sizeof(unsigned long) = %d\n", (int)sizeof(unsigned long));
printf("sizeof(uint32_t) = %d\n", (int)sizeof(uint32_t));
printf("sizeof(double) = %d\n", (int)sizeof(double));
unsigned long value = 1;
for (int i = 1; i <= 8 * (int)sizeof(unsigned long); i++) {
printf("[%d] %lu = %u\n", i, value, (uint32_t) value);
value = (value << 1);
}
return 0;
}
> gcc test.c && ./a.out
sizeof(int) = 4
sizeof(long) = 8
sizeof(unsigned long) = 8
sizeof(uint32_t) = 4
sizeof(double) = 8
…
[31] 1073741824 = 1073741824
[32] 2147483648 = 2147483648
[33] 4294967296 = 0
[34] 8589934592 = 0
…
ERROR: It seems my machine thinks a long is 8 bytes but the test code in stdin2testu01.c assumes it is 4 bytes! So when the long is cast to uint32_t the upper 32-bits are lost.
This means that the test suite run on my machine for TestU01 is passing alternating ints from UniformRandomProvider nextInt() through to the TestU01 test suite.
It may help explain why the test takes so long because it has to generate twice as many numbers.
Can you check your standard stress test environment for the size of (unsigned long) using the above code?
Note: This does not make the BigCrush results invalid for a standard long provider. But it does means that the BigCrush results correspond to the lower 32-bits from the long.
For an int provider it means that alternative ints are ignored. That is not good.
I am going to update stdin2testu01.c so that it passes all the input bits to TestU01 and try again.
I’ve read some of the code and manual of TestU01 and the values that are returned from the unif01_Gen->GetBits method (unsigned long) are assumed to be 32-bit unsigned. So I think just changing stdin2testu01.c to read the buffer using uint32_t should work.
Alex
Re: [Rng] New XoShiRo generators
Posted by Alex Herbert <al...@gmail.com>.
Sorry, my earlier message was truncated.
On 13/03/2019 18:31, Gilles Sadowski wrote:
>
>> 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
BigCrush has finally finished:
XorShiftXorComposite : 0, 3, 0
XorShiftSerialComposite : 0, 0, 0
SplitXorComposite : 0, 1, 0
These results are actually not bad.
I am wondering about the Dieharder results. I think that originally I
did a xor operation on nextLong for the XorShiftXorComposite. Although
it should not matter (due to caching of nextLong() to produce ints) I
will redo this using nextInt for all composites as I just did for
BigCrush. Dieharder did take an extremely long time so to make sure I
will repeat Dieharder after a machine reboot. A linux update to c
libraries may have affected it.
Alex
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [Rng] New XoShiRo generators
Posted by Alex Herbert <al...@gmail.com>.
On 13/03/2019 18:31, Gilles Sadowski wrote:
>>
>> 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
BigCrush has finally finished:
XorShiftSerialComposite : 0, 0, 0
XorShiftXorComposite : 0, 3, 0SplitXorComposite : 0, 1, 0
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [Rng] New XoShiRo generators
Posted by Gilles Sadowski <gi...@gmail.com>.
Hello Alex.
Le mer. 13 mars 2019 à 15:37, Alex Herbert <al...@gmail.com> a écrit :
>
> On 13/03/2019 02:20, Gilles Sadowski wrote:
> > Le mar. 12 mars 2019 à 22:34, Alex Herbert <al...@gmail.com> a écrit :
> >>
> >>
> >>> On 12 Mar 2019, at 17:12, Gilles Sadowski <gi...@gmail.com> wrote:
> >>>
> >>> [Replying to list.]
> >>>
> >>> Le mar. 12 mars 2019 à 15:39, Alex Herbert <alex.d.herbert@gmail.com <ma...@gmail.com>> a écrit :
> >>>>
> >>>> On 12/03/2019 15:33, Gilles Sadowski wrote:
> >>>>
> >>>> Hi Alex.
> >>>>
> >>>> Le mar. 12 mars 2019 à 12:53, Alex Herbert <al...@gmail.com> a écrit :
> >>>>
> >>>> On 11/03/2019 23:44, Gilles Sadowski wrote:
> >>>>
> >>>> Hello.
> >>>>
> >>>> Le jeu. 7 mars 2019 à 00:44, Alex Herbert <al...@gmail.com> a écrit :
> >>>>
> >>>> On 6 Mar 2019, at 22:57, Gilles Sadowski <gi...@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-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [Rng] New XoShiRo generators
Posted by Alex Herbert <al...@gmail.com>.
On 13/03/2019 02:20, Gilles Sadowski wrote:
> Le mar. 12 mars 2019 à 22:34, Alex Herbert <al...@gmail.com> a écrit :
>>
>>
>>> On 12 Mar 2019, at 17:12, Gilles Sadowski <gi...@gmail.com> wrote:
>>>
>>> [Replying to list.]
>>>
>>> Le mar. 12 mars 2019 à 15:39, Alex Herbert <alex.d.herbert@gmail.com <ma...@gmail.com>> a écrit :
>>>>
>>>> On 12/03/2019 15:33, Gilles Sadowski wrote:
>>>>
>>>> Hi Alex.
>>>>
>>>> Le mar. 12 mars 2019 à 12:53, Alex Herbert <al...@gmail.com> a écrit :
>>>>
>>>> On 11/03/2019 23:44, Gilles Sadowski wrote:
>>>>
>>>> Hello.
>>>>
>>>> Le jeu. 7 mars 2019 à 00:44, Alex Herbert <al...@gmail.com> a écrit :
>>>>
>>>> On 6 Mar 2019, at 22:57, Gilles Sadowski <gi...@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
This shows that a combined generator using two different variants of
XorShift1024 is not good. So the two XorShift1024 generators are
correlated. Evidence for deprecation.
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-unsubscribe@commons.apache.org <ma...@commons.apache.org>
>>> For additional commands, e-mail: dev-help@commons.apache.org <ma...@commons.apache.org>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
> For additional commands, e-mail: dev-help@commons.apache.org
>
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [Rng] New XoShiRo generators
Posted by Gilles Sadowski <gi...@gmail.com>.
Le mar. 12 mars 2019 à 22:34, Alex Herbert <al...@gmail.com> a écrit :
>
>
>
> > On 12 Mar 2019, at 17:12, Gilles Sadowski <gi...@gmail.com> wrote:
> >
> > [Replying to list.]
> >
> > Le mar. 12 mars 2019 à 15:39, Alex Herbert <alex.d.herbert@gmail.com <ma...@gmail.com>> a écrit :
> >>
> >>
> >> On 12/03/2019 15:33, Gilles Sadowski wrote:
> >>
> >> Hi Alex.
> >>
> >> Le mar. 12 mars 2019 à 12:53, Alex Herbert <al...@gmail.com> a écrit :
> >>
> >> On 11/03/2019 23:44, Gilles Sadowski wrote:
> >>
> >> Hello.
> >>
> >> Le jeu. 7 mars 2019 à 00:44, Alex Herbert <al...@gmail.com> a écrit :
> >>
> >> On 6 Mar 2019, at 22:57, Gilles Sadowski <gi...@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-unsubscribe@commons.apache.org <ma...@commons.apache.org>
> > For additional commands, e-mail: dev-help@commons.apache.org <ma...@commons.apache.org>
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [Rng] New XoShiRo generators
Posted by Alex Herbert <al...@gmail.com>.
> On 12 Mar 2019, at 17:12, Gilles Sadowski <gi...@gmail.com> wrote:
>
> [Replying to list.]
>
> Le mar. 12 mars 2019 à 15:39, Alex Herbert <alex.d.herbert@gmail.com <ma...@gmail.com>> a écrit :
>>
>>
>> On 12/03/2019 15:33, Gilles Sadowski wrote:
>>
>> Hi Alex.
>>
>> Le mar. 12 mars 2019 à 12:53, Alex Herbert <al...@gmail.com> a écrit :
>>
>> On 11/03/2019 23:44, Gilles Sadowski wrote:
>>
>> Hello.
>>
>> Le jeu. 7 mars 2019 à 00:44, Alex Herbert <al...@gmail.com> a écrit :
>>
>> On 6 Mar 2019, at 22:57, Gilles Sadowski <gi...@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.
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.
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.
Note that % 2 will break if it overflows to negative. 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-unsubscribe@commons.apache.org <ma...@commons.apache.org>
> For additional commands, e-mail: dev-help@commons.apache.org <ma...@commons.apache.org>
Re: [Rng] New XoShiRo generators
Posted by Gilles Sadowski <gi...@gmail.com>.
[Replying to list.]
Le mar. 12 mars 2019 à 15:39, Alex Herbert <al...@gmail.com> a écrit :
>
>
> On 12/03/2019 15:33, Gilles Sadowski wrote:
>
> Hi Alex.
>
> Le mar. 12 mars 2019 à 12:53, Alex Herbert <al...@gmail.com> a écrit :
>
> On 11/03/2019 23:44, Gilles Sadowski wrote:
>
> Hello.
>
> Le jeu. 7 mars 2019 à 00:44, Alex Herbert <al...@gmail.com> a écrit :
>
> On 6 Mar 2019, at 22:57, Gilles Sadowski <gi...@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).
> 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: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [Rng] New XoShiRo generators
Posted by Gilles Sadowski <gi...@gmail.com>.
Hello.
Le jeu. 7 mars 2019 à 00:44, Alex Herbert <al...@gmail.com> a écrit :
>
>
>
> > On 6 Mar 2019, at 22:57, Gilles Sadowski <gi...@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?
Gilles
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [Rng] New XoShiRo generators
Posted by Alex Herbert <al...@gmail.com>.
> On 6 Mar 2019, at 22:57, Gilles Sadowski <gi...@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.
Re: [Rng] New XoShiRo generators
Posted by Gilles Sadowski <gi...@gmail.com>.
Le mer. 6 mars 2019 à 23:07, Alex Herbert <al...@gmail.com> a écrit :>
> >
> > On 6 Mar 2019, at 21:42, Alex Herbert <al...@gmail.com> wrote:
> >
> >
> >
> >> On 6 Mar 2019, at 21:24, Gilles Sadowski <gi...@gmail.com> wrote:
> >>
> >> Hello.
> >>
> >> Le mer. 6 mars 2019 à 21:49, Alex Herbert <al...@gmail.com> a écrit :
> >>>
> >>>
> >>>
> >>>> On 6 Mar 2019, at 17:11, Gilles Sadowski <gi...@gmail.com> wrote:
> >>>>
> >>>> Do the two variants produce uncorrelated sequences?
> >>>
> >>> I will test this when I branch a new PR for just this code.
> >>
> >> IMHO, it's strange that there would be 2 sources of randomness in a single
> >> implementation.
> >> Concretely: If one needs a fast "int" provider, and a fast "long" provider, I'd
> >> consider the simpler solution of using 2 different providers.
> >
> > I think this has crossed wires somewhere. I was talking about the variant of the XorShift1024Star algorithm and whether XorShift1024Star should be deprecated in favour of XorShift1024StarPhi.
In the above quote, I was referring to the override of "nextInt()" in
"SplitMix64".
> >
> > The variant of the SplitMix64 algorithm for producing ints was tested in a benchmark that I am prepared to throw away. The results are in the Jira ticket. The way the SplittableRandom creates an int is slightly slower than the method used in [RNG] SplitMix64 which divides the long in half.
I'm not sure I understand correctly, but I'd not aim at copying how
"SplittableRandom" produces each type of sequences if it is at odd
with the component's design: one source (either "int" or "long"), and
one way to generate each of the other types.
> This ticket can be closed as done and I’ll add a comment that no speed improvement was found.
> >
> > I agree that this variant algorithm should have been in a new provider.
So, we agree.
> It would produce a different output of bytes since the bit shift in the second step is different. But I’m not going to add this algorithm so it does not matter.
OK.
> >
> > 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).
Regards,
Gilles
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [Rng] New XoShiRo generators
Posted by Alex Herbert <al...@gmail.com>.
>
> On 6 Mar 2019, at 21:42, Alex Herbert <al...@gmail.com> wrote:
>
>
>
>> On 6 Mar 2019, at 21:24, Gilles Sadowski <gi...@gmail.com> wrote:
>>
>> Hello.
>>
>> Le mer. 6 mars 2019 à 21:49, Alex Herbert <al...@gmail.com> a écrit :
>>>
>>>
>>>
>>>> On 6 Mar 2019, at 17:11, Gilles Sadowski <gi...@gmail.com> wrote:
>>>>
>>>> Do the two variants produce uncorrelated sequences?
>>>
>>> I will test this when I branch a new PR for just this code.
>>
>> IMHO, it's strange that there would be 2 sources of randomness in a single
>> implementation.
>> Concretely: If one needs a fast "int" provider, and a fast "long" provider, I'd
>> consider the simpler solution of using 2 different providers.
>
> I think this has crossed wires somewhere. I was talking about the variant of the XorShift1024Star algorithm and whether XorShift1024Star should be deprecated in favour of XorShift1024StarPhi.
>
> The variant of the SplitMix64 algorithm for producing ints was tested in a benchmark that I am prepared to throw away. The results are in the Jira ticket. The way the SplittableRandom creates an int is slightly slower than the method used in [RNG] SplitMix64 which divides the long in half. This ticket can be closed as done and I’ll add a comment that no speed improvement was found.
>
> I agree that this variant algorithm should have been in a new provider. It would produce a different output of bytes since the bit shift in the second step is different. But I’m not going to add this algorithm so it does not matter.
>
> 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?
>>
>> ---------------------------------------------------------------------
>> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
>> For additional commands, e-mail: dev-help@commons.apache.org
>>
>
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [Rng] New XoShiRo generators
Posted by Alex Herbert <al...@gmail.com>.
> On 6 Mar 2019, at 21:24, Gilles Sadowski <gi...@gmail.com> wrote:
>
> Hello.
>
> Le mer. 6 mars 2019 à 21:49, Alex Herbert <al...@gmail.com> a écrit :
>>
>>
>>
>>> On 6 Mar 2019, at 17:11, Gilles Sadowski <gi...@gmail.com> wrote:
>>>
>>> Do the two variants produce uncorrelated sequences?
>>
>> I will test this when I branch a new PR for just this code.
>
> IMHO, it's strange that there would be 2 sources of randomness in a single
> implementation.
> Concretely: If one needs a fast "int" provider, and a fast "long" provider, I'd
> consider the simpler solution of using 2 different providers.
I think this has crossed wires somewhere. I was talking about the variant of the XorShift1024Star algorithm and whether XorShift1024Star should be deprecated in favour of XorShift1024StarPhi.
The variant of the SplitMix64 algorithm for producing ints was tested in a benchmark that I am prepared to throw away. The results are in the Jira ticket. The way the SplittableRandom creates an int is slightly slower than the method used in [RNG] SplitMix64 which divides the long in half. This ticket can be closed as done and I’ll add a comment that no speed improvement was found.
I agree that this variant algorithm should have been in a new provider. It would produce a different output of bytes since the bit shift in the second step is different. But I’m not going to add this algorithm so it does not matter.
However I will test if XorShift1024Star and XorShift1024StarPhi are correlated just for completeness.
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
> For additional commands, e-mail: dev-help@commons.apache.org
>
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [Rng] New XoShiRo generators
Posted by Gilles Sadowski <gi...@gmail.com>.
Hello.
Le mer. 6 mars 2019 à 21:49, Alex Herbert <al...@gmail.com> a écrit :
>
>
>
> > On 6 Mar 2019, at 17:11, Gilles Sadowski <gi...@gmail.com> wrote:
> >
> > Do the two variants produce uncorrelated sequences?
>
> I will test this when I branch a new PR for just this code.
IMHO, it's strange that there would be 2 sources of randomness in a single
implementation.
Concretely: If one needs a fast "int" provider, and a fast "long" provider, I'd
consider the simpler solution of using 2 different providers.
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [Rng] New XoShiRo generators
Posted by Alex Herbert <al...@gmail.com>.
> On 6 Mar 2019, at 17:11, Gilles Sadowski <gi...@gmail.com> wrote:
>
> Do the two variants produce uncorrelated sequences?
I will test this when I branch a new PR for just this code.
Re: [Rng] New XoShiRo generators
Posted by Gilles Sadowski <gi...@gmail.com>.
Le mer. 6 mars 2019 à 17:27, Alex Herbert <al...@gmail.com> a écrit :
>
>
>
> > On 6 Mar 2019, at 16:22, Gilles Sadowski <gi...@gmail.com> wrote:
> >
> > Hi Alex.
> >
> > Le mer. 6 mars 2019 à 16:50, Alex Herbert <al...@gmail.com> a écrit :
> >>
> >> I would like to merge this PR introducing the new XoShiRo generators:
> >>
> >> https://github.com/apache/commons-rng/pull/20 <https://github.com/apache/commons-rng/pull/20>
> >>
> >> Can I get a review to check that nothing is obviously bad.
> >
> > * Can we indeed have separate PR/commits for the change/fix of the existing
> > "XorShift1024Star" and its improved version?
>
> I’ll move this to a new Jira and PR.
>
> Should we mark the old enum value XOR_SHIFT_1024_S as deprecated? You had previously mentioned that. The algorithm is not really broken. It has just been made better so I was thinking no.
Do the two variants produce uncorrelated sequences?
>
> > * Is it possible for the abstract classes to be package-private?
> > [I've just noticed that "AbstractWell" should have been made so too.]
>
> OK.
>
Thanks,
Gilles
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [Rng] New XoShiRo generators
Posted by Alex Herbert <al...@gmail.com>.
> On 6 Mar 2019, at 16:22, Gilles Sadowski <gi...@gmail.com> wrote:
>
> Hi Alex.
>
> Le mer. 6 mars 2019 à 16:50, Alex Herbert <al...@gmail.com> a écrit :
>>
>> I would like to merge this PR introducing the new XoShiRo generators:
>>
>> https://github.com/apache/commons-rng/pull/20 <https://github.com/apache/commons-rng/pull/20>
>>
>> Can I get a review to check that nothing is obviously bad.
>
> * Can we indeed have separate PR/commits for the change/fix of the existing
> "XorShift1024Star" and its improved version?
I’ll move this to a new Jira and PR.
Should we mark the old enum value XOR_SHIFT_1024_S as deprecated? You had previously mentioned that. The algorithm is not really broken. It has just been made better so I was thinking no.
> * Is it possible for the abstract classes to be package-private?
> [I've just noticed that "AbstractWell" should have been made so too.]
OK.
>
> Reg
>>
>> Thanks,
>>
>> Alex
>>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
> For additional commands, e-mail: dev-help@commons.apache.org
>
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [Rng] New XoShiRo generators
Posted by Gilles Sadowski <gi...@gmail.com>.
Hi Alex.
Le mer. 6 mars 2019 à 16:50, Alex Herbert <al...@gmail.com> a écrit :
>
> I would like to merge this PR introducing the new XoShiRo generators:
>
> https://github.com/apache/commons-rng/pull/20 <https://github.com/apache/commons-rng/pull/20>
>
> Can I get a review to check that nothing is obviously bad.
* Can we indeed have separate PR/commits for the change/fix of the existing
"XorShift1024Star" and its improved version?
* Is it possible for the abstract classes to be package-private?
[I've just noticed that "AbstractWell" should have been made so too.]
Reg
>
> Thanks,
>
> Alex
>
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org