home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / sci / crypt / 2980 < prev    next >
Encoding:
Text File  |  1992-08-21  |  1.7 KB  |  42 lines
  1. Newsgroups: sci.crypt
  2. Path: sparky!uunet!cis.ohio-state.edu!magnus.acs.ohio-state.edu!slc3.ins.cwru.edu!agate!linus!linus.mitre.org!news
  3. From: lewis@aera8700.mitre.org (Keith Lewis)
  4. Subject: Re: random values
  5. Message-ID: <1992Aug21.134217.23612@linus.mitre.org>
  6. Sender: news@linus.mitre.org (News Service)
  7. Nntp-Posting-Host: aera8700.mitre.org
  8. Organization: The MITRE Corporation
  9. References:   <1992Aug20.864.127@ALMAC>
  10. Date: Fri, 21 Aug 1992 13:42:17 GMT
  11. Lines: 29
  12.  
  13. In article <1992Aug20.864.127@ALMAC>, keith.willis@almac.co.uk writes:
  14. >        This is fine as a random bitstream, but for his application,
  15. >        he needs a set of random _values_, in a defined range, with
  16.  
  17. You can convert from a random bitstream to a stream of random discrete
  18. values (let's say, integers from 0..R) by the following algorithm.
  19.  
  20.     Determine N, the number of bits you need (lowest N such that 2**N > R)
  21.  
  22.     while (more bits available)
  23.         construct integer X out of next N bits (X = b(1)+2*b(2)+4*b(3)+...)
  24.         if X <= R
  25.             output X to stream
  26.         else
  27.             do nothing (discard bad X)
  28.     endwhile
  29.  
  30. For ranges that are exactly a power of two, this algorithm works perfectly. 
  31. For other ranges, it may discard (waste) almost half your bitstream.
  32.  
  33. >        the constraint that there must be at least one of each
  34. >        possible value.  
  35.  
  36. At least one of each possible value?  That's a weird requirement.  Could you
  37. just add a list of all possible values onto the end of the stream?
  38.  
  39. Keith Lewis             klewis@mitre.org          "Mr. Cheap"
  40. I don't dance to music; music dances to me.  Email me for my PGP key.
  41. The above may not (yet) represent the opinions of my employer.
  42.