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.9 required=5.0 tests=BAYES_00,FREEMAIL_FROM autolearn=unavailable autolearn_force=no version=3.4.4 X-Received: by 10.36.0.77 with SMTP id 74mr2591764ita.23.1475331781348; Sat, 01 Oct 2016 07:23:01 -0700 (PDT) X-Received: by 10.157.59.194 with SMTP id k60mr1134854otc.10.1475331781321; Sat, 01 Oct 2016 07:23:01 -0700 (PDT) Path: eternal-september.org!reader01.eternal-september.org!reader02.eternal-september.org!news.eternal-september.org!news.eternal-september.org!feeder.eternal-september.org!news.glorb.com!184no545249ity.0!news-out.google.com!w143ni3393itb.0!nntp.google.com!l13no1156609itl.0!postnews.google.com!glegroupsg2000goo.googlegroups.com!not-for-mail Newsgroups: comp.lang.ada Date: Sat, 1 Oct 2016 07:23:01 -0700 (PDT) In-Reply-To: <87bmz43ejx.fsf@jester.gateway.pace.com> Complaints-To: groups-abuse@google.com Injection-Info: glegroupsg2000goo.googlegroups.com; posting-host=2601:191:8302:3f70:191b:5407:a0e3:2639; posting-account=fdRd8woAAADTIlxCu9FgvDrUK4wPzvy3 NNTP-Posting-Host: 2601:191:8302:3f70:191b:5407:a0e3:2639 References: <5db08ea5-c088-4d16-9d88-d058e4bc48df@googlegroups.com> <62fef12a-90fb-4ac8-8e59-99568b914ee7@googlegroups.com> <8bb59ac2-f5ba-44df-87ae-63d3dd47f0a3@googlegroups.com> <875ab579-a6b3-4552-b1a8-16f68da6d704@googlegroups.com> <87bmz43ejx.fsf@jester.gateway.pace.com> User-Agent: G2/1.0 MIME-Version: 1.0 Message-ID: Subject: Re: Ada.Numerics.Float_Random.Generator question From: Robert Eachus Injection-Date: Sat, 01 Oct 2016 14:23:01 +0000 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable Xref: news.eternal-september.org comp.lang.ada:31957 Date: 2016-10-01T07:23:01-07:00 List-Id: On Friday, September 30, 2016 at 11:59:15 PM UTC-4, Paul Rubin wrote: > Robert Eachus writes: > >> aren't *all* PRNGs cyclic? > > No, a simple counter-example is a generator that uses the digits of > > pi. The digits of any transcendental number will do.=20 >=20 > I don't see how this would work--to never cycle, it would need infinite > internal state. You could consider the digits of pi to be part of the > state, but to count off the digits, you need a counter of infinite > width. A quick proof that a PRNG that never cycles requires infinite state: If th= e generator ever returns to a previous state? It cycles. But there is infinite state, and infinite state. An infinite state that is= a simple counter of the number of values returned is probably acceptable, = a generator that requires storing the whole sequence is not. (Hmm. The ge= nerators in http://www.cs.ox.ac.uk/people/jeremy.gibbons/publications/spigo= t.pdf for Pi have a state of k integers for some k. Of course, these are u= nbounded integers which will eventually require an array of finite integers= to represent. (Multiprecision arithmetic) I think that is acceptable. However, there is another problem with using the digits (binary, decimal, o= r hexadecimal) of Pi. There is only one such sequence, so every program th= at uses it should start where other programs (in particular reruns of the s= ame simulation) left off. Choosing an n, then calulating ln n or e^n provi= des a seed that can be different for each run. Is this discussion more than just idle chatter? I think so. Some of the s= pigot algorithms Paul Rubin points to are practical, given the speed of mac= hines today. Even if they are not quite, you can use a transcendental PRNG= to seed a very long period non-trancendental generator every k values. Als= o more practical, if you are running a simulation on thousands of CPU cores= , you can use a trancendental PRNG to seed each CPUs PRNG, or better reseed= every n steps of the simulation. (Note that you do not need to distribute= the new seeds, they can be generated locally. Again, a trancendental gene= rator with a parameter or parameters is the next thing to look for. ;-)