Testing the quality of PRNGs

Question

I am playing around with PRNGs (like Mersenne Twister and rand() function of stdlib) and I would want a good test that would help me ascertain the quality of random data produced by the PRNGs. I have calculated the value of Pi using random numbers generated by the PRNGs, and I find rand() and Mersenne Twister to be very close to offer a distinction (do I need to scrutinize after 10 decimal points?).

I do not have much idea about Monte Carlo simulations; please let me know about some algorithm/application (possibly something simple yet which could provide good inferences) that would help me distinguish them in terms of quality.

---

EDIT 1: I didn't notice before, but there is a similar thread: How to test random numbers?

EDIT 2: I am not able to interprete the results of NIST, as mentioned in one of the comments. I got this idea of visually interpreting the pattern (if any) from random.org and am following that because of it's simplicity. I would be very glad if someone could comment on the process of my testing:

1. Generate N randoms from [0,1] using rand() and MT1997
2. if (round(genrand_real1() / rand_0_1())) then red pixel, else black

As I understand that this is not a very precise solution, but if this provides a reasonable estimate, then I could live with this at the present moment.

Argyll

i'm not so sure about getting any random data from pseudorandom number generators - but i think you could implement en.wikipedia.org/wiki/Fair_coin#Fair_results_from_a_biased_coin with them.. – Blanketyblank

are you saying that because the values generated from PRNGs are predictable? thank you – Argyll

yes, that is the distinction - it was just a reminder for you to check whether a PRNG is good enought for your application and you don't need a TRNG like random.org – Blanketyblank

Answer 1

There are two standard test suites for testing random numbers.

1. NIST test suite. They have an implementation in C.
2. Diehard Test Suite (developed by George Marsaglia). There is a C library implementation of these tests.

There is a R interface to the Dieharder library, called RDieHarder. This library provides an interface to both the NIST and Diehard test suites.

Concealment

I am using NIST, but I think although my test passes, there's some problem; can you please help? - I have generated long random values, and converted them to binary and stored in a file. Say 100 randoms are there in the file, I do assess 100 and follow the steps in the "Running the Test Code" section of the doc (chose the bit streams generated to be 10 as in the doc). But I see that my "finalAnalysisReport.txt" for the default test case contains almost no info. – Argyll

Your best bet is to ask another question. – Concealment

This answer was good, but is outdated now. See the other answer for an update (TL;DR: L'Ecuyer's TestU01, or PractRand). – Shearin

Answer 2

There are several statistical tests suites available. I wrote, copied, and otherwise gathered together 120 PRNGs and tested each with a variety of tests suites given 4 hours per PRNG per test suite:

• PractRand (standard, 1 terabyte) found bias in 78 PRNGs
• TestU01 (BigCrush) found bias in 50 PRNGs
• RaBiGeTe (extended, 512 megabit, x1) found bias in 40 PRNGs
• Dieharder (custom command line options) found bias in 25 PRNGs
• Dieharder (-a command line option) found bias in 13 PRNGs
• NIST STS (default, 64 megabit x128) found bias in 11 PRNGs

How many of those were in PRNGs that the other test suites all missed?

• PractRand (standard, 1 terabyte) found 22 unique biases, in a wide variety of categories.
• RaBiGeTe (extended, 512 megabit, x1) found 5 unique biases, all in LCGs and combination LCGs.
• TestU01 BigCrush found 2 unique biases, both in small chaotic PRNGs.
  No other test suite found any unique biases.

In short, only PractRand, TestU01, and possibly RaBiGeTe are worth using.

Full disclosure: I wrote PractRand, so either the set of PRNGs or any other non-qualitative measure could be biased in its favor.

Miscellaneous advantages:

• PractRand and TestU01 tend to be the easiest to interpret the output of in my opinion.
• PractRand and Dieharder tend to be the easiest to automate testing for via command line interface I think.
• PractRand and RaBiGeTe were the only ones to support multithreaded testing.

Miscellaneous disadvantages:

• PractRand required more bits of input to test than other test suites - could be a problem if your RNG is very slow or otherwise limited on amount of data produced.
• RaBiGeTe and NIST STS both have interface issues.
• Dieharder and NIST STS both have false-positive issues.
• NIST STS had the worst interface in my opinion.
• I could not get Dieharder to compile on Windows. I managed to get TestU01 to compile on windows but it took some work.
• Recent versions of RaBiGeTe are closed-source and windows-only.

The set of PRNGs tested: The PRNG set includes 1 large GFSR, 1 large LFSR, 4 xorshift type PRNGs, 2 xorwow type PRNGs, 3 other not-quite-LFSR PRNGs. It includes 10 simple power-of-2 modulus LCGs (which discard low bits to reach acceptable quality levels), 10 power-of-2 modulus not-quite-LCGs, and 9 combination generators based primarily around LCGs and not-quite-LCGs. It includes 19 reduced strength versions of CSPRNGs, plus one full strength CSPRNG. Of those, 14 were based upon indirection / dynamic s-boxes (e.g. RC4, ISAAC), four were ChaCha/Salsa parameterizations, and the remaining 2 were Trivium variants. It includes 11 PRNGs broadly classifiable as LFib-type or similar, not counting the LFSRs/GFSRs. The rest (about 35) were small state chaotic PRNGs, of which 10 used multiplication and the others were limited to arithmetic and bitwise logic.

Edit: There is also the test set in gjrand, which is very obscure and a little odd, but actually does extremely well.

Also, all of the PRNGs tested are included as non-recommended PRNGs in PractRand.

Temikatemp

I'm happy to recommend your answer, however, as written there is no evidence. Can you provide links to papers, that back up your claim? Or a some instructions on how to repeat your experiments. – Concealment

No evidence whatsoever! DieHarder has around 106 tests. PractRand and TestU01 are written in C and C++ and require the user to integrate their generator! The easiest ever to use so far are DieHarder (ubuntu package) and NIST STS (python UI and implementation)! I strongly believe you're biased to your work and indeed as @Concealment mentioned in his comment, you need to provide a paper that supports your claims though! – Guttate

Answer 3

You're best off looking into the volume 2 of the Knuth's series.

For a shorter read, look up the corresponding chapter of the Numerical Recipes.

If you're only interested in a sort of a baseline for a MC simulation--- linear congruential generators are best avoided, Mersenne Twister is good enough in the vast majority of cases.

Jehad

Can you give a link to evidence for the claim that LGCs are best avoided for Monte-Carlo simulations? – Judoka

@ziggystar: well, you can look up in Knuth. Or Numerical Recipes. Or google up the results the standard test suites, eg from the csgillespie answer. – Jehad

Answer 4

I created and maintain this flexible framework for when I want to play around random numbers. It may help newcomers get started more easily.

https://github.com/sysaulab/softrng

Reade