A simple implementation of maximal length Linear Feedback Shift-Registers from 4 bits to 64 bits, allowing for fast generation of a pseudo-random permutation of the numbers {1, 2, ..., N} for any N from 1 to 2^64 - 1.
The sole exported function from this package is
LFSR(length; seed = 1)
which, constructs a maximum length shift register that will randomly cycle once through the numbers 1 to length.
Keyword argument seed defines the starting point for the LFSR.
# Standard LFSR
julia> A = LFSR(10)
LFSR for 1:10 starting at 1
julia> for i in A
println(i)
end
1
9
7
10
5
6
3
8
4
2
# Change the starting location
julia> A = LFSR(10; seed = 7)
LFSR for 1:10 starting at 7
julia> for i in A
println(i)
end
7
10
5
6
3
8
4
2
1
9If your desired length satisfies ispow2(length + 1), then you can take advantage of the FastLFSR, which iterates a little more quickly.
julia> A = FastLFSR(15)
LFSR for 1:10 starting at 1
julia> println.(A);
1
9
13
15
14
7
10
5
11
12
6
3
8
4
2The implementation attempts to be as efficient as possible.
To construct a LFSR for an arbitrary length, MaxLFSR will choose the minimum possible number of bits needed to encode that length.
During iteration, values generated by the underlying LFSR will be skipped.
Feedback terms were taken from https://users.ece.cmu.edu/~koopman/lfsr/index.html
In theory, this package generates LFSRs up to 64 bits in length. However, it is impossible to actually test sequences this long. Hence, the test-suite only tests LFSRs up to a maximum length of 30 bits.