Random numbers using C#

I'm looking at generating a random number between 1 and 5 million. The process doesn't have to be quick (although it would be good if it was), but it must be as random as possible (I know nothing is random). I have a variety of data sources for the seed.

I'm not sure if开发者_运维知识库 the .NET Random class is going to be good enough for this.

This will be used to select a winning ticket.

The System.Random class probably is good enough:

Pseudo-random numbers are chosen with equal probability from a finite set of numbers. The chosen numbers are not completely random because a definite mathematical algorithm is used to select them, but they are sufficiently random for practical purposes. The current implementation of the Random class is based on Donald E. Knuth's subtractive random number generator algorithm. For more information, see D. E. Knuth. "The Art of Computer Programming, volume 2: Seminumerical Algorithms". Addison-Wesley, Reading, MA, second edition, 1981.

The only thing you have to watch out for is that you don't reuse the same seed too often:

If the same seed is used repeatedly, the same series of numbers is generated. One way to produce different sequences is to make the seed value time-dependent, thereby producing a different series with each new instance of Random.

If you need cryptographic random number, go with the System.Security.Cryptography.RNGCryptoServiceProvider class or use the RandomNumberGenerator.Create() factory method to create the default configured random number generator.

There was actually a really good article I read fairly recently on different types of PRNGs and how they fare in terms of several different randomness tests. Unfortunately, I can't seem to find it now. The gist of it, however, was that the default random number generators in almost every popular programming language are quite naïve and have pretty significant biases.

Another answer already mentions that no PRNG at all, no matter how sophisticated the algorithm, is good enough for cryptographic applications. This is true. Since you mention that this will be used to "select a winning ticket", let's ignore that for now.

The Knuth algorithm used by the .NET System.Random class is optimized mainly for speed, not random distribution. It is "random enough" for many purposes, which most applications never stray too far from, but in the fields of (a) gaming and (b) statistical simulation, most people seem to think that it is a poor choice. It's better than the LCGs that used to be the default in older libraries, but you still don't want to be using it for something like a lotto.

Don't get fooled into thinking that you just use a crypto source, either. The problem with crypto RNGs is that they fill a stream of bytes, but turning this into a single random integer between x and y requires that you do some modular arithmetic (or rounding - same result either way). And if your random range doesn't divide perfectly evenly into whatever power of 2 is defined by the byte length, then you're going to end up with a bias in the lower numbers. The generated data has high entropy, but your result will be biased.

As a simple example, let's just say you get a "perfect" random number from 1 to 10 and now you want to turn that into a random number between 1 and 7. How do you do it? Simply calculating result % 7 will be heavily biased toward the numbers 1-3. There are some ways to reduce the bias when using a crypto RNG but the point I'm trying to make is that crypto RNGs are designed for crypto applications, and using one of those for a Monte Carlo simulation isn't usually the best idea.

As far as I know, the most popular "good" PRNG today, which is used commonly in gaming applications, is the Mersenne Twister. There's a .NET implementation here. This algorithm passes all of the Diehard Tests for random distribution; it shows almost no bias and is a good choice when you are using random numbers for probabilistic and statistical applications.

The GNU Scientific Library also has a number of RNG algorithms and, not surprisingly, the Mersenne Twister is at the top of the list. Some of the others are worth looking at for curiosity's sake, though; RANLUX also scores pretty high on the diehard test IIRC.

Eric is correct with his comment, of course; all of this information is for naught if you don't have specific technical requirements on "how random" you need your random numbers to be. I'm using a definition that would be applicable to a relatively low-impact gambling/gaming application (i.e. not a major registered gambling site with millions of visitors per day - there are stricter rules on randomness for those).

See Jon Skeet's blog post Revisiting Randomness a very good review of how to use Randomness:

Revisiting randomness
Almost every Stack Overflow question which includes the words "random" and "repeated" has the same basic answer. It's one of the most common "gotchas" in .NET, Java, and no doubt other platforms: creating a new random number generator without specifying a seed will depend on the current instant of time. The current time as measured by the computer doesn't change very often compared with how often you can create and use a random number generator – so code which repeatedly creates a new instance of Random and uses it once will end up showing a lot of repetition.

more...

To generate a random number, create an object of Random class, and then use Next function of this object to generate a random number. It has many overloads like:

Next(int minimum, int maximum);
Next(int Maximum);

where you can specify the minimum and maximum range between which you want the random number.

Code snippet:

Random random = new Random();
int maxValue = 100;

int r = random.Next(maxValue);

The System.Random class is very problematic and isn't a good fit with the requirement. In theory, it should provide better results than many other pseudo-random generators out there. It is a direct and literal port of example C code for a Lagged Fibonacci Generator (LFG) provided on page 283 of the second edition of 'Numerical Recipes in C' (the code was re-written in later editions). LFGs use a better algorithm than Linear Congruential Generators (LCGs) used is many other libraries (e.g., Java).

Unfortunately, Microsoft's implementation of System.Random class has a bug in it. See http://connect.microsoft.com/VisualStudio/feedback/details/634761/system-random-serious-bug for more information. It seems someone accidently typed in '21' when the meant to type in '31'. This compromises the algorithm's pseudo-random characteristics. The link includes an explanation from MS as to why they feel unable to fix the error at this stage.

If you're looking for true random numbers then you should consider using an online random number generator that uses natural phenomenon, such as http://www.random.org, which uses atmospheric noise. True random numbers also make good seeds for psuedo-random number generators.

Sipwiz shows how to use it in C# in his answer: Generate random values in C#. It's also discussed here: http://www.vcskicks.com/random-number-generator.php.

There's a lot of angles to random number generators. An interesting alternative implementation is ISSAC (ttp://burtleburtle.net/bob/rand/isaac.html), which also contains a good discussion of bias and such, and there's a C# version, too (http://burtleburtle.net/bob/rand/isaacafa.html).

.NET's Random should be fine for this:

var random = new Random(System.DateTime.Now.Millisecond);

int randomNumber = random.Next(1, 5000000);