Path: utzoo!attcan!uunet!cs.utexas.edu!tut.cis.ohio-state.edu!ucbvax!agate!eris.berkeley.edu!mwm
From: mwm@eris.berkeley.edu (Mike (I'll think of something yet) Meyer)
Newsgroups: comp.sys.amiga.tech
Subject: Re: ARexx psuedo-random number generator
Keywords: ARexx Random Number Generator
Message-ID: <1989Sep22.082034.1405@agate.berkeley.edu>
Date: 22 Sep 89 08:20:34 GMT
References: <19504@unix.cis.pitt.edu> <1989Sep13.032352.10321@agate.berkeley.edu> <12003@cit-vax.Caltech.Edu>
Sender: usenet@agate.berkeley.edu (USENET Administrator;;;;ZU44)
Reply-To: mwm@eris.berkeley.edu (Mike (I'll think of something yet) Meyer)
Organization: Missionaria Phonibalonica
Lines: 70

In article <12003@cit-vax.Caltech.Edu> walton@tybalt.caltech.edu.UUCP (Steve Walton) writes:
<In article <1989Sep13.032352.10321@agate.berkeley.edu> mwm@eris.berkeley.edu (Mike (I'll think of something yet) Meyer) writes:
<>As a general rule, serious applications should never use the random
<>number generator provided with a language...
<>"The Art of Computer Programming" vol.  2 - "Seminumerical Algorithms"
<>- is the canonical reference,
<
<Well, I find Knuth pretty tough sledding.

I think I said that. In any case, I gave a second reference that gave
a cookbook approach.

<I'm not sure one can make such a "general rule."

I do - if you include the part you elided about "known good" random
number generators. The one provided by a language may qualify, but
usualy the documentation is completely inadequate - neglecting even
the most basic things, like the length of the cycle.

You also have to look at "serious" applications. Definitions of
"serious" vary, but the one I was thinking of was needing a few
hundred thousand random numbers for a monte carlo simulation, the
results of which were going to be used as input to decide where a
plant worth a couple of hundred million dollars was going to be
located.

The documentation for rand() in the Lattice 5 manual implies that I
might get a 64K cycle if I use 16 bit ints. This is clearly
unacceptable for this application. For the last application I used a
random number generator for, it was just fine (a tod clock would have
been equally usefull, but that's another story).

The documentation for drand() is better - it gives me enough data to
decide that it's at least follows the cookbook. But it would be nice
if I didn't have to do that determination myself.

<One advantage of a language's included generator is that it is (usually) fast.

This, of course, is immaterial if the generator is otherwise
unnaceptable. And that's the real catch with them - you usually don't
have enough information to make that decision for serious
applications.

<A trick recommended by the authors of
<_Numerical Recipes_ (in addition to their own, portable generators) is to
<"scramble " your generator by calling it twice;  the first time is
<used as an index to an array of numbers from the generator.

Knuth recommends a better version of this - use two generators, one
to generate indices, one to generate values.

This will solve a lot of problems - bad low-order bits (drand in
Lattice 5.0 suffers from that; the low-order bit has a cycle only 2^31
as long as the the high-order bit), high sequential correlation, and
simliar things. However, it won't increase the cycle length (though it
will add a non-cyclic sequence to the beginning twice as long as the
number of elements in the "scramble array"), and the NumRecipes hack
could reduce it's length by half (it will do that to drand).

Add to the request for random.library - that it be properly
documented.  Length of the cycle, how far apart the elements are known
to be basically uncorellated, and some measure of how good the low
order bits are would seem to be a bare minimum.

	<mike
--
I'm gonna lasso you with my rubberband lazer,		Mike Meyer
Pull you closer to me, and look right to the moon.	mwm@berkeley.edu
Ride side by side when worlds collide,			ucbvax!mwm
And slip into the Martian tide.				mwm@ucbjade.BITNET