From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me
X-Spam-Level: 
X-Spam-Status: No, score=-1.3 required=5.0 tests=BAYES_00,INVALID_MSGID
	autolearn=no autolearn_force=no version=3.4.4
X-Google-Language: ENGLISH,ASCII-7-bit
X-Google-Thread: 103376,5291fa0ea59b8b29
X-Google-Attributes: gid103376,public
From: jp3@rl.ac.uk ( Dr J Parker)
Subject: Re: Random Number Generation
Date: 1996/10/10
Message-ID: <53jgrh$r20@newton.cc.rl.ac.uk>#1/1
X-Deja-AN: 188554011
organization: Rutherford Appleton Laboratory, Oxon, UK
newsgroups: comp.lang.ada
Date: 1996-10-10T00:00:00+00:00
List-Id: <comp.lang.ada>


Jonathan Parker (jp3@rl.ac.uk) wrote:
-`` Another simple example:
-
-   Suppose you have a high quality random number generator R1 in the range
-   0 .. 1023 and you want to turn it into a high quality random number
-   generator R2 in the range 0 .. 2. ''
-
-This is not a simple example. It is not possible to write an
-Ada program that does convert R1 to R2 and is guaranteed to
-finish in finite time.
-
-Regards,
-   Geert
--
-E-Mail: geert@sun3.iaf.nl


Nah... the rejection method is rigorously correct, and so is
the subsequent use of x rem 3 in the code fragment below.

The original post never reached some newsreaders so I repeat it below.
btw, the answer to the ? below is about N = 10**7, about 10 secs
on a PC.  If R1 has range
0..2**15-1 instead then it takes about an hour to detect the bias.
The method Tucker suggests is one of best, provided
you know how it can fail and you know how to avoid it.

cheers, Jonathan


*******************************************************8
Another Simple example:

Suppose you have a high quality random number generator R1 in the range
0 .. 1023
and you want to turn it into a high quality random number generator R2
in the range 0 .. 2.

R1 has 8 more bits than R2.

Suppose you try R2  =  R1 / 342.

this maps
0..341    to 0,
342..683  to 1
684..1023 to 2

0 has probability 342/1024, 1 has probability 342/1024, and
2 has probability 340/1024.

You can use  R1 mod 3, get same problem.
You can use  R1 * 3.0, with floating point R1 in [0.0..1.0)
and you get same problem if R1 has 1024  elements in its range.

Suppose you think R2 is uniformly distributed in 0,1, 2.
How many trials (N) would it take to detect the bias?

In under 5 miinutes you can generate N = 3 * 10**8 random numbers on
a PC.  expect 10**8 0's, 10**8 1's 10**8 2's , with stnd deviation
about 10**4 and error = 10**8 * 1.333/1024.0.

You get wrong answer by about 10 stnd deviations!

And all you had to do was reject number 1023 from the range of R2!
(because the number of elements in the range of 0..1022 is
divisible by 3.)

x := random;
while x > R1'Last - 1024 rem 3 loop
   x := random;
end loop;
return x rem 3;
*********************************************************