changes for 0.94

(which isn't out yet, just to be clear)

RNG_test: theshold levels fixed
There's supposed to be, on average, 0.1 unusual results per results summary on a good PRNG. Instead there's 0.2. Likewise there's supposed to be 0.01 mildly suspicious results and instead there's 0.02, and so on. Every threshold was twice what it was supposed to be due to a bug, fixed for PractRand 0.94.

RNG_test: added new threshold level
Added a new theshold level between "normal" and "unusual". The new level is named "normalish". On average, there should be 1 result at this level per results summary. Note that, at default settings, results at this level are not shown, just listed as "test result(s) without anomalies".

RNG_output:
As requested, you can now get as output the same datastream that RNG_test uses internally when testing seeding and entropy pooling. To do so, use "SeedingTester(base_rng)" as the name of the RNG to get the output of. This format also works for RNG_test if you prefer this form over the usual use of "-ttseed64" or "-ttep". Examples in case my explanation was unclear:
"./RNG_test jsf32 -ttseed64"
is now equivalent to:
"./RNG_test SeedingTester(jsf32)"
and also equivalent to:
"./RNG_output SeedingTester(jsf32) inf | ./RNG_test stdin64"
(the seeding tester generates 64 bits per seed regardless of the tested RNGs native format)

RNG_output: minor changes
The output buffer size was increased again. The endianness issues in the output on some platforms were also fixed.

RNGs: xsm32/64 changed
xsm64 was failing some tests on some seeds. So I revised xsm32 and xsm64 a bit to improve quality, especially on bad seeds.

tests: BRank
bugfix, was going out of array bounds, usually not causing any serious problems (on my compilers, YMMV) but causing extreme failures to get misreported as even more extreme failures, fixed.

still in progress:

tests: new tests
Still a work in progress, but I've got a test that attempts to do what avalanche tests do, but using only PRNG output. That is, it looks for sequences of output that are low hamming distance from each other, and looks at how quickly such sequences diverge from each other. It's not working all that well. I've got another one that looks for medium range correlations that might normally be hidden due to being at odd bit positions and/or too far apart, but can only detect very strong such correlations. It actually seems to find bias in a reasonable number of testing PRNGs. And I may try to do something to specifically target LCGs if I get around to it. Probably none of these will make it in to the core test set, and maybe not more than 1 or 2 in to the expanded test set.

RNG_output:
I'm adding the ability to request PRNGs from the set tested in Test_results.txt by number, for easier automation. So you can say something like "RNG_output nonrecommended_rng(71) name", and it would give you the name of the 71st non-recommended PRNGs listed in Test_results.txt. Or you could request bytes of output instead of the name, or you could call RNG_test with that to test it directly (RNG_test output would list the RNG by its actual name, not by its number).

RNGs:
I'm thinking of adding rarns16/32/64 to either the recommended PRNG set or the non-recommended set. I wrote this a while ago to act as a good random access PRNG, but fast-forwarding was slower than I wanted so I scrapped it. Still, it supports random access, and unlike xsm it doesn't require multiplication, and maybe eventually I'll figure out how to speed up fast-forwarding/rewinding on it, the literature seems to suggest that faster ways than what I'm doing are possible. Internally it's an xorshift-style LFSR of 48, 96, or 192 bits, but it has a non-linear output function so it passes most tests. I think rarns16 fails PractRand standard at around 16 TB. Still uncertain about this.

[G. Jones]

Re: rarns.
I'm interested. There is a way to do fairly quick fast-forward with polynomial exponentiation, which is
O(n) times faster than matrix exponentiation, where there are n bits of state. If you're planning to do 0.94 inside a week or so, just do it and i'll attempt to do the faster code and send it to you afterwards. If it's going to be longer, maybe try to get me just rarns so i can get you the fast-forward code in time for inclusion. (BTW, i'm not really a C++ programmer. Guaranteed you will want to clean up my code before releasing it.)

RNG_output:
On RNGs that have no meaningful seed that PractRand can see (ie stdin, stdin8/16/32/64), instead of displaying a meaningless random seed value it nows displays "unknown". But I'm considering changing that so that such RNGs can specify a "seed" string from the command line options and have that show up instead.
old:
./RNG_test stdin64
RNG_test using PractRand version 0.93
RNG = stdin, seed = 0x9a431728
test set = normal, folding = standard (64 bit)

new:
./RNG_test stdin64
RNG_test using PractRand version 0.94
RNG = stdin, seed = unknown
test set = normal, folding = standard (64 bit)

alternative under consideration:
./RNG_test stdin64 -seed spooooon!
RNG_test using PractRand version 0.94
RNG = stdin, seed = spooooon!
test set = normal, folding = standard (64 bit)

rarns16/32/64 have been added as non-recommended PRNGs. If you can get them to fast-forward/rewind quickly (I was indeed doing matrix exponentiation, and it was ssslllooowww) I'll make them recommended PRNGs for 0.95. I'm aiming for a release in the next couple of days, but not sure if I'll make it.

A new test has been added to the core test battery, named mod3n. Actually, [1st128K/8M]mod3n, since I'm testing only a limited subset of the PRNG output, the first 128 kilobytes out of every 8 megabytes of PRNG output. That's done to avoid spending too much time on this, which is a relatively slow test that detects relatively few PRNGs. Nevertheless it's going in to the core set because it's fairly general purpose, and detects bias in PRNGs that my other tests miss, and still works fairly even when it only gets to see a little of the data. This test is based upon the mod3 test in gjrand (thanks Geronimo Jones!) that looks at overlapping frequency of the modulo 3 value of 9 consecutive integers. However, this version is generalized a bit - where gjrand does that on 32 bit integers, this does it for 8, 16, 32, 64, 128, 256, etc bit integers, allowing it to find bias a wider variety of PRNGs. I'd actually done a lot of the work on this a while ago, but a bug had kept it from working decently and I'd forgotten about it until just recently. I'm still working on getting better p-value quality out of this, but that should be done in the next day or so.

I'm also working on tests to do better against LCGs, since they're the category of PRNGs that PractRand seems weakest against (in 0.93 PractRand mainly detects standard LCGs by exhausting their period, or at least coming close to exhausting it). I've had a fair bit of success, but am not entirely happy - the results tend to be overly brittle, not finding flaws in any significant non-LCGs, finding bias in LCGs too quickly, sometimes (rarely, but still) having the failures disappear as longer sequences get tested, not producing usable results off of short test runs even for poor LCGs, not distinguishing good LCG constants from bad, etc. I'd like to have at the tests in PractRand be... relatively general purpose, not just targetting a single formula, and relatively stable, so that once it finds a failure it just gets more and more extreme failures as more bytes get tested. I've got a few ideas on what to do here, but not sure if they'll work, and they'll probably take more time than I have before the 0.94 release.
(admittedly some of the same complaints I'm making on this could be applied to the BRank test, but that test finds flaws in non-LFSR PRNGs, including some where it's not obvious glancing at the code that it will have binary rank issues; that makes up for the issues, where my current anti-LCG code doesn't quite I think)

[G. Jones]

Lcgs, except for the weakest of them, are a real pain. Having failures disappear with more data seems normal. Lcgs are too uniform over the full cycle, and not uniform enough over some portions of the cycle. Quite a significant bias builds up, then they balance it out exactly by filling in all the missing values. Some sort of meta-testing may help, but that is a lot harder to do than most people think. Calculating accurate distributions (and quickly) for your test over portions of the data can be tricky. Good luck :-)

Originally I was doing large numbers of non-overlapping frequency tests on a couple small (2-4 bit) windows of bits at various different arrangements, then generating a p-value off of the most extreme subtest result found there. That is, for every 32 bit output I'd take the low ~3 bits or so, plus another ~3 bits at offset X, and another at offset Y, and combine those to make a ~9 bit index, but I'd do that a large variety of X & Y values at once, or in some variants just a large variety of X values and then changing Y every ~2 megabytes tested. That worked a little against a reasonable variety of weaker PRNGs, including some LCGs. Some versions were pretty slow, so sometimes I'd only do N sweeps per M kilobytes.

So for LCGs I tried a variant that such that X = -Y (symetric spacings of bit windows), and always a multiple of 16 bits, and that worked a bit better, but not well enough for LCGs that discarded 40+ low bits. Then I tried one where X was always very large (previously I'd start near zero and work up, ie 0,16,...16 times 255, then here I switched to starting at a kilobyte or more and working down in steps of 16 bits), and it got much better against LCGs, and didn't even seem to need varied values of X I think, just large powers of 2. And it could nab some big LCGs, though I only tested power-of-2 modulus LCGs, and on some settings it could do so very quickly.

But yeah, some versions, particlarly the better ones in terms of speed and whatnot were acting as if the frequency tests produced very uneven results in the short term but patterns that tended to cancel each other out after a little bit. And some versions didn't like to produce stable results until they had a lot of bytes, even if they'd flunk good LCGs as soon as they had stable results. And the better they did against LCGs the worse they did against other stuff I think.

For the disappearing bias in the frequency tests, my thought was to run a coupon collectors test on the same indeces I was using for the frequency tests, that way bias and counterbias shouldn't be to cancel each other out so easily. I hope. But before I finished implementing that I broke that code, and decided I had better things to do than fix it. When I go back, probably instead of going back to that approach straight away, instead I'll go my FPF variants that try to combine multiple tests. The idea there is to start with seperating things out the way FPF does, where it X values that occur at rate 0.5/X, and another X that occur at rate 0.25/X, and another X at 0.125/X and so on, but instead of just doing simple frequency tests on them like I do in FPF try doing a wider variety of tests - simple frequency, coupon collector, gap, and a limited overlapping frequency test. I think that might be able to detect power-of-2-modulus LCGs too, at least eventually, and be more general-purpose than what I've been doing. Or not. Probably I'll have to come back to this stuff instead if I actually want to detect LCGs that discard 48+ low bits.

While I'm at it, for rarns, the underlying state transition function is:
old = xs1;
xs1 = xs2 ^ (xs2 >> S1);
xs2 = xs3 ^ (xs3 << S2);
xs3 = xs3 ^ (xs3 >> S3) ^ old;

For the 16 bit variant, S1=3,S2=7,S3=8.
For the 32 bit variant, the shifts are... uh oh. In the code they're set at 1,2,3, but I'm pretty sure that was just placeholders until I got around to testing for a combination of large cycle lengths and relatively good avalanche properties. Same for the 64 bit version. Either I never got around to figuring out good values at 32 and 64 bit, or the values got lost over the intervening years.

[G. Jones]

Thanks, got it working for 64 bit. Looks like about 300 microseconds for a random 128 bit seek on a 2.7GHz AMD64. Should be plenty good enough for practical purposes. I'm planning to get it going for the smaller sizes and clean up a bit before posting back in a day or two. Probably it will still be C and quite ugly. Hope the non-linear back end is fairly good. Quality without a back-end is about as good as Xoroshiro128 without a back end.

Sounds good. C is no problem. Ugly should be fine too, though it's hard to say with certainty without seeing it.

The output function isn't that great, but seems good enough in my testing, even when applied to bad shift constants. I figure that for single-cycle PRNGs I should test them with poor constants, since the short-range patterns that show up with bad constants are still present with good constants just at practicaly impossible to detect long ranges instead of at short ranges. I'll try the output on gjrand and TestU01 before releasing it to be sure. With the full (3,7,8) shift constants it passed gjrand out to --ten-tera, though the results on --ten-tera looked a bit suspicious.

[G. Jones]

Here's the random seek code, in the attachment. I've probably not done an attachment here before. Complain if it didn't work and i'll find another way.