I'm looking to find the most efficient way to change integers from a random number generator to a different inclusive number range.
I know of 2 ways so far:
- Change the number into a decimal in the range of [0,1) and multiply it by the difference between the minimum and maximum values* in the new range.
- Find the remainder of the number divided by the difference between the minimum and maximum numbers* in the new range.
*The difference will have to be incremented by 1 to get the correct inclusive range on the results
There is however, a problem with both of these methods:
- the decimal method involve a lot of floating point calculations, which are slow
- the remainder method will favor lower numbers in the number range
To illustrate #2 above, consider getting a random value of a unsigned byte.
You get a random number in the range of 0-255.
Suppose you wanted a number in the range of 1-255, you might use the following formula:
number = random() % 255 + 1;
any number from 0-254 will simply be increased by 1, giving you a range of 1-255.
255, however will also grant you a 1, giving 1 DOUBLE the probability as the rest of the numbers.
this illustrates the following:
probabilty of number in range [newMin, newMin + oldMax % (newMax - newMin) ] is (oldMax - oldMin) / (newMax - newMin) rounded UP
probability of number in range (newMin + oldMax % (newMax - newMin) , newMax] is (oldMax - oldMin) / (newMax - newMin) rounded DOWN
In my situation, I am getting an 8 byte value, so the effects of this flaw in the remainder method would require an insanely large sample of numbers before the flaw effects the results noticeably.
So if these are the only 2 methods available, I would disregard this distribution flaw to increase performance.
Is there a method that has better performance than method #1 but better results than #2?