I ran into the concept of a Linear Feedback Shift Register
so I wrote one:
#!/usr/bin/perl -w
use strict;
# Generate a closure that implements a Feedback Shift Register:
# Usage:
# my $fsr= genFSR( $bits, $seed, \&feedBack, [@taps] );
# my $nextBit= $fsr->();
sub genFSR {
my( $bits, $seed, $code, $avTaps )= @_;
return sub {
my $ret= $seed & 1;
my $b= $code->( map $seed & 1<<$_ ? 1 : 0, @$avTaps );
$seed >>= 1;
$seed |= (1&$b)<<$bits;
return $ret;
};
}
# XOR all arguments:
sub xorList {
my $b= 0;
$b ^= pop while @_;
return $b;
}
# Generate a Linear Feedback Shift Register closure:
# Usage:
# my $lfsr= genFSR( $bits, $seed, [@taps] );
# $nextBit= $lfsr->();
sub genLFSR {
my( $bits, $seed, $avTaps )= @_;
return genFSR( $bits, $seed, \&xorList, $avTaps );
}
# Test the above using command-line arguments:
# Usage: lfsr nBits Seed tap tap [tap [...]]
# perl lfsr.pl 5 10 3 5
# perl lfsr.pl 5 0b1010 3 5 # Same if using perl 5.6 or later
# Both of the above use:
# genLFSR( 5, 10, [3,5] );
my $bits= shift;
my $seed= shift;
$seed= oct($seed) if $seed =~ /^0/;
my $lfsr= genLFSR( $bits, $seed, [@ARGV] );
while( 1 ) {
print join( " ", map $lfsr->(), 1..$bits ), $/;
}
To make playing golf on this easier, you only have to
implement a Linear FSR, and you don't have to accept the
list of taps from an anonymous array.
So write a function that generates a closure that implements
an N-bit LFSR with 2 or more taps:
my $lfsr= golfGenLFSR( $nBits, $iSeed, $tap0, $tap1, $tap2 );
my $nextBit= $lfsr->();
You may choose to use packed bit strings instead of
integers (see
vec).
-
tye
(but my friends call me "Tye")
In reply to LFSR golf
by tye
-
Are you posting in the right place? Check out Where do I post X? to know for sure.
-
Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
<code> <a> <b> <big>
<blockquote> <br /> <dd>
<dl> <dt> <em> <font>
<h1> <h2> <h3> <h4>
<h5> <h6> <hr /> <i>
<li> <nbsp> <ol> <p>
<small> <strike> <strong>
<sub> <sup> <table>
<td> <th> <tr> <tt>
<u> <ul>
-
Snippets of code should be wrapped in
<code> tags not
<pre> tags. In fact, <pre>
tags should generally be avoided. If they must
be used, extreme care should be
taken to ensure that their contents do not
have long lines (<70 chars), in order to prevent
horizontal scrolling (and possible janitor
intervention).
-
Want more info? How to link
or How to display code and escape characters
are good places to start.