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?

Improve this question
$\endgroup$
2
  • $\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
    Commented Sep 13, 2014 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
    Commented Sep 14, 2014 at 5:08

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
2
  • $\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
    Commented Sep 15, 2014 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
    Commented Sep 16, 2014 at 1:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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