What is the proper method of constraining a pseudo-random number to a smaller range?

Question

What is the best way to constrain the values of a PRNG to a smaller range? If you use modulus and the old max number is not evenly divisible by the new max number you bias toward the 0 through (old_max - new_max - 1). I assume the best way would be something like this (this is floating point, not integer math)

random_num = PRNG() / max_orginal_range * max_smaller_range

But something in my gut makes me question that method (maybe floating point implementation and representation differences?).

The random number generator will produce consistent results across hardware and software platforms, and the constraint needs to as well.

I was right to doubt the pseudocode above (but not for the reasons I was thinking). MichaelGG's answer got me thinking about the problem in a different way. I can model it using smaller numbers and test every outcome. So, let's assume we have a PRNG that produces a random number between 0 and 31 and you want the smaller range to be 0 to 9. If you use modulus you bias toward 0, 1, 2, and 3. If you use the pseudocode above you bias toward 0, 2, 5, and 7. I don't think there can be a good way to map one set into the other. The best that I have come up with so far is to regenerate the random numbers that are greater than old_max/new_max, but that has deep problems as well (reducing the period, time to generate new numbers until one is in the right range, etc.).

I think I may have naively approached this problem. It may be time to start some serious research into the literature (someone has to have tackled this before).

Answer 1

I know this might not be a particularly helpful answer, but I think the best way would be to conceive of a few different methods, then trying them out a few million times, and check the result sets.

When in doubt, try it yourself.

EDIT

It should be noted that many languages (like C#) have built in limiting in their functions

int maximumvalue = 20;
Random rand = new Random();

rand.Next(maximumvalue);

And whenever possible, you should use those rather than any code you would write yourself. Don't Reinvent The Wheel.

Answer 2

This problem is akin to rolling a k-sided die given only a p-sided die, without wasting randomness.

In this sense, by Lemma 3 in "Simulating a dice with a dice" by B. Kloeckner, this waste is inevitable unless "every prime number dividing k also divides p". Thus, for example, if p is a power of 2 (and any block of random bits is the same as rolling a die with a power of 2 number of faces) and k has prime factors other than 2, the best you can do is get arbitrarily close to no waste of randomness, such as by batching multiple rolls of the p-sided die until p^n is "close enough" to a power of k.

Let me also go over some of your concerns about regenerating random numbers:

• "Reducing the period": Besides batching of bits, this concern can be dealt with in several ways:
  • Use a PRNG with a bigger "period" (maximum cycle length).
  • Add a Bays–Durham shuffle to the PRNG's implementation.
  • Use a "true" random number generator; this is not trivial.
  • Employ randomness extraction, which is discussed in Devroye and Gravel 2015-2020 and in my Note on Randomness Extraction. However, randomness extraction is pretty involved.
  • Ignore the problem, especially if it isn't a security application or serious simulation.
• "Time to generate new numbers until one is in the right range": If you want unbiased random numbers, then any algorithm that does so will generally have to run forever in the worst case. Again, by Lemma 3, the algorithm will run forever in the worst case unless "every prime number dividing k also divides p", which is not the case if, say, k is 10 and p is 32.

See also the question: How to generate a random integer in the range [0,n] from a stream of random bits without wasting bits?, especially my answer there.

Answer 3

If PRNG() is generating uniformly distributed random numbers then the above looks good. In fact (if you want to scale the mean etc.) the above should be fine for all purposes. I guess you need to ask what the error associated with the original PRNG() is, and whether further manipulating will add to that substantially.

If in doubt, generate an appropriately sized sample set, and look at the results in Excel or similar (to check your mean / std.dev etc. for what you'd expect)

Answer 4

If you have access to a PRNG function (say, random()) that'll generate numbers in the range 0 <= x < 1, can you not just do:

 random_num = (int) (random() * max_range);

to give you numbers in the range 0 to max_range?

Answer 5

Here's how the CLR's Random class works when limited (as per Reflector):

long num = maxValue - minValue;
if (num <= 0x7fffffffL) {
    return (((int) (this.Sample() * num)) + minValue);
}
return (((int) ((long) (this.GetSampleForLargeRange() * num))) + minValue);

Even if you're given a positive int, it's not hard to get it to a double. Just multiply the random int by (1/maxint). Going from a 32-bit int to a double should provide adequate precision. (I haven't actually tested a PRNG like this, so I might be missing something with floats.)

Answer 6

Psuedo random number generators are essentially producing a random series of 1s and 0s, which when appended to each other, are an infinitely large number in base two. each time you consume a bit from you're prng, you are dividing that number by two and keeping the modulus. You can do this forever without wasting a single bit.

If you need a number in the range [0, N), then you need the same, but instead of base two, you need base N. It's basically trivial to convert the bases. Consume the number of bits you need, return the remainder of those bits back to your prng to be used next time a number is needed.