On the right you can see my version of the Linear Feedback Shift Register. The function random takes the value in seed and uses a mask to pick off bits in the middle of the value. The variable mid holds 1 if the middle bit is set. The variable top holds 1 if the top bit is set. When I combine these using the XOR (^) operator I get the value of the new bottom bit. I can them shift the value of seed to the left and OR in the new value.

The maximum possible length of the sequence I can get would be 256, since this is the largest number which my eight bit register can hold. However, some sequences will be longer than others, depending on the value we start with and the pattern in the mask. I want the longest possible sequence, since this gives me the best random effect.

If I had time I could work out the longest sequence mathematically, but I can't be bothered with that. Instead I will take the brute force approach and write a program which will try all the combinations of masks and start values. It will then print out the best settings for me to use.

/* use LFSR based algorithm for */
/* random number generation     */

/* holds the successive random  */
/* values                       */
unsigned char seed = 1 ;

/* mask to apply each time      */
unsigned char mask = 1 ;

unsigned char random ( void )
{
  unsigned char top, mid ;

  /* get middle bit  */
    if ( seed & mask )
  {
    mid = 1 ;
  }
  else
  {
    mid = 0 ;
  }

  /* get top bit  */
    if ( seed & 0x80 )
  {
    top = 1 ;
  }
  else
  {
    top = 0 ;
  }

  /*  assemble the result    */
  /*  by ORing them together */

  seed = ( seed << 1 ) |
         ( mid ^ top ) ;
  return seed ;
}