Re: Ada.Numerics.Float_Random.Generator question

[Robert Eachus <rieachus@comcast.net>]

On Friday, September 30, 2016 at 11:59:15 PM UTC-4, Paul Rubin wrote:
> Robert Eachus <rieachus@comcast.net> 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. 
> 
> 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 the 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 generators in http://www.cs.ox.ac.uk/people/jeremy.gibbons/publications/spigot.pdf for Pi have a state of k integers for some k.  Of course, these are unbounded 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, or hexadecimal) of Pi.  There is only one such sequence, so every program that uses it should start where other programs (in particular reruns of the same simulation) left off.  Choosing an n, then calulating ln n or e^n provides a seed that can be different for each run.

Is this discussion more than just idle chatter?  I think so.  Some of the spigot algorithms Paul Rubin points to are practical, given the speed of machines 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. Also 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 generator with a parameter or parameters is the next thing to look for. ;-)