home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #20 / NN_1992_20.iso / spool / sci / math / numanal / 2716 < prev    next >
Encoding:
Text File  |  1992-09-13  |  4.0 KB  |  73 lines

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