Monday, May 31, 2010

random number generator

Problem: Using a function(rand5) which produces a random integer in the range 1 to 5, write a function which produces a random integer in the range 1 to 7.

Solution:
You cant add add random numbers it creates a bias(think 2 dice the most common number is 7) Instead treat it as a base X number(in this case 5), scale it upto to sufficient granularity. (5*5 => 25 and 3*7 = 21)
Then drop the top end that is biasing the range. (in this case 21,22,23,24)

Of course in normal rand generation the base generator puts out a massive range so the low number bias is very minor and generally ignored.

//code untested
int rand7()
{
  int scaleRand   = 25;
  while(scaleRand >= 21)
     scaleRand = 5*(rand5()-1) + (rand5() - 1);   

  //rescale to the new base
  return (scaleRand % 7) + 1;
}

No comments:

Post a Comment