Re: Gnat Chat, Random Numbers in GNAT

Re: Gnat Chat, Random Numbers in GNAT

[Christoph Grein]

Jeff Carter wrote:

<<FWIW (personal experience anecdote), I did a parking-lot test of both
Float_Random and Marsaglia's Universal Random-Number algorithm and no
structure was apparent in either.>>

I think Marsaglia's Universal Random-Number generator should be made public
somewhere, perhaps the best place would be David Botton's AdaPower.

(Just a proposal that you put it there.)

I have also an Ada version at home, which produces the prescribed numbers
on test, but I do not have the original paper where it was published. The
note I took the code from mentioned a periodical where it was to
appear, but that edition doesn't have it, and also later editions don't.
So apparently it was published somewhere else in another periodical.
Without reference to the original publication, I do not want to publish my
version.

Gnat Chat, Random Numbers in GNAT

[Kent Paul Dolan]

Aside:

I realize this should go to the Gnat Chat mailing list, but I'm on too
many mailing lists as it is, so my first question is, would it be
appropriate, and would there be any interest in or support for moving
Gnat Chat to a new leaf of comp.lang.ada?  I'm assuming without
evidence that the level of traffic would justify a newsgroup, and I
much prefer newsgroup threading to mailing list linearity.

If several anyones encourage me quite a bit, and no furor of protest
emerges, I'd do a newsgroup RFD to make comp.lang.ada into
comp.lang.ada.*, but I'd like before going to the four months of
trouble that would take to find out if there would be any interest in a
split, and if so along what lines people would like to see things
divided.  I will confess in advance that there is nothing that
overwhelming about the traffic in comp.lang.ada, I just like more
neatly sorted out conversations.

Whatever.

On to my main agenda.

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.

Thanks for any help.  I read and archive this newsgroup daily, so an
email response is welcome, but not necessary.

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

Re: Gnat Chat, Random Numbers in GNAT

[Gisle S�lensminde]

In article <SLSi4.702$dw3.34085@news.wenet.net>, Kent Paul Dolan wrote:
>Aside:
>On to my main agenda.
>
>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.
>
>Thanks for any help.  I read and archive this newsgroup daily, so an
>email response is welcome, but not necessary.

In the gnat runtime library sources I found the following comment
in bot the float_random and discrete_random packages, on how they
are implemented. 

--  Note: the implementation used in this package was contributed by
--  Robert Eachus. It is based on the work of L. Blum, M. Blum, and
--  M. Shub, SIAM Journal of Computing, Vol 15. No 2, May 1986. The
--  particular choices for P and Q chosen here guarantee a period of
--  562,085,314,430,582 (about 2**49), and the generated sequence has
--  excellent randomness properties. For further details, see the
--  paper "Fast Generation of Trustworthy Random Numbers", by Robert
--  Eachus, which describes both the algorithm and the efficient
--  implementation approach used here. This paper is available at
--  the Ada Core Technologies web site (http://www.gnat.com).




--
Gisle S�lensminde ( gisle@ii.uib.no )   

ln -s /dev/null ~/.netscape/cookies

Re: Gnat Chat, Random Numbers in GNAT

[Jeff Carter]

"Gisle S�lensminde" wrote:
> 
> In article <SLSi4.702$dw3.34085@news.wenet.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.
> >
> >Thanks for any help.  I read and archive this newsgroup daily, so an
> >email response is welcome, but not necessary.
> 
> In the gnat runtime library sources I found the following comment
> in bot the float_random and discrete_random packages, on how they
> are implemented.
> 
> --  Note: the implementation used in this package was contributed by
> --  Robert Eachus. It is based on the work of L. Blum, M. Blum, and
> --  M. Shub, SIAM Journal of Computing, Vol 15. No 2, May 1986. The
> --  particular choices for P and Q chosen here guarantee a period of
> --  562,085,314,430,582 (about 2**49), and the generated sequence has
> --  excellent randomness properties. For further details, see the
> --  paper "Fast Generation of Trustworthy Random Numbers", by Robert
> --  Eachus, which describes both the algorithm and the efficient
> --  implementation approach used here. This paper is available at
> --  the Ada Core Technologies web site (http://www.gnat.com).

The sources of Ada.Numerics.Float_Random for GNAT are in a-nuflra.ad?

If you have GNAT, you can examine the implementation for yourself.

FWIW (personal experience anecdote), I did a parking-lot test of both
Float_Random and Marsaglia's Universal Random-Number algorithm and no
structure was apparent in either.

I can provide you with Ada source for the Marsaglia generator if you
have tests you'd like to run on it.

-- 
Jeff Carter
"Monsieur Arthur King, who has the brain of a duck, you know."
Monty Python & the Holy Grail

Re: Gnat Chat, Random Numbers in GNAT

[Kent Paul Dolan]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 4158 bytes --]

Jeff Carter  <jrcarter@acm.org> wrote:
>"Gisle S�lensminde" wrote:

>> In article <SLSi4.702$dw3.34085@news.wenet.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.

>> >Thanks for any help.  I read and archive this newsgroup daily, so an
>> >email response is welcome, but not necessary.

>> In the gnat runtime library sources I found the following comment
>> in bot the float_random and discrete_random packages, on how they
>> are implemented.

>> --  Note: the implementation used in this package was contributed by
>> --  Robert Eachus. It is based on the work of L. Blum, M. Blum, and
>> --  M. Shub, SIAM Journal of Computing, Vol 15. No 2, May 1986. The
>> --  particular choices for P and Q chosen here guarantee a period of
>> --  562,085,314,430,582 (about 2**49), and the generated sequence has
>> --  excellent randomness properties. For further details, see the
>> --  paper "Fast Generation of Trustworthy Random Numbers", by Robert
>> --  Eachus, which describes both the algorithm and the efficient
>> --  implementation approach used here. This paper is available at
>> --  the Ada Core Technologies web site (http://www.gnat.com).

Thanks Gisel!  That is more than good enough for my modest needs.

>The sources of Ada.Numerics.Float_Random for GNAT are in a-nuflra.ad?

>If you have GNAT, you can examine the implementation for yourself.

I have gnat, and can easily bring it down again from the FreeBSD
/usr/ports mechanisms with a few keystrokes, but now there's no need.
On my stingy hard drive, by choice, the sources disappeared with the
object modules when I cleaned up after building gnat.

>FWIW (personal experience anecdote), I did a parking-lot test of both
>Float_Random and Marsaglia's Universal Random-Number algorithm and no
>structure was apparent in either.

Thanks for that reassurance, too, Jeff.

>I can provide you with Ada source for the Marsaglia generator if you
>have tests you'd like to run on it.

Thanks, Jeff.  No, as I said earlier, my 1962-era random number generator
testing experience is pretty useless today, and I'm more than willing to
go ahead on the advice of others.  I've just been burned a dozen or more
times by RNGs delivered as part of compilers and interpreters that were
of very low quality, so I wanted to see if someone else had "tried" before
I "buyed"(sic).  I don't have any reason to distrust the gnat implementation,
I just needed some help to trust it; I'm happy to hear that Dr. Dewar and
the rest of the ACT troups have done their usual professional job.

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

"...Roxanne  falls  in  love  with  Christian,  a  cavileer  in Cyrano's
regiment who hasn't got the brains god gave an eclair..."
                                                      -- reviewer on NPR

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

Re: Gnat Chat, Random Numbers in GNAT

[Jean-Pierre Rosen]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 1019 bytes --]


Kent Paul Dolan <xanthian@well.com> a �crit dans le message :
sYyj4.804$dw3.37978@news.wenet.net...
> Thanks, Jeff.  No, as I said earlier, my 1962-era random number generator
> testing experience is pretty useless today, and I'm more than willing to
> go ahead on the advice of others.  I've just been burned a dozen or more
> times by RNGs delivered as part of compilers and interpreters that were
> of very low quality, so I wanted to see if someone else had "tried" before
> I "buyed"(sic).  I don't have any reason to distrust the gnat
implementation,
> I just needed some help to trust it; I'm happy to hear that Dr. Dewar and
> the rest of the ACT troups have done their usual professional job.

Do not forget we are in the Ada world here!
There ARE tests for the RNG in the validation suite, and GNAT is validated
for the Numerics annex!
--
---------------------------------------------------------
           J-P. Rosen (Rosen.Adalog@wanadoo.fr)
Visit Adalog's web site at http://pro.wanadoo.fr/adalog

Re: Gnat Chat, Random Numbers in GNAT

[Ted Dennison]

In article <SLSi4.702$dw3.34085@news.wenet.net>,
  xanthian@well.com (Kent Paul Dolan) wrote:
> Aside:
>
> I realize this should go to the Gnat Chat mailing list, but I'm on too
> many mailing lists as it is, so my first question is, would it be
> appropriate, and would there be any interest in or support for moving
> Gnat Chat to a new leaf of comp.lang.ada?  I'm assuming without
> evidence that the level of traffic would justify a newsgroup, and I
> much prefer newsgroup threading to mailing list linearity.

There isn't really that much traffic in gnat-chat. I subscribed almost
exactly a year ago, and have gotten 1674 messages in that time. That may
sound like a lot, but its only an average of 4.6 a day. The reality of
the traffic is that there are sometimes large spurts of traffic around
contraversial postings, and there are more often large spurts with no
messages for days. Just to list the periods of more than 3 days, there
were no messages from 2/19 to 2/24, 3/5 to 3/8, 3/10 to 3/15, 6/5 to
6/8, and 10/16 to 10/19.

--
T.E.D.

http://www.telepath.com/~dennison/Ted/TED.html


Sent via Deja.com http://www.deja.com/
Before you buy.

Re: Gnat Chat, Random Numbers in GNAT

[Ehud Lamm]

If you are interested, I have two simple frameworks that provide the core
a GA functionality. OOne is 100% general, that other implements the
classic GA: bit-strings as chrmosome, single point cross-over, roulette
wheel selection. Pc,Pm,N,l supplied as parameteres, naturally.

This is one of the examples in the frameworks chapter of "The Little
Abstractionist." My almost finsihed Ada example oriented tutorial&tour.

Ehud Lamm mslamm@mscc.huji.ac.il
http://purl.oclc.org/NET/ehudlamm <== My home on the web 
Check it out and subscribe to the E-List- for interesting essays and more!

Re: Gnat Chat, Random Numbers in GNAT

[Keith Thompson]

xanthian@well.com (Kent Paul Dolan) writes:
> I realize this should go to the Gnat Chat mailing list, but I'm on too
> many mailing lists as it is, so my first question is, would it be
> appropriate, and would there be any interest in or support for moving
> Gnat Chat to a new leaf of comp.lang.ada?  I'm assuming without
> evidence that the level of traffic would justify a newsgroup, and I
> much prefer newsgroup threading to mailing list linearity.

The GNAT Chat list is archived at <http://www.act-europe.fr/mail/chat/>.
Older messages are at <http://www.gnat.com/chat/>.  Both archives are
indexed both by date and by thread.

In any case, there's no much point in creating a GNAT Chat newsgroup
unless ACT agrees to shut down the mailing list, which seems unlikely.
(I personally wouldn't mind, but I don't get a vote.)

-- 
Keith Thompson (The_Other_Keith) kst@cts.com  <http://www.ghoti.net/~kst>
San Diego Supercomputer Center           <*>  <http://www.sdsc.edu/~kst>
Welcome to the last year of the 20th century.

Re: Gnat Chat, Random Numbers in GNAT

[Nick Roberts]

I might be interested in the near future for comp.lang.ada.ascl and
comp.lang.ada.adaos newsgroups.

AdaOS has a 'lab' page on the AdaPower site, and I have no complaints, but
I'd be happy if an NNTP newsgroup helped increase this project's 'profile' a
little.

Similarly, I had an ASCL group on eGroups, but this had some technical
diffculties. Dave Botton has kindly offered me space on AdaPower for an ASCL
page, and that's fine by me, but it may possibly be more appropriate for it
to be a newsgroup.

I guess, if comp.lang.ada is going to sprout leaves, it might be an idea to
have something like a comp.lang.ada.questions to take the place of those
"How do I ...?" articles much posted at the moment.

(We might also have a comp.lang.ada.religiousflamesdontbothertoread or the
like, too ;-)

--
Nick Roberts
http://www.adapower.com/lab/adaos

Re: Gnat Chat, Random Numbers in GNAT

[Robert Dewar]

In article <SLSi4.702$dw3.34085@news.wenet.net>,
  xanthian@well.com (Kent Paul Dolan) wrote:

>so my first question is, would it be
> appropriate, and would there be any interest in or support for
> moving Gnat Chat to a new leaf of comp.lang.ada?

Well this is not exactly a democratic issue. GNAT Chat is a
mailing list that ACT controls and moderates in an attempt
to maintain a high level of GNAT relevance. We don't see a
non-moderated leaf of CLA as an appropriate substitute. Many
serious GNAT users are on chat who would not come near any
newsgroup at this stage (I myself have completely stopped
reading CLA except for subject topics that include the
word GNAT, just too low a signal to noise ratio to be worth
while for me).

There is of course absolutely nothing at all to stop someone
forming a GNAT sub leaf (e.g. comp.lang.ada.gnat). All you need
is a vote to form the group (if you use alt....gnat, then you
do not even need that).

Everyone is free to be on any mailing list or newsgroup that
they please of course. The reason I often encourage people to
send GNAT specific questions to chat is simply that there are
more people there who know GNAT well. For example, this thread
on random number generators is missing very important
information, and I suspect that a thread on GNAT chat might
have been more informative!

Robert Dewar
Ada Core Technologies


Sent via Deja.com http://www.deja.com/
Before you buy.

Re: Gnat Chat, Random Numbers in GNAT

[Ashley Deas Eachus]

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.

Re: Gnat Chat, Random Numbers in GNAT

[Keith Thompson]

Ashley Deas Eachus <rieachus@earthlink.net> writes:
[...]
>       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.
[...]

If this is an issue, perhaps you can call Random twice for each random
number you need.  For example, if the Random function gives you a good
32-bit value, you can call it twice to construct a good 64-bit value.

(I'm probably missing some vital point here, so don't take my word for
it.)

-- 
Keith Thompson (The_Other_Keith) kst@cts.com  <http://www.ghoti.net/~kst>
San Diego Supercomputer Center           <*>  <http://www.sdsc.edu/~kst>
Welcome to the last year of the 20th century.

Re: Gnat Chat, Random Numbers in GNAT

[Robert Iredell Eachus]

Keith Thompson wrote:

> If this is an issue, perhaps you can call Random twice for each random
> number you need.  For example, if the Random function gives you a good
> 32-bit value, you can call it twice to construct a good 64-bit value.
>
> (I'm probably missing some vital point here, so don't take my word for
> it.)

    You are missing a very vital point here, and you can take my word for it.
;-)  If  you generated random variates as described above, the number of possible
generator states would not change, so you would still only generate the same
number of different VALUES.  They would just have more bits in them.  (You would
generate the same number of values because the period of the generator is not
divisible by 2.  With some other generators, this would decrease the number of
possible values generated.)

      The simple rule to remember is that when mixing computers and randomness,
entropy always decreases.  In this particular example, since the generator would
be used with a 32-bit seed, you have a maximum of 32 bits of entropy.  If you use
two generators, with two independent seeds, you may get 64 bits of entropy, and
for a  good generator you should expect almost that.   Where to you get entropy?
The usual source is some physical measurement external to the computer.  The most
commonly used is the value of the clock.  If you really care, you can buy devices
that measure Schott noise in diodes or the interval between geiger counter
clicks.  If Kent has a large processor farm, he may want to splurge and buy one.
They usually cost under $100 plus software, the problem is that they usually take
up an internal slot or external port.

     If the situation does arise where you do need more than about 10 million
variates, the better way to go is to use a generator with a longer period.
Incidently, don't let any of this scare you away from using the built-in
generator in gnat.  It is very solid, and for complex reasons explained in the
paper will pass any reasonable test of randomness.

Re: Gnat Chat, Random Numbers in GNAT

[Kent Paul Dolan]

Robert Iredell Eachus  <rieachus@earthlink.net> wrote:

Nothing quite so confuses the mind as two authors with the same email box.

>If Kent has a large processor farm,

That a bit overstates my glorious CPU cycle surplus.

We subcontract the manufacture of our InterJets, which are pretty mean
FreeBSD x86 computers deliberately disguised as internet appliances, so
I suppose if the need arose and I were very persuasive we could
probably hook up the hundred or so usually cluttering up an annex to
the meeting room as ready to ship stock, but what I have at present is
more an engineering lab with two or three (or occasionally seven or
more) leased computers on/at every desk, plus more in freestanding
racks, most of their processing cycles of necessity going to the
generation of heat and little else for lack of a typist per keyboard
matchup, or of a 24x7 operations model, or of enough data to keep them
busy.  Besides the split between "productivity software" (hack, spit)
and machines on which real work can be done, most of the rest are wired
up in dedicated networks for testing updated build images, since a
large part of what we do has to do with making really icky things work
well (to the point of "transparently") across a network.

> he may want to splurge and buy one.

Again, for the kind of experimentation I want to do (and will soon be
doing), a genuinely random seed is not particularly interesting, a long
period and nice distribution statistics are what are important, so that
a single run will provide enough appropriately independent random
numbers to keep the testing valid.

And again, thanks for help from the Eachus family, if that isn't
already assuming too much from a shared email box and last name.

[For the morbidly curious, my current single test run of The Blind
Travelling Salesman Problem, a Java applet from Scott Robert Ladd's
pages at www.coyotegulch.com, has 500 cities, a population size of 40
chromosomes, the most I could stand to watch trudge along, the last
time I benchmarked it had been running at 300MHz or so for 11.5 days
and 4.28 million generations, was about 2/3rds of its way toward a
"'final' solution" in terms of excess distance removed, had dropped by
a factor of about 6,000 in rate of progress since the run began,
continues to "ignore" (fail to find) changes that would be huge wins
instead finding changes that are part in 10,000 improvements, and
looks, optimistically, to have about another 50 days to run to achieve
at least a non-self-intersecting approximate solution.  My reasons for
wanting to replace this code with code of my own should be achingly
obvious, when you consider that TSPs, though not, to my knowledge, the
more difficult supremely masochistic BTSPs, are routinely solved in the
chip fabrication industry with node counts in the hundreds of millions
by other techniques, if I understand correctly.]

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

Walk  to  an  unused  portion of diskspace and create.  And if you don't
like where you are, uncreate.
                                                         -- Robert Kelly

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

Re: Gnat Chat, Random Numbers in GNAT

[Robert Iredell Eachus]

Kent Paul Dolan wrote:

> Robert Iredell Eachus  <rieachus@earthlink.net> wrote:
>
> Nothing quite so confuses the mind as two authors with the same email box.

     Slip of the tongue, or whatever.  I was swapping some things around in
Netscape, to set my wife up to use
Netscape for mail, and confused myself and replied to some messages from her
account on my home computer,
but using my account to read newsgroups.

> That a bit overstates my glorious CPU cycle surplus.

     Not really, from what you say below.  Over four million generations is
coming close to looping a 32-bit
seed.  Technically, the gnat generator becomes non-cryptographically secure
when you use more than p or q values,
but that is probably only of theoretical interest.  When you start exceeding N
(= p*q) values, then start worrying, but that is on the order of 2**49...

Re: Gnat Chat, Random Numbers in GNAT

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

Re: Gnat Chat, Random Numbers in GNAT

[Robert Iredell Eachus]

Kent Paul Dolan wrote:

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

    Not really, the limit is actually to Standard.Integer seeds, so it will
automagically grow to 64 bits in a few years.   But notice that the generator can
contain much more state, this is just a limit on the number of starting points.
The caution here was that you could easily exceed 2**32 entities in your GA run.
Once you do, you may see no new behavior.  By limiting the number of generators to
one per thread, you go up to ~2**49 starting states for entities.

    And incidently, the generator does go to some work so that sequential starting
values will produce uncorrelated sequences, even right at the start.  This allows
you to write Reset(Generator(N), Seed+N); or some such.