1
$\begingroup$

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:

  1. 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.
  2. 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:

  1. the decimal method involve a lot of floating point calculations, which are slow
  2. 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?

$\endgroup$
  • $\begingroup$ Do you need an integer or a floating point result in the end? Floating point computations are NOT slow. Modern chips can do many per cycle (depending on vector length). Remainder division, on the other hand, can require many cycles. However, converting between floats and ints can take some time, so the answer to your question may depend on the which type you ultimately need. $\endgroup$ – Bill Barth Sep 13 '14 at 18:45
  • $\begingroup$ I need an integer as my final result, so I assumed that the floating point computations would be slower. I may just have to test out both and compare speeds. $\endgroup$ – Dylan Sawchuk Sep 14 '14 at 5:08
1
$\begingroup$

The usual approach to get an integer random number in the range $[0,\ldots,N)$ (a half open range) is a piece of code of the form

unsigned int rnd()
{
  unsigned int k;
  do {
    k = rand()
  } while (k >= RAND_MAX/N*N) 

  return k % N;
}

This works because rand() produces random numbers uniformly in the range [0,RAND_MAX]. Then, the do-while loop produces random numbers uniformly in the range [0,RAND_MAX/N*N) where the upper bound is the largest multiple of RAND_MAX less than or equal to RAND_MAX, and consequently k % N is a uniformly distributed random number in the range [0,N).

If you want random numbers in an interval [a,b), use the function above on the interval [0,N=b-a) and just add a to every number you get.

$\endgroup$
  • $\begingroup$ I never thought of this method. While I like the concept, the random number generator I'm using is fairly costly and the possibility of having to ask for a random number multiple times would make the floating point arithmetic method faster. $\endgroup$ – Dylan Sawchuk Sep 15 '14 at 4:14
  • $\begingroup$ Well, the do loop almost always executes only once. On average you are asking for 1+(RAND_MAX%N)/RAND_MAX random number for every time you call this function. Unless your $N$ is a significant fraction of RAND_MAX, this is for all practical purposes one evaluation of rand() per call of the function. $\endgroup$ – Wolfgang Bangerth Sep 16 '14 at 1:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.