[
https://issues.apache.org/jira/browse/RNG-57?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16640855#comment-16640855
]
Alex D Herbert commented on RNG-57:
-----------------------------------
I've had a look at {{ProvidersCommonParametricTest}} and why this fails.
In summary the test runs the RNG to create a uniform sample using 1000 samples
and tests it is uniform using a Chi squared test with a critical value at 1%.
500 repeat chi square tests are made and if more than 2% fail then this is a
test fail.
This is fair.
I only found one bug in the test and that was a rounding error setting the
range of the upper bin when the max was 2305843009213693951L (Long.MAX_VALUE /
4). It was out by 1 and so not a problem with a range this big and not the
reason for the test being flaky.
I did notice that the test is usually failing when the range under test is an
integer range that is not a power of 2. So it may be failing because the test
is checking not the randomness of the entire binary bits from the RNG but the
algorithm for generating an integer that is not a power of two. This algorithm
does not use the entire binary bits but is biased to using the least
significant bits since it sets the returned value using the modulus of the
binary bits using a rejection algorithm:
{code:java}
// Excerpt from BaseProvider.nextInt(int)
do {
bits = nextInt() >>> 1;
// Here the bits returned are composed of the least
// significant bits (bar one) from the random
val = bits % n;
} while (bits - val + (n - 1) < 0);
{code}
Since I have modified {{ProvidersCommonParametricTest}} to randomly seed each
time I am running it 1000 times and logging the number of test fails for each
test, e.g.
{noformat}
org.apache.commons.rng.core.source32.Well512a: Pass for n = 1234 <Integer> (9
out of 500 tests failed)
org.apache.commons.rng.core.source32.Well512a: Pass for n = 4 <Integer> (0 out
of 500 tests failed)
org.apache.commons.rng.core.source32.Well512a: Pass for n = 10 <Integer> (6 out
of 500 tests failed)
org.apache.commons.rng.core.source32.Well512a: Pass for n = 12 <Integer> (8 out
of 500 tests failed)
org.apache.commons.rng.core.source32.Well512a: Pass for n = 31 <Integer> (3 out
of 500 tests failed)
org.apache.commons.rng.core.source32.Well512a: Pass for n = 32 <Integer> (4 out
of 500 tests failed)
org.apache.commons.rng.core.source32.Well512a: Pass for n = 2016128993
<Integer> (2 out of 500 tests failed)
org.apache.commons.rng.core.source32.Well512a: Pass for n = 1834691456
<Integer> (7 out of 500 tests failed)
org.apache.commons.rng.core.source32.Well512a: Pass for n = 869657561 <Integer>
(7 out of 500 tests failed)
org.apache.commons.rng.core.source32.Well512a: Pass for n = 1570504788
<Integer> (9 out of 500 tests failed)
org.apache.commons.rng.core.source32.Well512a: Pass for n = 4 <Long> (0 out of
500 tests failed)
org.apache.commons.rng.core.source32.Well512a: Pass for n = 11 <Long> (6 out of
500 tests failed)
org.apache.commons.rng.core.source32.Well512a: Pass for n = 19 <Long> (5 out of
500 tests failed)
org.apache.commons.rng.core.source32.Well512a: Pass for n = 31 <Long> (8 out of
500 tests failed)
org.apache.commons.rng.core.source32.Well512a: Pass for n = 32 <Long> (4 out of
500 tests failed)
org.apache.commons.rng.core.source32.Well512a: Pass for n = 2305843009213693951
<Long> (4 out of 500 tests failed)
org.apache.commons.rng.core.source32.Well512a: Pass for n = 4611686018427387902
<Long> (9 out of 500 tests failed)
org.apache.commons.rng.core.source32.Well512a: Pass for n = 6917529027641081853
<Long> (2 out of 500 tests failed)
org.apache.commons.rng.core.source32.Well512a: Pass for n = 578 <Integer> (3
out of 500 tests failed)
{noformat}
We expect to see 5 out of 500 tests failed.
I am going to do some analysis on the output to see if the tests for non-power
of two {{nextInt(int)}} and {{nextLong(long)}} are more flaky than the others.
If correct then this may be solved by:
- increasing the tolerance for those tests (i.e. >2% fail rate)
- increasing the number of samples for those tests (i.e. >1000)
- removing those tests and just using nextBytes[]
The last idea or a modification of it is to just test the RNG produces an
acceptable random stream of bits. Although fine for the current providers it
would not cover future providers that may override nextFloat, nextDouble,
nextInt(int), nextLong(long).
> CachedUniformRandomProvider for nextBoolean() and nextInt()
> -----------------------------------------------------------
>
> Key: RNG-57
> URL: https://issues.apache.org/jira/browse/RNG-57
> Project: Commons RNG
> Issue Type: Improvement
> Components: sampling
> Affects Versions: 1.2
> Reporter: Alex D Herbert
> Priority: Minor
> Labels: performance
>
> Implement a wrapper around a {{UniformRandomProvider}} that can cache the
> underlying source of random bytes for use in the methods {{nextBoolean()}}
> and {{nextInt()}} (in the case of {{LongProvider}}). E.g.
> {code:java}
> LongProvider provider = RandomSource.create(RandomSource.SPLIT_MIX_64);
> CachedLongProvider rng = new CachedLongProvider(provider);
> // Uses cached nextLong() 64 times
> rng.nextBoolean();
> // Uses cached nextLong() twice
> rng.nextInt();
> IntProvider provider = RandomSource.create(RandomSource.KISS);
> CachedIntProvider rng2 = new CachedIntProvider(provider);
> // Uses cached nextInt() 32 times
> rng2.nextBoolean();
> // This could be wrapped by a factory method:
> UniformRandomProvider rng = CachedUniformRandomProviderFactory.wrap(
> // Any supported source: IntProvider or LongProvider
> RandomSource.create(RandomSource...));
> {code}
> The implementation should be speed tested to determine the benefit for
> {{nextBoolean()}} and if {{nextInt()}} can be improved for {{LongProviders}}.
--
This message was sent by Atlassian JIRA
(v7.6.3#76005)
