home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / sci / crypt / 7180 < prev    next >
Encoding:
Text File  |  1993-01-28  |  3.1 KB  |  68 lines
  1. Newsgroups: sci.crypt
  2. Path: sparky!uunet!charon.amdahl.com!pacbell.com!att-out!walter!qualcom.qualcomm.com!qualcom!rdippold
  3. From: rdippold@qualcom.qualcomm.com (Ron Dippold)
  4. Subject: Re: Wanted: very fast random number generator
  5. Message-ID: <rdippold.728097174@qualcom>
  6. Sender: news@qualcomm.com
  7. Nntp-Posting-Host: qualcom.qualcomm.com
  8. Organization: Qualcomm, Inc., San Diego, CA
  9. References: <C1H7tG.7At.2@cs.cmu.edu>
  10. Date: Wed, 27 Jan 1993 01:12:54 GMT
  11. Lines: 55
  12.  
  13. tgl+@cs.cmu.edu (Tom Lane) writes:
  14. >What I need is a very very fast random number generator; it does NOT need to
  15. >be cryptographically strong.  The application is in generating random noise
  16. >for dithering a color image.  I need about 8 random bits on each call
  17. >(randomness of the low order bits is less important than the higher).
  18. >Ideally it would take, say, just a shift and XOR per value.  The code has to
  19. >be portable C, so circular shifts and other non-C operations are out.
  20.  
  21. Sounds like what you want may be a PN generator.  I don't have any
  22. references on them, but that's a start.  They're very fast, they're
  23. _almost_ random by all the usual tests, they're just slick.  It's been
  24. a while since I did them in software rather than hardware, but here's
  25. the basic loop, I believe:
  26.  
  27.     unsigned int pn;
  28.  
  29.     if( pn & 1 == 1 ) {
  30.       pn = ( ( pn >>1 ) ^ mask ) | 0x8000;
  31.     } else {
  32.       pn >>= 1;
  33.     }
  34.  
  35. 0x8000 assumes that it's a 16-bit PN register.  You can adjust this to
  36. anything you want.  The mask is the crucial part.  The length of the
  37. sequence depends on the value you use for the mask and the initial
  38. value of pn.  Eventually the sequence will repeat again.  The number
  39. of iterations before that happens is the PN sequence length.
  40. Obviously you don't want a length that's too low.  Nor do you ever
  41. want a value of 0 in your pn register, or it'll never change.
  42.  
  43. In most applications (hardware) you actually use the bottom bit of the
  44. pn sequence as your random output.  There shouldn't be any problem,
  45. however, with using, say, the lower 8 bits for your application.
  46. Another method (though somewhat costly in software) is to xor all the
  47. bits in the register together - again this produces a one bit serial
  48. output.
  49.  
  50. Usually, the bigger the register the longer the sequences - my code
  51. above is for the PC and assumes a 16-bit size.  If the computer you're
  52. going to be running this on will do 32-bit just as easily or almost as
  53. fast you might consider a 32-bit sequence, which should run from here
  54. to eternity.  As to which sequence to use, I'm sure there's some
  55. published, but I don't have any good ones handy.  May I suggest brute
  56. force?  Just chug along until you find one that's sufficiently long
  57. for your needs.  
  58.  
  59. For a 16-bit PN register, if you use a mask of 0xfff6 and a non-zero
  60. starting value in the register with the above code you get a pn
  61. sequence that runs through every possible value value in the pn
  62. register (except 0)!  I believe there is such a mask for any size
  63. register...  And now you also know an excellent way to do pixel by
  64. pixel "random" fades from one picture to another.
  65.  
  66. -- 
  67. What passes for woman's intuition is often nothing more than man's transparency
  68.