njk@diku.dk (Niels J|rgen Kruse) (05/01/89)
matloff%mole.Berkeley.EDU@ucbvax.Berkeley.EDU (Norman Matloff) writes: >Here is the setting. It's discrete-event simulation, which many or most >of your references are concerned with, on multiple-processor systems >(tightly or loosely coupled). Let P be the number of processors and T >be the amount of run time needed to get the desired statistical accuracy. >Moreover, it seems to me that the best method is also the simplest -- >just have all P processors run the uniprocessor version of the program, >but for T/P amount of run time, instead of T. [Of course, each processor >needs to use a different random number seed.] Beware! It is not uncommon for pseudo random number generators to show a much reduced independence between streams generated from different seeds, compared to the independence within each stream. For instance, the Bsd random suffer from this. If you sample the 2 least significant bits, collect them to form 7 bit numbers (discarding the least significant), take an equal number of samples from more than 15 or so streams, perform chi square analysis on the samples, you will get a value *well* above the 0.99 percentile. -- Niels J|rgen Kruse Email njk@diku.dk Mail Tustrupvej 7, 2 tv, 2720 Vanlose, Denmark
matloff%mole.Berkeley.EDU@ucbvax.Berkeley.EDU (Norman Matloff) (05/02/89)
In article <5347@hubcap.clemson.edu> njk@diku.dk (Niels J|rgen Kruse) writes: >matloff%mole.Berkeley.EDU@ucbvax.Berkeley.EDU (Norman Matloff) writes: *>Here is the setting. It's discrete-event simulation, which many or most *>of your references are concerned with, on multiple-processor systems *>(tightly or loosely coupled). Let P be the number of processors and T *>be the amount of run time needed to get the desired statistical accuracy. *>Moreover, it seems to me that the best method is also the simplest -- *>just have all P processors run the uniprocessor version of the program, *>but for T/P amount of run time, instead of T. [Of course, each processor *>needs to use a different random number seed.] *Beware! It is not uncommon for pseudo random number generators *to show a much reduced independence between streams generated *from different seeds, compared to the independence within each *stream. >For instance, the Bsd random suffer from this. If you sample the >2 least significant bits, collect them to form 7 bit numbers >(discarding the least significant), take an equal number of >samples from more than 15 or so streams, perform chi square >analysis on the samples, you will get a value *well* above the >0.99 percentile. I agree with all points except the last. Do NOT do chi square analyis as your criterion for deciding whether to use a random number generator. You can get results "well above the 0.99 percentile" for ANY generator, if you look at a long stream. A statistical hypothesis test can only test whether the null hypothesis is EXACTLY correct, i.e. in this case, whether the random number generator is exactly random. But since we must work with PSEUDO-random generators, the null hypothesis will be false, and will be rejected -- dramatically so -- with large samples. Norm