[jira] [Commented] (RNG-106) XorShiRo generators require non-zero input seeds
[
https://issues.apache.org/jira/browse/RNG-106?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16861870#comment-16861870
]
Alex D Herbert commented on RNG-106:
{quote}Do you mean: test whether {{a[0] == 0}}, and if so set {{a[0] = next()}}
?
{quote}
Yes.
> XorShiRo generators require non-zero input seeds
>
>
> Key: RNG-106
> URL: https://issues.apache.org/jira/browse/RNG-106
> Project: Commons RNG
> Issue Type: Improvement
> Components: core, simple
>Affects Versions: 1.3
>Reporter: Alex D Herbert
>Assignee: Alex D Herbert
>Priority: Major
> Fix For: 1.3
>
>
> The following generators based on Xor shifts all require non-zero seeds:
> {noformat}
> XOR_SHIFT_1024_S
> XOR_SHIFT_1024_S_PHI
> XO_RO_SHI_RO_64_S
> XO_RO_SHI_RO_64_SS
> XO_SHI_RO_128_PLUS
> XO_SHI_RO_128_SS
> XO_RO_SHI_RO_128_PLUS
> XO_RO_SHI_RO_128_SS
> XO_SHI_RO_256_PLUS
> XO_SHI_RO_256_SS
> XO_SHI_RO_512_PLUS
> XO_SHI_RO_512_SS
> {noformat}
> A zero seed results in zero output for each call to the generator.
> Tests added to the rng-core module show that only a single bit is required to
> be set and the generator is able to generate non-zero output. These tests are
> simple and do not test the output for many cycles or do statistical analysis
> on the output randomness. However the authors of the generators state that
> they require a non-zero seed and are not any more specific so I assume that a
> single bit is enough to maintain the internal state capable of randomness.
> This can be fixed with the following methods:
> # Set the final bit in the seed to 1. This will be fast but loses 1 bit of
> seed entropy.
> # Check the seed array for zeros. If the entire array is zero then generate
> a single seed value until it is non-zero in a loop and set it into the seed
> array.
> # Check the seed array for zeros. If the entire array is zero then
> re-generate the seed using recursive method call.
> Note that this is an edge case. The smallest seed uses 64 bits, others use
> 128, 256, 512, 1024 (the number of bits in the seed is the state size and is
> the number in the enum). For the worst case this will occur 1 in 2^64 times.
> Here is the robust approach:
> {code:java}
> int[] seed;
> do {
> seed = createSeed(); // Appropriate seed array generation
> } while (SeedFactory.isZero(seed);
> return seed;
> {code}
> This would add new isZero(int[]) and isZero(long[]) methods to the seed
> factory. The entire method for creating a non-zero array seed could be added
> to the SeedFactory.
> Here is the compromise approach:
> {code:java}
> int[] seed = createSeed(); // Appropriate seed array generation
> if (SeedFactory.isZero(seed)) {
> do {
> seed[0] = SeedFactory.createInt();
> } while (seed[0] == 0);
> }
> {code}
> Given the loop will happen 1 in 2^64 times the speed of the two approaches
> will differ due to how the JVM produces the final code for the hot path (i.e.
> not the edge case).
> Here is the simple approach:
> {code:java}
> // Ensure non-zero (loses 1 bit of entropy)
> return createSeed() | 1;
> {code}
> Losing 1 bit of entropy is undesirable.
> A performance test of the approaches (and variants) should be done for
> reference.
--
This message was sent by Atlassian JIRA
(v7.6.3#76005)
[jira] [Commented] (RNG-106) XorShiRo generators require non-zero input seeds
[
https://issues.apache.org/jira/browse/RNG-106?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16861605#comment-16861605
]
Gilles commented on RNG-106:
bq. setting the first value in an array to non-zero to avoid broken generators.
+1
Do you mean: test whether {{a[0] == 0}}, and if so set {{a[0] = next()}} ?
> XorShiRo generators require non-zero input seeds
>
>
> Key: RNG-106
> URL: https://issues.apache.org/jira/browse/RNG-106
> Project: Commons RNG
> Issue Type: Improvement
> Components: core, simple
>Affects Versions: 1.3
>Reporter: Alex D Herbert
>Assignee: Alex D Herbert
>Priority: Major
> Fix For: 1.3
>
>
> The following generators based on Xor shifts all require non-zero seeds:
> {noformat}
> XOR_SHIFT_1024_S
> XOR_SHIFT_1024_S_PHI
> XO_RO_SHI_RO_64_S
> XO_RO_SHI_RO_64_SS
> XO_SHI_RO_128_PLUS
> XO_SHI_RO_128_SS
> XO_RO_SHI_RO_128_PLUS
> XO_RO_SHI_RO_128_SS
> XO_SHI_RO_256_PLUS
> XO_SHI_RO_256_SS
> XO_SHI_RO_512_PLUS
> XO_SHI_RO_512_SS
> {noformat}
> A zero seed results in zero output for each call to the generator.
> Tests added to the rng-core module show that only a single bit is required to
> be set and the generator is able to generate non-zero output. These tests are
> simple and do not test the output for many cycles or do statistical analysis
> on the output randomness. However the authors of the generators state that
> they require a non-zero seed and are not any more specific so I assume that a
> single bit is enough to maintain the internal state capable of randomness.
> This can be fixed with the following methods:
> # Set the final bit in the seed to 1. This will be fast but loses 1 bit of
> seed entropy.
> # Check the seed array for zeros. If the entire array is zero then generate
> a single seed value until it is non-zero in a loop and set it into the seed
> array.
> # Check the seed array for zeros. If the entire array is zero then
> re-generate the seed using recursive method call.
> Note that this is an edge case. The smallest seed uses 64 bits, others use
> 128, 256, 512, 1024 (the number of bits in the seed is the state size and is
> the number in the enum). For the worst case this will occur 1 in 2^64 times.
> Here is the robust approach:
> {code:java}
> int[] seed;
> do {
> seed = createSeed(); // Appropriate seed array generation
> } while (SeedFactory.isZero(seed);
> return seed;
> {code}
> This would add new isZero(int[]) and isZero(long[]) methods to the seed
> factory. The entire method for creating a non-zero array seed could be added
> to the SeedFactory.
> Here is the compromise approach:
> {code:java}
> int[] seed = createSeed(); // Appropriate seed array generation
> if (SeedFactory.isZero(seed)) {
> do {
> seed[0] = SeedFactory.createInt();
> } while (seed[0] == 0);
> }
> {code}
> Given the loop will happen 1 in 2^64 times the speed of the two approaches
> will differ due to how the JVM produces the final code for the hot path (i.e.
> not the edge case).
> Here is the simple approach:
> {code:java}
> // Ensure non-zero (loses 1 bit of entropy)
> return createSeed() | 1;
> {code}
> Losing 1 bit of entropy is undesirable.
> A performance test of the approaches (and variants) should be done for
> reference.
--
This message was sent by Atlassian JIRA
(v7.6.3#76005)
[jira] [Commented] (RNG-106) XorShiRo generators require non-zero input seeds
[
https://issues.apache.org/jira/browse/RNG-106?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16861566#comment-16861566
]
Alex D Herbert commented on RNG-106:
{quote}Is it worth given the low probability that an actual seed will have a
single bit set?
{quote}
Not really. I've been pondering the best way to do this. One way is to modify
the stress test application with a new command that can poorly seed the
generator and test it. But then I couldn't decide which test to use.
There is a simple test in Dieharder that just counts the 1 bits in the output.
It should be 50%. So I've tried running the generator and checking the ratio of
1 bits in the output for blocks of n outputs. It should gradually increase to
50% showing the generator has recovered from outputting zeros. It seems the
Well generators recover after 3 cycles where a cycle is an output of the number
of bits in their state:
{noformat}
Well512
...
Element [15], Bit [10]: Iteration 1 = 0.06
Element [15], Bit [10]: Iteration 2 = 0.29
Element [15], Bit [10]: Iteration 3 = 0.47
Element [15], Bit [9]: Iteration 1 = 0.06
Element [15], Bit [9]: Iteration 2 = 0.28
Element [15], Bit [9]: Iteration 3 = 0.48
...
Well44497b
...
Element [1389], Bit [0]: Iteration 1 = 0.05
Element [1389], Bit [0]: Iteration 2 = 0.33
Element [1389], Bit [0]: Iteration 3 = 0.50
Element [1390], Bit [31]: Iteration 1 = 0.06
Element [1390], Bit [31]: Iteration 2 = 0.35
Element [1390], Bit [31]: Iteration 3 = 0.50
...
{noformat}
The XorShiRo generators recover within about 3 to 5 cycles
{noformat}
XoRoShiRo128Plus
...
Element [0], Bit [59]: Iteration 1 = 0.03
Element [0], Bit [59]: Iteration 2 = 0.16
Element [0], Bit [59]: Iteration 3 = 0.29
Element [0], Bit [59]: Iteration 4 = 0.43
Element [0], Bit [59]: Iteration 5 = 0.52
Element [0], Bit [58]: Iteration 1 = 0.03
Element [0], Bit [58]: Iteration 2 = 0.17
Element [0], Bit [58]: Iteration 3 = 0.28
Element [0], Bit [58]: Iteration 4 = 0.46
XorShift1024StarPhi
...
Element [10], Bit [10]: Iteration 1 = 0.20
Element [10], Bit [10]: Iteration 2 = 0.44
Element [10], Bit [10]: Iteration 3 = 0.46
Element [10], Bit [9]: Iteration 1 = 0.21
Element [10], Bit [9]: Iteration 2 = 0.44
Element [10], Bit [9]: Iteration 3 = 0.43
Element [10], Bit [9]: Iteration 4 = 0.47
...
{noformat}
The MWC is much slower to recover. For a state size of int[256] it takes more
than 265+ cycles to get close to 50%. This is to be expected given the
algorithm just visits each position and does a multiply with carry to the next
position. So if only 1 position has a non-zero bit it will take at least 256
cycles through the entire array for all the zeros to be cleared by a carry from
the position below. That is at least 65336 int outputs to recover.
{noformat}
...
Element [96], Bit [30]: Iteration 263 = 0.45
Element [96], Bit [30]: Iteration 264 = 0.45
Element [96], Bit [30]: Iteration 265 = 0.45
Element [96], Bit [30]: Iteration 266 = 0.45
Element [96], Bit [29]: Iteration 1 = 0.00
Element [96], Bit [29]: Iteration 2 = 0.00
Element [96], Bit [29]: Iteration 3 = 0.01
Element [96], Bit [29]: Iteration 4 = 0.01
...
{noformat}
A quick check using a seed with all the bits set except a single 0-bit shows
similar results (but the fraction of 1 bits starts at 1 and reduces towards
0.5).
So it seems only the MWC_256 generator suffers from very low quality seeds.
All will eventually recover and you could argue that this shows the output is
only random immediately after seeding if the seed itself passes a test of
randomness. Otherwise the generator may have to be used a large number of times
before it is random.
So do we just go with setting the first value in an array to non-zero to avoid
broken generators. Creating a good seed would then be in the hands of fate.
The MWC could have its own seeding override where it checks all values have
some transitions (but how many is enough?). Alternatively it could be seeded
using a SplitMix generator which only outputs 0 once in its cycle and will be
uniform from initial seeding. But this seems unnecessary given the low
probability of poor quality output from any generator behind the SeedFactory.
> XorShiRo generators require non-zero input seeds
>
>
> Key: RNG-106
> URL: https://issues.apache.org/jira/browse/RNG-106
> Project: Commons RNG
> Issue Type: Improvement
> Components: core, simple
>Affects Versions: 1.3
>Reporter: Alex D Herbert
>Assignee: Alex D Herbert
>Priority: Major
> Fix For: 1.3
>
>
> The following generators based on Xor shifts all require non-zero seeds:
> {noformat}
> XOR_SHIFT_1024_S
> XOR_SHIFT_1024_S_PHI
> XO_RO_SHI_RO_64_S
> XO_RO_SHI_RO_64_SS
> XO_SHI_RO_128_PLUS
> XO_SHI_RO_128_SS
> XO_RO_SHI_RO_128_PLUS
> XO_RO_SHI_RO_128_SS
> XO_S
[jira] [Commented] (RNG-106) XorShiRo generators require non-zero input seeds
[
https://issues.apache.org/jira/browse/RNG-106?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16861499#comment-16861499
]
Gilles commented on RNG-106:
{quote}modify the stress test application to be able to seed generators with
the n-th bit of a k-bit long byte array seed.
{quote}
Is it worth given the low probability that an actual seed will have a single
bit set?
Will you go on and assume that some RNGs might have a weakness with certain 2
bits set, then 3 bits, ... ;)
> XorShiRo generators require non-zero input seeds
>
>
> Key: RNG-106
> URL: https://issues.apache.org/jira/browse/RNG-106
> Project: Commons RNG
> Issue Type: Improvement
> Components: core, simple
>Affects Versions: 1.3
>Reporter: Alex D Herbert
>Assignee: Alex D Herbert
>Priority: Major
> Fix For: 1.3
>
>
> The following generators based on Xor shifts all require non-zero seeds:
> {noformat}
> XOR_SHIFT_1024_S
> XOR_SHIFT_1024_S_PHI
> XO_RO_SHI_RO_64_S
> XO_RO_SHI_RO_64_SS
> XO_SHI_RO_128_PLUS
> XO_SHI_RO_128_SS
> XO_RO_SHI_RO_128_PLUS
> XO_RO_SHI_RO_128_SS
> XO_SHI_RO_256_PLUS
> XO_SHI_RO_256_SS
> XO_SHI_RO_512_PLUS
> XO_SHI_RO_512_SS
> {noformat}
> A zero seed results in zero output for each call to the generator.
> Tests added to the rng-core module show that only a single bit is required to
> be set and the generator is able to generate non-zero output. These tests are
> simple and do not test the output for many cycles or do statistical analysis
> on the output randomness. However the authors of the generators state that
> they require a non-zero seed and are not any more specific so I assume that a
> single bit is enough to maintain the internal state capable of randomness.
> This can be fixed with the following methods:
> # Set the final bit in the seed to 1. This will be fast but loses 1 bit of
> seed entropy.
> # Check the seed array for zeros. If the entire array is zero then generate
> a single seed value until it is non-zero in a loop and set it into the seed
> array.
> # Check the seed array for zeros. If the entire array is zero then
> re-generate the seed using recursive method call.
> Note that this is an edge case. The smallest seed uses 64 bits, others use
> 128, 256, 512, 1024 (the number of bits in the seed is the state size and is
> the number in the enum). For the worst case this will occur 1 in 2^64 times.
> Here is the robust approach:
> {code:java}
> int[] seed;
> do {
> seed = createSeed(); // Appropriate seed array generation
> } while (SeedFactory.isZero(seed);
> return seed;
> {code}
> This would add new isZero(int[]) and isZero(long[]) methods to the seed
> factory. The entire method for creating a non-zero array seed could be added
> to the SeedFactory.
> Here is the compromise approach:
> {code:java}
> int[] seed = createSeed(); // Appropriate seed array generation
> if (SeedFactory.isZero(seed)) {
> do {
> seed[0] = SeedFactory.createInt();
> } while (seed[0] == 0);
> }
> {code}
> Given the loop will happen 1 in 2^64 times the speed of the two approaches
> will differ due to how the JVM produces the final code for the hot path (i.e.
> not the edge case).
> Here is the simple approach:
> {code:java}
> // Ensure non-zero (loses 1 bit of entropy)
> return createSeed() | 1;
> {code}
> Losing 1 bit of entropy is undesirable.
> A performance test of the approaches (and variants) should be done for
> reference.
--
This message was sent by Atlassian JIRA
(v7.6.3#76005)
[jira] [Commented] (RNG-106) XorShiRo generators require non-zero input seeds
[
https://issues.apache.org/jira/browse/RNG-106?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16861231#comment-16861231
]
Alex D Herbert commented on RNG-106:
{quote}I'll do this to see if a single bit seed is statistically OK.
{quote}
Adding this to the general test suite is tricky as for a large seed such as
Well44497 there are 44497 opportunities for the test to statistically fail. So
the p-value should be adjusted appropriately but this does not pinpoint which
single bit seeds are good or bad, only that as an entire collection they fail
more than expected.
I've pushed the simple test of non-zero output to master and will modify the
stress test application to be able to seed generators with the n-th bit of a
k-bit long byte array seed. This can be used to run a suitable test from
Dieharder on each possible single bit seed permutation for the generator.
Since Dieharder repeats tests if the results is marginal it should work to find
some pass/fail statistics for the generators.
> XorShiRo generators require non-zero input seeds
>
>
> Key: RNG-106
> URL: https://issues.apache.org/jira/browse/RNG-106
> Project: Commons RNG
> Issue Type: Improvement
> Components: core, simple
>Affects Versions: 1.3
>Reporter: Alex D Herbert
>Assignee: Alex D Herbert
>Priority: Major
> Fix For: 1.3
>
>
> The following generators based on Xor shifts all require non-zero seeds:
> {noformat}
> XOR_SHIFT_1024_S
> XOR_SHIFT_1024_S_PHI
> XO_RO_SHI_RO_64_S
> XO_RO_SHI_RO_64_SS
> XO_SHI_RO_128_PLUS
> XO_SHI_RO_128_SS
> XO_RO_SHI_RO_128_PLUS
> XO_RO_SHI_RO_128_SS
> XO_SHI_RO_256_PLUS
> XO_SHI_RO_256_SS
> XO_SHI_RO_512_PLUS
> XO_SHI_RO_512_SS
> {noformat}
> A zero seed results in zero output for each call to the generator.
> Tests added to the rng-core module show that only a single bit is required to
> be set and the generator is able to generate non-zero output. These tests are
> simple and do not test the output for many cycles or do statistical analysis
> on the output randomness. However the authors of the generators state that
> they require a non-zero seed and are not any more specific so I assume that a
> single bit is enough to maintain the internal state capable of randomness.
> This can be fixed with the following methods:
> # Set the final bit in the seed to 1. This will be fast but loses 1 bit of
> seed entropy.
> # Check the seed array for zeros. If the entire array is zero then generate
> a single seed value until it is non-zero in a loop and set it into the seed
> array.
> # Check the seed array for zeros. If the entire array is zero then
> re-generate the seed using recursive method call.
> Note that this is an edge case. The smallest seed uses 64 bits, others use
> 128, 256, 512, 1024 (the number of bits in the seed is the state size and is
> the number in the enum). For the worst case this will occur 1 in 2^64 times.
> Here is the robust approach:
> {code:java}
> int[] seed;
> do {
> seed = createSeed(); // Appropriate seed array generation
> } while (SeedFactory.isZero(seed);
> return seed;
> {code}
> This would add new isZero(int[]) and isZero(long[]) methods to the seed
> factory. The entire method for creating a non-zero array seed could be added
> to the SeedFactory.
> Here is the compromise approach:
> {code:java}
> int[] seed = createSeed(); // Appropriate seed array generation
> if (SeedFactory.isZero(seed)) {
> do {
> seed[0] = SeedFactory.createInt();
> } while (seed[0] == 0);
> }
> {code}
> Given the loop will happen 1 in 2^64 times the speed of the two approaches
> will differ due to how the JVM produces the final code for the hot path (i.e.
> not the edge case).
> Here is the simple approach:
> {code:java}
> // Ensure non-zero (loses 1 bit of entropy)
> return createSeed() | 1;
> {code}
> Losing 1 bit of entropy is undesirable.
> A performance test of the approaches (and variants) should be done for
> reference.
--
This message was sent by Atlassian JIRA
(v7.6.3#76005)
[jira] [Commented] (RNG-106) XorShiRo generators require non-zero input seeds
[
https://issues.apache.org/jira/browse/RNG-106?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16861150#comment-16861150
]
Alex D Herbert commented on RNG-106:
{quote}I must have misunderstood the previous test: I thought that a single
non-zero bit was not enough for some RNGs
{quote}
For most RNGs a single bit is OK.
Only for Well19937 and Well44497 and it is in the special case where you put a
single bit in a part of the seed they do not use. This is because Well19937 and
Well44497 have a bit pool that is not a multiple of 32.
If you seed these with a *single bit in the bit pool that it uses* then they
are good.
So my suggestion was to ensure that at least the first position in seed arrays
was non-zero. This would create a seed that will work for any of the generators
in the library.
{quote}bq. If you know they are all good, then they are not random.
{quote}
If you boost transitions then they are also not random.
Elimination of a zero value at seed array position 0 is the minimal
interference with the randomness of the seed that allows all the generators to
function.
Note: 'generators to function' is loosely applied. The test I ran shows that a
single bit is all that is needed to ensure output is not zero. Its main purpose
is to check the single bit does not become no bits and the generator then dies.
It found the problem in Well19937 and Well44497.
It was not a test of randomness. That would require the generator is warmed up
by iterating over its state size a number of times (allowing it to expand the
single bit in its state pool to a lot more) and then applying one of the tests
from the JUnit test suite.
This may be worth doing once as a trial but the test for setting each bit is
time consuming for Well44497 because the state is so large. It would make the
build slow to have it running all the time so should be annotated with Ignore.
I'll do this to see if a single bit seed is statistically OK.
> XorShiRo generators require non-zero input seeds
>
>
> Key: RNG-106
> URL: https://issues.apache.org/jira/browse/RNG-106
> Project: Commons RNG
> Issue Type: Improvement
> Components: core, simple
>Affects Versions: 1.3
>Reporter: Alex D Herbert
>Assignee: Alex D Herbert
>Priority: Major
> Fix For: 1.3
>
>
> The following generators based on Xor shifts all require non-zero seeds:
> {noformat}
> XOR_SHIFT_1024_S
> XOR_SHIFT_1024_S_PHI
> XO_RO_SHI_RO_64_S
> XO_RO_SHI_RO_64_SS
> XO_SHI_RO_128_PLUS
> XO_SHI_RO_128_SS
> XO_RO_SHI_RO_128_PLUS
> XO_RO_SHI_RO_128_SS
> XO_SHI_RO_256_PLUS
> XO_SHI_RO_256_SS
> XO_SHI_RO_512_PLUS
> XO_SHI_RO_512_SS
> {noformat}
> A zero seed results in zero output for each call to the generator.
> Tests added to the rng-core module show that only a single bit is required to
> be set and the generator is able to generate non-zero output. These tests are
> simple and do not test the output for many cycles or do statistical analysis
> on the output randomness. However the authors of the generators state that
> they require a non-zero seed and are not any more specific so I assume that a
> single bit is enough to maintain the internal state capable of randomness.
> This can be fixed with the following methods:
> # Set the final bit in the seed to 1. This will be fast but loses 1 bit of
> seed entropy.
> # Check the seed array for zeros. If the entire array is zero then generate
> a single seed value until it is non-zero in a loop and set it into the seed
> array.
> # Check the seed array for zeros. If the entire array is zero then
> re-generate the seed using recursive method call.
> Note that this is an edge case. The smallest seed uses 64 bits, others use
> 128, 256, 512, 1024 (the number of bits in the seed is the state size and is
> the number in the enum). For the worst case this will occur 1 in 2^64 times.
> Here is the robust approach:
> {code:java}
> int[] seed;
> do {
> seed = createSeed(); // Appropriate seed array generation
> } while (SeedFactory.isZero(seed);
> return seed;
> {code}
> This would add new isZero(int[]) and isZero(long[]) methods to the seed
> factory. The entire method for creating a non-zero array seed could be added
> to the SeedFactory.
> Here is the compromise approach:
> {code:java}
> int[] seed = createSeed(); // Appropriate seed array generation
> if (SeedFactory.isZero(seed)) {
> do {
> seed[0] = SeedFactory.createInt();
> } while (seed[0] == 0);
> }
> {code}
> Given the loop will happen 1 in 2^64 times the speed of the two approaches
> will differ due to how the JVM produces the final code for the hot path (i.e.
> not the edge case).
> Here is the simple approach:
> {code:java}
> // Ensure non-zero (loses 1 bit of entropy)
> return createSee
[jira] [Commented] (RNG-106) XorShiRo generators require non-zero input seeds
[
https://issues.apache.org/jira/browse/RNG-106?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16861126#comment-16861126
]
Gilles commented on RNG-106:
bq. The main use case is solved by just avoiding zeros for the entire seed.
I must have misunderstood the previous test: I thought that a single non-zero
bit was not enough for some RNGs (?).
bq. a better approach is to just replace the entire number.
That's what I meant.
bq. But then you have to count transitions again...
Yes. But, for the usual case, it's a small part of the job...
In any case, not each number of the array must meet the "ideal"; it's the
number of transitions over
the whole array that must be improved. E.g.
# select the slot with the smallest number of transitions,
# generate a number and replace that slot
# if not sufficient, go to step 1
bq. an algorithm that creates good random numbers using a seeded RNG.
If you know they are all good, then they are not random. :-)
> XorShiRo generators require non-zero input seeds
>
>
> Key: RNG-106
> URL: https://issues.apache.org/jira/browse/RNG-106
> Project: Commons RNG
> Issue Type: Improvement
> Components: core, simple
>Affects Versions: 1.3
>Reporter: Alex D Herbert
>Assignee: Alex D Herbert
>Priority: Major
> Fix For: 1.3
>
>
> The following generators based on Xor shifts all require non-zero seeds:
> {noformat}
> XOR_SHIFT_1024_S
> XOR_SHIFT_1024_S_PHI
> XO_RO_SHI_RO_64_S
> XO_RO_SHI_RO_64_SS
> XO_SHI_RO_128_PLUS
> XO_SHI_RO_128_SS
> XO_RO_SHI_RO_128_PLUS
> XO_RO_SHI_RO_128_SS
> XO_SHI_RO_256_PLUS
> XO_SHI_RO_256_SS
> XO_SHI_RO_512_PLUS
> XO_SHI_RO_512_SS
> {noformat}
> A zero seed results in zero output for each call to the generator.
> Tests added to the rng-core module show that only a single bit is required to
> be set and the generator is able to generate non-zero output. These tests are
> simple and do not test the output for many cycles or do statistical analysis
> on the output randomness. However the authors of the generators state that
> they require a non-zero seed and are not any more specific so I assume that a
> single bit is enough to maintain the internal state capable of randomness.
> This can be fixed with the following methods:
> # Set the final bit in the seed to 1. This will be fast but loses 1 bit of
> seed entropy.
> # Check the seed array for zeros. If the entire array is zero then generate
> a single seed value until it is non-zero in a loop and set it into the seed
> array.
> # Check the seed array for zeros. If the entire array is zero then
> re-generate the seed using recursive method call.
> Note that this is an edge case. The smallest seed uses 64 bits, others use
> 128, 256, 512, 1024 (the number of bits in the seed is the state size and is
> the number in the enum). For the worst case this will occur 1 in 2^64 times.
> Here is the robust approach:
> {code:java}
> int[] seed;
> do {
> seed = createSeed(); // Appropriate seed array generation
> } while (SeedFactory.isZero(seed);
> return seed;
> {code}
> This would add new isZero(int[]) and isZero(long[]) methods to the seed
> factory. The entire method for creating a non-zero array seed could be added
> to the SeedFactory.
> Here is the compromise approach:
> {code:java}
> int[] seed = createSeed(); // Appropriate seed array generation
> if (SeedFactory.isZero(seed)) {
> do {
> seed[0] = SeedFactory.createInt();
> } while (seed[0] == 0);
> }
> {code}
> Given the loop will happen 1 in 2^64 times the speed of the two approaches
> will differ due to how the JVM produces the final code for the hot path (i.e.
> not the edge case).
> Here is the simple approach:
> {code:java}
> // Ensure non-zero (loses 1 bit of entropy)
> return createSeed() | 1;
> {code}
> Losing 1 bit of entropy is undesirable.
> A performance test of the approaches (and variants) should be done for
> reference.
--
This message was sent by Atlassian JIRA
(v7.6.3#76005)
[jira] [Commented] (RNG-106) XorShiRo generators require non-zero input seeds
[
https://issues.apache.org/jira/browse/RNG-106?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16861094#comment-16861094
]
Alex D Herbert commented on RNG-106:
Boosting transitions in a custom manner would require knowing where they are.
The bit count method does not return the locations of transitions. So you have
to iterate over the bits in sequence and check if it changes from 0 to 1.
A custom boost would then have to decide how to boost them. You can remove the
bits where there is no transition so shortening the number of bits in your data:
{noformat}
0011001 -> 0101 (4 bits removed)
{noformat}
Then you have to fill the end with more bits to make up the correct length and
these bits would be chosen non-randomly to increase transitions, e.g. by
alternating bits. This is cutting down randomness by the number of bits you
removed.
So in a poor case with low initial transitions you have a very non-random
result:
{noformat}
0111 -> 01 (7 bits removed)
01010101 (fill 7 bits with transitions)
{noformat}
Perhaps a better approach is to just replace the entire number. But then you
have to count transitions again...
The step taken in the reference code for the Middle-Square Weyl Sequence
generator is to pre-compute good random numbers to be used for seeding
directly, or use an algorithm that creates good random numbers using a seeded
RNG.
Given that generating numbers with high transitions is a minor use case it
should be put into a separate factory method. A user can then use this routine
to generate 'good' seed values in advance.
The main use case is solved by just avoiding zeros for the entire seed. Given
the low collision rate with a zero output it may be simplest to just check the
first position is not zero:
{code:java}
int[] seed = createSeed(); // Appropriate seed array generation
while (seed[0] == 0) {
// Occurs 1 in 2^32 times (or 1 in 4 billion)
seed[0] = SeedFactory.createInt();
}
{code}
An array of any length would then be suitable to seed all of the generators in
the library, even if you create a seed of length 2, all of which are zero
apart from position 0.
> XorShiRo generators require non-zero input seeds
>
>
> Key: RNG-106
> URL: https://issues.apache.org/jira/browse/RNG-106
> Project: Commons RNG
> Issue Type: Improvement
> Components: core, simple
>Affects Versions: 1.3
>Reporter: Alex D Herbert
>Assignee: Alex D Herbert
>Priority: Major
> Fix For: 1.3
>
>
> The following generators based on Xor shifts all require non-zero seeds:
> {noformat}
> XOR_SHIFT_1024_S
> XOR_SHIFT_1024_S_PHI
> XO_RO_SHI_RO_64_S
> XO_RO_SHI_RO_64_SS
> XO_SHI_RO_128_PLUS
> XO_SHI_RO_128_SS
> XO_RO_SHI_RO_128_PLUS
> XO_RO_SHI_RO_128_SS
> XO_SHI_RO_256_PLUS
> XO_SHI_RO_256_SS
> XO_SHI_RO_512_PLUS
> XO_SHI_RO_512_SS
> {noformat}
> A zero seed results in zero output for each call to the generator.
> Tests added to the rng-core module show that only a single bit is required to
> be set and the generator is able to generate non-zero output. These tests are
> simple and do not test the output for many cycles or do statistical analysis
> on the output randomness. However the authors of the generators state that
> they require a non-zero seed and are not any more specific so I assume that a
> single bit is enough to maintain the internal state capable of randomness.
> This can be fixed with the following methods:
> # Set the final bit in the seed to 1. This will be fast but loses 1 bit of
> seed entropy.
> # Check the seed array for zeros. If the entire array is zero then generate
> a single seed value until it is non-zero in a loop and set it into the seed
> array.
> # Check the seed array for zeros. If the entire array is zero then
> re-generate the seed using recursive method call.
> Note that this is an edge case. The smallest seed uses 64 bits, others use
> 128, 256, 512, 1024 (the number of bits in the seed is the state size and is
> the number in the enum). For the worst case this will occur 1 in 2^64 times.
> Here is the robust approach:
> {code:java}
> int[] seed;
> do {
> seed = createSeed(); // Appropriate seed array generation
> } while (SeedFactory.isZero(seed);
> return seed;
> {code}
> This would add new isZero(int[]) and isZero(long[]) methods to the seed
> factory. The entire method for creating a non-zero array seed could be added
> to the SeedFactory.
> Here is the compromise approach:
> {code:java}
> int[] seed = createSeed(); // Appropriate seed array generation
> if (SeedFactory.isZero(seed)) {
> do {
> seed[0] = SeedFactory.createInt();
> } while (seed[0] == 0);
> }
> {code}
> Given the loop will happen 1 in 2^64 times the speed of the two approaches
> will differ due to how the JVM p
[jira] [Commented] (RNG-106) XorShiRo generators require non-zero input seeds
[
https://issues.apache.org/jira/browse/RNG-106?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16861059#comment-16861059
]
Gilles commented on RNG-106:
{quote}restricting 1% of output from the seed factory [...] is quite a lot.
{quote}
Sure; but could we have some "quality" argument, say ranging from 0 to 9 (or a
value between 0 and 1):
* 0: no boost
* 9: boost until the ideal (whatever that means, and allowed to change in
successive versions of the library) number of transitions.
* 1: boost to about 1/8 the ideal number of transitions
* 2: boost to about 1/7 ...
* etc.
?
> XorShiRo generators require non-zero input seeds
>
>
> Key: RNG-106
> URL: https://issues.apache.org/jira/browse/RNG-106
> Project: Commons RNG
> Issue Type: Improvement
> Components: core, simple
>Affects Versions: 1.3
>Reporter: Alex D Herbert
>Assignee: Alex D Herbert
>Priority: Major
> Fix For: 1.3
>
>
> The following generators based on Xor shifts all require non-zero seeds:
> {noformat}
> XOR_SHIFT_1024_S
> XOR_SHIFT_1024_S_PHI
> XO_RO_SHI_RO_64_S
> XO_RO_SHI_RO_64_SS
> XO_SHI_RO_128_PLUS
> XO_SHI_RO_128_SS
> XO_RO_SHI_RO_128_PLUS
> XO_RO_SHI_RO_128_SS
> XO_SHI_RO_256_PLUS
> XO_SHI_RO_256_SS
> XO_SHI_RO_512_PLUS
> XO_SHI_RO_512_SS
> {noformat}
> A zero seed results in zero output for each call to the generator.
> Tests added to the rng-core module show that only a single bit is required to
> be set and the generator is able to generate non-zero output. These tests are
> simple and do not test the output for many cycles or do statistical analysis
> on the output randomness. However the authors of the generators state that
> they require a non-zero seed and are not any more specific so I assume that a
> single bit is enough to maintain the internal state capable of randomness.
> This can be fixed with the following methods:
> # Set the final bit in the seed to 1. This will be fast but loses 1 bit of
> seed entropy.
> # Check the seed array for zeros. If the entire array is zero then generate
> a single seed value until it is non-zero in a loop and set it into the seed
> array.
> # Check the seed array for zeros. If the entire array is zero then
> re-generate the seed using recursive method call.
> Note that this is an edge case. The smallest seed uses 64 bits, others use
> 128, 256, 512, 1024 (the number of bits in the seed is the state size and is
> the number in the enum). For the worst case this will occur 1 in 2^64 times.
> Here is the robust approach:
> {code:java}
> int[] seed;
> do {
> seed = createSeed(); // Appropriate seed array generation
> } while (SeedFactory.isZero(seed);
> return seed;
> {code}
> This would add new isZero(int[]) and isZero(long[]) methods to the seed
> factory. The entire method for creating a non-zero array seed could be added
> to the SeedFactory.
> Here is the compromise approach:
> {code:java}
> int[] seed = createSeed(); // Appropriate seed array generation
> if (SeedFactory.isZero(seed)) {
> do {
> seed[0] = SeedFactory.createInt();
> } while (seed[0] == 0);
> }
> {code}
> Given the loop will happen 1 in 2^64 times the speed of the two approaches
> will differ due to how the JVM produces the final code for the hot path (i.e.
> not the edge case).
> Here is the simple approach:
> {code:java}
> // Ensure non-zero (loses 1 bit of entropy)
> return createSeed() | 1;
> {code}
> Losing 1 bit of entropy is undesirable.
> A performance test of the approaches (and variants) should be done for
> reference.
--
This message was sent by Atlassian JIRA
(v7.6.3#76005)
[jira] [Commented] (RNG-106) XorShiRo generators require non-zero input seeds
[
https://issues.apache.org/jira/browse/RNG-106?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16861037#comment-16861037
]
Alex D Herbert commented on RNG-106:
{quote}Am I correct that they concur to having a SeedFactory that ensures
"enough" transitions?
{quote}
I missed the target of the question during cross posting.
If we have a SeedFactory that checks transitions for every element of an array
then this is not a problem. From previous work the number of transitions
targeted in the SplittableRandom function is present in roughly 1% of all
numbers. So the slowdown of checking transitions is the first issue, then how
to boost them is another slowdown.
But I would argue that you are then restricting 1% of output from the seed
factory. That is quite a lot. If you just limit to non-zero values then you
only restrict to 1/2^32 for ints or 2.3e-10. And this is for a single element
which is not the problem. We only need to check arrays, the smallest is int[2]
which is then 1/2^64 or 5.4e-20.
It is such an edge case that checking for non-zero array seeds and putting a
warning on the large state well generators should be enough. For the later case
it could be recommended to either create a (full length seed -1) or a full
length seed and ensure the first position in the array is non-zero.
> XorShiRo generators require non-zero input seeds
>
>
> Key: RNG-106
> URL: https://issues.apache.org/jira/browse/RNG-106
> Project: Commons RNG
> Issue Type: Improvement
> Components: core, simple
>Affects Versions: 1.3
>Reporter: Alex D Herbert
>Assignee: Alex D Herbert
>Priority: Major
> Fix For: 1.3
>
>
> The following generators based on Xor shifts all require non-zero seeds:
> {noformat}
> XOR_SHIFT_1024_S
> XOR_SHIFT_1024_S_PHI
> XO_RO_SHI_RO_64_S
> XO_RO_SHI_RO_64_SS
> XO_SHI_RO_128_PLUS
> XO_SHI_RO_128_SS
> XO_RO_SHI_RO_128_PLUS
> XO_RO_SHI_RO_128_SS
> XO_SHI_RO_256_PLUS
> XO_SHI_RO_256_SS
> XO_SHI_RO_512_PLUS
> XO_SHI_RO_512_SS
> {noformat}
> A zero seed results in zero output for each call to the generator.
> Tests added to the rng-core module show that only a single bit is required to
> be set and the generator is able to generate non-zero output. These tests are
> simple and do not test the output for many cycles or do statistical analysis
> on the output randomness. However the authors of the generators state that
> they require a non-zero seed and are not any more specific so I assume that a
> single bit is enough to maintain the internal state capable of randomness.
> This can be fixed with the following methods:
> # Set the final bit in the seed to 1. This will be fast but loses 1 bit of
> seed entropy.
> # Check the seed array for zeros. If the entire array is zero then generate
> a single seed value until it is non-zero in a loop and set it into the seed
> array.
> # Check the seed array for zeros. If the entire array is zero then
> re-generate the seed using recursive method call.
> Note that this is an edge case. The smallest seed uses 64 bits, others use
> 128, 256, 512, 1024 (the number of bits in the seed is the state size and is
> the number in the enum). For the worst case this will occur 1 in 2^64 times.
> Here is the robust approach:
> {code:java}
> int[] seed;
> do {
> seed = createSeed(); // Appropriate seed array generation
> } while (SeedFactory.isZero(seed);
> return seed;
> {code}
> This would add new isZero(int[]) and isZero(long[]) methods to the seed
> factory. The entire method for creating a non-zero array seed could be added
> to the SeedFactory.
> Here is the compromise approach:
> {code:java}
> int[] seed = createSeed(); // Appropriate seed array generation
> if (SeedFactory.isZero(seed)) {
> do {
> seed[0] = SeedFactory.createInt();
> } while (seed[0] == 0);
> }
> {code}
> Given the loop will happen 1 in 2^64 times the speed of the two approaches
> will differ due to how the JVM produces the final code for the hot path (i.e.
> not the edge case).
> Here is the simple approach:
> {code:java}
> // Ensure non-zero (loses 1 bit of entropy)
> return createSeed() | 1;
> {code}
> Losing 1 bit of entropy is undesirable.
> A performance test of the approaches (and variants) should be done for
> reference.
--
This message was sent by Atlassian JIRA
(v7.6.3#76005)
[jira] [Commented] (RNG-106) XorShiRo generators require non-zero input seeds
[
https://issues.apache.org/jira/browse/RNG-106?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16861020#comment-16861020
]
Alex D Herbert commented on RNG-106:
For the large array Well generators this is not currently a problem as the
seeding routine in RandomSource.create(...) creates a seed of maximum 128. The
self seeding of the generator will fill the rest.
If I repeat the test using a maximum of 128 for the seed size then there are no
failures.
If I repeat the test using a bit pool of 19937 or 44497 respectively then there
are no failures.
So just checking for a non-zero array seed in the SeedFactory will allow all
the generators to be created with full length seeds output from the SeedFactory
with the exception of the two large state Well generators where for:
19937: A seed of all zero except the last element would fail if the last
element is < 2^31 - 1.
44497: A seed of all zero except the last element would fail if the last
element is < 2^15 - 1.
So in the use case where a user creates a full length seed from the SeedFactory
and uses it for the 19937 generator the probability of failure is less than 1
in 2^19936 and for the 44497 generator is less than 1 in 2^44480 (probabilities
are for creating a seed of zeros for all but the last element).
This is unlikely. So perhaps a warning for the user in the Javadoc of the
RandomSource enum type for WELL_19937 and WELL_44497 generators that although
the native seed size is 624/1391 the number of bits taken from the seed will be
less than that and an input seed should contain non-zero bits in the first
19937 or 44497 bits of the seed. Then any user creating a full length seed for
these generators will have been warned.
> XorShiRo generators require non-zero input seeds
>
>
> Key: RNG-106
> URL: https://issues.apache.org/jira/browse/RNG-106
> Project: Commons RNG
> Issue Type: Improvement
> Components: core, simple
>Affects Versions: 1.3
>Reporter: Alex D Herbert
>Assignee: Alex D Herbert
>Priority: Major
> Fix For: 1.3
>
>
> The following generators based on Xor shifts all require non-zero seeds:
> {noformat}
> XOR_SHIFT_1024_S
> XOR_SHIFT_1024_S_PHI
> XO_RO_SHI_RO_64_S
> XO_RO_SHI_RO_64_SS
> XO_SHI_RO_128_PLUS
> XO_SHI_RO_128_SS
> XO_RO_SHI_RO_128_PLUS
> XO_RO_SHI_RO_128_SS
> XO_SHI_RO_256_PLUS
> XO_SHI_RO_256_SS
> XO_SHI_RO_512_PLUS
> XO_SHI_RO_512_SS
> {noformat}
> A zero seed results in zero output for each call to the generator.
> Tests added to the rng-core module show that only a single bit is required to
> be set and the generator is able to generate non-zero output. These tests are
> simple and do not test the output for many cycles or do statistical analysis
> on the output randomness. However the authors of the generators state that
> they require a non-zero seed and are not any more specific so I assume that a
> single bit is enough to maintain the internal state capable of randomness.
> This can be fixed with the following methods:
> # Set the final bit in the seed to 1. This will be fast but loses 1 bit of
> seed entropy.
> # Check the seed array for zeros. If the entire array is zero then generate
> a single seed value until it is non-zero in a loop and set it into the seed
> array.
> # Check the seed array for zeros. If the entire array is zero then
> re-generate the seed using recursive method call.
> Note that this is an edge case. The smallest seed uses 64 bits, others use
> 128, 256, 512, 1024 (the number of bits in the seed is the state size and is
> the number in the enum). For the worst case this will occur 1 in 2^64 times.
> Here is the robust approach:
> {code:java}
> int[] seed;
> do {
> seed = createSeed(); // Appropriate seed array generation
> } while (SeedFactory.isZero(seed);
> return seed;
> {code}
> This would add new isZero(int[]) and isZero(long[]) methods to the seed
> factory. The entire method for creating a non-zero array seed could be added
> to the SeedFactory.
> Here is the compromise approach:
> {code:java}
> int[] seed = createSeed(); // Appropriate seed array generation
> if (SeedFactory.isZero(seed)) {
> do {
> seed[0] = SeedFactory.createInt();
> } while (seed[0] == 0);
> }
> {code}
> Given the loop will happen 1 in 2^64 times the speed of the two approaches
> will differ due to how the JVM produces the final code for the hot path (i.e.
> not the edge case).
> Here is the simple approach:
> {code:java}
> // Ensure non-zero (loses 1 bit of entropy)
> return createSeed() | 1;
> {code}
> Losing 1 bit of entropy is undesirable.
> A performance test of the approaches (and variants) should be done for
> reference.
--
This message was sent by Atlassian JIRA
(v7.6.3#76005)
[jira] [Commented] (RNG-106) XorShiRo generators require non-zero input seeds
[
https://issues.apache.org/jira/browse/RNG-106?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16861018#comment-16861018
]
Gilles commented on RNG-106:
bq. Results of using a single bit seed.
Am I correct that they concur to having a {{SeedFactory}} that ensures "enough"
transitions?
> XorShiRo generators require non-zero input seeds
>
>
> Key: RNG-106
> URL: https://issues.apache.org/jira/browse/RNG-106
> Project: Commons RNG
> Issue Type: Improvement
> Components: core, simple
>Affects Versions: 1.3
>Reporter: Alex D Herbert
>Assignee: Alex D Herbert
>Priority: Major
> Fix For: 1.3
>
>
> The following generators based on Xor shifts all require non-zero seeds:
> {noformat}
> XOR_SHIFT_1024_S
> XOR_SHIFT_1024_S_PHI
> XO_RO_SHI_RO_64_S
> XO_RO_SHI_RO_64_SS
> XO_SHI_RO_128_PLUS
> XO_SHI_RO_128_SS
> XO_RO_SHI_RO_128_PLUS
> XO_RO_SHI_RO_128_SS
> XO_SHI_RO_256_PLUS
> XO_SHI_RO_256_SS
> XO_SHI_RO_512_PLUS
> XO_SHI_RO_512_SS
> {noformat}
> A zero seed results in zero output for each call to the generator.
> Tests added to the rng-core module show that only a single bit is required to
> be set and the generator is able to generate non-zero output. These tests are
> simple and do not test the output for many cycles or do statistical analysis
> on the output randomness. However the authors of the generators state that
> they require a non-zero seed and are not any more specific so I assume that a
> single bit is enough to maintain the internal state capable of randomness.
> This can be fixed with the following methods:
> # Set the final bit in the seed to 1. This will be fast but loses 1 bit of
> seed entropy.
> # Check the seed array for zeros. If the entire array is zero then generate
> a single seed value until it is non-zero in a loop and set it into the seed
> array.
> # Check the seed array for zeros. If the entire array is zero then
> re-generate the seed using recursive method call.
> Note that this is an edge case. The smallest seed uses 64 bits, others use
> 128, 256, 512, 1024 (the number of bits in the seed is the state size and is
> the number in the enum). For the worst case this will occur 1 in 2^64 times.
> Here is the robust approach:
> {code:java}
> int[] seed;
> do {
> seed = createSeed(); // Appropriate seed array generation
> } while (SeedFactory.isZero(seed);
> return seed;
> {code}
> This would add new isZero(int[]) and isZero(long[]) methods to the seed
> factory. The entire method for creating a non-zero array seed could be added
> to the SeedFactory.
> Here is the compromise approach:
> {code:java}
> int[] seed = createSeed(); // Appropriate seed array generation
> if (SeedFactory.isZero(seed)) {
> do {
> seed[0] = SeedFactory.createInt();
> } while (seed[0] == 0);
> }
> {code}
> Given the loop will happen 1 in 2^64 times the speed of the two approaches
> will differ due to how the JVM produces the final code for the hot path (i.e.
> not the edge case).
> Here is the simple approach:
> {code:java}
> // Ensure non-zero (loses 1 bit of entropy)
> return createSeed() | 1;
> {code}
> Losing 1 bit of entropy is undesirable.
> A performance test of the approaches (and variants) should be done for
> reference.
--
This message was sent by Atlassian JIRA
(v7.6.3#76005)
[jira] [Commented] (RNG-106) XorShiRo generators require non-zero input seeds
[
https://issues.apache.org/jira/browse/RNG-106?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16861002#comment-16861002
]
Gilles commented on RNG-106:
bq. Testing for non-zero is a fast operation. Testing the number of transitions
may be slower than generating a random number.
I would not take that into account for "SeedFactory"; its "normal" use-case is
for seeding a generator that will output many values; for the "throw-away"
use-case, the seed should be set explicitly, e.g. using the output of
known-to-be-fast generator:
{code}
UniformRandomProvider seeder = RandomSource.create(SPLIT_MIX_64); // Use
"SeedFactory".
for (int i = 0; i < 1; i++) {
// Explicit seed (i.e. do not use "SeedFactory").
UniformRandomProvider rng = RandomSource.create(SPLIT_MIX_64,
seeder.nextLong());
// ...
}
{code}
The above must be a bad (contrived) example: Why not use a single RNG?
> XorShiRo generators require non-zero input seeds
>
>
> Key: RNG-106
> URL: https://issues.apache.org/jira/browse/RNG-106
> Project: Commons RNG
> Issue Type: Improvement
> Components: core, simple
>Affects Versions: 1.3
>Reporter: Alex D Herbert
>Assignee: Alex D Herbert
>Priority: Major
> Fix For: 1.3
>
>
> The following generators based on Xor shifts all require non-zero seeds:
> {noformat}
> XOR_SHIFT_1024_S
> XOR_SHIFT_1024_S_PHI
> XO_RO_SHI_RO_64_S
> XO_RO_SHI_RO_64_SS
> XO_SHI_RO_128_PLUS
> XO_SHI_RO_128_SS
> XO_RO_SHI_RO_128_PLUS
> XO_RO_SHI_RO_128_SS
> XO_SHI_RO_256_PLUS
> XO_SHI_RO_256_SS
> XO_SHI_RO_512_PLUS
> XO_SHI_RO_512_SS
> {noformat}
> A zero seed results in zero output for each call to the generator.
> Tests added to the rng-core module show that only a single bit is required to
> be set and the generator is able to generate non-zero output. These tests are
> simple and do not test the output for many cycles or do statistical analysis
> on the output randomness. However the authors of the generators state that
> they require a non-zero seed and are not any more specific so I assume that a
> single bit is enough to maintain the internal state capable of randomness.
> This can be fixed with the following methods:
> # Set the final bit in the seed to 1. This will be fast but loses 1 bit of
> seed entropy.
> # Check the seed array for zeros. If the entire array is zero then generate
> a single seed value until it is non-zero in a loop and set it into the seed
> array.
> # Check the seed array for zeros. If the entire array is zero then
> re-generate the seed using recursive method call.
> Note that this is an edge case. The smallest seed uses 64 bits, others use
> 128, 256, 512, 1024 (the number of bits in the seed is the state size and is
> the number in the enum). For the worst case this will occur 1 in 2^64 times.
> Here is the robust approach:
> {code:java}
> int[] seed;
> do {
> seed = createSeed(); // Appropriate seed array generation
> } while (SeedFactory.isZero(seed);
> return seed;
> {code}
> This would add new isZero(int[]) and isZero(long[]) methods to the seed
> factory. The entire method for creating a non-zero array seed could be added
> to the SeedFactory.
> Here is the compromise approach:
> {code:java}
> int[] seed = createSeed(); // Appropriate seed array generation
> if (SeedFactory.isZero(seed)) {
> do {
> seed[0] = SeedFactory.createInt();
> } while (seed[0] == 0);
> }
> {code}
> Given the loop will happen 1 in 2^64 times the speed of the two approaches
> will differ due to how the JVM produces the final code for the hot path (i.e.
> not the edge case).
> Here is the simple approach:
> {code:java}
> // Ensure non-zero (loses 1 bit of entropy)
> return createSeed() | 1;
> {code}
> Losing 1 bit of entropy is undesirable.
> A performance test of the approaches (and variants) should be done for
> reference.
--
This message was sent by Atlassian JIRA
(v7.6.3#76005)
[jira] [Commented] (RNG-106) XorShiRo generators require non-zero input seeds
[
https://issues.apache.org/jira/browse/RNG-106?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16860988#comment-16860988
]
Alex D Herbert commented on RNG-106:
Results of using a single bit seed.
The test sets a single bit in the seed, runs the generator for 2 times the seed
size for warm-up, then again for 2 times the seed size to test for non-zero
output. Output uses nextLong() so for the 32-bit providers the warm-up is 4
iterations through the state.
||Generator||Single bit seed OK||Message||Details||
|WELL_512_A|OK| | |
|WELL_1024_A|OK| | |
|WELL_19937_A|Fail|No non-zero output after 2496 cycles.
Seed element [623], bit=0|Fails on bits 0-30 of the last seed element|
|WELL_19937_C|Fail|No non-zero output after 2496 cycles.
Seed element [623], bit=0|Fails on bits 0-30 of the last seed element|
|WELL_44497_A|Fail|No non-zero output after 5564 cycles.
Seed element [1390], bit=0|Fails on bits 0-14 of the last seed element|
|WELL_44497_B|Fail|No non-zero output after 5564 cycles.
Seed element [1390], bit=0|Fails on bits 0-14 of the last seed element|
|MWC_256|OK| | |
For the larger Well generators the number in the name of the generator is the
number of bits in the pool. This does not have to be a multiple of 32. If the
seed is zero across the number of bits in the pool then seeding will fail. Thus
setting a bit in part of the seed which is ignored by the generator results in
a broken generator.
19937 = 624 * 32 - *31* => Fails on least significant 31 bits of the last seed
element
44497 = 1391 * 32 - *15* => Fails on least significant 15 bits of the last seed
element
> XorShiRo generators require non-zero input seeds
>
>
> Key: RNG-106
> URL: https://issues.apache.org/jira/browse/RNG-106
> Project: Commons RNG
> Issue Type: Improvement
> Components: core, simple
>Affects Versions: 1.3
>Reporter: Alex D Herbert
>Assignee: Alex D Herbert
>Priority: Major
> Fix For: 1.3
>
>
> The following generators based on Xor shifts all require non-zero seeds:
> {noformat}
> XOR_SHIFT_1024_S
> XOR_SHIFT_1024_S_PHI
> XO_RO_SHI_RO_64_S
> XO_RO_SHI_RO_64_SS
> XO_SHI_RO_128_PLUS
> XO_SHI_RO_128_SS
> XO_RO_SHI_RO_128_PLUS
> XO_RO_SHI_RO_128_SS
> XO_SHI_RO_256_PLUS
> XO_SHI_RO_256_SS
> XO_SHI_RO_512_PLUS
> XO_SHI_RO_512_SS
> {noformat}
> A zero seed results in zero output for each call to the generator.
> Tests added to the rng-core module show that only a single bit is required to
> be set and the generator is able to generate non-zero output. These tests are
> simple and do not test the output for many cycles or do statistical analysis
> on the output randomness. However the authors of the generators state that
> they require a non-zero seed and are not any more specific so I assume that a
> single bit is enough to maintain the internal state capable of randomness.
> This can be fixed with the following methods:
> # Set the final bit in the seed to 1. This will be fast but loses 1 bit of
> seed entropy.
> # Check the seed array for zeros. If the entire array is zero then generate
> a single seed value until it is non-zero in a loop and set it into the seed
> array.
> # Check the seed array for zeros. If the entire array is zero then
> re-generate the seed using recursive method call.
> Note that this is an edge case. The smallest seed uses 64 bits, others use
> 128, 256, 512, 1024 (the number of bits in the seed is the state size and is
> the number in the enum). For the worst case this will occur 1 in 2^64 times.
> Here is the robust approach:
> {code:java}
> int[] seed;
> do {
> seed = createSeed(); // Appropriate seed array generation
> } while (SeedFactory.isZero(seed);
> return seed;
> {code}
> This would add new isZero(int[]) and isZero(long[]) methods to the seed
> factory. The entire method for creating a non-zero array seed could be added
> to the SeedFactory.
> Here is the compromise approach:
> {code:java}
> int[] seed = createSeed(); // Appropriate seed array generation
> if (SeedFactory.isZero(seed)) {
> do {
> seed[0] = SeedFactory.createInt();
> } while (seed[0] == 0);
> }
> {code}
> Given the loop will happen 1 in 2^64 times the speed of the two approaches
> will differ due to how the JVM produces the final code for the hot path (i.e.
> not the edge case).
> Here is the simple approach:
> {code:java}
> // Ensure non-zero (loses 1 bit of entropy)
> return createSeed() | 1;
> {code}
> Losing 1 bit of entropy is undesirable.
> A performance test of the approaches (and variants) should be done for
> reference.
--
This message was sent by Atlassian JIRA
(v7.6.3#76005)
[jira] [Commented] (RNG-106) XorShiRo generators require non-zero input seeds
[
https://issues.apache.org/jira/browse/RNG-106?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16860957#comment-16860957
]
Alex D Herbert commented on RNG-106:
{quote}Perhaps the fix should also imply that the seed contain a minimum number
of "transitions"
{quote}
I think this is particularly applicable to the generators using a Weyl sequence
to provide randomness. With too few transitions the bits output by the Weyl
sequence do not change very much. This lowers the quality for example of a
SplitMix generator which hashes the bits using a suitable function. When the
underlying bits do not change then the hash output is not as random.
Testing for non-zero is a fast operation. Testing the number of transitions may
be slower than generating a random number. Take a look at the code behind
Long.bitCount() for this function:
{code:java}
private static int countTransitions(long value) {
// Sign-extending shift properly counts bits at the ends
return Long.bitCount(value ^ (value >> 1));
}
// From OpenJDK 1.8
public static int bitCount(long i) {
// HD, Figure 5-14
i = i - ((i >>> 1) & 0xL);
i = (i & 0xL) + ((i >>> 2) & 0xL);
i = (i + (i >>> 4)) & 0x0f0f0f0f0f0f0f0fL;
i = i + (i >>> 8);
i = i + (i >>> 16);
i = i + (i >>> 32);
return (int)i & 0x7f;
}
{code}
I added tests to all the XorShiRo generators to seed them using a single bit
and check that the output was non-zero after a number of iterations equal to
twice the seed size. The single bit was set in every possible position in the
seed array to test all worst case seeds. These tests pass. I could add the same
tests to the Well generators and MWC_256.
The MWC will pass as a single bit when multiplied will be non-zero. But it may
take the generator a lot of iterations to regain enough internal state to be
random as its state size is 256, i.e. parts of the output after the single bit
was set in the seed will be random while some long sequences will be still be
zero.
The Well generators are more complex to follow what happens to a single bit. So
I'll try these tests so see what happens.
Since these are extreme edge cases (e.g. Well512 is a 1 in 2^512 chance of a
full zero seed) the simple approach of ensuring non-zero should be enough.
Also note that if the SeedFactory is changed to a XorShift1024 generator the
fact that it cannot output enough seeds for a long[128] is because it has a
state size of 16 longs. This does mean it cannot output more than 15 zeros in
succession. So changing to this generator would ensure long array seeds are
non-zero.
> XorShiRo generators require non-zero input seeds
>
>
> Key: RNG-106
> URL: https://issues.apache.org/jira/browse/RNG-106
> Project: Commons RNG
> Issue Type: Improvement
> Components: core, simple
>Affects Versions: 1.3
>Reporter: Alex D Herbert
>Assignee: Alex D Herbert
>Priority: Major
> Fix For: 1.3
>
>
> The following generators based on Xor shifts all require non-zero seeds:
> {noformat}
> XOR_SHIFT_1024_S
> XOR_SHIFT_1024_S_PHI
> XO_RO_SHI_RO_64_S
> XO_RO_SHI_RO_64_SS
> XO_SHI_RO_128_PLUS
> XO_SHI_RO_128_SS
> XO_RO_SHI_RO_128_PLUS
> XO_RO_SHI_RO_128_SS
> XO_SHI_RO_256_PLUS
> XO_SHI_RO_256_SS
> XO_SHI_RO_512_PLUS
> XO_SHI_RO_512_SS
> {noformat}
> A zero seed results in zero output for each call to the generator.
> Tests added to the rng-core module show that only a single bit is required to
> be set and the generator is able to generate non-zero output. These tests are
> simple and do not test the output for many cycles or do statistical analysis
> on the output randomness. However the authors of the generators state that
> they require a non-zero seed and are not any more specific so I assume that a
> single bit is enough to maintain the internal state capable of randomness.
> This can be fixed with the following methods:
> # Set the final bit in the seed to 1. This will be fast but loses 1 bit of
> seed entropy.
> # Check the seed array for zeros. If the entire array is zero then generate
> a single seed value until it is non-zero in a loop and set it into the seed
> array.
> # Check the seed array for zeros. If the entire array is zero then
> re-generate the seed using recursive method call.
> Note that this is an edge case. The smallest seed uses 64 bits, others use
> 128, 256, 512, 1024 (the number of bits in the seed is the state size and is
> the number in the enum). For the worst case this will occur 1 in 2^64 times.
> Here is the robust approach:
> {code:java}
> int[] seed;
> do {
> seed = createSeed(); // Appropriate seed array generation
> } while (SeedFactory.isZero(seed);
> return seed;
> {code}
> This would add new isZero(i
[jira] [Commented] (RNG-106) XorShiRo generators require non-zero input seeds
[
https://issues.apache.org/jira/browse/RNG-106?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16860949#comment-16860949
]
Gilles commented on RNG-106:
+1
> XorShiRo generators require non-zero input seeds
>
>
> Key: RNG-106
> URL: https://issues.apache.org/jira/browse/RNG-106
> Project: Commons RNG
> Issue Type: Improvement
> Components: core, simple
>Affects Versions: 1.3
>Reporter: Alex D Herbert
>Assignee: Alex D Herbert
>Priority: Major
> Fix For: 1.3
>
>
> The following generators based on Xor shifts all require non-zero seeds:
> {noformat}
> XOR_SHIFT_1024_S
> XOR_SHIFT_1024_S_PHI
> XO_RO_SHI_RO_64_S
> XO_RO_SHI_RO_64_SS
> XO_SHI_RO_128_PLUS
> XO_SHI_RO_128_SS
> XO_RO_SHI_RO_128_PLUS
> XO_RO_SHI_RO_128_SS
> XO_SHI_RO_256_PLUS
> XO_SHI_RO_256_SS
> XO_SHI_RO_512_PLUS
> XO_SHI_RO_512_SS
> {noformat}
> A zero seed results in zero output for each call to the generator.
> Tests added to the rng-core module show that only a single bit is required to
> be set and the generator is able to generate non-zero output. These tests are
> simple and do not test the output for many cycles or do statistical analysis
> on the output randomness. However the authors of the generators state that
> they require a non-zero seed and are not any more specific so I assume that a
> single bit is enough to maintain the internal state capable of randomness.
> This can be fixed with the following methods:
> # Set the final bit in the seed to 1. This will be fast but loses 1 bit of
> seed entropy.
> # Check the seed array for zeros. If the entire array is zero then generate
> a single seed value until it is non-zero in a loop and set it into the seed
> array.
> # Check the seed array for zeros. If the entire array is zero then
> re-generate the seed using recursive method call.
> Note that this is an edge case. The smallest seed uses 64 bits, others use
> 128, 256, 512, 1024 (the number of bits in the seed is the state size and is
> the number in the enum). For the worst case this will occur 1 in 2^64 times.
> Here is the robust approach:
> {code:java}
> int[] seed;
> do {
> seed = createSeed(); // Appropriate seed array generation
> } while (SeedFactory.isZero(seed);
> return seed;
> {code}
> This would add new isZero(int[]) and isZero(long[]) methods to the seed
> factory. The entire method for creating a non-zero array seed could be added
> to the SeedFactory.
> Here is the compromise approach:
> {code:java}
> int[] seed = createSeed(); // Appropriate seed array generation
> if (SeedFactory.isZero(seed)) {
> do {
> seed[0] = SeedFactory.createInt();
> } while (seed[0] == 0);
> }
> {code}
> Given the loop will happen 1 in 2^64 times the speed of the two approaches
> will differ due to how the JVM produces the final code for the hot path (i.e.
> not the edge case).
> Here is the simple approach:
> {code:java}
> // Ensure non-zero (loses 1 bit of entropy)
> return createSeed() | 1;
> {code}
> Losing 1 bit of entropy is undesirable.
> A performance test of the approaches (and variants) should be done for
> reference.
--
This message was sent by Atlassian JIRA
(v7.6.3#76005)
[jira] [Commented] (RNG-106) XorShiRo generators require non-zero input seeds
[
https://issues.apache.org/jira/browse/RNG-106?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16860940#comment-16860940
]
Alex D Herbert commented on RNG-106:
Changed my mind. The SeedFactory should be the place to make the change. The
SeedFactory has 4 public methods. These should be documented as suitable for
creating seeds to pass to RandomSource.create(...).
This allows a user to create a seed with the SeedFactory, record the seed and
then create any generator from the seed knowing it will work. This scenario
would be used when the simulation must be repeatable and the recorded seed can
be re-used to achieve that.
> XorShiRo generators require non-zero input seeds
>
>
> Key: RNG-106
> URL: https://issues.apache.org/jira/browse/RNG-106
> Project: Commons RNG
> Issue Type: Improvement
> Components: core, simple
>Affects Versions: 1.3
>Reporter: Alex D Herbert
>Assignee: Alex D Herbert
>Priority: Major
> Fix For: 1.3
>
>
> The following generators based on Xor shifts all require non-zero seeds:
> {noformat}
> XOR_SHIFT_1024_S
> XOR_SHIFT_1024_S_PHI
> XO_RO_SHI_RO_64_S
> XO_RO_SHI_RO_64_SS
> XO_SHI_RO_128_PLUS
> XO_SHI_RO_128_SS
> XO_RO_SHI_RO_128_PLUS
> XO_RO_SHI_RO_128_SS
> XO_SHI_RO_256_PLUS
> XO_SHI_RO_256_SS
> XO_SHI_RO_512_PLUS
> XO_SHI_RO_512_SS
> {noformat}
> A zero seed results in zero output for each call to the generator.
> Tests added to the rng-core module show that only a single bit is required to
> be set and the generator is able to generate non-zero output. These tests are
> simple and do not test the output for many cycles or do statistical analysis
> on the output randomness. However the authors of the generators state that
> they require a non-zero seed and are not any more specific so I assume that a
> single bit is enough to maintain the internal state capable of randomness.
> This can be fixed with the following methods:
> # Set the final bit in the seed to 1. This will be fast but loses 1 bit of
> seed entropy.
> # Check the seed array for zeros. If the entire array is zero then generate
> a single seed value until it is non-zero in a loop and set it into the seed
> array.
> # Check the seed array for zeros. If the entire array is zero then
> re-generate the seed using recursive method call.
> Note that this is an edge case. The smallest seed uses 64 bits, others use
> 128, 256, 512, 1024 (the number of bits in the seed is the state size and is
> the number in the enum). For the worst case this will occur 1 in 2^64 times.
> Here is the robust approach:
> {code:java}
> int[] seed;
> do {
> seed = createSeed(); // Appropriate seed array generation
> } while (SeedFactory.isZero(seed);
> return seed;
> {code}
> This would add new isZero(int[]) and isZero(long[]) methods to the seed
> factory. The entire method for creating a non-zero array seed could be added
> to the SeedFactory.
> Here is the compromise approach:
> {code:java}
> int[] seed = createSeed(); // Appropriate seed array generation
> if (SeedFactory.isZero(seed)) {
> do {
> seed[0] = SeedFactory.createInt();
> } while (seed[0] == 0);
> }
> {code}
> Given the loop will happen 1 in 2^64 times the speed of the two approaches
> will differ due to how the JVM produces the final code for the hot path (i.e.
> not the edge case).
> Here is the simple approach:
> {code:java}
> // Ensure non-zero (loses 1 bit of entropy)
> return createSeed() | 1;
> {code}
> Losing 1 bit of entropy is undesirable.
> A performance test of the approaches (and variants) should be done for
> reference.
--
This message was sent by Atlassian JIRA
(v7.6.3#76005)
[jira] [Commented] (RNG-106) XorShiRo generators require non-zero input seeds
[
https://issues.apache.org/jira/browse/RNG-106?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16860939#comment-16860939
]
Gilles commented on RNG-106:
Because of the statistics which you mentioned (19/23), I'd tend to favour
{{SeedFactory}} not returning all zero seeds. In the discussion on the "dev"
ML, we mentioned checking for that condition and fix it. Perhaps the fix
should also imply that the seed contain a minimum number of "transitions" (?).
> XorShiRo generators require non-zero input seeds
>
>
> Key: RNG-106
> URL: https://issues.apache.org/jira/browse/RNG-106
> Project: Commons RNG
> Issue Type: Improvement
> Components: core, simple
>Affects Versions: 1.3
>Reporter: Alex D Herbert
>Assignee: Alex D Herbert
>Priority: Major
> Fix For: 1.3
>
>
> The following generators based on Xor shifts all require non-zero seeds:
> {noformat}
> XOR_SHIFT_1024_S
> XOR_SHIFT_1024_S_PHI
> XO_RO_SHI_RO_64_S
> XO_RO_SHI_RO_64_SS
> XO_SHI_RO_128_PLUS
> XO_SHI_RO_128_SS
> XO_RO_SHI_RO_128_PLUS
> XO_RO_SHI_RO_128_SS
> XO_SHI_RO_256_PLUS
> XO_SHI_RO_256_SS
> XO_SHI_RO_512_PLUS
> XO_SHI_RO_512_SS
> {noformat}
> A zero seed results in zero output for each call to the generator.
> Tests added to the rng-core module show that only a single bit is required to
> be set and the generator is able to generate non-zero output. These tests are
> simple and do not test the output for many cycles or do statistical analysis
> on the output randomness. However the authors of the generators state that
> they require a non-zero seed and are not any more specific so I assume that a
> single bit is enough to maintain the internal state capable of randomness.
> This can be fixed with the following methods:
> # Set the final bit in the seed to 1. This will be fast but loses 1 bit of
> seed entropy.
> # Check the seed array for zeros. If the entire array is zero then generate
> a single seed value until it is non-zero in a loop and set it into the seed
> array.
> # Check the seed array for zeros. If the entire array is zero then
> re-generate the seed using recursive method call.
> Note that this is an edge case. The smallest seed uses 64 bits, others use
> 128, 256, 512, 1024 (the number of bits in the seed is the state size and is
> the number in the enum). For the worst case this will occur 1 in 2^64 times.
> Here is the robust approach:
> {code:java}
> int[] seed;
> do {
> seed = createSeed(); // Appropriate seed array generation
> } while (SeedFactory.isZero(seed);
> return seed;
> {code}
> This would add new isZero(int[]) and isZero(long[]) methods to the seed
> factory. The entire method for creating a non-zero array seed could be added
> to the SeedFactory.
> Here is the compromise approach:
> {code:java}
> int[] seed = createSeed(); // Appropriate seed array generation
> if (SeedFactory.isZero(seed)) {
> do {
> seed[0] = SeedFactory.createInt();
> } while (seed[0] == 0);
> }
> {code}
> Given the loop will happen 1 in 2^64 times the speed of the two approaches
> will differ due to how the JVM produces the final code for the hot path (i.e.
> not the edge case).
> Here is the simple approach:
> {code:java}
> // Ensure non-zero (loses 1 bit of entropy)
> return createSeed() | 1;
> {code}
> Losing 1 bit of entropy is undesirable.
> A performance test of the approaches (and variants) should be done for
> reference.
--
This message was sent by Atlassian JIRA
(v7.6.3#76005)
[jira] [Commented] (RNG-106) XorShiRo generators require non-zero input seeds
[
https://issues.apache.org/jira/browse/RNG-106?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16860920#comment-16860920
]
Alex D Herbert commented on RNG-106:
bq. would change the user's request (a zero seed) into a non-zero seed?
No. Any input seed is passed through untouched as this is a no-op seed
conversion. Any zero seed of the wrong format (e.g. byte[] for an int[]) would
be converted to the appropriate zero seed of the correct format.
I am suggesting that (array?) seeds created by the library are never zero.
Since we have 19/23 generators with input array seeds that are vulnerable to
zero seeds the options are:
# Modify the 19 RandomSourceInternal instances with overrides to create
non-zero seeds. This allows other RandomSource not vulnerable to zero seeds to
still create them
# Modify the two createSeed(int) methods in NativeSeedType.INT_ARRAY and
NativeSeedType.LONG_ARRAY to not create a zero seed
# Modify the SeedFactory to not create zero seeds
It would make sense to modify it in one location rather than modify the 19
RandomSourceInternal instances. But where to modify? I favour doing it in the
NativeSeedType in the internal package. So the public facing SeedFactory can
still return zero seeds and users should be aware of that. This also is no
change to the public functionality.
It should be noted that the generators that require a single int or long can
handle zero seeds. So the only problem generators currently are those with
array seeds.
> XorShiRo generators require non-zero input seeds
>
>
> Key: RNG-106
> URL: https://issues.apache.org/jira/browse/RNG-106
> Project: Commons RNG
> Issue Type: Improvement
> Components: core, simple
>Affects Versions: 1.3
>Reporter: Alex D Herbert
>Assignee: Alex D Herbert
>Priority: Major
> Fix For: 1.3
>
>
> The following generators based on Xor shifts all require non-zero seeds:
> {noformat}
> XOR_SHIFT_1024_S
> XOR_SHIFT_1024_S_PHI
> XO_RO_SHI_RO_64_S
> XO_RO_SHI_RO_64_SS
> XO_SHI_RO_128_PLUS
> XO_SHI_RO_128_SS
> XO_RO_SHI_RO_128_PLUS
> XO_RO_SHI_RO_128_SS
> XO_SHI_RO_256_PLUS
> XO_SHI_RO_256_SS
> XO_SHI_RO_512_PLUS
> XO_SHI_RO_512_SS
> {noformat}
> A zero seed results in zero output for each call to the generator.
> Tests added to the rng-core module show that only a single bit is required to
> be set and the generator is able to generate non-zero output. These tests are
> simple and do not test the output for many cycles or do statistical analysis
> on the output randomness. However the authors of the generators state that
> they require a non-zero seed and are not any more specific so I assume that a
> single bit is enough to maintain the internal state capable of randomness.
> This can be fixed with the following methods:
> # Set the final bit in the seed to 1. This will be fast but loses 1 bit of
> seed entropy.
> # Check the seed array for zeros. If the entire array is zero then generate
> a single seed value until it is non-zero in a loop and set it into the seed
> array.
> # Check the seed array for zeros. If the entire array is zero then
> re-generate the seed using recursive method call.
> Note that this is an edge case. The smallest seed uses 64 bits, others use
> 128, 256, 512, 1024 (the number of bits in the seed is the state size and is
> the number in the enum). For the worst case this will occur 1 in 2^64 times.
> Here is the robust approach:
> {code:java}
> int[] seed;
> do {
> seed = createSeed(); // Appropriate seed array generation
> } while (SeedFactory.isZero(seed);
> return seed;
> {code}
> This would add new isZero(int[]) and isZero(long[]) methods to the seed
> factory. The entire method for creating a non-zero array seed could be added
> to the SeedFactory.
> Here is the compromise approach:
> {code:java}
> int[] seed = createSeed(); // Appropriate seed array generation
> if (SeedFactory.isZero(seed)) {
> do {
> seed[0] = SeedFactory.createInt();
> } while (seed[0] == 0);
> }
> {code}
> Given the loop will happen 1 in 2^64 times the speed of the two approaches
> will differ due to how the JVM produces the final code for the hot path (i.e.
> not the edge case).
> Here is the simple approach:
> {code:java}
> // Ensure non-zero (loses 1 bit of entropy)
> return createSeed() | 1;
> {code}
> Losing 1 bit of entropy is undesirable.
> A performance test of the approaches (and variants) should be done for
> reference.
--
This message was sent by Atlassian JIRA
(v7.6.3#76005)
[jira] [Commented] (RNG-106) XorShiRo generators require non-zero input seeds
[
https://issues.apache.org/jira/browse/RNG-106?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16860795#comment-16860795
]
Gilles commented on RNG-106:
bq. simplest solution would be \[...\] to always create a non zero seed.
Do you mean that this call (in the referred unit test):
{code}
RandomSource.create(originalSource, zero, originalArgs);
{code}
would change the user's request (a zero seed) into a non-zero seed?
> XorShiRo generators require non-zero input seeds
>
>
> Key: RNG-106
> URL: https://issues.apache.org/jira/browse/RNG-106
> Project: Commons RNG
> Issue Type: Improvement
> Components: core, simple
>Affects Versions: 1.3
>Reporter: Alex D Herbert
>Assignee: Alex D Herbert
>Priority: Major
> Fix For: 1.3
>
>
> The following generators based on Xor shifts all require non-zero seeds:
> {noformat}
> XOR_SHIFT_1024_S
> XOR_SHIFT_1024_S_PHI
> XO_RO_SHI_RO_64_S
> XO_RO_SHI_RO_64_SS
> XO_SHI_RO_128_PLUS
> XO_SHI_RO_128_SS
> XO_RO_SHI_RO_128_PLUS
> XO_RO_SHI_RO_128_SS
> XO_SHI_RO_256_PLUS
> XO_SHI_RO_256_SS
> XO_SHI_RO_512_PLUS
> XO_SHI_RO_512_SS
> {noformat}
> A zero seed results in zero output for each call to the generator.
> Tests added to the rng-core module show that only a single bit is required to
> be set and the generator is able to generate non-zero output. These tests are
> simple and do not test the output for many cycles or do statistical analysis
> on the output randomness. However the authors of the generators state that
> they require a non-zero seed and are not any more specific so I assume that a
> single bit is enough to maintain the internal state capable of randomness.
> This can be fixed with the following methods:
> # Set the final bit in the seed to 1. This will be fast but loses 1 bit of
> seed entropy.
> # Check the seed array for zeros. If the entire array is zero then generate
> a single seed value until it is non-zero in a loop and set it into the seed
> array.
> # Check the seed array for zeros. If the entire array is zero then
> re-generate the seed using recursive method call.
> Note that this is an edge case. The smallest seed uses 64 bits, others use
> 128, 256, 512, 1024 (the number of bits in the seed is the state size and is
> the number in the enum). For the worst case this will occur 1 in 2^64 times.
> Here is the robust approach:
> {code:java}
> int[] seed;
> do {
> seed = createSeed(); // Appropriate seed array generation
> } while (SeedFactory.isZero(seed);
> return seed;
> {code}
> This would add new isZero(int[]) and isZero(long[]) methods to the seed
> factory. The entire method for creating a non-zero array seed could be added
> to the SeedFactory.
> Here is the compromise approach:
> {code:java}
> int[] seed = createSeed(); // Appropriate seed array generation
> if (SeedFactory.isZero(seed)) {
> do {
> seed[0] = SeedFactory.createInt();
> } while (seed[0] == 0);
> }
> {code}
> Given the loop will happen 1 in 2^64 times the speed of the two approaches
> will differ due to how the JVM produces the final code for the hot path (i.e.
> not the edge case).
> Here is the simple approach:
> {code:java}
> // Ensure non-zero (loses 1 bit of entropy)
> return createSeed() | 1;
> {code}
> Losing 1 bit of entropy is undesirable.
> A performance test of the approaches (and variants) should be done for
> reference.
--
This message was sent by Atlassian JIRA
(v7.6.3#76005)
[jira] [Commented] (RNG-106) XorShiRo generators require non-zero input seeds
[
https://issues.apache.org/jira/browse/RNG-106?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16860389#comment-16860389
]
Alex D Herbert commented on RNG-106:
There are ignored tests in ProvidersCommonParametricTest that test zero-filled
array seeds. Re-instating these tests lead to failures of:
{noformat}
WELL_512_A
WELL_1024_A
WELL_19937_A
WELL_19937_C
WELL_44497_A
WELL_44497_B
MWC_256
{noformat}
These should be fixed too. Note that WELL_512_A has the smallest state of these
generators. It uses int[16] so the chance of a zero seed is 1 in (2^32)^16 = 1
in 2^512. So a zero seed is so unlikely this has never been a problem.
The WELL generators are based on xor and shift operations. With no 1-bits there
is nothing to xor and shift. The MWC generator uses multiplication of int
values and a carries the overflow to a long to add to the next multiplication.
So if initialised with zero there is never anything to multiply.
This results in 19 / 23 generators that accept an array seed to require it to
be non-zero. The simplest solution would be to change the NativeSeedType enum
that creates the seed arrays to always create a non zero seed.
> XorShiRo generators require non-zero input seeds
>
>
> Key: RNG-106
> URL: https://issues.apache.org/jira/browse/RNG-106
> Project: Commons RNG
> Issue Type: Improvement
> Components: core, simple
>Affects Versions: 1.3
>Reporter: Alex D Herbert
>Assignee: Alex D Herbert
>Priority: Major
> Fix For: 1.3
>
>
> The following generators based on Xor shifts all require non-zero seeds:
> {noformat}
> XOR_SHIFT_1024_S
> XOR_SHIFT_1024_S_PHI
> XO_RO_SHI_RO_64_S
> XO_RO_SHI_RO_64_SS
> XO_SHI_RO_128_PLUS
> XO_SHI_RO_128_SS
> XO_RO_SHI_RO_128_PLUS
> XO_RO_SHI_RO_128_SS
> XO_SHI_RO_256_PLUS
> XO_SHI_RO_256_SS
> XO_SHI_RO_512_PLUS
> XO_SHI_RO_512_SS
> {noformat}
> A zero seed results in zero output for each call to the generator.
> Tests added to the rng-core module show that only a single bit is required to
> be set and the generator is able to generate non-zero output. These tests are
> simple and do not test the output for many cycles or do statistical analysis
> on the output randomness. However the authors of the generators state that
> they require a non-zero seed and are not any more specific so I assume that a
> single bit is enough to maintain the internal state capable of randomness.
> This can be fixed with the following methods:
> # Set the final bit in the seed to 1. This will be fast but loses 1 bit of
> seed entropy.
> # Check the seed array for zeros. If the entire array is zero then generate
> a single seed value until it is non-zero in a loop and set it into the seed
> array.
> # Check the seed array for zeros. If the entire array is zero then
> re-generate the seed using recursive method call.
> Note that this is an edge case. The smallest seed uses 64 bits, others use
> 128, 256, 512, 1024 (the number of bits in the seed is the state size and is
> the number in the enum). For the worst case this will occur 1 in 2^64 times.
> Here is the robust approach:
> {code:java}
> int[] seed;
> do {
> seed = createSeed(); // Appropriate seed array generation
> } while (SeedFactory.isZero(seed);
> return seed;
> {code}
> This would add new isZero(int[]) and isZero(long[]) methods to the seed
> factory. The entire method for creating a non-zero array seed could be added
> to the SeedFactory.
> Here is the compromise approach:
> {code:java}
> int[] seed = createSeed(); // Appropriate seed array generation
> if (SeedFactory.isZero(seed)) {
> do {
> seed[0] = SeedFactory.createInt();
> } while (seed[0] == 0);
> }
> {code}
> Given the loop will happen 1 in 2^64 times the speed of the two approaches
> will differ due to how the JVM produces the final code for the hot path (i.e.
> not the edge case).
> Here is the simple approach:
> {code:java}
> // Ensure non-zero (loses 1 bit of entropy)
> return createSeed() | 1;
> {code}
> Losing 1 bit of entropy is undesirable.
> A performance test of the approaches (and variants) should be done for
> reference.
--
This message was sent by Atlassian JIRA
(v7.6.3#76005)
