randomserver
Free Random Numbers

Home » Random Numbers » Math and Practical » Range/Distribution conversion (How to convert random numbers into a specified range)
Show: Today's Messages :: Show Polls :: Message Navigator
E-mail to friend 
Switch to threaded view of this topic Create a new topic Submit Reply
Range/Distribution conversion [message #56] Sun, 27 February 2011 18:18 Go to next message
TRNG98 is currently offline  TRNG98
Messages: 21
Registered: January 2011
Location: Lund
Senior Member
A hardware random number generator typically produce random bytes or random unsigned 32 bit integers. These numbers have a flat distribution in the range [0..255] or [0..4294967295]. For most applications some other distribution (not flat) is needed, or we need numbers in a specified range, such as [0..5] (Dice), or [0..51] (Deck of cards).

It is easy to convert a number from one range to another. The important conceptual part is that the conversion, in general, cannot be complete, so all input random numbers do not convert into an output number. This is due to that we prefer an exact conversion, where the output numbers also have a flat distribution (exactly). As an example, I convert a random number in the range [0..15] to the range [0..2].

It is easy so see how this should be done. We have 16 input possibilities of exactly equal probabillity, that shall be divided into three sets of 5 number each, and then there will be a last input number that cannot be converted.
If the input number is Rand this can be accomplished by calculating Result=Rand/5. Then Result=[0..3] where the probabilities are Result=[0:P(5/16); 1:P(5/16); 2:P(5/16); 3:P(1/16)]. So the conversion succeeds if Result <= 2, and fail if Result == 3. If the conversion fails we then simply iterate the conversion with a new input random number!

The magic divisor "5", in the example above can be calculated by D=15/3 where "15" is the largest random number in the input range, and "3" is the output range.


Range = 3;
Largest = 15;
D = Largest / Range;
Result = Range;
while ( Result == Range)
{
   Rand = read_random_number;
   Result = Rand / D;
}




TRNG98 We sell hardware random number generators
Re: Range/Distribution conversion [message #59 is a reply to message #56] Mon, 28 February 2011 09:15 Go to previous messageGo to next message
KeithW is currently offline  KeithW
Messages: 8
Registered: November 2010
Location: USA
Member
I have found this function on Intel's webb:
unsigned int Random_conversion(Range)
{
   unsigned int Range:
   unsigned int inc_scale,Rand_word,Done,count;

   if (Range==0){
      trap("Range is zero in Random_conversion()");
   } else {
      inc_scale=0xFFFFFFFF/Range;
      if (inc_scale==0){
         inc_scale=1;
      }
      while (!Done){
         Rand_word=int32_truerandomnumber();
         count=Rand_word/inc_scale;
         Done=count<Range;
      }
   }
   return count;
}



Keith Random Numbers and Poker Servers

Re: Range/Distribution conversion [message #60 is a reply to message #59] Thu, 03 March 2011 16:44 Go to previous messageGo to next message
David_T is currently offline  David_T
Messages: 18
Registered: November 2010
Senior Member
There is a loss - a 32 bit input number converts to a single three-way selection ?
Re: Range/Distribution conversion [message #61 is a reply to message #60] Tue, 22 March 2011 04:05 Go to previous message
TRNG98 is currently offline  TRNG98
Messages: 21
Registered: January 2011
Location: Lund
Senior Member
Yes - you can easily make the lost bits fewer.

TRNG98 We sell hardware random number generators
  Switch to threaded view of this topic Create a new topic Submit Reply
Next Topic: Converting random bytes into a range
Goto Forum:
  

-=] Back to Top [=-
[ Syndicate this forum (XML) ] [ RSS ] [ PDF ]

Current Time: Fri Nov 15 13:25:04 W. Europe Standard Time 2019