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: bobduff@world.std.com (Robert A Duff) Subject: Re: Random Number Generation Date: 1996/10/14 Message-ID: #1/1 X-Deja-AN: 189200554 references: <13OCT96.18283680@enh.nist.gov> organization: The World Public Access UNIX, Brookline, MA newsgroups: comp.lang.ada Date: 1996-10-14T00:00:00+00:00 List-Id: In article <13OCT96.18283680@enh.nist.gov>, wrote: > >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. But so-called "random number generators" are *not* really random. They're really pseudo-random number generators, and they will eventually produce a value that will cause the above loop to terminate. R1 will *not* generate an arbitrarily long series of 1024's, or whatever, even though a *truly* random sequence might. The above loop *might* take a long time, but in any case, it *is* finite, given a pseudo-random number generator. Of course, in a real-time situation, you want a small upper bound on that time, which Jonathan addresses: >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. - Bob