Re: Gnat Chat, Random Numbers in GNAT

[xanthian@well.com (Kent Paul Dolan)]

Ashley Deas Eachus  <rieachus@earthlink.net> wrote:
>Kent Paul Dolan wrote:

>> ...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

>      Haven't seen you around for a while Kent,

Oh, I never go away, but my attention drifts around the net a lot.  Since I
have little of value to contribute to comp.lang.ada, I can resist the urge
to post for sometimes months in a row of lurking.

>but I am probably the best
>one to answer this, since it is sort of my algorithm.

Always nice to find an authoritative opinion, I always say.

>(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.

Not a problem, since there is no cryptographic aspect to the use.

>      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.

Hmm.  Thanks for the warning, I'll need to be very careful about that, there
are other ways to get messed up by discontinuities in the generated random
numbers.  The current Java applet which I would like to improve upon:

http://www.coyotegulch.com/alife/Traveller.html

for which I don't yet have the source, can go at least the square of the
expected number of iterations expected to accomplish a certain change, without
making that change.  It
is hard to isolate that to algorithm problems or RNG problems based just
on the symptoms, so I have to be very careful about the RNG ideosyncracies.

>      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.

One can only hope that will be fixed _real soon now_; that's a pretty terrible
misfeature.

>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.

Thanks again for the warning.

>      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.

I'd like the paper just for the education I'll gain reading it.  I can cope
with *.html, *.ps, *.pdf immediately, TeX with a little trouble I need to
undergo anyway, MS word with some pain, and Framemaker with some expense,
in case you have a choice of formats.

My work email would be best: xanthian@whistle.com.

Thanks very much for your help!



               ===== random archival quality quote =====

[the new kind of mysticism called Quantum Mind] must be rejected as
non-parsimonious, especially since we have in our hands a perfectly
economical and logically-consistent theory that agrees with all the
data and requires no additional component in the universe beyond
matter.
   -- http://www.phys.hawaii.edu/vjs/www/meta.txt Victor J. Stenger

--
Kent Paul Dolan.
<xanthian@well.com> <xanthian@aztec.asu.edu> <xanthian@whistle.com>