Re: Gnat Chat, Random Numbers in GNAT

[Ashley Deas Eachus <rieachus@earthlink.net>]

Kent Paul Dolan wrote:

> I want to do some genetic algorithm (GA) programming in GNAT, to do
> proof of concept for some new approaches I've been mulling to speed up
> convergence and remove the need for sorts, and I need to know about the
> kind and quality of the Ada.Numerics.Float_Random implementation in
> GNAT, to decide whether I can trust it to work well in a statistical
> distribution sense when called (probably) hundreds of millions of times
> in a single program run (you may guess that I have abundant cpu cycles
> at work, and you'd be correct, at least 15 machines behind our firewall
> sit mostly idle for good reason that my using them for week long low
> priority GA runs wouldn't impact significantly).
>
> Header excerpts from the source, from someone who knows right where to
> look, so I don't have to slog through it from a zero knowledge starting
> point, would be a perfectly fine answer, if the info is there.  Formal
> pseudorandom number generator test reports of whatever style have
> become popular since I was last doing that kind of quality control
> personally back in the sixties would be good.  Anecdotal personal
> experience is also welcome as an answer.  URLs pointing to any of the
> non-source code information would be equally useful.

      Haven't seen you around for a while Kent, but I am probably the best
one to answer this, since it is sort of my algorithm.   (The sequence
generated is a Blum, Blum, and Shub sequence, which for your purposes will
be polynomial-time unpredictable, but the implementation tricks to generate
it efficiently are mine.)   In any case, for the size of GA run you are
anticipating, there are three other factors to consider.  You will not
exceed the period of the generator, but you will probably get into the
range where the generator could be predicted from the previous state
information you have used.  Since for most generators, this happens when
you have have used under a dozen, and in some cases a single value, this is
more of theoretical interest.

      The second issue is that the number of possible values generated does
not completely cover all of the representable values in [0.0 .. 1.0).
Again the generator in gnat is much better than most in this area, but it
only generates about 2**50 values, so there are small floating-point values
near zero that cannot be generated.  Not a big worry, unless you are
creating events with a very small probability of occurring.

      Finally, and very important, if you use several instances of this
generator, you must concern yourself with distributing entropy to the
various generators.  (One generator per Ada task that needs random variates
is probably best.)  You need to insure that multiple generators don't start
with the same seed.  The algorithm for initializing the generator is such
that providing such seeds in sequence works fine, but the standard Ada
interface limits you to 2**32 possible starting values.   The simple model
for GA would create lots of tasks, and you might start pushing that limit.
So recycle tasks without resetting the task specific generator and you
should be fine.

      If this particular generator is not sufficient for your purpose, I
can send you an electronic copy of the design paper.  It has a few other
prime pairs in it that will give you a longer period and more possible
values.  I only recommend this if you are using more than 64-bit
floating-point, and expect to generate more than 10**40 variates in a
single run.