home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / sci / math / stat / 2847 < prev    next >
Encoding:
Text File  |  1993-01-23  |  6.4 KB  |  205 lines
  1. Newsgroups: sci.math.stat
  2. Path: sparky!uunet!usc!sol.ctr.columbia.edu!The-Star.honeywell.com!umn.edu!cda.mrs.umn.edu!naras
  3. From: naras@cda.mrs.umn.edu (B. Narasimhan)
  4. Subject: Re:  More on Random Number Generators.
  5. Message-ID: <C19MDn.8xu@cda.mrs.umn.edu>
  6. Sender: news@cda.mrs.umn.edu (USENET News System)
  7. Nntp-Posting-Host: sci234e.mrs.umn.edu
  8. Organization: University of Minnesota - Morris
  9. References:  <C17rJD.KAv@cda.mrs.umn.edu>
  10. Date: Fri, 22 Jan 1993 17:10:35 GMT
  11. Lines: 192
  12.  
  13. Due to some requests following my previous post, I am posting 
  14. the entire paper here to the net. (I do not know where it is
  15. located on the net.)  It is not long.
  16.  
  17. Note, paper is in plain TeX.
  18.  
  19. ****************** Cut Here *******************
  20. \magnification=\magstep1
  21. \hfuzz=4.pt
  22. \baselineskip 20 pt
  23. \hsize=15truecm
  24. \vsize=23truecm
  25. \voffset=0pt
  26. \hoffset=1truecm
  27. \def\big{\bigskip \noindent}
  28. \def\med{\medskip \noindent}
  29. \def\c{\line}
  30. \def\i{\item}
  31.  
  32. \parindent=0mm
  33. \centerline{\bf Hidden Errors in Simulations and the Quality of Pseudorandom
  34.                 Numbers}
  35.  
  36. \big
  37. \big
  38. In a recent letter Ferrenberg {\it et al.} (FLW) [1] present intriguing
  39. results arising from combinations of some random number generators
  40. and Monte Carlo acceleration algorithms. In particular, they observe
  41. systematic errors when the Wolff algorithm [2] is used at $T_c$ in the
  42. $2-d$ Ising model.
  43. As an explanation of this, they propose that subtle correlations
  44. arise in the random number sequences, in the sense that the
  45. higher order bits of the random numbers are correlated.
  46.  
  47. \med
  48. We have recently carried out extensive statistical,
  49. bit level, and visual tests for several commonly used
  50. pseudorandom number generators in physics applications [3].
  51. Two of these were used in Ref. 1, namely
  52. R250 [4] and CONG [5].
  53. Using the Wolff algorithm FLW discovered problems
  54. with R250, but not with CONG. Thus, our test results bear
  55. direct relevance to the existence of possible problems, and
  56. differences between these two algorithms.
  57.  
  58. \med
  59. To directly probe the correlations between each bit of consecutive pseudorandom
  60. numbers, we have performed two quantitative tests. The first one
  61. is an extended version of the $m$-tuple test [6].
  62. The second test was based on the range of binary
  63. random matrices [7].
  64. In Table 1 we present a summary of the results
  65. for each of the 31 significant bits from random
  66. numbers generated by R250 and CONG.
  67. Our results indicate no bit level correlations in CONG.
  68. The same is true for R250, {\it provided} it is properly initialized.
  69. This is demonstrated in Table 2, where R250 was initialized by a
  70. lagged Fibonacci generator RAN3 [8], which contains several
  71. correlated bits, including five of the most significant ones.
  72. As seen in the results, correlations from RAN3 transform into R250.
  73.  
  74. \med
  75. Our results thus indicate that the problems observed
  76. in Ref. 1 have no simple explanation in terms of bit level correlations.
  77. We note that both R250 and CONG were also subjected to an array of
  78. statistical tests [3,5], in which neither of them
  79. showed any particular weaknesses. However, our $2-d$ visual tests
  80. did reveal a periodic spatial fine structure in CONG,
  81. a result not unexpected with this type of algorithm [3].
  82. Yet, no problems with CONG were reported by FLW.
  83. Since their results presently have no clear explanation,
  84. we wholeheartedly agree with them
  85. on the importance of careful physical tests [3]
  86. before a particular "good quality" generator is chosen for simulations.
  87.  
  88. \big
  89. \big
  90. \c{I. Vattulainen$^1$, K. Kankaala$^{1,2}$, J. Saarinen$^1$, and
  91. T. Ala-Nissila$^3$ \hfil}
  92.  
  93. \baselineskip=12pt
  94.  
  95. \big
  96. \c{$^1$Department of Electrical Engineering \hfil}
  97. \c{Tampere University of Technology \hfil}
  98. \c{P.O. Box 692 \hfil}
  99. \c{SF-33101 Tampere \hfil}
  100. \c{Finland \hfil}
  101.  
  102. \med
  103. \c{$^2$CSC Scientific Computing \hfil}
  104. \c{P.O. Box 405 \hfil}
  105. \c{SF-02101 Espoo \hfil}
  106. \c{Finland \hfil}
  107.  
  108. \med
  109. \c{$^3$Research Institute for Theoretical Physics \hfil}
  110. \c{P.O. Box 9 (Siltavuorenpenger 20 C) \hfil}
  111. \c{SF-00014 University of Helsinki \hfil}
  112. \c{Finland \hfil}
  113.  
  114. \big
  115. PACS numbers: 75.40Mg, 02.70.Lq, 64.60.Fr
  116.  
  117. \vfill \eject
  118.  
  119. \baselineskip=16pt
  120. \centerline{\bf References:}
  121.  
  122. \big
  123. \i{[1]} A. M. Ferrenberg, D. P. Landau, and Y. J. Wong, Phys. Rev. Lett.
  124.        {\bf 69}, 3382 (1992).
  125.  
  126. \i{[2]} U. Wolff, Phys. Rev. Lett. {\bf 62}, 361 (1989).
  127.  
  128. \i{[3]} I. Vattulainen, K. Kankaala, J. Saarinen, and T. Ala-Nissila,
  129.         CSC Research Report R05/92 (Centre for Scientific Computing,
  130.         Espoo, Finland, 1992); to be published.
  131.  
  132. \i{[4]} S. Kirkpatrick and E. Stoll, J. Comput. Phys. {\bf 40}, 517 (1981).
  133.  
  134. \i{[5]} D. E. Knuth, {\it The Art of Computer Programming, vol. 2:
  135. Seminumerical
  136.         Algorithms}, 2nd. ed. (Addison - Wesley, Reading, 1981).
  137.  
  138. \i{[6]} S. N. Altman, J. Sci. Stat. Comput. {\bf 9}, 941 (1988).
  139.  
  140. \i{[7]} G. A. Marsaglia, in {\it Computational Science and Statistics:
  141.         The Interface}, ed. L. Billiard (Elsevier, New York, 1985).
  142.  
  143. \i{[8]} W. H. Press, B. P. Flannery, S. A. Tenkolsky, and W. T. Vetterling,
  144.         {\it Numerical Recipes: The Art of Scientific Computing
  145.     (FORTRAN Version) } (Cambridge University Press, 1989).
  146.  
  147.  
  148. \vfill \eject
  149. \hoffset=-1truecm \hsize=12truecm \centerline{\bf Table Captions:}
  150. \big
  151. \big
  152. \rm
  153. \vbox{\tabskip=0pt \offinterlineskip
  154. \halign{
  155. \strut \vrule \quad #\quad & \vrule \hfil \quad #\quad \hfil &
  156. \vrule \hfil \quad #\quad \hfil \vrule \cr
  157. \noalign{\hrule}
  158. Random & Failing bits & Failing bits \cr
  159. number & in the & in the \cr
  160. generator & {\it m}-tuple test & random matrix test \cr
  161. \noalign{\hrule}
  162. R250 & none & none \cr
  163. CONG & none & none \cr
  164. \noalign{\hrule}
  165. }
  166. }
  167. \hoffset=3truecm
  168. \hsize=12truecm
  169. \big
  170. \i{Table 1.} The \hfil results \hfil of \hfil an \hfil extended \hfil
  171. {\it m}-tuple \hfil test \hfil with \hfil parameters \break
  172. $m~=~t~=~3$, and a test using $2 \times 2$ random matrices. In these tests
  173. R250 was initialized by CONG.
  174. \big
  175. \big
  176. \big
  177. \big
  178. \vbox{\tabskip=0pt \offinterlineskip
  179. \halign{
  180. \strut \vrule \quad #\quad & \vrule \hfil \quad #\quad \hfil &
  181. \vrule \hfil \quad #\quad \hfil \vrule \cr
  182. \noalign{\hrule}
  183. Random & Failing bits & Failing bits \cr
  184. number & in the & in the \cr
  185. generator & {\it m}-tuple test & random matrix test \cr
  186. \noalign{\hrule}
  187. R250 & 1 - 2, 27 - 31 & 1, 27 - 31 \cr
  188. RAN3 & 1 - 5, 25 - 30 & 1 - 5, 26 - 30 \cr
  189. \noalign{\hrule}
  190. }
  191. }
  192. \big
  193. \i{Table 2.} The results of bit level tests for R250 initialized by RAN3.
  194.  
  195. \bye
  196.  
  197.  
  198.  
  199.  
  200. -- 
  201. B. Narasimhan                             naras@cda.mrs.umn.edu
  202. Division of Science and Math.
  203. The University of Minnesota at Morris
  204. Morris, MN 56267
  205.