Pseudo-random number generator

问题:

What is the best way to create the best pseudo-random number generator? (any language works)

回答1:

Best way to create one is to not to.

Pseudo-random number generators are a very complex subject, so it's better off to use the implementations produced by the people that have a good understanding of the subject.

回答2:

It all depends on the application. The generator that creates the "most random" numbers might not be the fastest or most memory-efficient one, for example.

The Mersenne Twister algorithm is a fairly fast pseudo-random number generator that produces quite good results. However it is not deemed good enough for cryptographic applications.

This is just one example; without more details about your specific application it is impossible to give a conclusive answer.

回答3:

The German magazine C't tested a number of software and hardware generators in the 2/2009 issue and ran the results through various statistical tests.

I scanned the results here.

I would not bother writing my own. The article mentions that even Donald Knuth failed with his "Super-random number generator", which was not so random after all. Get one that passed all tests (had a result > 0 in all columns). They also tested a setup with a VIA EPIA M10000 mobo, which has a hardware RNG. I like this option for a commercial or semi-commercial setup that requires a robust random number server with high throughput.

Unless, of course, you are just playing around, in which case this may be good enough.

回答4:

PRNG algorithms are complicated, as is acquiring the right sources of entropy to make them work well. This is not something you want to do yourself. Every modern language has a PRNG library that will almost certainly be suitable for your use.

回答5:

Yikes, that can get VEEEEEERY complicated! There seem to be a number of metrics for how to measure the "randomness" of a random number generator, so it's difficult to meaure which are "best". I would start with Numerical Recipes in C (or whatever langauge you can find one for) for a few examples. I coded up my first simple one from the examples given there.

EDIT: It's also important to start by determining how complex you need your random number generator to be. I remember a rude awakening I had in C years ago when I discovered that the default random number generator had a period somewhere around 32,767, meaning that it tended to repeat itself periodically after generating that many numbers! If you need a few dice rolls, that's fine. But not when you need to generate millions of "random" values for a simulation.

回答6:

See Pitfalls in Random Number Generation

回答7:

See this link for the TestU01 suite of tests, which includes several batteries of tests.

http://www.iro.umontreal.ca/~simardr/testu01/tu01.html

In the paper, the author demonstrates the test result on a variety of existing RNGs, but not .NET System.Random (as far as I can tell). Though he does test VB6's generator.

Very few pass all the tests...

回答8:

Steal the one out of knuth seminumeric. It is high quality and simple to implement. It uses a pair of arrays, addition, and a couple of ifs. Cheap, effective, and a nice long period 2^55 if i recall correctly.

回答9:

If you're going to work in C++, Boost has a collection of PRNGs that I'd trust a lot more than whatever comes in standard libraries. The documentation might be helpful in picking one out. As always, how good a PRNG is depends on what you're using it for.

回答10:

My favorites are Hardware random number generators