#!/usr/bin/perl -w
# Linear feedback shift register
#
# 2014-03-02

use strict;

my $lfsr = 5;

sub NextRand()
{
   # Period = 85932
   #$lfsr = (($lfsr >> 1) ^ (0x0d000001 & -($lfsr & 1))) & 0x0fffffff;

   # Period = 2793131
   #$lfsr = (($lfsr >> 1) ^ (0x34000001 & -($lfsr & 1))) & 0x3fffffff;

   # Period > 40000000
   $lfsr = (($lfsr >> 1) ^ (0x68000001 & -($lfsr & 1))) & 0x7fffffff;
   return $lfsr;
}


my %seen = ();
my @freq = (0, 0, 0, 0);
for(my $i = 0; $i < 40000000; $i++)
{
   my $x = NextRand();
   $freq[$x & 3]++;
   if( exists $seen{$x} )
   {
      print "Period = $i\n";
      last;
   }
   $seen{$x}++;
}
for(my $i = 0; $i < 4; $i++)
{
   print "freq[$i] = $freq[$i]\n";
}