cik@l.cc.purdue.edu (Herman Rubin) (02/23/89)
In article <5313@cognos.UUCP>, rayt@cognos.uucp (R.) writes: > In article <9653@smoke.BRL.MIL> gwyn@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@l.cc.purdue.edu (Internet, bitnet, UUCP)