Generating Uniform Random Deviates within a given range

Question

I'd like to generate uniformly distributed random integers over a given range. The interpreted language I'm using has a builtin fast random number generator that returns a floating point number in the range 0 (inclusive) to 1 (inclusive). Unfortunately this means that I can't use the standard solution seen in another SO question (when the RNG returns numbers between 0 (inclusive) to 1 (exclusive) ) for generating uniformly distributed random integers in a given range:

result=Int((highest - lowest + 1) * RNG() + lowest)

The only sane method I can see at the moment is in the rare case that the random number generator returns 1 to just ask for a new number.

But if anyone knows a better method I'd be glad to hear it.

Rob

NB: Converting an existing random number generator to this language would result in something infeasibly slow so I'm afraid that's not a viable solution.

Edit: To link to the actual SO answer.

Answer 1

I don't see why the + 1 is needed. If the random number generator delivers a uniform distribution of values in the [0,1] interval then...

result = lowest + (rng() * (highest - lowest))

should give you a unform distribution of values between lowest

rng() == 0, result = lowest + 0 = lowest

and highest

rng() == 1, result = lowest + highest - lowest = highest

Including + 1 means that the upper bound on the generated number can be above highest

rng() == 1, result = lowest + highest - lowest + 1 = highest + 1.

The resulting distribution of values will be identical to the distribution of the random numbers, so uniformity depends on the quality of your random number generator.

Following on from your comment below you are right to point out that Int() will be the source of a lop-sided distribution at the tails. Better to use Round() to the nearest integer or whatever equivalent you have in your scripting language.

Answer 2

Presumably you are desperately interested in speed, or else you would just suck up the conditional test with every RNG call. Any other alternative is probably going to be slower than the branch anyway...

...unless you know exactly what the internal structure of the RNG is. Particularly, what are its return values? If they're not IEEE-754 floats or doubles, you have my sympathies. If they are, how many real bits of randomness are in them? You would expect 24 for floats and 53 for doubles (the number of mantissa bits). If those are naively generated, you may be able to use shifts and masks to hack together a plain old random integer generator out of them, and then use that in your function (depending on the size of your range, you may be able to use more shifts and masks to avoid any branching if you have such a generator). If you have a high-quality generator that produces full quality 24- or 53-bit random numbers, then with a single multiply you can convert them from [0,1] to [0,1): just multiply by the largest generatable floating-point number that is less than 1, and your range problem is gone. This trick will still work if the mantissas aren't fully populated with random bits, but you'll need to do a bit more work to find the right multiplier.

You may want to look at the C source to the Mersenne Twister to see their treatment of similar problems.