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,e3f74ab8a2c61af2
X-Google-Attributes: gid103376,public
From: parker@enh.nist.gov
Subject: Re: Random Number Generation
Date: 1996/10/13
Message-ID: <13OCT96.18283680@enh.nist.gov>#1/1
X-Deja-AN: 189285291
organization: NIST
newsgroups: comp.lang.ada
Date: 1996-10-13T00:00:00+00:00
List-Id: <comp.lang.ada>



Geert Bosch wrote:

"I don't say it is not possible to present a correct algorithm
to convert R1 to R2. Such a correct algorithm just is not guaranteed to
finish in finite time.

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

You can't give an upper boundary for the number of iterations
of the while loop if R1 is a truly random generator.

Of course in practise you're only interested in having an
algorithm that has a good probability to finish in a certain
amount of time.

I just pointed out that the example wasn't that simple.
Somebody using this code should be aware of that. "


Now I see what you're getting at.
I wouldn't worry about it tho.....overhead from M rejections goes linearly
with M (M calls to R1), probability of M rejections goes as 2**(-M*10)...

Keith and Geert are concerned about fluctuating overhead in the rejection
method.  I like Keith's solution: an upper limit on the number of
rejections.  In this case, if the upper limit is set to 2, then the error
is undetectable: ie if you reject 2 1023's in a row, then accept whatever 
comes next; the offending 3 1023's come with a probability of 2**(-30)
for an undetectable bias.  So max overhead is 3 calls to R1, average
overhead is 1.001 calls to R1 (plus the if, and the rem).

An alterative with same error, but constant overhead: make R1 into
the range 0..2**30-1. iTo do this think of R1 as returnig a single
digit number base 1024; use 3 calls to R1 to make x, 
a 3 digit number  base 1024.  Now
just return x rem 3: same bias, same max overhead as other
method, but 3 times the average overhead.

cheers, Jonathan