home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #16 / NN_1992_16.iso / spool / sci / math / stat / 1525 < prev    next >
Encoding:
Text File  |  1992-07-27  |  2.8 KB  |  57 lines
  1. Newsgroups: sci.math.stat
  2. Path: sparky!uunet!cs.utexas.edu!asuvax!ncar!uchinews!galton.uchicago.edu!thisted
  3. From: thisted@galton.uchicago.edu (Ronald A. Thisted)
  4. Subject: Re: random number generator
  5. Message-ID: <1992Jul27.181520.16958@midway.uchicago.edu>
  6. Sender: news@uchinews.uchicago.edu (News System)
  7. Organization: Dept of Statistics, Univ of Chicago
  8. References: <1992Jul27.103659.11820@kth.se> <1992Jul27.124120.29511@cl.cam.ac.uk> <1992Jul27.132508.217@ginger.hnrc.tufts.edu>
  9. Date: Mon, 27 Jul 1992 18:15:20 GMT
  10. Lines: 45
  11.  
  12. In article <1992Jul27.132508.217@ginger.hnrc.tufts.edu> jerry@ginger.hnrc.tufts.edu (Jerry Dallal) writes:
  13. >In article <1992Jul27.124120.29511@cl.cam.ac.uk>, nmm@cl.cam.ac.uk (Nick Maclaren) writes:
  14. >> In article <1992Jul27.103659.11820@kth.se>, md87-mpe@hemul.nada.kth.se
  15. >> (Magnus Pettersson) writes:
  16. >>  
  17.  [regarding the Box-Muller method of generating normal deviates]
  18. >> 
  19. >> Don't use this method in single precision - it has a very serious
  20. >> flaw.  While it is OK in double precision, there are faster and simpler
  21. >> methods available (e.g. the Polar Method as described in Knuth).  The
  22. >> reference for the flaw is by H.R. Neave round about 1970.
  23.  
  24. >...There is nothing wrong with the Box-Muller method.  It is
  25. >theoretically sound... [description of method and other comments
  26. >omitted]
  27.  
  28. >I don't have the article in front of me but I recall that (as explained in a
  29. >followup letter) Neave's argument was flawed.  The problem was with a
  30. >uniform random number generator that used too small a modulus and didn't "kick
  31. >over" fast enough.  
  32.  
  33. Well, actually, the problem is an *interaction* between multiplicative
  34. linear congruential uniform random number generators (modulo 2^^k) and
  35. the Box-Muller transformation.  The Neave interaction occurs with all
  36. such uniform generators, but the problem is most pronounced when the
  37. multiplier is small relative to the modulus.  However, this is a
  38. *sufficient* but not necessary condition for the problem to occur, a
  39. fact ignored in the followups to Neave's paper.  As a simple example,
  40. if  a  is a "bad" multiplier, exactly the same problem will occur if
  41. the random number stream is "played in reverse order", that is, if the
  42. multiplier is replaced by  a^{-1} mod m, where  m  is the modulus of
  43. the generator.  But a^{-1} can be quite large relative to  m, and is
  44. generally not easy to compute (without Macsyma or Maple or
  45. Mathematica).  And, as Nick Maclaren points out, the Marsaglia
  46. modification -- based on exactly the same theorem -- is usually
  47. faster, cheaper, and as easy to program.
  48.  
  49. This is an example of a rare phenomenon that I am particularly
  50. interested in, namely, the situation where two natural algorithms,
  51. each of which is at least adequate, can fail miserably in some way
  52. when combined.
  53.  
  54. Ron Thisted
  55. Department of Statistics/The University of Chicago
  56. thisted@galton.uchicago.edu
  57.