Submodule sequin
A Python reimplementation of James Coglan’s “sequin” Node.js module.
James Coglan’s “sequin” Node.js module provides a pseudorandom number generator (using rejection sampling on a stream of input numbers) that attempts to minimize the amount of information it throws away: (non-degenerate) rejected samples are fed into a stream of higher-order numbers from which the next random number generation request will be served. The sequin module is used in Coglan’s “vault” module (a deterministic, stateless password manager that recomputes passwords instead of storing them), and this reimplementation is used for a similar purpose.
The main API is the Sequin class, which is thoroughly documented.
Generate pseudorandom non-negative numbers in different ranges.
Given a (presumed high-quality) uniformly random sequence of input
bits, generate pseudorandom non-negative integers in a certain range
on each call of the generate method. (It is permissible to
specify a different range per call to generate; this is the main
use case.) We use a modified version of rejection sampling, where
rejected values are stored in “rejection queues” if possible, and
these rejection queues re-seed the next round of rejection sampling.
This is a Python reimplementation of James Coglan’s Node.js sequin module, as introduced in his blog post. It uses a technique by Christian Lawson-Perfect. I do not know why the original module is called “sequin”; I presume it to be a pun on “sequence”.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
sequence
|
str | bytes | bytearray | Sequence[int]
|
A sequence of bits, or things convertible to bits, to seed the pseudorandom number generator. Byte and text strings are converted to 8-bit integer sequences. (Conversion will fail if the text string contains non-ISO-8859-1 characters.) The numbers are then converted to bits. |
required |
is_bitstring
|
bool
|
If true, treat the input as a bitstring. By default, the input is treated as a string of 8-bit integers, from which the individual bits must still be extracted. |
False
|
Raises:
| Type | Description |
|---|---|
ValueError
|
The sequence contains values outside the permissible range. |
Generate a base n non-negative integer.
We attempt to generate a value using rejection sampling. If the generated sample is outside the desired range (i.e., is rejected), then attempt to reuse the sample by seeding a “higher-order” input sequence of uniformly random numbers (for a different base).
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
n
|
int
|
Generate numbers in the range 0, …, |
required |
Returns:
| Type | Description |
|---|---|
int
|
A pseudorandom number in the range 0, …, |
Raises:
| Type | Description |
|---|---|
ValueError
|
The range is empty. |
SequinExhaustedError
|
The sequin is exhausted. |
Examples:
>>> seq = Sequin(
... [1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 1],
... is_bitstring=True,
... )
>>> seq2 = Sequin(
... [1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 1],
... is_bitstring=True,
... )
>>> seq.generate(5)
3
>>> seq.generate(5)
3
>>> seq.generate(5)
1
>>> seq.generate(5)
Traceback (most recent call last):
...
SequinExhaustedError: Sequin is exhausted
Using n = 1 does not actually consume input bits:
>>> seq2.generate(1)
0
But it still won’t work on exhausted sequins:
>>> seq.generate(1)
Traceback (most recent call last):
...
SequinExhaustedError: Sequin is exhausted