home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / sci / math / stat / 1713 < prev    next >
Encoding:
Text File  |  1992-08-20  |  2.2 KB  |  54 lines
  1. Newsgroups: sci.math.stat
  2. Path: sparky!uunet!mcsun!news.funet.fi!cc.tut.fi!vattu
  3. From: vattu@cc.tut.fi (Vattulainen Ilpo)
  4. Subject: Re: Generating a set of random bits
  5. Message-ID: <1992Aug20.195901.2259@cc.tut.fi>
  6. Organization: Tampere University of TeXnology
  7. References: <36984@sdcc12.ucsd.edu> <1992Aug19.122345.27772@cl.cam.ac.uk>
  8. Date: Thu, 20 Aug 92 19:59:01 GMT
  9. Lines: 42
  10.  
  11.  
  12. >In article <36984@sdcc12.ucsd.edu>, whart@cs.ucsd.edu (Bill Hart) writes:
  13. >|> I have an application for which I need to generate a random 'vector' of 
  14. >|> bits of length N.  
  15. >
  16. >nmm@cl.cam.ac.uk (Nick Maclaren) writes:
  17. >Standard warnings:
  18. >
  19. >    2) Don't trust Numerical Recipes - about half of its techniques are
  20. >reliable, but the others contain serious traps.  
  21.  
  22.     I agree.
  23.  
  24. >Perhaps the best method for your application is a Tausworthe (also called
  25. >shift-register, primitive polynomial over GF(2), etc.) with a generating
  26. >polynomial of order at least N.
  27.  
  28.     Indeed, although one cannot generalize the properties of 
  29.     shift-register generators, especially many GFSR (generalized feedback
  30.     shift-register) generators have been noticed to have good 
  31.     statistical bit-wise properties. The results, however, depend 
  32.     strongly on initialization and the choice of exponents in the 
  33.     primitive polynomial (like p and q in a polynomial 
  34.     x**p + x**q + 1 ). Hence it might be a quite good choice to 
  35.     call such a generator with integers, and transform them to 
  36.     bits. These words of bits you could use for your purpose. Notice, 
  37.     however, that this rng should not be called to get real numbers 
  38.     distributed [0,1) and then multiplied with some integer (like 
  39.     2**p - 1, where p is the number of bits in a particular cpu). 
  40.     This way you will get only 24 random bits out of 31 (on a 
  41.     32-bit machine), due to 24-bit mantissas in real mode...
  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.     And one quite reliable method is to take only few most 
  47.     significant bits out of random numbers. Usually all the bits 
  48.     are not random, but at least 10 of the most significant ones 
  49.     are. But - do not use RAN3 (in Numerical Recipes ), if you 
  50.     want random bit-wise properties... This is due to my own 
  51.     experiences :-/
  52.  
  53.     vattu@ee.tut.fi
  54.