home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / sci / math / 10698 < prev    next >
Encoding:
Internet Message Format  |  1992-08-30  |  2.1 KB
  1. Path: sparky!uunet!van-bc!rsoft!agate!ames!haven.umd.edu!darwin.sura.net!gatech!purdue!news.cs.indiana.edu!umn.edu!epx.cis.umn.edu!rogers
  2. From: rogers@epx.cis.umn.edu
  3. Newsgroups: sci.math
  4. Subject: Psuedo Random sequences   Help needed
  5. Summary: Binary psuedo random sequence,  which bits or XORed in?
  6. Message-ID: <1992Aug29.230020.12972@news2.cis.umn.edu>
  7. Date: 29 Aug 92 23:00:20 GMT
  8. Sender: news@news2.cis.umn.edu (Usenet News Administration)
  9. Organization: University of Minnesota
  10. Lines: 43
  11.  
  12.  
  13.    I am need a random sequence for a graphics effect, and I can't
  14. remember which bits to exclusive or together.  About ten years ago
  15. I used data in a book to generate 24 bit sequences, but right now I need
  16. a 12 bit sequence.   This is how it works:
  17.  
  18.       xxxxxxxxxxxx
  19.    -->010101011001   <- a 12 bit binary number that will be shifted right
  20.    |          |  | 
  21.    |          |  |  <- two bits to be excluse ored together (and the result 
  22.    | <-bit    \  /         inverted and shifted back in)
  23.    |  shifted  []  
  24.    | back in    |
  25.    \            /
  26.     ------------
  27.  
  28. The sequence will lock up if all ones are in the register, but otherwise
  29. should give every number between zero and 4095 (inclusive) in an apparently
  30. random order.  This is just what I need for what I am doing because I
  31. need every number once to clear every location on the screen in a random
  32. order.  
  33.   
  34.    The problem is I cannot remember which bits to XOR (or XNOR) together
  35. and I think I have tried every combination. (of two bits)  I know that
  36. some of the larger (bit length) sequences needed four bits to XNOR together.
  37.  
  38.   Does this sound familer to anyone?  Does anyone know what book I could 
  39. find it in?
  40.  
  41. In C, the algorithm looks like this: (R=num, P= 2^p, Q= 2^q , p and q are bits)
  42. (bits 0 and 3 were used in the example above,
  43.   which would give P=2^0=1 and Q=2^3=8 )
  44.  
  45. if (((R&P)&!(R&Q))||(!(R&P)&(R&Q)))   /* R bit p XORed with R bit q */
  46.    R = R >>1;                         /* R = R/2 */
  47. else
  48.    R = (R+4096)>>1;                   /* R gets a one shifted in */
  49.  
  50.  
  51. Thanks in advance,
  52. Brynn
  53.  
  54. rogers@epx.cis.umn.edu         (612) 536-6444
  55.