Path: bga.com!news.sprintlink.net!hookup!ames!lll-winken.llnl.gov!noc.near.net!pad-thai.aktis.com!la-jiao.aktis.com!not-for-mail From: don@cam.ov.com (Donald T. Davis) Newsgroups: sci.math,sci.stat.math Subject: Re: BSD random() - any good (source included)? Date: 28 Jun 1994 17:52:48 -0400 Organization: OpenVision Technologies, Inc. Lines: 65 Distribution: na Message-ID: <2uq63g$g5c@la-jiao.aktis.com> References: <deleydCs1L9A.2L6@netcom.com> <iFwLoc3w165w@hakatac.almanac.bc.ca> <Cs4B6w.IqE@SSD.intel.com> NNTP-Posting-Host: la-jiao.aktis.com Xref: bga.com sci.math:15008 sci.stat.math:1243 (George Carr) writes:
(robert bursey) writes: |> deleyd@netcom.com writes: |> |> > I did a research paper on Computer Generated Random Number Sequences in |> > 1991. Included are the results of testing numerous popular generators. |> > The code used for testing the generators is also available if one |> > is so inclined to do some testing of a particular generator. (The only |> > thing is a thorough test to determine the limits of the generator can |> > take many hours of CPU time). |> > |> > Perhaps later this week I'll post the paper and see what the response |> > is. I'm always a bit apprehensive to post. Never sure what the |> > response will be. Maybe someone will think it's interesting. |> > |> > David Deley |> > deleyd@netcom.com |> |> Does anybody know of a good test for randomness? I would definitely like to |> know how good computer RNG's are. Post away!
The classic reference is Volume 2 of Donald Knuth's The Art of Computer Programming, Second Edition, Seminumerical Algorithms. I highly recommend it to anyone wanting to know what "random" is all about.
If you really need to know whether your generator is random-enough for your application you should expect to do your own testing and yes it will require many hours of your time in addition to that of your computer. -- knuth's chapter's practical results are about linear-congruential rngs, their optimization and testing. though these rngs are still distressingly common, nonlinear rngs are the way to go for two burgeoning areas that consume random numbers: graphics and cryptography. both areas are concerned with getting extremely long periods, but cryptography is also concerned with proving unpredictability of secure rngs. that is, knowing some outputs of an rng as applied to a given seed, it should be impossible to deduce or predict other outputs' values.
so, you see, the "good test for randomness" depends strongly on which features of a random variable you want to use. if you're careful, knuth's approach will work fine for some statistical applications, like monte-carlo techniques. but knuth's is by no means the last word on the subject. btw, for cryptographic purposes, the received wisdom is that there is NO adequate test for randomness; if an rng passes lots of tests, that's very nice, but the presumption is that the variable's deterministic structure is simply hidden, and that the clever-enough test was not yet applied or devised. nevertheless, in the cryptographic field, the list of tests used is long. typically, you design the test to probe the weaknesses of a specific rng algorithm. period tests, runs tests, and substring-interarrival tests are common, and some people like entropy estimates. one of the trusted names in the crypto-rng literature is marsaglia; he has published extensively on the subject of rng-testing. i don't know what the graphics literature on rngs is like; i only know that if you want to simulate textured surfaces, like grass, a bad rng makes a striped texture. be forwarned: the rng literature is amazingly vast, with a low signal- to-noise ratio. it seems that everyone thinks he can design a "good" rng. btw, i favor hardware rngs. -don davis openvision technologies cambridge, ma