Subj : Re: Random Subset of Linked List
To   : comp.programming
From : mschaef
Date : Tue Sep 13 2005 11:49 am

In article <dg6pek$2jm$1@malatesta.hpl.hp.com>,
Chris Dollin  <kers@hpl.hp.com> wrote:
   ...
>(b) is an issue of picking a good way of reducing the output from
>    your local random-number generator to an integer in the range
>    1..Whatever *without bias*.

WRT the non-biased, in a range RNG, I've been thinking this:

1. Use something like Mersenne Twister
2. For a random number in [0..N)
   a. Use the RNG to generate enough bits for to generate a number in 
      the range [0..N*M) where M is at least a few thousand.
   b. Use mod to get back down to [0..N)

My hope is that a large enough M will reduce the bias to acceptable 
levels.  If M is 1000, it seems like that means that the upper part of 
[0,N) will be 1000/999 times as likely as the lower part. That's not 
quite as bad as using, say, a 15-bit RNG to produce a number in the range 
[0,20000).

Thanks to all for the advice.

-Mike
-- 
http://www.mschaef.com

.