commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Alex Herbert <alex.d.herb...@gmail.com>
Subject Re: [Rng] New XoShiRo generators
Date Mon, 18 Mar 2019 23:14:59 GMT


> On 18 Mar 2019, at 19:27, Gilles Sadowski <gilleseran@gmail.com> wrote:
> 
> Le lun. 18 mars 2019 à 16:49, Alex Herbert <alex.d.herbert@gmail.com <mailto:alex.d.herbert@gmail.com>>
a écrit :
>> 
>> 
>> On 18/03/2019 14:12, Gilles Sadowski wrote:
>>> Hi.
>>> 
>>>>>> [...]
>>>>>> 
>>>>>> One actual issue is that we are testing long providers using the
long to create 2 int values. Should we test using a series of the upper 32 bits and then a
series of the lower 32 bits?
>>>>> Is that useful since the test now sees the integers as they are produced
(i.e. 2
>>>>> values per long)?
>>>>> 
>>>> It is not relevant if you are concerned about int quality. But if you are
concerned about long quality then it is relevant. The long quality is important for the quality
of nextDouble(). Although in that case only the upper 53 bits of the long. This means that
the quality of a long from an int provider is also not covered by the benchmark as that would
require testing alternating ints twice using the series: 1, 3, 5…, 2n+1 and 2, 4, 6, …
2n.
>>> I don't follow: I'd think that if the full sequence passes the test,
>>> then "decimated"
>>> sequences will too.
>> 
>> My position was that if a series of int values is random, that does not
>> mean a subset of the int values is random due to bias in the subset sample.
> 
> Doesn't this statement contradict...
> 
>> 
>> However I acknowledge that:
>> 
>> - the test suites may have this covered already
>> 
>> - if it really is random then any subset will also be random, even if it
>> is a systematic subset such as alternating values
> 
> ... this one?

Yes but my get out clause is that there are a lot of IFs. Basically I don’t know which is
right. It is easiest to assume that the test suite has this covered and we just test RNGs
passing all the bits through.

> 
>> 
>>>> Given that half of the int values were previously discarded from the BigCrush
analysis, the current results on the user guide page actually represent BigCrush running on
the upper 32-bits of the long, byte reversed due to the big/little endian interpretation of
the bytes in Java and linux.
>>>> 
>>>> So maybe the an update to the RandomStressTester to support analysis for
int or long quality is needed.
>>> I'm not convinced.
>> 
>> I'm not totally convinced either. It is a lot more work to test upper
>> and lower bits separately.
>> 
>> It may be that a producer of long values has better randomness in the
>> upper bits. Or put another way has less than 64-bits of randomness.
>> 
>> The question is whether running the test suite on all the bits (as we
>> currently do) or targetting just the upper or lower 32-bits is useful.
>> E.g. would a RNG that fails a few tests using all the bits pass with
>> just the upper 32-bits,
> 
> Since the RNG outputs all the bits, passing the test with part
> of them would have no particular value (except if the goal is to
> create a new implementation based on that observation).
> 
>> and fail more with just the lower 32-bits, or
>> would the fails be the same?
>> 
>> Note: The current results for long providers do not test the lower
>> 32-bits at all, and currently test alternating values from any int
>> providers. So they will have to be rerun anyway.
> 
> +1
> [For the sake of consistency, but I don't think that the results
> will be different.]
> 
>> Previously I looked at systematic failures in the test suite (where the
>> same test always fails). IIRC the MersenneTwister has some systematic
>> failures. Since we are not doing systematic failure analysis for the
>> user guide, and we are not developing the algorithms, then I agree that
>> a more detailed analysis of the failures and their origins is beyond the
>> scope of the quality section.
> 
> We already provide a wider choice of good implementations than
> any other Java library; indeed, I think that time is better spent in
> porting more algorithms (even "bad" ones).
> 
>> 
>> So leave the testing to just ints and document on the user guide that is
>> what we are testing.
> 
> +1

OK. That seems simplest.

Given all the stress tests will be rerun shall I go ahead and reorder the existing files,
user guide .apt file and the GeneratorsList to be in the order of the RandomSource enum?
 

Big/Little Endian for Dieharder:

I’ve spent some time looking at the source code for Dieharder. It reads binary file data
using this (taken from libdieharder/rng_file_input_raw.c):

unsigned int iret;
// ...
fread(&iret,sizeof(uint),1,state->fp);

So it reads single unsigned integers using fread().

Given that it is possible to run die harder using numbers from ascii and binary input files
I set up a test. I created them using a RNG with the same seed with the standard output from
a DataOutputStream and the byte reversed output using Integer.reverseBytes. Here’s what
happens:

> dieharder -g 201 -d 0 -f raw.bin.rev
   diehard_birthdays|   0|       100|     100|0.89220858|  PASSED
> dieharder -g 202 -d 0 -f raw.txt
   diehard_birthdays|   0|       100|     100|0.89220858|  PASSED

> dieharder -g 201 -d 0 -f raw.bin
   diehard_birthdays|   0|       100|     100|0.30776452|  PASSED 
> dieharder -g 202 -d 0 -f raw.txt.rev
   diehard_birthdays|   0|       100|     100|0.30776452|  PASSED 

> cat raw.bin | dieharder -g 200 -d 0
   diehard_birthdays|   0|       100|     100|0.30776452|  PASSED 


Note the reversed byte sequence (.rev suffix) is required to get the same results from the
binary (.bin) file as from the text (.txt) file.

So the binary read of Dieharder is using the little endian representation, as was required
for TestU01.

I had modified the stdin2testu01.c bridge to detect if the system was little endian and then
correct the input data by reversing the bytes. It may be a better idea to write a test c program
to detect the endianness of the system for reference. Then update the stress test benchmark
to have an argument for little or big endian output when piping the int data to the command
line program.

I think it is important to get the endianness of the data correct. At least for Dieharder
it runs tests using tuples of bits from the data which can span multiple bytes. For example
the sts_serial test (-d 102) uses overlapping n-tuples of bits with n from 1 to 16. Other
tests using non overlapping tuples such as rgb_bitdist (-d 200) use n 1 to 12. 

Reversing the bytes in the Java code is the easiest option. Others are:

- Write binary data to file and then run it using that. This will end up looping the file
though and repeating the sequence unless the binary file is huge.
- Call Dieharder from a bridge program using the libdieharder API. I’ve not checked if there
is an API method call for Dieharder to run everything.

Alex






Mime
  • Unnamed multipart/alternative (inline, None, 0 bytes)
View raw message