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: kst@thomsoft.com (Keith Thompson) Subject: Re: Random Number Generation Date: 1996/10/12 Message-ID: #1/1 X-Deja-AN: 189002340 sender: news@thomsoft.com (USENET News Admin @flash) x-nntp-posting-host: pulsar references: <53jgrh$r20@newton.cc.rl.ac.uk> organization: Thomson Software Products, San Diego, CA, USA newsgroups: comp.lang.ada originator: kst@pulsar Date: 1996-10-12T00:00:00+00:00 List-Id: In <53jgrh$r20@newton.cc.rl.ac.uk> jp3@rl.ac.uk ( Dr J Parker) writes: > 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. I think the point is that you can't convert R1 into R2 without rejecting some value from R1; typically, you'd reject the value 1023 and map 0 .. 340 => 0 341 .. 681 => 1 682 .. 1022 => 2 If R1 is truly random, there's no guarantee that it won't generate an arbitrarily long sequence of 1023's; therefore the conversion is not guaranteed to finish in finite time. Geert: is this what you meant? In practice, of course, this probably won't matter; long sequences of a single value are vanishingly rare. It might matter for a hard realtime system. In that case, you could give up and return an arbitrary value after N failed attempts; the choice of N is a tradeoff between worst-case behavior and the quality of the random output. I think there may actually be a way around this, similar to the way uuencode maps 3 input bytes (base 256) to 4 output characters (base 64). The first R1 value (0..1023) would give you 6 R2 values (0..2) with a little bit of randomness to spare. It's more difficult than uuencode since the input and output will never actually resynchronize. (There must be a way to state this more precisely.) I'm too lazy to figure out the details. -- Keith Thompson (The_Other_Keith) kst@thomsoft.com <*> TeleSoft^H^H^H^H^H^H^H^H Alsys^H^H^H^H^H Thomson Software Products 10251 Vista Sorrento Parkway, Suite 300, San Diego, CA, USA, 92121-2706 FIJAGDWOL