This code (which uses random()) would have no bias and may=
even be faster, bypassing floats

const long rng =3D RAND_MAX/6;

= const long limit =3D rng * 6;

/* get one random dice */

int getd(= ) {

=A0 long v =3D limit;

=A0 while( v >=3D limit ) {

=A0=A0=A0 v =3D = random();

=A0 }

=A0 return=A0 v/rng;=A0 // dice in [0..5], add 1 for = dice in [1..6]

}

You obviously have to slightly adjust it if the = random number generator produces unsigned longs and has another maximum, bu= t the principle is universal.

-Joseph=A0

--20cf302d4e542df62004b2706bcb--
const long rng =3D RAND_MAX/6;

= const long limit =3D rng * 6;

/* get one random dice */

int getd(= ) {

=A0 long v =3D limit;

=A0 while( v >=3D limit ) {

=A0=A0=A0 v =3D = random();

=A0 }

=A0 return=A0 v/rng;=A0 // dice in [0..5], add 1 for = dice in [1..6]

}

You obviously have to slightly adjust it if the = random number generator produces unsigned longs and has another maximum, bu= t the principle is universal.

-Joseph=A0

On 24 November 2011 11:48=
, Jim Segrave <jes@j-e-s.net> wrote:

While I agree that using high order bits is preferable, the que= stionOn 11/23/2011 08:42 AM, Michael Petch wrote:

> On 22/11/2011 3:11 PM, Philippe Michel wrote:

>

>> Are there list members who are knowledgeable on rng robustness and= could

>> confirm that, if one starts with a "good" rng for intege= rs uniformly

>> distributed between 0 and n and discards any occurence of the top = p

>> values, one gets a good rng for the [0, n-p] interval ?

>>

>> Intuitively, it is tempting to say : "yes, and it is a condit= ion for the

>> original generator being any good" but I'm afraid it may = be a treacherous

>> domain.

>>

>

> I brought this up a good 8 years ago. Previously it was using straight=

> modulo. My original post was:

>

> http://lists.gnu.org/archive/html/bug-gnubg/2003-= 08/msg00410.html

>

> Joern Thyssen

> http://lists.gnu.org/archive/html/bug-gnubg/2003-= 08/msg00438.html

>

> The fix he put in was based on this information which you will note in=

> his response:

>

> -------

>

> I've modified the code to use:

>

> =A0 =A0 =A0 =A0 anDice[ 0 ] =3D 1+(int) (6.0*rand()/(RAND_MAX+1.0));>

> instead. This is suggested on the rand(3) man page:

>

> =A0 =A0 =A0 =A0In Numerical Recipes in C: The Art of Scientific Comput= ing

> =A0 =A0 =A0 =A0(William =A0H. =A0Press, Brian P. Flannery, Saul A. Teu= kolsky,

> =A0 =A0 =A0 =A0William T. =A0Vetterling; =A0New =A0York: =A0Cambridge = =A0University

> =A0 =A0 =A0 =A0Press, 1992 (2nd ed., p. 277)), the following comments = are

> =A0 =A0 =A0 =A0made:

> =A0 =A0 =A0 =A0 =A0 =A0 =A0 "If you want to generate a random int= eger between 1

> =A0 =A0 =A0 =A0 =A0 =A0 =A0 and 10, you should always do it by using h= igh-order

> =A0 =A0 =A0 =A0 =A0 =A0 =A0 bits, as in

>

> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0j=3D1+(int) (10.0*rand()/(R= AND_MAX+1.0));

>

> =A0 =A0 =A0 =A0 =A0 =A0 =A0 and never by anything resembling

>

> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0j=3D1+(rand() % 10);

>

> =A0 =A0 =A0 =A0 =A0 =A0 =A0 (which uses lower-order bits)."

>

being asked is different. Assume you've already done this in producing = a

random number in the range 0..n, such that the probability of some value

x in that range occuring should be 1/n.

Warning =A0- I am not a mathemetician or statistician by trade, so the

following example may not be sound, but I think it is.

Suppose there is a small bias, such that x actually occurs with

probability 1/n * bias, where bias is a number close to but not equal to

1. IF you reduce the range from 0..n to 0..p, where p < n. then the

deviation of bias from 1 increases.

For example, if the original range is 0..6 and for some reason, 2 comes

up a bit too often, so that out of 1,200,000 trials, 2 comes up 205,000

times (and each of 0, 1, 3, 4, 5 come up 199,000 times. Now you decide

to cut the range to 0..3. That same list of 1,200,000 trials now becomes

603,000 trials, of which 205,000 have the outcome 2.

Over the 0..6 range, the probability of an outcome of 2 is 0.170833

instead of the expected value of 0.166666 - in other words it's 1.025times the expected value.

Over the 0..3 range, the probability of an outcome of 2 is .339966,

instead of the expected .333333... This is 1.13322 times the expected value= .

So no, don't generate a range and then use a subset of it

_______________________________________________

Bug-gnubg mailing list

Bug-gnubg@gnu.org

https://lists.gnu.org/mailman/listinfo/bug-gnubg