home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / sci / math / stat / 1697 < prev    next >
Encoding:
Internet Message Format  |  1992-08-19  |  2.3 KB
  1. Path: sparky!uunet!centerline!noc.near.net!news.Brown.EDU!qt.cs.utexas.edu!yale.edu!yale!mintaka.lcs.mit.edu!bloom-beacon!eru.mt.luth.se!lunic!sunic!mcsun!uknet!cam-cl!cam-cl!nmm
  2. From: nmm@cl.cam.ac.uk (Nick Maclaren)
  3. Newsgroups: sci.math.stat
  4. Subject: Re: Generating a set of random bits
  5. Message-ID: <1992Aug19.122345.27772@cl.cam.ac.uk>
  6. Date: 19 Aug 92 12:23:45 GMT
  7. References: <36984@sdcc12.ucsd.edu>
  8. Sender: news@cl.cam.ac.uk (The news facility)
  9. Reply-To: nmm@cl.cam.ac.uk (Nick Maclaren)
  10. Organization: U of Cambridge Computer Lab, UK
  11. Lines: 41
  12.  
  13. In article <36984@sdcc12.ucsd.edu>, whart@cs.ucsd.edu (Bill Hart) writes:
  14. |> I have an application for which I need to generate a random 'vector' of 
  15. |> bits of length N.  I have looked at stuff in Numerical Recipies for
  16. |> generating a random sequence of bits, but it remains unclear whether
  17. |> such a generator would be appropriate for generating a random
  18. |> vector of bits.
  19. |> 
  20. |> I need/want to have the distribution of vectors remain 'random'.  Right
  21. |> now I'm generating a random float in [0,1> and testing to see
  22. |> if it is less than 0.5 or not.  This works, but I'm sure there is
  23. |> a better way of doing this.
  24.  
  25. Standard warnings:
  26.  
  27.     1) Your current technique is OK, but do NOT break up a random float
  28. into multiple bits to save on efficiency.  Some techniques will survive
  29. this but others will not.
  30.  
  31.     2) Don't trust Numerical Recipes - about half of its techniques are
  32. reliable, but the others contain serious traps.  In this case it is not
  33. too bad, though your reservations about whether its techniques extend to
  34. vectors are fully justified.
  35.  
  36. Perhaps the best method for your application is a Tausworthe (also called
  37. shift-register, primitive polynomial over GF(2), etc.) with a generating
  38. polynomial of order at least N.  Knuth and others have details, but finding
  39. a good one is non-trivial and dependent on the size of N, whether it varies
  40. and what degree of randomness you need.  Much of the theory of this sort of
  41. generator is in hardware-related journals.
  42.  
  43. I am afraid that there is no simple solution to the general case of random
  44. vectors of bits, but there are several fairly reliable ones.
  45.  
  46.  
  47. Nick Maclaren
  48. University of Cambridge Computer Laboratory,
  49. New Museums Site, Pembroke Street,
  50. Cambridge CB2 3QG, England.
  51. Email:  nmm@cl.cam.ac.uk
  52. Tel.:   +44 223 334761
  53. Fax:    +44 223 334679
  54.