Elixir implementation of a binary Galois Linear Feedback Shift Register.
It can be used to generate out-of-order counters, since a LFSR of size n can generate a sequence of length 2n-1 (without repetitions).
Add LFSR as a dependency in your mix.exs file.
def deps do
[{:lfsr, "~> 0.0.2"}]
endAfter you are done, run mix deps.get in your shell to fetch and compile LFSR. Start an interactive Elixir shell with iex -S mix.
iex> lfsr = LFSR.new(1, 16)
%LFSR{mask: 46080, state: 1}
iex> lfsr = lfsr |> LFSR.next |> LFSR.next
%LFSR{mask: 46080, state: 23040}
iex> LFSR.state(lfsr)
23040
Let's generate a pseudo-random sequence of numbers between 1_000_000 and 9_999_999.
We need a 24-bit LFSR, since with a 23-bit we can only produce a sequence with length 8_388_607.
iex> LFSR.new(5_345_234, 24) \
...> |> Stream.iterate(&LFSR.next/1) \
...> |> Stream.map(&LFSR.state/1) \
...> |> Stream.filter(&(&1 in 1_000_000..9_999_999)) \
...> |> Enum.take(100)
[5345234, 2672617, 6697466, 3348733, 6342207, 9312455, 9930289, 9683736,
4841868, 2420934, 1210467, 5787404, 2893702, 1446851, 5816952, 2908476,
1454238, 8610569, 5036226, 2518113, 6658840, 3329420, 1664710, 6002284,
3001142, 1500571, 5823667, 5315478, 2657739, 6230457, 8111214, 4055607,
8764486, 4382243, 5397444, 2698722, 1349361, 6890940, 3445470, 1722735,
8472877, 5001803, 5474889, 7922322, 3961161, 6495314, 3247657, 6316938,
3158469, 6294641, ...]
defmodule PRNG do
def start_link do
Agent.start_link(fn -> LFSR.new(5_345_234, 24) end, name: __MODULE__)
end
def next do
Agent.get_and_update(__MODULE__, fn lfsr ->
lfsr = next_valid(lfsr)
{lfsr.state, lfsr}
end)
end
defp next_valid(%LFSR{} = lfsr) do
lfsr = LFSR.next(lfsr)
if lfsr.state in 1_000_000..9_999_999, do: lfsr, else: next_valid(lfsr)
end
endiex> PRNG.start_link
{:ok, #PID<0.101.0>}
iex> PRNG.next
2672617
iex> PRNG.next
6697466