[
https://issues.apache.org/jira/browse/RNG-106?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Alex D Herbert resolved RNG-106.
--------------------------------
Resolution: Implemented
In master.
> 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
>
> Time Spent: 20m
> Remaining Estimate: 0h
>
> 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)
