How good (or bad) is my makeshift PRNG?

Question

Say I have designed a makeshift PRNG for my personal amusement, now I would like to see how good it is. How do I benchmark its "randomness"? Ideally, I want to know a statistics test, such that if I pass it (or get a high score) I can write up a paper to announce a new state-of-the-art PRNG to the world. Yeah I know that's unlikely, but by saying this I mean I expect a really "strict" test.

I did some searching and Wikipedia points me to TestU01, which is said to be state-of-the-art, but its latest release is in 2009, or nearly ten years ago. I suppose a lot of things have happened since then.

Answer 1

There is no such test. All automated tests for examining the randomness of a PRNG have limitations. If you read some papers in the literature that propose PRNGs, you might notice that they do more than just run an automated test against their scheme.

Of course you can always write up anything at any time. For the research community to find it interesting, or for practitioners to find it useful, it will probably take more than just passing an automated test. Getting a paper to be accepted at a quality peer-reviewed conference will probably require the reviewers to find it novel and interesting. For your PRNG to be adopted in practice, your PRNG will probably need to be better than existing ones in some relevant respect (perhaps it is faster and the quality of the pseudorandomness is "as good" in some sense as existing schemes; or better in some other way that implementors care about).

Answer 2

If you want just some basic ideas what you might test.

The simplest test just generates a million random numbers and puts them into say 100 buckets depending on their value. Each bucket should contain about 10,000 random numbers. If not, your random number generator is off. However, just generating 1, 2, 3, 4, 5, ... will pass this test, so it's not a very good test.

Next, generate a million "random" numbers. Count how often the second of two consecutive "random" numbers is larger than the first. This should happen in about 50% of all cases (the very first random number generator that I ever used had a distribution of 40% / 60%).

A slightly more complicated one: If you generate a, b, c there are six possibilities how these numbers could be ordered. Each possibility should happen 1/6th of the time. If you examine Marsaglia's XORshift generator where he programer has to choose some constants for the generator, quite a few constants fail this test.

Each test that you pass gives you a bit more confidence that the random number generator is Ok. Once you run out of ideas for more tests you follow the links in Mars' answer. I wouldn't worry about a set of tests being 10 years old, there's not that much changing. The examples that I gave for example are nowhere near state of the art, but you'd still have to pass them, like you'd have to pass the TestU01 tests.

Answer 3

I can't argue with the second paragraph of D.W.'s answer, and D.W. is right that all tests have limitations: That's intrinsic to PRNG-testing. But TestU01 is still pretty much state of the art. You can use the NIST suite, too, which includes some tests not in TestU01, I believe. You might want to skim L'Ecuyer and Simard's paper on TestU01 and O'Neill's PCG paper. Both provide insight. Kneusel's Random Numbers and Computers is a good introductory book.