home *** CD-ROM | disk | FTP | other *** search
- Newsgroups: sci.math.num-analysis
- Path: sparky!uunet!cs.utexas.edu!wupost!darwin.sura.net!Sirius.dfn.de!Urmel.Informatik.RWTH-Aachen.DE!kaa!dak
- From: dak@kaa.informatik.rwth-aachen.de (David Kastrup)
- Subject: Re: Distributed Random Number Generation
- Message-ID: <dak.716460475@kaa>
- Sender: news@Urmel.Informatik.RWTH-Aachen.DE (Newsfiles Owner)
- Nntp-Posting-Host: kaa
- Organization: Rechnerbetrieb Informatik / RWTH Aachen
- References: <h_8yzkk@rpi.edu> <DAVEG.92Sep13010611@synaptx.synaptics.com> <dak.716387354@tabaqui> <5h9ya7-@rpi.edu>
- Date: 14 Sep 92 08:47:55 GMT
- Lines: 60
-
- maniattb@cs.rpi.edu (Bill Maniatty) writes:
-
- >In article <dak.716387354@tabaqui>, dak@tabaqui.informatik.rwth-aachen.de (David Kastrup) writes:
- >|> daveg@synaptics.com (Dave Gillespie) writes:
- >|>
- >|> >In article <h_8yzkk@rpi.edu> maniattb@cs.rpi.edu (Bill Maniatty) writes:
- >|> >> I have a large distributed stochastic model (runs on MasPar MP-1 with 2,048
- >|> >> processing elements). I'm not an expert on random number generation, but
- >|> >> I need to simultaneously g enerate different ``Random'' sequences on each
- >|> >> node.
- >|>
- >|> >If the nodes must be independent, then it would probably work pretty
- >|> >well to use one random number generator, say, linear congruential,
- >|> >to create a sequence of 2048 seeds for a different type of generator,
- >|> >say additive congruential, running in parallel on the various nodes.
- >|>
- >|> This idea is really bad, because it ensures that no two generators will
- >|> give the same number at one moment (or even always the same). Besides, random
- >|> number generators are usually not designed to produce uncorrelated
- >|> numbers at ARBITRARY distances in their sequence, so you would probably
- >|> fail even simple tests terribly. As I said before, the only mathematically
- >|> safe way is to use ONE (and only one) generator of very high quality to
- >|> produce values in turn. This is because the mathematics for a good RNG
- >|> can only be ensured with regard to itself, not to other instances of it
- >|> (different seeds), and certainly not to different RNGs without further
- >|> information.
-
- >The problem with this solution as I see it is that it eliminates any parallelism
- >I might have in my program. Please remember that there is a LARGE number of
- >random number generated (2048) for each time step. It seems that making each
- >time step wait for all 2048 random numbers to be generated is terribly
- >inefficient (wait to generate 2047 random numbers never used by this processor).
-
- >Can you tell me just what sort of metrics are used to determine ``randomness'',
- >and suggest some solutions/references (can a sequential algorithm be extended
- >to operate in parallel? can a parallel algorithm be developed directly with any
- >reasonable degree of confidence?)
-
- The most important test for randomness is the spectral test. In essence,
- ina p-dimensional spectral test, you take all possible sequences of
- p consecutive numbers, and regard them as points in p-dimensional space.
- The maximum distance of two p-1-dimensional planes in any direction of
- the space is a measure for the goodness of the generator. All good
- algorithms have been shown to pass this test reasonaby, all bad
- generators seem to fail it. p usually runs about to 1-8 when testing.
-
- For more specifications and some good generators, try Seminumerical
- Algorithms (The Art of Computer Programming) by Knuth.
-
- Letting ONE generator run on all machines is no problem, because
- applying a linear congruential generator 2048 times can be replaced by
- applying a different one only one time. So you start by giving
- each generator the next value in sequence of the basic generator
- as a seed, then proceed by letting the individual generators
- advance 2048 steps at a time. But in 2048-dimensional space a
- single LNG is pretty probable to be bad. Maybe the best idea would
- be to choose a set of different LNG with relatively prime period,
- and use them instead. This would certainly imply having to program
- a spectral test to check the generators, or else bad ones will be
- there (I know no precompiled tables of 2048 RNGs)
-