Yet another pseudo-random number generator

[Herman Rubin]

In article <5313 at cognos.UUCP>, rayt at cognos.uucp (R.) writes:
> In article <9653 at smoke.BRL.MIL> gwyn at brl.arpa (Doug Gwyn) writes
> in response to my mention of the recent CACM article on random
> generators, that:
> 
> "Virtually all PRNG schemes in common use have provable
>  statistical behavior.  That doesn't mean they're always
>  suitable.  In fact I'm not enthised about that CACM article."

They have good uniformity of distribution.  But this by itself is
meaningless.  Suppose that the n-th PRN is n (modulo k).  Then the
distribution is uniform.  Or one can use quasi-random numbers, such
as the fractional part of n*2(.5).  These are provably more uniform
than random numbers.  If they are to be used for estimating the integral
of a "smooth" function, even in many dimensions, and are used one-at-
a-time, then multidimensional quasi-random numbers are likely to be
much better than random numbers.

But the problem is independence.  Suppose that one is using an acceptance-
rejection or acceptance-replacement scheme to generate exponential or
normal random variables.  Then there is interaction between the uniform
input at different places.  So independence becomes important.  The
only really good ones here are the "cryptographically strong" generators,
which are quite expensive.  Some of the procedures with long seeds, like

	x[n] = x[n-460] XOR x[n-607]

with a seed of 607 words of the longest type which could be used, are 
probably fairly good.  Using any type of physical random numbers XORed
with the pseudo-random numbers is likely to improve the performance;
radioactive sources, using the parity of the number of counts in intervals,
are quite good and even improve with a quite considerable dead time.
If repeatability is needed, the physical random numbers should be stored.

> Are you refering to the need to have skewed or otherwise non-normal
> distributions? Also I'm interested in knowing what you found
> wanting in the CACM article.

The type of non-uniform random variables wanted has little to do with
the problem.  Now sometimes good results can be obtained with quasi-
random numbers; in this case, one needs a QRNG, not a PRNG.  But the
circumstances in which QRNs work well are more restrictive.
-- 
Herman Rubin, Dept. of Statistics, Purdue Univ., West Lafayette IN47907
Phone: (317)494-6054
hrubin at l.cc.purdue.edu (Internet, bitnet, UUCP)