Alex D Herbert created RNG-106:
----------------------------------
Summary: 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
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)
