Using paired numbers to create a random integer

Question

I posted a bunch of open source random number generators on my site , including a normally distributed number random number generator. To generate a random integer in the range of 10-20, I would write something like new NormalRandomGenerator(10, 20).Next() .

Someone wrote this comment:

Just wondering if you need to implement it "int Next ()" in the terms "double NextDouble ()", as int for double conversions (and visa-versa) can be very slow on some hardware, including the latest PC hardware, although Im not particularly relevant on the latest processors at the moment.

I believe this comment refers to the fact that when someone calls Next(20) on one of my classes, internally this call translates to something like (int)someMersenneTwister.NextDouble() * 20 (I don't I remember if I used rounding).

I implemented it this way because MT is fast and efficient (although it has a huge random period). From what I understand, this is the standard way to generate random numbers - calling Next() , which returns double in the range [0 .. 1), and then multiplies and outputs by int.

Are there any problems in terms of my design? Is there a better way (more efficient, faster) to generate an integer random number that doesn't use doubles?

Sorry if this sounds vague. I am not sure if there is a problem here.

Answer 1

Not the answer to your question (because it does not make sense in its current form of IMO). But looking through my code, I see a number of errors and other problems:

• Sowing. You are wasting time, and this leads to seed collisions when creating several UniformRandomGenerator within a few milliseconds. You inherit this problem from System.Random .
• MersenneTwister.NextDouble - low quality. double has about 53 digits, you fill in 32. Almost as bad as System.Random , which fills in 31.
• MersenneTwister.Next(int maxValue) now stretches this bad double for the desired interval. If the interval is long, this can lead to severe deviations. System.Random has a very similar problem.
• Next(int minValue, int maxValue) contains int overflow when evaluating maxValue-minValue
• The constructor of NormalRandomGenerator calculates the average value as this.Mean = ((max - min) / 2) + min; . This is integer division and therefore leads to bias if max-min is odd. A strange choice, since this.Mean is double.
• The code for calculating normally distributed numbers also looks strange, but I can’t help you, since I don’t know what it should do.

---

If you want to generate uniform random integers, this is a duplicate of my own question: Generating homogeneous random integers with a certain maximum that focuses on efficiently creating these integers without introducing an offset. I recommend combining my answer with LukeH's answer.

Answer 2

The generation of random integers by scaling the double in the range [0..1] is excellent, provided that the generated double is fairly evenly distributed. However, most pseudo-random number generators, including Mersenne Twister, initially generate (32-bit unsigned) integers, so it would be nice if we didn't need to double rounding.

If the boundary of N is a power of 2, we can first create a 32-bit random integer X and take X mod N. This is guaranteed to give an even distribution result. But if N is not a power of 2, taking the absolute value of the offset in the resulting distribution (there are more than 32-bit unsigned integers for which X mod 7 is 0, for example 6.) If N is small, then finding such an offset will require a huge number of generated numbers but theoretically the distribution will be wrong.

To generate integers with a truly even distribution in the range [0..N) for N that are not powers of two, we can resort to a sampling algorithm: first, calculate M so that it is the smallest power of 2 more than N (for N = 13, M = 16, etc.). Then generate a 32-bit integer X, compute Y = X mod M. Now, if Y <N, we are done, Y is our number. If Y> = N, discard it and generate another one until Y <N. is displayed. If the base prng is good, the expected number of generated numbers never exceeds 2 (it depends on N), and although the cycle is not guaranteed to end, it will be interrupted with overwhelming probability. In a practical application, you need to put a limit counter in a loop and drop it to another method to protect it from degassing generators.

Which method is the fastest? Only profiling will tell. It depends on the hardware, language and quality of the code.

A more detailed discussion can be found in Knuth TAOCP, Part 2.

Answer 3

You can use the Random.Next method:

http://msdn.microsoft.com/en-us/library/system.random.next.aspx

You will receive a non-negative random number less than the specified maximum specified at your suggestion or specify a range of numbers (min and max)

Sincerely.