If I restrict the sample sizes to 2^15 bytes, nothing against Xorshift 32 is found. Does it make sense to say that up to 2^15 bytes, Xorshift cannot be said to be nonrandom?
The short answer is that if you limit the statistical tests to those in PractRand with mostly default options, then 'yes', Xorshift cannot be said to be nonrandom up to 2^15 bytes.
The point I was trying to make is that 'Xorshift cannot be said to be nonrandom up to 2^15 bytes' is true even if I run no randomness tests at all. This is as opposed to running all (easily available) randomness tests, which show Xorshift32 is not random up to 2^15 bytes.
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
-
2020-08-17
If I restrict the sample sizes to 2^15 bytes, nothing against Xorshift 32 is found. Does it make sense to say that up to 2^15 bytes, Xorshift cannot be said to be nonrandom?
No. Xorshift generators could be detected as non-random given only a few bits of output more than their state size. PractRand is deliberately designed to NOT do so, for two reasons.
One reason is because PractRand attempts to keep the ratio of CPU cycles used to bytes tested relatively constant over the long term, and doing such tests ASAP would mess that up - binary rank tests use data proportionate to the square of the matrix width, but use time proportionate to the cube. The other reason is because the amount of data that PractRand uses to reject a PRNG (or rather the log of that amount) is intended to be usable as basically a score for that PRNG, and while xorshift PRNGs are bad, they're not as bad as rejecting them ASAP would suggest.
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
Your language is a little beyond my currenty capacity for understanding. You're saying no, not having detected anything wrong with a sample of 2^15 bytes does not let us say that Xorshift is not nonrandom up to 2^15.
I thought Xorshift 32 were 32 bits in internal state. So 2^15 is well below the internal state capacity.
You're saying PractRand is deliberatly designed not to try to claim a generator as non-random consuming only roughly their state size. Then you give us two reasons for that.
Am I understanding what you're asserting? Thanks!
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
-
2020-08-17
You are mixing up the values and the log-base-2 of the values. And possibly the units too. A 32-bit xorshift would fail more aggressive testing at about 64 bits tested, or about 8 bytes. Written as powers of 2, that would be 2^6 bits or 2^3 bytes of output. PractRand can't even test that little data, its minimum test size is one kilobyte.
Also, when PractRand finds bias after whatever number of kilobytes tested, that is an upper bound on the amount of data needed to show non-randomness. A more specialized test can almost always show bias using less data, usually far less data. Especially since PractRand is optimized to minimize computation time, not amount of data needed.
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
A few critical points with your example (yes, I ramble):
1. To access the full power of PractRand in the sense you are looking for, in theory you should use additional command line switches.
2. The specific additional switches I use are '-tf 2 -te 1' (and 'stdin', instead of 'stdin32' might provide some additional benefit, but not sure about it with Xorshift).
3. However, doing so exposes issues with statistical calibration at ~64KB and lower.
4. Therefore, PractRand is not optimal for in-depth study of sample sizes in that range.
5. However, the good news is that you can run multiple tests with a highly random source to determine which test statistics are skewed in each small sample size range, and either mathematically correct them yourself, or ignore them.
7. PractRand pre0.95 has even more tests, including a special command line switch for birthday spacing focus, which sadly I have not had a chance to try.
8. PractRand is comprised of many tests that are biased toward identifying the most common statistical failures, whereas TestU01 has a broader scope (that is only truly realized with BigCrush, which requires larger sample size, though you could build your own library with more tests at smaller size... too painful for me to do).
9. Comprehensive small scale testing is something that RaBiGeTe excels at, which you might try.
10. PractRand is just part of an arsenal I use also comprised of TestU01, gjrand and Vigna's Hamming Weight Dependancy test (with RaBiGeTe typically taking a back seat to those, but as I indicated, it definitely has its place due to its comprehensive statistical prowess).
11. Older test suites, e.g., NIST, Diehard, Dieharder generally should be avoided (but, again, are not entirely without value).
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
If I restrict the sample sizes to 2^15 bytes, nothing against Xorshift 32 is found. Does it make sense to say that up to 2^15 bytes, Xorshift cannot be said to be nonrandom?
The short answer is that if you limit the statistical tests to those in PractRand with mostly default options, then 'yes', Xorshift cannot be said to be nonrandom up to 2^15 bytes.
The point I was trying to make is that 'Xorshift cannot be said to be nonrandom up to 2^15 bytes' is true even if I run no randomness tests at all. This is as opposed to running all (easily available) randomness tests, which show Xorshift32 is not random up to 2^15 bytes.
No. Xorshift generators could be detected as non-random given only a few bits of output more than their state size. PractRand is deliberately designed to NOT do so, for two reasons.
One reason is because PractRand attempts to keep the ratio of CPU cycles used to bytes tested relatively constant over the long term, and doing such tests ASAP would mess that up - binary rank tests use data proportionate to the square of the matrix width, but use time proportionate to the cube. The other reason is because the amount of data that PractRand uses to reject a PRNG (or rather the log of that amount) is intended to be usable as basically a score for that PRNG, and while xorshift PRNGs are bad, they're not as bad as rejecting them ASAP would suggest.
Your language is a little beyond my currenty capacity for understanding. You're saying no, not having detected anything wrong with a sample of 2^15 bytes does not let us say that Xorshift is not nonrandom up to 2^15.
I thought Xorshift 32 were 32 bits in internal state. So 2^15 is well below the internal state capacity.
You're saying PractRand is deliberatly designed not to try to claim a generator as non-random consuming only roughly their state size. Then you give us two reasons for that.
Am I understanding what you're asserting? Thanks!
You are mixing up the values and the log-base-2 of the values. And possibly the units too. A 32-bit xorshift would fail more aggressive testing at about 64 bits tested, or about 8 bytes. Written as powers of 2, that would be 2^6 bits or 2^3 bytes of output. PractRand can't even test that little data, its minimum test size is one kilobyte.
Also, when PractRand finds bias after whatever number of kilobytes tested, that is an upper bound on the amount of data needed to show non-randomness. A more specialized test can almost always show bias using less data, usually far less data. Especially since PractRand is optimized to minimize computation time, not amount of data needed.
A few critical points with your example (yes, I ramble):
1. To access the full power of PractRand in the sense you are looking for, in theory you should use additional command line switches.
2. The specific additional switches I use are '-tf 2 -te 1' (and 'stdin', instead of 'stdin32' might provide some additional benefit, but not sure about it with Xorshift).
3. However, doing so exposes issues with statistical calibration at ~64KB and lower.
4. Therefore, PractRand is not optimal for in-depth study of sample sizes in that range.
5. However, the good news is that you can run multiple tests with a highly random source to determine which test statistics are skewed in each small sample size range, and either mathematically correct them yourself, or ignore them.
7. PractRand pre0.95 has even more tests, including a special command line switch for birthday spacing focus, which sadly I have not had a chance to try.
8. PractRand is comprised of many tests that are biased toward identifying the most common statistical failures, whereas TestU01 has a broader scope (that is only truly realized with BigCrush, which requires larger sample size, though you could build your own library with more tests at smaller size... too painful for me to do).
9. Comprehensive small scale testing is something that RaBiGeTe excels at, which you might try.
10. PractRand is just part of an arsenal I use also comprised of TestU01, gjrand and Vigna's Hamming Weight Dependancy test (with RaBiGeTe typically taking a back seat to those, but as I indicated, it definitely has its place due to its comprehensive statistical prowess).
11. Older test suites, e.g., NIST, Diehard, Dieharder generally should be avoided (but, again, are not entirely without value).